Wenn man die ersten k Terme einer Folge gezeigt bekommt, it es unmöglich, mit Gewissheit den Wert des nächsten Terms zu sagen, denn es gibt unendlich viele Polynomfunktionen, die die Folge bilden können.

Als Beispiel betrachten wir die Folge der Kubikzahlen. Diese ist definiert durch die Bildungsfunktion
un = n3: 1, 8, 27, 64, 125, 216, ...

Angenommen, uns werden nur die ersten zwei Terme dieser Folge gegeben. Wenn wir mit dem Prinzip "einfacher ist besser" arbeiten, sollten wir eine lineare Beziehung annehmen und für den nächsten Term 15 vorhersagen (gemeinsame Differenz 7). Selbst wenn uns die ersten drei Terme gezeigt werden, sollte nach dem Prinzip der Einfachheit eine quadratische Beziehung angenommen werden.

Wir definieren OP(k, n) als den nten Term der optimalen Polynomfunktion für die ersten k Terme der Folge. Es sollte ersichtlich sein, dass OP(k, n) die Terme für n ≤ k korrekt generieren wird, und der erste inkorrekte Term (FIT) OP(k, k+1) sein wird; in diesem Fall nennen wir ihn einen schlechten OP (BOP).

Als Basis, wenn uns nur der erste Term gegeben würde, wäre es am sinnvollsten, Konstanz anzunehmen; das bedeutet, für n ≥ 2, OP(1, n) = u1.

Somit erhalten wir die folgenden OPs für die kubische Folge:

OP(1, n) = 1 1, 1, 1, 1, ...
OP(2, n) = 7n−6 1, 8, 15, ...
OP(3, n) = 6n2−11n+6      1, 8, 27, 58, ...
OP(4, n) = n3 1, 8, 27, 64, 125, ...

Offensichtlich existieren keine OPs für k ≥ 4.

Betrachtet man die Summe der FITs, die durch die BOPs gebildet werden (oben in rot gekennzeichnet), erhalten wir 1 + 15 + 58 = 74.

Betrachten Sie die folgende Polynomfunktion zehnten Grades:

un = 1 − n + n2 − n3 + n4 − n5 + n6 − n7 + n8 − n9 + n10

Finden Sie die Summe der FITs für die BOPs.

Diese Aufgabe auf projecteuler.net