The sequence in Problem 101 is generated by
$$u_n = 1 - n + n^2 - n^3 + \cdots + (-n)^{10} = \sum_{r=0}^{10} (-n)^r.$$
For each \(k = 1,2,\dots,10\), we build the unique polynomial \(\operatorname{OP}_k(x)\) of degree at most \(k-1\) that agrees with the first \(k\) sequence values \(u_1,\dots,u_k\). The first value produced outside the fitted data is \(\operatorname{OP}_k(k+1)\); when that prediction is wrong, it is the first incorrect term, or FIT. The problem asks for the sum of all such FITs.
Because the true generator has degree \(10\), an interpolant based on \(11\) points recovers it exactly. So only the ten prefix fits with \(k \lt 11\) can contribute.
This problem is a clean interpolation exercise on the consecutive nodes \(1,2,\dots,11\). The useful viewpoints are the direct Lagrange formula and the Newton forward-difference expansion; they describe the same optimum polynomial from two different angles.
Although the terms are written as an alternating sum, the sequence is still produced by an ordinary degree-\(10\) polynomial:
$$u(n)=\sum_{r=0}^{10}(-n)^r=\frac{1-(-n)^{11}}{1+n}=\frac{n^{11}+1}{n+1}.$$
Since \(11\) is odd, the geometric-series numerator becomes \(n^{11}+1\), and division by \(n+1\) leaves
$$u(n)=n^{10}-n^9+n^8-\cdots-n+1.$$
This immediately explains why \(11\) correct values determine the whole sequence: a degree-\(10\) polynomial is uniquely determined by \(11\) distinct points.
For a fixed prefix length \(k\), interpolation gives a unique polynomial \(\operatorname{OP}_k(x)\) such that
$$\deg \operatorname{OP}_k \le k-1,\qquad \operatorname{OP}_k(m)=u_m \text{ for } m=1,\dots,k.$$
This is the optimum polynomial from the statement: among all formulas that match the first \(k\) terms, it has the smallest possible degree. By construction it matches the data at \(1,2,\dots,k\), so the first place where it can disagree with the true sequence is \(k+1\). For this particular sequence, every \(k=1,\dots,10\) does produce a mismatch there, while the \(11\)-point interpolant matches the generator exactly.
The Lagrange interpolation formula for the first \(k\) points is
$$\operatorname{OP}_k(x)=\sum_{i=1}^{k} u_i \prod_{\substack{j=1 \\ j\ne i}}^{k}\frac{x-j}{i-j}.$$
Evaluating at the next integer \(x=k+1\) produces the extrapolated value. Because the nodes are exactly \(1,2,\dots,k\), the basis factor collapses to a simple alternating binomial coefficient:
$$\prod_{\substack{j=1 \\ j\ne i}}^{k}\frac{(k+1)-j}{i-j}=(-1)^{k-i}\binom{k}{i-1}.$$
Therefore
$$\operatorname{FIT}_k=\operatorname{OP}_k(k+1)=\sum_{i=1}^{k}(-1)^{k-i}\binom{k}{i-1}u_i.$$
This is exactly the quantity computed by the direct interpolation approach: each term is one sequence value multiplied by its Lagrange weight at the next integer.
Define forward differences by \(\Delta a_n = a_{n+1}-a_n\), with \(\Delta^0 a_n = a_n\) and higher differences obtained by repeating the same operation. For equally spaced nodes, a polynomial has a Newton expansion in binomial coefficients:
$$u(n)=\sum_{j=0}^{10}\binom{n-1}{j}\Delta^j u_1.$$
Truncating this expansion after \(j=k-1\) gives the unique degree-\((k-1)\) polynomial matching the first \(k\) terms, so
$$\operatorname{OP}_k(n)=\sum_{j=0}^{k-1}\binom{n-1}{j}\Delta^j u_1.$$
At the first extrapolation point \(n=k+1\), this becomes
$$\operatorname{FIT}_k=\sum_{j=0}^{k-1}\binom{k}{j}\Delta^j u_1.$$
For this sequence, the first column of the difference table begins \(1, 682, 42922, 708048, \dots\) and ends with \(\Delta^{10}u_1 = 3628800 = 10!\). The next difference vanishes, which is the finite-difference signature of a degree-\(10\) polynomial. This is the exact arithmetic viewpoint used by the C++ implementation.
The first few true values are
$$u_1=1,\qquad u_2=683,\qquad u_3=44287,\qquad u_4=838861.$$
Using only the first two points, the optimum polynomial is the line
$$\operatorname{OP}_2(n)=1+682(n-1)=682n-681.$$
Its next prediction is \(\operatorname{OP}_2(3)=1365\), while the true value is \(u_3=44287\). So the FIT for \(k=2\) is \(1365\).
Using the first three points, Newton's form adds the second difference \(42922\):
$$\operatorname{OP}_3(n)=1+682(n-1)+42922\binom{n-1}{2}.$$
Evaluating at \(n=4\) gives \(\operatorname{OP}_3(4)=130813\), whereas \(u_4=838861\). Repeating the same procedure for every \(k=1,\dots,10\) and summing the ten extrapolated values gives the required total.
The implementations first generate \(u_1,u_2,\dots,u_{11}\). That is exactly the amount of data needed for a degree-\(10\) problem: the first \(k\) values define \(\operatorname{OP}_k\), and the \((k+1)\)-st value tells us whether the extrapolation is a FIT.
The Python and Java implementations evaluate the Lagrange interpolant directly at \(x=k+1\) for each prefix length \(k\). The C++ implementation instead builds the forward-difference column once and then evaluates the equivalent Newton formula with binomial coefficients. Both strategies compute the same \(\operatorname{OP}_k(k+1)\); one emphasizes the interpolation basis, the other emphasizes the finite-difference structure.
Because the instance is tiny, the direct Lagrange versions use floating-point arithmetic and round the result back to the nearest integer. That is safe here because the values are far below the precision limit of a double, while the exact-difference version avoids rounding altogether.
For each \(k\), the predicted value is compared with the actual next sequence value \(u_{k+1}\). If they differ, the prediction is added to the running sum. In this degree-\(10\) instance every \(k=1,\dots,10\) contributes, and the \(11\)-point interpolant would contribute nothing because it reproduces the generating polynomial exactly.
Let \(d\) be the degree of the generating polynomial. Producing the first \(d+1\) sequence values with the straightforward power-sum evaluation used here costs \(O(d^2)\) arithmetic operations. After that, the forward-difference method needs \(O(d^2)\) time in total to build the difference column and compute all FITs, with \(O(d)\) storage for the working arrays.
The direct Lagrange evaluation used in the Python and Java versions computes one extrapolation for prefix length \(k\) in \(O(k^2)\) time, so the full sweep over \(k=1,\dots,d\) costs \(\sum_{k=1}^{d} O(k^2)=O(d^3)\), again with \(O(d)\) memory. For the Project Euler instance \(d=10\), both approaches are effectively instantaneous.
Die Folge aus Problem 101 wird erzeugt durch
$$u_n = 1 - n + n^2 - n^3 + \cdots + (-n)^{10} = \sum_{r=0}^{10} (-n)^r.$$
Für jedes \(k = 1,2,\dots,10\) bilden wir das eindeutige Polynom \(\operatorname{OP}_k(x)\) vom Grad höchstens \(k-1\), das mit den ersten \(k\) Folgengliedern \(u_1,\dots,u_k\) übereinstimmt. Der erste Wert außerhalb der angepassten Daten ist \(\operatorname{OP}_k(k+1)\); falls diese Vorhersage falsch ist, nennt die Aufgabe sie den first incorrect term, kurz FIT. Gesucht ist die Summe aller FITs.
Da das wahre erzeugende Polynom Grad \(10\) hat, rekonstruiert eine Interpolation mit \(11\) Punkten die Folge exakt. Also können nur die zehn Präfix-Interpolationen mit \(k \lt 11\) beitragen.
Die Aufgabe ist ein sauberes Interpolationsproblem auf den aufeinanderfolgenden Stutzstellen \(1,2,\dots,11\). Besonders nützlich sind zwei äquivalente Darstellungen: die direkte Lagrange-Formel und die Newton-Entwicklung über Vorwärtsdifferenzen.
Obwohl die Werte als alternierende Summe notiert sind, stammt die Folge von einem gewöhnlichen Polynom zehnten Grades:
$$u(n)=\sum_{r=0}^{10}(-n)^r=\frac{1-(-n)^{11}}{1+n}=\frac{n^{11}+1}{n+1}.$$
Weil \(11\) ungerade ist, wird der Zähler der geometrischen Reihe zu \(n^{11}+1\), und nach Division durch \(n+1\) bleibt
$$u(n)=n^{10}-n^9+n^8-\cdots-n+1.$$
Damit ist sofort klar, warum \(11\) korrekte Werte die gesamte Folge festlegen: Ein Polynom vom Grad \(10\) ist durch \(11\) verschiedene Punkte eindeutig bestimmt.
Fur eine feste Präfixlänge \(k\) liefert die Interpolation genau ein Polynom \(\operatorname{OP}_k(x)\) mit
$$\deg \operatorname{OP}_k \le k-1,\qquad \operatorname{OP}_k(m)=u_m \text{ fur } m=1,\dots,k.$$
Genau das ist das optimale Polynom aus der Aufgabenstellung: Unter allen Formeln, die die ersten \(k\) Werte treffen, hat es den kleinstmöglichen Grad. Per Konstruktion stimmt es an den Stellen \(1,2,\dots,k\) mit der Folge überein, also ist \(k+1\) die erste Stelle, an der es abweichen kann. In dieser konkreten Aufgabe weicht es dort für jedes \(k=1,\dots,10\) ab, während der \(11\)-Punkte-Interpolant das erzeugende Polynom exakt reproduziert.
Die Lagrange-Formel für die ersten \(k\) Punkte lautet
$$\operatorname{OP}_k(x)=\sum_{i=1}^{k} u_i \prod_{\substack{j=1 \\ j\ne i}}^{k}\frac{x-j}{i-j}.$$
Setzt man die nächste ganze Zahl \(x=k+1\) ein, erhält man den extrapolierten Wert. Weil die Stutzstellen genau \(1,2,\dots,k\) sind, vereinfacht sich der Basisfaktor zu einem alternierenden Binomialkoeffizienten:
$$\prod_{\substack{j=1 \\ j\ne i}}^{k}\frac{(k+1)-j}{i-j}=(-1)^{k-i}\binom{k}{i-1}.$$
Damit gilt
$$\operatorname{FIT}_k=\operatorname{OP}_k(k+1)=\sum_{i=1}^{k}(-1)^{k-i}\binom{k}{i-1}u_i.$$
Genau diese Größe wird im direkten Interpolationsansatz berechnet: Jeder Summand ist ein Folgewert multipliziert mit seinem Lagrange-Gewicht an der Stelle \(k+1\).
Definiere Vorwärtsdifferenzen durch \(\Delta a_n = a_{n+1}-a_n\), mit \(\Delta^0 a_n = a_n\), und erhalte höhere Differenzen durch wiederholte Anwendung derselben Operation. Für äquidistante Stutzstellen besitzt jedes Polynom eine Newton-Entwicklung in Binomialkoeffizienten:
$$u(n)=\sum_{j=0}^{10}\binom{n-1}{j}\Delta^j u_1.$$
Schneidet man diese Entwicklung nach \(j=k-1\) ab, erhält man genau das eindeutige Polynom vom Grad \(k-1\), das zu den ersten \(k\) Werten passt, also
$$\operatorname{OP}_k(n)=\sum_{j=0}^{k-1}\binom{n-1}{j}\Delta^j u_1.$$
Am ersten Extrapolationspunkt \(n=k+1\) wird daraus
$$\operatorname{FIT}_k=\sum_{j=0}^{k-1}\binom{k}{j}\Delta^j u_1.$$
Bei dieser Folge beginnt die erste Spalte der Differenztabelle mit \(1, 682, 42922, 708048, \dots\) und endet mit \(\Delta^{10}u_1 = 3628800 = 10!\). Die nächste Differenz verschwindet; genau das ist die Differenzen-Invariante eines Polynoms zehnten Grades. Diese Sichtweise mit exakter Ganzzahlarithmetik nutzt die C++-Implementierung.
Die ersten echten Folgenglieder sind
$$u_1=1,\qquad u_2=683,\qquad u_3=44287,\qquad u_4=838861.$$
Verwendet man nur die ersten beiden Punkte, so ist das optimale Polynom die Gerade
$$\operatorname{OP}_2(n)=1+682(n-1)=682n-681.$$
Die nächste Vorhersage lautet \(\operatorname{OP}_2(3)=1365\), der wahre Wert ist aber \(u_3=44287\). Also ist der FIT für \(k=2\) gleich \(1365\).
Mit den ersten drei Punkten kommt in Newton-Form die zweite Differenz \(42922\) hinzu:
$$\operatorname{OP}_3(n)=1+682(n-1)+42922\binom{n-1}{2}.$$
Für \(n=4\) ergibt das \(\operatorname{OP}_3(4)=130813\), während \(u_4=838861\) gilt. Dieselbe Rechnung wird für alle \(k=1,\dots,10\) wiederholt; die Summe dieser zehn Extrapolationen ist die gesuchte Antwort.
Die Implementierungen erzeugen zunächst \(u_1,u_2,\dots,u_{11}\). Genau diese Datenmenge wird für ein Problem mit Grad \(10\) benötigt: Die ersten \(k\) Werte definieren \(\operatorname{OP}_k\), und der \((k+1)\)-te Wert sagt, ob die Extrapolation ein FIT ist.
Die Python- und Java-Implementierungen werten für jede Präfixlänge \(k\) den Lagrange-Interpolanten direkt bei \(x=k+1\) aus. Die C++-Implementierung baut stattdessen einmal die Vorwärtsdifferenzspalte auf und verwendet dann die äquivalente Newton-Formel mit Binomialkoeffizienten. Beide Strategien berechnen dasselbe \(\operatorname{OP}_k(k+1)\); die eine betont die Interpolationsbasis, die andere die Differenzenstruktur.
Weil die Instanz sehr klein ist, benutzen die direkten Lagrange-Versionen Gleitkommazahlen und runden anschließend auf die nächste ganze Zahl. Das ist hier unkritisch, weil alle Werte weit innerhalb der exakten Double-Präzision liegen; die Differenzenversion vermeidet Rundung vollständig.
Für jedes \(k\) wird der vorhergesagte Wert mit dem tatsächlichen nächsten Folgenglied \(u_{k+1}\) verglichen. Nur wenn beide verschieden sind, geht die Vorhersage in die Summe ein. In diesem Problem trägt jedes \(k=1,\dots,10\) bei, und der \(11\)-Punkte-Interpolant würde nichts beitragen, weil er das erzeugende Polynom exakt trifft.
Sei \(d\) der Grad des erzeugenden Polynoms. Das Erzeugen der ersten \(d+1\) Folgenglieder mit der hier verwendeten direkten Auswertung der Potenzsumme kostet \(O(d^2)\) arithmetische Operationen. Danach benötigt die Vorwärtsdifferenzen-Methode insgesamt \(O(d^2)\) Zeit, um die Differenzspalte aufzubauen und alle FITs zu berechnen, bei \(O(d)\) Speicher für die Arbeitsfelder.
Die direkte Lagrange-Auswertung in den Python- und Java-Versionen berechnet eine Extrapolation für Präfixlänge \(k\) in \(O(k^2)\) Zeit. Der gesamte Durchlauf über \(k=1,\dots,d\) kostet also \(\sum_{k=1}^{d} O(k^2)=O(d^3)\), ebenfalls bei \(O(d)\) Speicher. Für den Project-Euler-Fall \(d=10\) sind beide Varianten praktisch sofort fertig.
Problem 101'deki dizi su sekilde uretilir:
$$u_n = 1 - n + n^2 - n^3 + \cdots + (-n)^{10} = \sum_{r=0}^{10} (-n)^r.$$
Her \(k = 1,2,\dots,10\) icin, ilk \(k\) terim olan \(u_1,\dots,u_k\) ile ayni degerleri veren ve derecesi en fazla \(k-1\) olan tek polinomu \(\operatorname{OP}_k(x)\) olarak kuruyoruz. Uydurulan verinin disindaki ilk deger \(\operatorname{OP}_k(k+1)\) olur; bu tahmin yanlissa buna first incorrect term, yani FIT denir. Sorulan sey tum FIT degerlerinin toplami.
Gercek uretecin derecesi \(10\) oldugu icin, \(11\) noktali interpolasyon onu tam olarak geri verir. Bu nedenle yalnizca \(k \lt 11\) icin olusan on prefix interpolasyonu toplama katkida bulunur.
Bu soru, \(1,2,\dots,11\) gibi ardısik dugumler uzerinde kurulan temiz bir polinom interpolasyonu problemidir. En yararli iki bakis acisi, dogrudan Lagrange formulu ile Newton ileri fark acilimidir; ikisi de ayni optimum polinomu farkli bicimlerde yazar.
Terimler alternatif toplam olarak yazilsa da dizi siradan bir onuncu derece polinomdan gelir:
$$u(n)=\sum_{r=0}^{10}(-n)^r=\frac{1-(-n)^{11}}{1+n}=\frac{n^{11}+1}{n+1}.$$
\(11\) tek oldugu icin geometrik seri payi \(n^{11}+1\) olur ve \(n+1\) ile bolununce
$$u(n)=n^{10}-n^9+n^8-\cdots-n+1$$
elde edilir. Dolayisiyla \(11\) dogru nokta tum diziyi belirler; cunku onuncu derece bir polinom \(11\) farkli noktada tekil olarak belirlenir.
Sabit bir \(k\) icin interpolasyon, su kosullari saglayan tek bir \(\operatorname{OP}_k(x)\) polinomu verir:
$$\deg \operatorname{OP}_k \le k-1,\qquad \operatorname{OP}_k(m)=u_m \text{ for } m=1,\dots,k.$$
Sorudaki optimum polinom budur: ilk \(k\) terimi tutturan tum ifadeler arasinda derece olarak en kucuk olan form. Tanimi geregi \(1,2,\dots,k\) noktalarinda diziyle aynidir; dolayisiyla ilk kez ayrisabilecegi yer \(k+1\)'dir. Bu ozel dizide \(k=1,\dots,10\) icin her seferinde orada yanlis tahmin uretilir; \(11\) noktayla kurulan interpolant ise gercek ureteci aynen yakalar.
Ilk \(k\) nokta icin Lagrange interpolasyon formulu
$$\operatorname{OP}_k(x)=\sum_{i=1}^{k} u_i \prod_{\substack{j=1 \\ j\ne i}}^{k}\frac{x-j}{i-j}$$
seklindedir. Bir sonraki tam sayi olan \(x=k+1\) noktasinda degerlendirdigimizde ekstrapolasyon elde edilir. Dugumler tam olarak \(1,2,\dots,k\) oldugu icin temel carpim sade bir alternatif binom katsayisina indirgenir:
$$\prod_{\substack{j=1 \\ j\ne i}}^{k}\frac{(k+1)-j}{i-j}=(-1)^{k-i}\binom{k}{i-1}.$$
Buna gore
$$\operatorname{FIT}_k=\operatorname{OP}_k(k+1)=\sum_{i=1}^{k}(-1)^{k-i}\binom{k}{i-1}u_i.$$
Dogrudan interpolasyon yaklasimi aslinda tam olarak bu miktari hesaplar: her terim, bir dizi degerinin \(k+1\) noktasindaki Lagrange agirligiyla carpimidir.
Ileri fark operatorunu \(\Delta a_n = a_{n+1}-a_n\) seklinde tanimlayalim. \(\Delta^0 a_n = a_n\) olsun; daha yuksek farklar ayni islemin tekrarindan elde edilir. Esit aralikli dugumlerde her polinom, binom katsayili Newton acilimina sahiptir:
$$u(n)=\sum_{j=0}^{10}\binom{n-1}{j}\Delta^j u_1.$$
Bu acilimi \(j=k-1\) sonrasinda kesmek, ilk \(k\) terimi tutturan derece-\((k-1)\) polinomu verir:
$$\operatorname{OP}_k(n)=\sum_{j=0}^{k-1}\binom{n-1}{j}\Delta^j u_1.$$
Ilk ekstrapolasyon noktasi \(n=k+1\) icin de
$$\operatorname{FIT}_k=\sum_{j=0}^{k-1}\binom{k}{j}\Delta^j u_1$$
olur. Bu dizi icin fark tablosunun ilk sutunu \(1, 682, 42922, 708048, \dots\) diye baslar ve \(\Delta^{10}u_1 = 3628800 = 10!\) ile biter. Bir sonraki farkin sifir olmasi, bunun onuncu derece polinom oldugunu gosteren sonlu fark imzasidir. C++ uygulamasi tam sayi aritmetiginde bu bakis acisini kullanir.
Ilk gercek terimler sunlardir:
$$u_1=1,\qquad u_2=683,\qquad u_3=44287,\qquad u_4=838861.$$
Yalnizca ilk iki nokta kullanilirsa optimum polinom su dogrudur:
$$\operatorname{OP}_2(n)=1+682(n-1)=682n-681.$$
Bir sonraki tahmin \(\operatorname{OP}_2(3)=1365\) olur; gercek deger ise \(u_3=44287\)'dir. Dolayisiyla \(k=2\) icin FIT degeri \(1365\) olur.
Ilk uc nokta kullanildiginda Newton bicimine ikinci fark olan \(42922\) eklenir:
$$\operatorname{OP}_3(n)=1+682(n-1)+42922\binom{n-1}{2}.$$
\(n=4\) icin bu \(\operatorname{OP}_3(4)=130813\) verir; oysa \(u_4=838861\)'dir. Ayni islem \(k=1,\dots,10\) icin tekrarlanir ve on ekstrapolasyonun toplami istenen sonucu verir.
Uygulamalar once \(u_1,u_2,\dots,u_{11}\) degerlerini hesaplar. Onuncu derece bir problem icin gereken veri miktari tam olarak budur: ilk \(k\) deger \(\operatorname{OP}_k\)'yi belirler, \((k+1)\). deger ise ekstrapolasyonun FIT olup olmadigini soyler.
Python ve Java uygulamalari her \(k\) icin Lagrange interpolantini dogrudan \(x=k+1\) noktasinda degerlendirir. C++ uygulamasi ise once ileri fark sutununu kurar, sonra esit matematigi Newton formulu ve binom katsayilariyla tam olarak hesaplar. Her iki yol da ayni \(\operatorname{OP}_k(k+1)\) degerine ulasir; biri interpolasyon bazini, digeri sonlu fark yapisini one cikarir.
Ornek cok kucuk oldugu icin dogrudan Lagrange surumleri kayan nokta aritmetigi kullanir ve sonucu en yakin tam sayiya yuvarlar. Burada bu guvenlidir; cunku tum degerler double hassasiyetinin rahat icindedir. Ileri fark surumu ise yuvarlamayi tamamen ortadan kaldirir.
Her \(k\) icin tahmin edilen deger, gercek sonraki terim \(u_{k+1}\) ile karsilastirilir. Eger farklilarsa tahmin toplama eklenir. Bu soruda \(k=1,\dots,10\) icin hepsi katkida bulunur; \(11\) noktalik interpolant ise ureteci tam tuttugu icin ek bir FIT vermez.
Ureten polinomun derecesi \(d\) olsun. Buradaki dogrudan kuvvet-toplami degerlendirmesiyle ilk \(d+1\) dizi terimini uretmek \(O(d^2)\) aritmetik islem gerektirir. Bundan sonra ileri fark yontemi, fark sutununu kurmak ve tum FIT'leri cikarmak icin toplam \(O(d^2)\) zaman ve calisma dizileri icin \(O(d)\) bellek kullanir.
Python ve Java surumlerindeki dogrudan Lagrange yaklasimi, prefix uzunlugu \(k\) icin tek bir ekstrapolasyonu \(O(k^2)\) zamanda hesaplar. Dolayisiyla \(k=1,\dots,d\) uzerindeki tam tarama \(\sum_{k=1}^{d} O(k^2)=O(d^3)\) zaman ve yine \(O(d)\) bellek gerektirir. Project Euler orneginde \(d=10\) oldugu icin iki yaklasim da anliktir.
La sucesion del Problema 101 se genera mediante
$$u_n = 1 - n + n^2 - n^3 + \cdots + (-n)^{10} = \sum_{r=0}^{10} (-n)^r.$$
Para cada \(k = 1,2,\dots,10\), construimos el unico polinomio \(\operatorname{OP}_k(x)\) de grado a lo sumo \(k-1\) que coincide con los primeros \(k\) valores \(u_1,\dots,u_k\). El primer valor producido fuera de los datos ajustados es \(\operatorname{OP}_k(k+1)\); cuando esa prediccion es incorrecta, el problema la llama first incorrect term, o FIT. La tarea consiste en sumar todos esos FIT.
Como el generador real tiene grado \(10\), la interpolacion con \(11\) puntos lo recupera exactamente. Por eso solo pueden contribuir los diez ajustes de prefijo con \(k \lt 11\).
Todo el problema es una interpolacion polinomica sobre los nodos consecutivos \(1,2,\dots,11\). Las dos perspectivas utiles son la formula directa de Lagrange y la expansion de Newton basada en diferencias progresivas; ambas describen el mismo polinomio optimo.
Aunque la sucesion aparece escrita como suma alternante, sigue estando generada por un polinomio ordinario de grado \(10\):
$$u(n)=\sum_{r=0}^{10}(-n)^r=\frac{1-(-n)^{11}}{1+n}=\frac{n^{11}+1}{n+1}.$$
Como \(11\) es impar, el numerador de la serie geometrica se convierte en \(n^{11}+1\), y al dividir por \(n+1\) queda
$$u(n)=n^{10}-n^9+n^8-\cdots-n+1.$$
Esto explica de inmediato por que \(11\) valores correctos determinan toda la sucesion: un polinomio de grado \(10\) queda fijado por \(11\) puntos distintos.
Para una longitud de prefijo fija \(k\), la interpolacion produce un unico polinomio \(\operatorname{OP}_k(x)\) tal que
$$\deg \operatorname{OP}_k \le k-1,\qquad \operatorname{OP}_k(m)=u_m \text{ para } m=1,\dots,k.$$
Ese es el polinomio optimo del enunciado: entre todas las expresiones que reproducen los primeros \(k\) terminos, tiene el menor grado posible. Por construccion coincide con la sucesion en \(1,2,\dots,k\), de modo que el primer lugar donde puede fallar es \(k+1\). En esta instancia concreta, falla alli para todo \(k=1,\dots,10\), mientras que el interpolante de \(11\) puntos reproduce exactamente el generador verdadero.
La formula de Lagrange para los primeros \(k\) puntos es
$$\operatorname{OP}_k(x)=\sum_{i=1}^{k} u_i \prod_{\substack{j=1 \\ j\ne i}}^{k}\frac{x-j}{i-j}.$$
Al evaluarla en el siguiente entero \(x=k+1\) obtenemos la extrapolacion. Como los nodos son exactamente \(1,2,\dots,k\), el factor basico se reduce a un coeficiente binomial alternante:
$$\prod_{\substack{j=1 \\ j\ne i}}^{k}\frac{(k+1)-j}{i-j}=(-1)^{k-i}\binom{k}{i-1}.$$
Por tanto,
$$\operatorname{FIT}_k=\operatorname{OP}_k(k+1)=\sum_{i=1}^{k}(-1)^{k-i}\binom{k}{i-1}u_i.$$
Eso es exactamente lo que calcula el enfoque de interpolacion directa: cada termino es un valor de la sucesion multiplicado por su peso de Lagrange en el siguiente entero.
Definimos la diferencia progresiva por \(\Delta a_n = a_{n+1}-a_n\), con \(\Delta^0 a_n = a_n\), y obtenemos las diferencias superiores repitiendo la misma operacion. Para nodos igualmente espaciados, un polinomio posee una expansion de Newton en coeficientes binomiales:
$$u(n)=\sum_{j=0}^{10}\binom{n-1}{j}\Delta^j u_1.$$
Si truncamos esta expansion despues de \(j=k-1\), obtenemos el unico polinomio de grado \(k-1\) que coincide con los primeros \(k\) terminos, es decir,
$$\operatorname{OP}_k(n)=\sum_{j=0}^{k-1}\binom{n-1}{j}\Delta^j u_1.$$
En el primer punto de extrapolacion \(n=k+1\) esto se convierte en
$$\operatorname{FIT}_k=\sum_{j=0}^{k-1}\binom{k}{j}\Delta^j u_1.$$
Para esta sucesion, la primera columna de la tabla de diferencias empieza como \(1, 682, 42922, 708048, \dots\) y termina en \(\Delta^{10}u_1 = 3628800 = 10!\). La diferencia siguiente se anula; esa es justamente la firma en diferencias finitas de un polinomio de grado \(10\). Esta es la perspectiva exacta que usa la implementacion en C++.
Los primeros valores verdaderos son
$$u_1=1,\qquad u_2=683,\qquad u_3=44287,\qquad u_4=838861.$$
Si usamos solo los dos primeros puntos, el polinomio optimo es la recta
$$\operatorname{OP}_2(n)=1+682(n-1)=682n-681.$$
Su siguiente prediccion es \(\operatorname{OP}_2(3)=1365\), mientras que el valor real es \(u_3=44287\). Por tanto, el FIT para \(k=2\) es \(1365\).
Si usamos los tres primeros puntos, la forma de Newton anade la segunda diferencia \(42922\):
$$\operatorname{OP}_3(n)=1+682(n-1)+42922\binom{n-1}{2}.$$
Al evaluar en \(n=4\) se obtiene \(\operatorname{OP}_3(4)=130813\), mientras que \(u_4=838861\). El resultado final se obtiene repitiendo este procedimiento para todos los \(k=1,\dots,10\) y sumando las diez extrapolaciones.
Las implementaciones generan primero \(u_1,u_2,\dots,u_{11}\). Esa es exactamente la cantidad de datos necesaria para un generador de grado \(10\): los primeros \(k\) valores determinan \(\operatorname{OP}_k\), y el valor \((k+1)\)-esimo indica si la extrapolacion es realmente un FIT.
Las implementaciones en Python y Java evalúan directamente el interpolante de Lagrange en \(x=k+1\) para cada longitud de prefijo \(k\). La implementacion en C++ construye una sola vez la columna de diferencias progresivas y luego evalua la formula equivalente de Newton con coeficientes binomiales. Ambos caminos calculan el mismo \(\operatorname{OP}_k(k+1)\); uno enfatiza la base de interpolacion y el otro la estructura de diferencias finitas.
Como la instancia es pequena, las versiones directas de Lagrange usan aritmetica de punto flotante y luego redondean al entero mas cercano. Aqui eso es seguro porque todos los valores quedan muy por debajo del limite de precision exacta de un double, mientras que la version basada en diferencias evita por completo cualquier redondeo.
Para cada \(k\), el valor predicho se compara con el siguiente termino real \(u_{k+1}\). Si son distintos, la prediccion se agrega al acumulado. En este problema concreto todos los \(k=1,\dots,10\) aportan, y el interpolante de \(11\) puntos no aportaria nada porque ya reproduce exactamente el polinomio generador.
Sea \(d\) el grado del polinomio generador. Producir los primeros \(d+1\) valores de la sucesion con la evaluacion directa de la suma de potencias utilizada aqui cuesta \(O(d^2)\) operaciones aritmeticas. A partir de ahi, el metodo de diferencias progresivas necesita \(O(d^2)\) tiempo total para construir la columna de diferencias y calcular todos los FIT, con \(O(d)\) memoria para los arreglos de trabajo.
La evaluacion directa de Lagrange usada en las versiones de Python y Java calcula una extrapolacion de prefijo \(k\) en \(O(k^2)\) tiempo. Por lo tanto, el barrido completo sobre \(k=1,\dots,d\) cuesta \(\sum_{k=1}^{d} O(k^2)=O(d^3)\), otra vez con \(O(d)\) memoria. En la instancia de Project Euler con \(d=10\), ambos enfoques son esencialmente instantaneos.
Problem 101 中的数列由下式生成：
$$u_n = 1 - n + n^2 - n^3 + \cdots + (-n)^{10} = \sum_{r=0}^{10} (-n)^r.$$
对每个 \(k = 1,2,\dots,10\)，都定义一个唯一的多项式 \(\operatorname{OP}_k(x)\)，它的次数不超过 \(k-1\)，并且满足前 \(k\) 项插值条件 \(u_1,\dots,u_k\)。超出已拟合数据后的第一个值是 \(\operatorname{OP}_k(k+1)\)；如果这个预测值不等于真正的下一项，它就是题目所说的 first incorrect term，也就是 FIT。题目要求把所有 FIT 相加。
因为真正的生成函数本身就是一个 \(10\) 次多项式，所以一旦使用 \(11\) 个点做插值，就会把原多项式完全恢复出来。因此真正可能产生 FIT 的，只是 \(k \lt 11\) 的这十个前缀插值。
这道题本质上是建立在连续节点 \(1,2,\dots,11\) 上的多项式插值。最有用的两种写法分别是直接的 Lagrange 插值公式，以及基于前向差分的 Newton 展开；它们描述的是同一个最优多项式，只是观察角度不同。
虽然题目把 \(u_n\) 写成了交替求和，但它仍然是一个普通的 \(10\) 次多项式：
$$u(n)=\sum_{r=0}^{10}(-n)^r=\frac{1-(-n)^{11}}{1+n}=\frac{n^{11}+1}{n+1}.$$
由于 \(11\) 是奇数，有限等比级数的分子会化成 \(n^{11}+1\)，再除以 \(n+1\) 就得到
$$u(n)=n^{10}-n^9+n^8-\cdots-n+1.$$
这立刻说明了为什么 \(11\) 个正确的取值就能唯一确定整条数列：一个 \(10\) 次多项式由 \(11\) 个互异点唯一决定。
固定一个前缀长度 \(k\) 之后，插值定理保证存在唯一的多项式 \(\operatorname{OP}_k(x)\)，满足
$$\deg \operatorname{OP}_k \le k-1,\qquad \operatorname{OP}_k(m)=u_m \text{ for } m=1,\dots,k.$$
这就是题目中的 optimum polynomial：在所有能够复现前 \(k\) 项的表达式里，它的次数最小。按照定义，它在 \(1,2,\dots,k\) 这些点上与原数列完全一致，所以最早可能出错的位置就是 \(k+1\)。在本题的这条具体数列中，\(k=1,\dots,10\) 时这里都会出错；而用 \(11\) 个点构造出来的插值多项式会与真正的生成多项式完全重合。
前 \(k\) 个点的 Lagrange 插值公式是
$$\operatorname{OP}_k(x)=\sum_{i=1}^{k} u_i \prod_{\substack{j=1 \\ j\ne i}}^{k}\frac{x-j}{i-j}.$$
把 \(x=k+1\) 代入，就得到向前外推一步的值。由于节点恰好是连续整数 \(1,2,\dots,k\)，这个基函数的乘积可以化成一个非常简单的交替二项式系数：
$$\prod_{\substack{j=1 \\ j\ne i}}^{k}\frac{(k+1)-j}{i-j}=(-1)^{k-i}\binom{k}{i-1}.$$
因此
$$\operatorname{FIT}_k=\operatorname{OP}_k(k+1)=\sum_{i=1}^{k}(-1)^{k-i}\binom{k}{i-1}u_i.$$
这正是直接插值实现所计算的量：每一项都是某个序列值乘以它在下一整数点上的 Lagrange 权重。
定义前向差分算子 \(\Delta a_n = a_{n+1}-a_n\)，并令 \(\Delta^0 a_n = a_n\)。更高阶差分通过重复同样的操作得到。对等间距节点，多项式可以写成 Newton 的二项式展开：
$$u(n)=\sum_{j=0}^{10}\binom{n-1}{j}\Delta^j u_1.$$
如果把这个展开在 \(j=k-1\) 之后截断，就得到恰好通过前 \(k\) 项的次数不超过 \(k-1\) 的多项式，也就是
$$\operatorname{OP}_k(n)=\sum_{j=0}^{k-1}\binom{n-1}{j}\Delta^j u_1.$$
在第一个外推点 \(n=k+1\) 处，公式变为
$$\operatorname{FIT}_k=\sum_{j=0}^{k-1}\binom{k}{j}\Delta^j u_1.$$
对本题这条数列而言，差分表第一列从 \(1, 682, 42922, 708048, \dots\) 开始，并以 \(\Delta^{10}u_1 = 3628800 = 10!\) 结束。再往下一阶差分就变成零，这正是“原函数是 \(10\) 次多项式”的有限差分特征。C++ 实现采用的就是这种完全精确的整数差分视角。
前几个真实的函数值是
$$u_1=1,\qquad u_2=683,\qquad u_3=44287,\qquad u_4=838861.$$
如果只使用前两个点，那么最优多项式就是直线
$$\operatorname{OP}_2(n)=1+682(n-1)=682n-681.$$
它在下一点给出的预测是 \(\operatorname{OP}_2(3)=1365\)，而真实值是 \(u_3=44287\)。所以 \(k=2\) 时的 FIT 就是 \(1365\)。
如果使用前三个点，Newton 形式中会额外加入二阶差分 \(42922\)：
$$\operatorname{OP}_3(n)=1+682(n-1)+42922\binom{n-1}{2}.$$
代入 \(n=4\) 得到 \(\operatorname{OP}_3(4)=130813\)，但真实值 \(u_4=838861\)。对所有 \(k=1,\dots,10\) 重复同样的计算，再把这十个外推值求和，就得到题目的最终结果。
实现首先计算 \(u_1,u_2,\dots,u_{11}\)。对于一个 \(10\) 次多项式问题，这正好是足够的数据量：前 \(k\) 项决定 \(\operatorname{OP}_k\)，第 \(k+1\) 项则用来判断外推值是不是 FIT。
Python 和 Java 实现对每个前缀长度 \(k\) 都直接在 \(x=k+1\) 处计算 Lagrange 插值。C++ 实现则先一次性构造前向差分表的第一列，再用等价的 Newton 二项式公式计算同样的值。两种方法得到的都是同一个 \(\operatorname{OP}_k(k+1)\)：前者更直接体现插值基函数，后者更直接体现有限差分结构。
由于本题规模极小，直接 Lagrange 版本使用浮点数运算，然后再四舍五入回整数。这里这样做是安全的，因为所有数值都远低于 double 的精确整数范围；而基于差分的版本则完全避免了舍入误差。
对每个 \(k\)，程序都会把预测值和真实的下一项 \(u_{k+1}\) 进行比较。如果两者不同，就把这个预测值加入答案。在当前这道 \(10\) 次多项式题里，\(k=1,\dots,10\) 都会贡献一个 FIT，而 \(11\) 点插值不会再贡献任何值，因为它已经完全恢复了生成多项式。
设生成多项式的次数为 \(d\)。按照这里使用的直接幂和求值方式，先生成前 \(d+1\) 项需要 \(O(d^2)\) 次算术运算。之后，前向差分方法总共只需要 \(O(d^2)\) 时间来构造差分列并计算所有 FIT，额外工作空间为 \(O(d)\)。
Python 和 Java 所采用的直接 Lagrange 计算，在前缀长度为 \(k\) 时需要 \(O(k^2)\) 时间，因此遍历全部 \(k=1,\dots,d\) 的总代价是 \(\sum_{k=1}^{d} O(k^2)=O(d^3)\)，空间仍为 \(O(d)\)。在 Project Euler 的实际参数 \(d=10\) 下，这两种方法都几乎是瞬间完成。
Последовательность в Problem 101 задается формулой
$$u_n = 1 - n + n^2 - n^3 + \cdots + (-n)^{10} = \sum_{r=0}^{10} (-n)^r.$$
Для каждого \(k = 1,2,\dots,10\) строится единственный полином \(\operatorname{OP}_k(x)\) степени не выше \(k-1\), совпадающий с первыми \(k\) значениями \(u_1,\dots,u_k\). Первый член, вычисленный уже за пределами подогнанных данных, равен \(\operatorname{OP}_k(k+1)\); если этот прогноз неверен, он называется first incorrect term, то есть FIT. Требуется просуммировать все такие FIT.
Поскольку настоящий порождающий закон имеет степень \(10\), интерполяция по \(11\) точкам восстанавливает его точно. Значит, вклад могут давать только десять префиксных интерполянтов с \(k \lt 11\).
Вся задача сводится к полиномиальной интерполяции на последовательных узлах \(1,2,\dots,11\). Удобно смотреть на один и тот же объект с двух сторон: через прямую формулу Лагранжа и через разложение Ньютона по прямым разностям.
Хотя последовательность записана как чередующаяся сумма, она все равно задается обычным полиномом степени \(10\):
$$u(n)=\sum_{r=0}^{10}(-n)^r=\frac{1-(-n)^{11}}{1+n}=\frac{n^{11}+1}{n+1}.$$
Так как \(11\) нечетно, числитель конечной геометрической прогрессии превращается в \(n^{11}+1\), а после деления на \(n+1\) остается
$$u(n)=n^{10}-n^9+n^8-\cdots-n+1.$$
Отсюда сразу видно, почему \(11\) правильных значений полностью определяют последовательность: полином степени \(10\) единственным образом задается \(11\) различными точками.
Для фиксированной длины префикса \(k\) интерполяция дает единственный полином \(\operatorname{OP}_k(x)\), удовлетворяющий условиям
$$\deg \operatorname{OP}_k \le k-1,\qquad \operatorname{OP}_k(m)=u_m \text{ for } m=1,\dots,k.$$
Это и есть optimum polynomial из условия: среди всех формул, совпадающих с первыми \(k\) членами, он имеет наименьшую возможную степень. По построению он верен в точках \(1,2,\dots,k\), поэтому первое место, где он может ошибиться, это \(k+1\). В данной задаче ошибка действительно возникает для каждого \(k=1,\dots,10\), а интерполянт по \(11\) точкам уже в точности совпадает с истинным порождающим полиномом.
Формула Лагранжа для первых \(k\) точек имеет вид
$$\operatorname{OP}_k(x)=\sum_{i=1}^{k} u_i \prod_{\substack{j=1 \\ j\ne i}}^{k}\frac{x-j}{i-j}.$$
Если подставить следующий целый аргумент \(x=k+1\), получится значение экстраполяции. Поскольку узлы равны ровно \(1,2,\dots,k\), базисный множитель упрощается до чередующегося биномиального коэффициента:
$$\prod_{\substack{j=1 \\ j\ne i}}^{k}\frac{(k+1)-j}{i-j}=(-1)^{k-i}\binom{k}{i-1}.$$
Следовательно,
$$\operatorname{FIT}_k=\operatorname{OP}_k(k+1)=\sum_{i=1}^{k}(-1)^{k-i}\binom{k}{i-1}u_i.$$
Именно эту величину вычисляет прямой интерполяционный подход: каждое слагаемое есть значение последовательности, умноженное на соответствующий вес Лагранжа в точке \(k+1\).
Определим оператор прямой разности как \(\Delta a_n = a_{n+1}-a_n\), положив \(\Delta^0 a_n = a_n\). Разности более высоких порядков получаются повторением той же операции. Для равноотстоящих узлов любой полином имеет разложение Ньютона по биномиальным коэффициентам:
$$u(n)=\sum_{j=0}^{10}\binom{n-1}{j}\Delta^j u_1.$$
Если обрезать это разложение после \(j=k-1\), получится ровно тот полином степени не выше \(k-1\), который совпадает с первыми \(k\) членами, то есть
$$\operatorname{OP}_k(n)=\sum_{j=0}^{k-1}\binom{n-1}{j}\Delta^j u_1.$$
В первой точке экстраполяции \(n=k+1\) получаем
$$\operatorname{FIT}_k=\sum_{j=0}^{k-1}\binom{k}{j}\Delta^j u_1.$$
Для этой последовательности первый столбец таблицы разностей начинается как \(1, 682, 42922, 708048, \dots\) и заканчивается значением \(\Delta^{10}u_1 = 3628800 = 10!\). Следующая разность уже равна нулю; это и есть конечностно-разностный признак полинома степени \(10\). Именно такую точную целочисленную схему использует реализация на C++.
Первые истинные значения равны
$$u_1=1,\qquad u_2=683,\qquad u_3=44287,\qquad u_4=838861.$$
Если взять только первые две точки, оптимальный полином будет прямой
$$\operatorname{OP}_2(n)=1+682(n-1)=682n-681.$$
Его следующий прогноз равен \(\operatorname{OP}_2(3)=1365\), тогда как настоящее значение есть \(u_3=44287\). Значит, FIT при \(k=2\) равен \(1365\).
Если использовать первые три точки, в форме Ньютона добавляется вторая разность \(42922\):
$$\operatorname{OP}_3(n)=1+682(n-1)+42922\binom{n-1}{2}.$$
Подстановка \(n=4\) дает \(\operatorname{OP}_3(4)=130813\), тогда как \(u_4=838861\). Дальше тот же расчет повторяется для всех \(k=1,\dots,10\), и сумма этих десяти экстраполяций дает ответ задачи.
Сначала реализации вычисляют \(u_1,u_2,\dots,u_{11}\). Для задачи с полиномом степени \(10\) это ровно тот объем данных, который нужен: первые \(k\) значений задают \(\operatorname{OP}_k\), а значение номер \(k+1\) показывает, получился ли FIT.
Реализации на Python и Java напрямую вычисляют интерполянт Лагранжа в точке \(x=k+1\) для каждого \(k\). Реализация на C++ один раз строит первый столбец таблицы прямых разностей, а затем использует эквивалентную формулу Ньютона с биномиальными коэффициентами. Оба подхода находят одно и то же значение \(\operatorname{OP}_k(k+1)\); первый подчеркивает базис интерполяции, второй - структуру конечных разностей.
Поскольку экземпляр очень мал, прямые версии Лагранжа используют арифметику с плавающей точкой и затем округляют результат до ближайшего целого. Здесь это безопасно, потому что все числа намного меньше границы точного представления целых в double, тогда как разностная версия вообще не использует округление.
Для каждого \(k\) предсказанное значение сравнивается с реальным следующим членом \(u_{k+1}\). Если они различаются, предсказание добавляется к общей сумме. В этой задаче каждый \(k=1,\dots,10\) дает вклад, а интерполянт по \(11\) точкам уже ничего не добавил бы, потому что полностью восстанавливает порождающий полином.
Пусть \(d\) - степень порождающего полинома. Получение первых \(d+1\) значений последовательности прямым вычислением суммы степеней, как сделано здесь, требует \(O(d^2)\) арифметических операций. После этого метод прямых разностей тратит суммарно \(O(d^2)\) времени на построение столбца разностей и вычисление всех FIT, используя \(O(d)\) памяти для рабочих массивов.
Прямое вычисление по Лагранжу в версиях на Python и Java находит экстраполяцию для префикса длины \(k\) за \(O(k^2)\) времени. Поэтому полный проход по \(k=1,\dots,d\) стоит \(\sum_{k=1}^{d} O(k^2)=O(d^3)\), снова при \(O(d)\) памяти. Для реального случая Project Euler с \(d=10\) оба подхода работают практически мгновенно.
المتتابعة في Problem 101 معرفة بالعلاقة
$$u_n = 1 - n + n^2 - n^3 + \cdots + (-n)^{10} = \sum_{r=0}^{10} (-n)^r.$$
لكل \(k = 1,2,\dots,10\)، نبني كثير الحدود الوحيد \(\operatorname{OP}_k(x)\) ذي الدرجة التي لا تتجاوز \(k-1\)، والذي يطابق القيم الاولى \(u_1,\dots,u_k\). اول قيمة نحصل عليها خارج البيانات التي تم ضبطها هي \(\operatorname{OP}_k(k+1)\)؛ فإذا كانت هذه القيمة خاطئة فهي ما تسميه المسألة first incorrect term، اي FIT. المطلوب هو جمع جميع هذه القيم.
بما ان المولد الحقيقي للمتتابعة هو كثير حدود من الدرجة \(10\)، فإن الاستيفاء باستخدام \(11\) نقطة يستعيده تماما. لذلك فالمساهمات الممكنة تأتي فقط من الاستيفاءات العشرة التي تحقق \(k \lt 11\).
المسألة كلها هي استيفاء كثيرات حدود على العقد المتتالية \(1,2,\dots,11\). والطريقتان المفيدتان هنا هما صيغة لاغرانج المباشرة وصيغة نيوتن المعتمدة على الفروق الامامية؛ وكلتاهما تصفان كثير الحدود الامثل نفسه لكن من زاويتين مختلفتين.
مع ان الحدود مكتوبة على شكل مجموع متناوب، فإن المتتابعة ما زالت ناتجة عن كثير حدود عادي من الدرجة \(10\):
$$u(n)=\sum_{r=0}^{10}(-n)^r=\frac{1-(-n)^{11}}{1+n}=\frac{n^{11}+1}{n+1}.$$
ولأن \(11\) عدد فردي، فإن بسط المتسلسلة الهندسية المنتهية يصبح \(n^{11}+1\)، وبعد القسمة على \(n+1\) نحصل على
$$u(n)=n^{10}-n^9+n^8-\cdots-n+1.$$
وهذا يوضح مباشرة لماذا تكفي \(11\) قيمة صحيحة لتحديد المتتابعة كلها: فكثير الحدود من الدرجة \(10\) يتحدد وحيدا بواسطة \(11\) نقطة متميزة.
عند تثبيت طول بادئة مقداره \(k\)، يعطينا الاستيفاء كثير الحدود الوحيد \(\operatorname{OP}_k(x)\) الذي يحقق
$$\deg \operatorname{OP}_k \le k-1,\qquad \operatorname{OP}_k(m)=u_m \text{ for } m=1,\dots,k.$$
هذا هو optimum polynomial المذكور في نص المسألة: من بين جميع الصيغ التي تطابق اول \(k\) حدود، تكون درجته هي الاصغر الممكنة. وبحكم التعريف فهو يطابق القيم عند \(1,2,\dots,k\)، لذلك فإن اول موضع يمكن ان يخطئ فيه هو \(k+1\). وفي هذه المتتابعة بالذات يخطئ هناك لكل \(k=1,\dots,10\)، بينما يعطي استيفاء \(11\) نقطة كثير الحدود المولد الحقيقي نفسه تماما.
صيغة لاغرانج لأول \(k\) نقاط هي
$$\operatorname{OP}_k(x)=\sum_{i=1}^{k} u_i \prod_{\substack{j=1 \\ j\ne i}}^{k}\frac{x-j}{i-j}.$$
وعند تقييمها في العدد الصحيح التالي \(x=k+1\) نحصل على قيمة الاستقراء خطوة واحدة الى الامام. ولأن العقد هي بالتحديد \(1,2,\dots,k\)، فإن عامل الاساس يتبسط الى معامل ثنائي حدين متناوب:
$$\prod_{\substack{j=1 \\ j\ne i}}^{k}\frac{(k+1)-j}{i-j}=(-1)^{k-i}\binom{k}{i-1}.$$
ومن ثم
$$\operatorname{FIT}_k=\operatorname{OP}_k(k+1)=\sum_{i=1}^{k}(-1)^{k-i}\binom{k}{i-1}u_i.$$
وهذه بالضبط هي الكمية التي يحسبها اسلوب الاستيفاء المباشر: كل حد فيها هو قيمة من المتتابعة مضروبة في وزن لاغرانج الموافق لها عند النقطة \(k+1\).
نعرف مؤثر الفرق الامامي بالعلاقة \(\Delta a_n = a_{n+1}-a_n\)، مع \(\Delta^0 a_n = a_n\)، ثم نحصل على الفروق العليا بتكرار العملية نفسها. ومع العقد المتساوية التباعد يمكن كتابة اي كثير حدود بصيغة نيوتن المبنية على معاملات ثنائية:
$$u(n)=\sum_{j=0}^{10}\binom{n-1}{j}\Delta^j u_1.$$
اذا قطعنا هذا التوسع بعد الحد \(j=k-1\)، نحصل بالضبط على كثير الحدود من الدرجة \(k-1\) الذي يطابق اول \(k\) حدود:
$$\operatorname{OP}_k(n)=\sum_{j=0}^{k-1}\binom{n-1}{j}\Delta^j u_1.$$
وعند اول نقطة خارجية \(n=k+1\) تصبح الصيغة
$$\operatorname{FIT}_k=\sum_{j=0}^{k-1}\binom{k}{j}\Delta^j u_1.$$
في هذه المتتابعة يبدأ العمود الاول من جدول الفروق بالقيم \(1, 682, 42922, 708048, \dots\) وينتهي عند \(\Delta^{10}u_1 = 3628800 = 10!\). ثم يختفي الفرق التالي تماما، وهذا هو التوقيع الكلاسيكي في حساب الفروق لكثير حدود من الدرجة \(10\). هذا المنظور الدقيق بالارقام الصحيحة هو ما تستخدمه نسخة C++.
اول القيم الحقيقية هي
$$u_1=1,\qquad u_2=683,\qquad u_3=44287,\qquad u_4=838861.$$
اذا استخدمنا اول نقطتين فقط، فإن كثير الحدود الامثل هو المستقيم
$$\operatorname{OP}_2(n)=1+682(n-1)=682n-681.$$
وتنبؤه التالي هو \(\operatorname{OP}_2(3)=1365\)، بينما القيمة الحقيقية هي \(u_3=44287\). لذلك يكون FIT عند \(k=2\) مساويا \(1365\).
اما عند استخدام اول ثلاث نقاط، فإن صيغة نيوتن تضيف الفرق الثاني \(42922\):
$$\operatorname{OP}_3(n)=1+682(n-1)+42922\binom{n-1}{2}.$$
وبالتعويض \(n=4\) نحصل على \(\operatorname{OP}_3(4)=130813\)، في حين ان \(u_4=838861\). ثم تتكرر العملية نفسها لكل \(k=1,\dots,10\)، ويعطي مجموع هذه القيم العشر الناتج المطلوب.
تبدأ التطبيقات بحساب \(u_1,u_2,\dots,u_{11}\). وهذه هي كمية البيانات اللازمة تماما لمسألة من الدرجة \(10\): اول \(k\) حدود تحدد \(\operatorname{OP}_k\)، والحد رقم \(k+1\) يبين هل قيمة الاستقراء هي FIT فعلا ام لا.
تقوم تطبيقات Python وJava بحساب استيفاء لاغرانج مباشرة عند \(x=k+1\) لكل طول بادئة \(k\). اما تطبيق C++ فيبني اولا عمود الفروق الامامية مرة واحدة، ثم يستخدم صيغة نيوتن المكافئة مع معاملات ثنائية. الطريقان يحسبان القيمة نفسها \(\operatorname{OP}_k(k+1)\)؛ الاول يبرز اساس الاستيفاء، والثاني يبرز بنية الفروق المنتهية.
ولأن الحالة هنا صغيرة جدا، فإن نسختي لاغرانج المباشرتين تستعملان اعداد الفاصلة العائمة ثم تقربان الناتج الى اقرب عدد صحيح. وهذا آمن في هذه المسألة لأن جميع القيم اصغر بكثير من حد التمثيل الصحيح الدقيق في double، بينما النسخة المعتمدة على الفروق تتجنب التقريب بالكامل.
لكل \(k\)، تتم مقارنة القيمة المتنبأ بها مع الحد الحقيقي التالي \(u_{k+1}\). فإذا اختلفتا، تضاف القيمة المتنبأ بها الى المجموع. وفي هذه المسألة تحديدا يساهم كل \(k=1,\dots,10\)، في حين ان استيفاء \(11\) نقطة لا يضيف شيئا لأنه يعيد انتاج كثير الحدود المولد على نحو تام.
لنفرض ان درجة كثير الحدود المولد هي \(d\). توليد اول \(d+1\) قيمة بالطريقة المباشرة المستعملة هنا لتقييم مجموع القوى يكلف \(O(d^2)\) عملية حسابية. بعد ذلك تحتاج طريقة الفروق الامامية الى \(O(d^2)\) زمنا كليا لبناء عمود الفروق وحساب جميع قيم FIT، مع ذاكرة \(O(d)\) للمصفوفات العاملة.
اما التقييم المباشر بصيغة لاغرانج في نسختي Python وJava فيحسب قيمة واحدة لبادئة طولها \(k\) خلال \(O(k^2)\) زمنيا. وبالتالي فإن المرور الكامل على \(k=1,\dots,d\) يكلف \(\sum_{k=1}^{d} O(k^2)=O(d^3)\)، مع ذاكرة \(O(d)\) ايضا. وفي حالة Project Euler حيث \(d=10\)، فإن كلا النهجين سريع جدا عمليا.