The function \(F(n)\) is defined by a four-layer nested recursion depending on parameters \((a,b,c)\), and the goal is to compute
$$S(a,b,c)=\sum_{n=0}^{b}F(n)$$
for extremely large inputs. In the Project Euler instance, \(a=21^7\), \(b=7^{21}\), and \(c=12^7\), so neither direct recursion nor iterating over all \(0 \le n \le b\) is realistic. The solution works only because the recursion collapses to a closed form.
Start from the definition
$$F(n)=\begin{cases} n-c, & n \gt b, \\ F\bigl(a+F(a+F(a+F(a+n)))\bigr), & n \le b. \end{cases}$$
Let
$$d=a-c,$$
so \(d \gt 0\). This quantity is the key simplifier throughout the derivation.
Whenever an argument \(x\) is already larger than \(b\), the recursion stops immediately and the rule becomes linear:
$$F(x)=x-c,\qquad x \gt b.$$
Now look at one outer layer of the nested expression. It always has the shape \(F(a+\text{something})\). If the inner value is already above \(b\), then that layer contributes
$$F(a+y)=a+y-c=y+d.$$
So after the computation has escaped above \(b\), each remaining outer layer adds exactly \(d\). The whole problem is therefore about determining how many layers are still genuinely recursive before we cross the boundary.
If \(n\) lies in the top strip just below \(b\), then \(n+a \gt b\). Therefore the innermost call is already outside the recursive region:
$$F(n+a)=n+a-c=n+d.$$
The next three outer layers also receive arguments \(>b\), so each of them adds another \(d\). Hence
$$F(n)=n+4d,\qquad b-a \lt n \le b.$$
This is the base case for the general pattern.
For a general \(n \le b\), define the strip index
$$s(n)=\left\lfloor\frac{b-n}{a}\right\rfloor.$$
This counts how many times we can add \(a\) to \(n\) before crossing above \(b\). Numbers with the same \(s(n)\) lie in the same width-\(a\) strip.
Assume \(s(n)=k \ge 1\). Then \(n+a\) lies one strip higher, so \(s(n+a)=k-1\). Suppose by induction that
$$F(n+a)=n+a+4d+(a+3d)(k-1).$$
Simplifying gives
$$F(n+a)=n+ak+3dk+d.$$
Because \(k=\left\lfloor\frac{b-n}{a}\right\rfloor\), we have \(n+ak \le b\). Since \(d \gt 0\), the extra term \(3dk+d\) is positive, so \(F(n+a) \gt b\). That means the remaining three outer layers are no longer recursive; each adds one more \(d\). Therefore
$$F(n)=F(n+a)+3d.$$
Substituting the induction hypothesis,
$$F(n)=n+a+4d+(a+3d)(k-1)+3d=n+4d+(a+3d)k.$$
Thus, for every \(n \le b\),
$$\boxed{F(n)=n+4d+(a+3d)\left\lfloor\frac{b-n}{a}\right\rfloor.}$$
The deep recursion has collapsed to a simple affine expression in \(n\) plus a floor term.
Now sum over all \(0 \le n \le b\):
$$S(a,b,c)=\sum_{n=0}^{b}\left(n+4d+(a+3d)\left\lfloor\frac{b-n}{a}\right\rfloor\right).$$
Split this into three standard parts:
$$S=\sum_{n=0}^{b}n+4d(b+1)+(a+3d)\sum_{n=0}^{b}\left\lfloor\frac{b-n}{a}\right\rfloor.$$
The first term is the usual triangular sum
$$\sum_{n=0}^{b}n=\frac{b(b+1)}{2}.$$
For the floor term, make the substitution \(m=b-n\). Since \(n\) runs from \(0\) to \(b\), so does \(m\), and therefore
$$\sum_{n=0}^{b}\left\lfloor\frac{b-n}{a}\right\rfloor=\sum_{m=0}^{b}\left\lfloor\frac{m}{a}\right\rfloor.$$
Write the Euclidean division of \(b\) by \(a\) as
$$b=aq+r,\qquad 0 \le r \lt a.$$
Then the values of \(\left\lfloor\frac{m}{a}\right\rfloor\) appear in blocks:
\(0\) occurs \(a\) times, \(1\) occurs \(a\) times, and so on, up to \(q-1\) occurring \(a\) times; the final value \(q\) occurs \(r+1\) times.
Hence
$$\sum_{m=0}^{b}\left\lfloor\frac{m}{a}\right\rfloor=a\sum_{j=0}^{q-1}j+(r+1)q=\frac{aq(q-1)}{2}+(r+1)q.$$
Substituting back yields the full closed form
$$\boxed{S(a,b,c)=\frac{b(b+1)}{2}+4d(b+1)+(a+3d)\left(\frac{aq(q-1)}{2}+(r+1)q\right),}$$
where \(d=a-c\), \(q=\left\lfloor\frac{b}{a}\right\rfloor\), and \(r=b\bmod a\).
This is the checkpoint used in the C++ solution. Here \(d=10\).
For the top strip \(1951 \le n \le 2000\), we have \(F(n)=n+40\).
For the next strip \(1901 \le n \le 1950\), the strip index is \(1\), so
$$F(n)=n+40+80=n+120.$$
At the very bottom, \(n=0\), we have
$$s(0)=\left\lfloor\frac{2000}{50}\right\rfloor=40,$$
so
$$F(0)=0+40+80\cdot 40=3240.$$
For the total sum, \(q=40\) and \(r=0\), hence
$$\sum_{m=0}^{2000}\left\lfloor\frac{m}{50}\right\rfloor=\frac{50\cdot 40\cdot 39}{2}+40=39040.$$
Therefore
$$S(50,2000,40)=\frac{2000\cdot 2001}{2}+40\cdot 2001+80\cdot 39040=5\,204\,240,$$
which matches the program's brute-force verification.
The C++ implementation has two main helpers. F_closed(n, a, b, c) evaluates the single-value closed form, and S_closed_mod_1e9(a, b, c) computes the summed formula directly modulo \(10^9\). The same algebra appears in the Python and Java versions. The C++ code additionally runs small brute-force checkpoints, including \((50,2000,40)\), to verify that the derived formula matches the original recursion.
Because the intermediate products can exceed 64-bit range, the C++ version uses __int128, the Java version uses BigInteger for the floor-sum term, and Python relies on its built-in arbitrary-precision integers.
Once the closed form is known, both \(F(n)\) and \(S(a,b,c)\) require only a constant number of arithmetic operations: \(O(1)\) time and \(O(1)\) extra memory. A naive recursive evaluation for all \(0 \le n \le b\) would be completely infeasible for Project Euler sized input.
Die Funktion \(F(n)\) ist durch eine vierfach verschachtelte Rekursion mit Parametern \((a,b,c)\) definiert. Gesucht ist
$$S(a,b,c)=\sum_{n=0}^{b}F(n)$$
für extrem große Eingaben. Im Euler-Fall gilt \(a=21^7\), \(b=7^{21}\) und \(c=12^7\). Weder direkte Rekursion noch ein Durchlauf über alle \(0 \le n \le b\) ist praktikabel; die Lösung funktioniert nur, weil sich die Rekursion zu einer geschlossenen Form reduziert.
Ausgangspunkt ist die Definition
$$F(n)=\begin{cases} n-c, & n \gt b, \\ F\bigl(a+F(a+F(a+F(a+n)))\bigr), & n \le b. \end{cases}$$
Setze
$$d=a-c,$$
also \(d \gt 0\). Diese Größe taucht in allen weiteren Umformungen auf.
Sobald ein Argument \(x\) bereits größer als \(b\) ist, endet die Rekursion sofort, und es gilt einfach
$$F(x)=x-c,\qquad x \gt b.$$
Eine äußere Ebene der Verschachtelung hat immer die Form \(F(a+\text{etwas})\). Falls der innere Wert schon größer als \(b\) ist, erhält man
$$F(a+y)=a+y-c=y+d.$$
Mit anderen Worten: Sobald man die Schranke \(b\) überschritten hat, fügt jede verbleibende äußere Ebene genau \(d\) hinzu. Die zentrale Frage ist also nur noch, wann dieser Austritt aus der Rekursion geschieht.
Liegt \(n\) in der obersten Schicht direkt unter \(b\), dann ist \(n+a \gt b\). Deshalb liegt schon der innerste Aufruf außerhalb des rekursiven Bereichs:
$$F(n+a)=n+a-c=n+d.$$
Die drei übrigen äußeren Ebenen erhalten ebenfalls nur noch Werte \(>b\) und addieren daher je ein weiteres \(d\). Somit
$$F(n)=n+4d,\qquad b-a \lt n \le b.$$
Das ist der Basisfall für das allgemeine Muster.
Für allgemeines \(n \le b\) definieren wir den Schichtindex
$$s(n)=\left\lfloor\frac{b-n}{a}\right\rfloor.$$
Er gibt an, wie oft man \(a\) zu \(n\) addieren kann, bevor der Wert über \(b\) hinausgeht. Alle Zahlen mit demselben \(s(n)\) liegen in derselben Schicht der Breite \(a\).
Sei nun \(s(n)=k \ge 1\). Dann liegt \(n+a\) genau eine Schicht höher, also \(s(n+a)=k-1\). Per Induktion nehmen wir an:
$$F(n+a)=n+a+4d+(a+3d)(k-1).$$
Dies vereinfacht sich zu
$$F(n+a)=n+ak+3dk+d.$$
Wegen \(k=\left\lfloor\frac{b-n}{a}\right\rfloor\) gilt \(n+ak \le b\). Da \(d \gt 0\), ist der Zusatz \(3dk+d\) positiv, also folgt \(F(n+a) \gt b\). Damit sind die verbleibenden drei äußeren Ebenen nicht mehr rekursiv; jede addiert genau ein weiteres \(d\). Also
$$F(n)=F(n+a)+3d.$$
Einsetzen der Induktionsannahme liefert
$$F(n)=n+a+4d+(a+3d)(k-1)+3d=n+4d+(a+3d)k.$$
Damit gilt für alle \(n \le b\)
$$\boxed{F(n)=n+4d+(a+3d)\left\lfloor\frac{b-n}{a}\right\rfloor.}$$
Die tiefe Rekursion ist also auf eine affine Formel in \(n\) plus einen Gaußklammer-Term reduziert.
Nun summieren wir über \(0 \le n \le b\):
$$S(a,b,c)=\sum_{n=0}^{b}\left(n+4d+(a+3d)\left\lfloor\frac{b-n}{a}\right\rfloor\right).$$
Das zerfällt in drei Standardterme:
$$S=\sum_{n=0}^{b}n+4d(b+1)+(a+3d)\sum_{n=0}^{b}\left\lfloor\frac{b-n}{a}\right\rfloor.$$
Der erste Term ist die Dreieckssumme
$$\sum_{n=0}^{b}n=\frac{b(b+1)}{2}.$$
Beim Floor-Term setzen wir \(m=b-n\). Dann läuft auch \(m\) von \(0\) bis \(b\), also
$$\sum_{n=0}^{b}\left\lfloor\frac{b-n}{a}\right\rfloor=\sum_{m=0}^{b}\left\lfloor\frac{m}{a}\right\rfloor.$$
Schreibe die euklidische Division von \(b\) durch \(a\) als
$$b=aq+r,\qquad 0 \le r \lt a.$$
Dann treten die Werte von \(\left\lfloor\frac{m}{a}\right\rfloor\) blockweise auf:
\(0\) kommt \(a\)-mal vor, \(1\) kommt \(a\)-mal vor, und so weiter, bis \(q-1\) ebenfalls \(a\)-mal vorkommt; der letzte Wert \(q\) erscheint \(r+1\)-mal.
Daher
$$\sum_{m=0}^{b}\left\lfloor\frac{m}{a}\right\rfloor=a\sum_{j=0}^{q-1}j+(r+1)q=\frac{aq(q-1)}{2}+(r+1)q.$$
Eingesetzt ergibt das die vollständige geschlossene Form
$$\boxed{S(a,b,c)=\frac{b(b+1)}{2}+4d(b+1)+(a+3d)\left(\frac{aq(q-1)}{2}+(r+1)q\right),}$$
wobei \(d=a-c\), \(q=\left\lfloor\frac{b}{a}\right\rfloor\) und \(r=b\bmod a\) ist.
Dies ist der Prüfpunkt aus der C++-Implementierung. Hier gilt \(d=10\).
In der obersten Schicht \(1951 \le n \le 2000\) ist \(F(n)=n+40\).
In der nächsten Schicht \(1901 \le n \le 1950\) ist der Schichtindex \(1\), also
$$F(n)=n+40+80=n+120.$$
Ganz unten bei \(n=0\) erhält man
$$s(0)=\left\lfloor\frac{2000}{50}\right\rfloor=40,$$
also
$$F(0)=0+40+80\cdot 40=3240.$$
Für die Gesamtsumme gilt \(q=40\) und \(r=0\), somit
$$\sum_{m=0}^{2000}\left\lfloor\frac{m}{50}\right\rfloor=\frac{50\cdot 40\cdot 39}{2}+40=39040.$$
Folglich
$$S(50,2000,40)=\frac{2000\cdot 2001}{2}+40\cdot 2001+80\cdot 39040=5\,204\,240,$$
genau wie in der Brute-Force-Verifikation des Programms.
Die C++-Lösung besitzt zwei zentrale Hilfsfunktionen. F_closed(n, a, b, c) berechnet die geschlossene Formel für einen einzelnen Wert, und S_closed_mod_1e9(a, b, c) wertet die Summenformel direkt modulo \(10^9\) aus. Dieselbe Algebra steckt auch in den Python- und Java-Versionen. Zusätzlich führt die C++-Fassung kleine Brute-Force-Tests, unter anderem für \((50,2000,40)\), zur Verifikation der Herleitung aus.
Da Zwischenprodukte den 64-Bit-Bereich überschreiten können, verwendet C++ __int128, Java nutzt für den Floor-Summen-Term BigInteger, und Python profitiert von eingebauten Ganzzahlen beliebiger Präzision.
Nach der Herleitung benötigen sowohl \(F(n)\) als auch \(S(a,b,c)\) nur noch eine konstante Anzahl arithmetischer Operationen: \(O(1)\) Zeit und \(O(1)\) zusätzlicher Speicher. Eine naive rekursive Auswertung für alle \(0 \le n \le b\) wäre für Euler-Größenordnungen völlig unbrauchbar.
\(F(n)\) fonksiyonu \((a,b,c)\) parametrelerine bağlı, dört katmanlı iç içe bir özyineleme ile tanımlıdır. Amaç
$$S(a,b,c)=\sum_{n=0}^{b}F(n)$$
toplamını çok büyük girdiler için hesaplamaktır. Project Euler örneğinde \(a=21^7\), \(b=7^{21}\) ve \(c=12^7\) olduğundan ne doğrudan özyineleme ne de \(0 \le n \le b\) aralığını dolaşmak mümkündür. Çözüm ancak özyineleme kapalı forma indirgenebildiği için çalışır.
Tanım şu şekildedir:
$$F(n)=\begin{cases} n-c, & n \gt b, \\ F\bigl(a+F(a+F(a+F(a+n)))\bigr), & n \le b. \end{cases}$$
Şimdi
$$d=a-c$$
tanımını yapalım. \(d \gt 0\) olduğu için türetimin tamamında bu fark belirleyici olacaktır.
Bir argüman \(x\) zaten \(b\)'den büyükse, özyineleme hemen biter ve tanım doğrusal hale gelir:
$$F(x)=x-c,\qquad x \gt b.$$
İç içe yapının her dış katmanı \(F(a+\text{bir şey})\) biçimindedir. Eğer iç taraftaki değer zaten \(b\)'yi aşmışsa, bu katmanda
$$F(a+y)=a+y-c=y+d$$
elde edilir. Yani hesap bir kez \(b\)'nin üstüne çıktıktan sonra kalan her dış katman toplamda yalnızca bir \(d\) daha ekler. Dolayısıyla asıl mesele, bu eşik hangi noktada aşılıyor sorusudur.
\(n\), \(b\)'nin hemen altındaki üst şeritteyse \(n+a \gt b\) olur. Bu yüzden en içteki çağrı artık özyinelemeli değildir:
$$F(n+a)=n+a-c=n+d.$$
Geriye kalan üç dış katman da yine \(>b\) argümanlarıyla çalışır ve her biri bir \(d\) daha ekler. Sonuç:
$$F(n)=n+4d,\qquad b-a \lt n \le b.$$
Genel formülün başlangıç noktası budur.
Genel bir \(n \le b\) için şerit indeksini
$$s(n)=\left\lfloor\frac{b-n}{a}\right\rfloor$$
olarak tanımlayalım. Bu değer, \(n\)'ye \(a\) kaç kez eklenebileceğini ve yine de \(b\)'yi aşmadan kalınacağını söyler. Aynı \(s(n)\) değerine sahip sayılar genişliği \(a\) olan aynı şerittedir.
\(s(n)=k \ge 1\) olsun. O zaman \(n+a\), bir üst şeritte yer alır ve \(s(n+a)=k-1\) olur. İndüksiyon varsayımı olarak
$$F(n+a)=n+a+4d+(a+3d)(k-1)$$
kabul edelim. Bu ifade sadeleşince
$$F(n+a)=n+ak+3dk+d$$
elde edilir. \(k=\left\lfloor\frac{b-n}{a}\right\rfloor\) olduğundan \(n+ak \le b\) bilinir. \(d \gt 0\) olduğu için \(3dk+d\) terimi pozitiftir; dolayısıyla \(F(n+a) \gt b\). Bu da kalan üç dış katmanın artık doğrusal dala düştüğü anlamına gelir; her biri bir \(d\) daha ekler. O halde
$$F(n)=F(n+a)+3d.$$
İndüksiyon varsayımını yerine koyarsak
$$F(n)=n+a+4d+(a+3d)(k-1)+3d=n+4d+(a+3d)k.$$
Sonuç olarak tüm \(n \le b\) için
$$\boxed{F(n)=n+4d+(a+3d)\left\lfloor\frac{b-n}{a}\right\rfloor.}$$
Derin özyineleme böylece \(n\) cinsinden basit bir affine ifade ile bir floor terimine indirgenmiş olur.
Şimdi \(0 \le n \le b\) için bu ifadeyi toplayalım:
$$S(a,b,c)=\sum_{n=0}^{b}\left(n+4d+(a+3d)\left\lfloor\frac{b-n}{a}\right\rfloor\right).$$
Bunu üç standart parçaya ayırabiliriz:
$$S=\sum_{n=0}^{b}n+4d(b+1)+(a+3d)\sum_{n=0}^{b}\left\lfloor\frac{b-n}{a}\right\rfloor.$$
İlk terim bildik üçgensel toplamdır:
$$\sum_{n=0}^{b}n=\frac{b(b+1)}{2}.$$
Floor terimi için \(m=b-n\) dönüşümünü yaparsak, \(m\) de yine \(0\)'dan \(b\)'ye kadar gider ve
$$\sum_{n=0}^{b}\left\lfloor\frac{b-n}{a}\right\rfloor=\sum_{m=0}^{b}\left\lfloor\frac{m}{a}\right\rfloor$$
elde edilir.
\(b\)'nin \(a\)'ya Öklid bölmesini
$$b=aq+r,\qquad 0 \le r \lt a$$
şeklinde yazalım.
Bu durumda \(\left\lfloor\frac{m}{a}\right\rfloor\) değerleri bloklar halinde oluşur:
\(0\) değeri \(a\) kez, \(1\) değeri \(a\) kez, ..., \(q-1\) değeri yine \(a\) kez görülür; son değer \(q\) ise \(r+1\) kez ortaya çıkar.
Dolayısıyla
$$\sum_{m=0}^{b}\left\lfloor\frac{m}{a}\right\rfloor=a\sum_{j=0}^{q-1}j+(r+1)q=\frac{aq(q-1)}{2}+(r+1)q.$$
Bunu ana ifadeye yerleştirince tam kapalı form elde edilir:
$$\boxed{S(a,b,c)=\frac{b(b+1)}{2}+4d(b+1)+(a+3d)\left(\frac{aq(q-1)}{2}+(r+1)q\right),}$$
burada \(d=a-c\), \(q=\left\lfloor\frac{b}{a}\right\rfloor\) ve \(r=b\bmod a\).
Bu örnek C++ çözümünde doğrulama amacıyla kullanılır. Burada \(d=10\).
Üst şeritte, yani \(1951 \le n \le 2000\) için \(F(n)=n+40\) olur.
Bir alt şeritte, \(1901 \le n \le 1950\) aralığında şerit indeksi \(1\) olduğu için
$$F(n)=n+40+80=n+120.$$
En altta \(n=0\) için
$$s(0)=\left\lfloor\frac{2000}{50}\right\rfloor=40,$$
dolayısıyla
$$F(0)=0+40+80\cdot 40=3240.$$
Toplam için \(q=40\) ve \(r=0\) olduğundan
$$\sum_{m=0}^{2000}\left\lfloor\frac{m}{50}\right\rfloor=\frac{50\cdot 40\cdot 39}{2}+40=39040.$$
Böylece
$$S(50,2000,40)=\frac{2000\cdot 2001}{2}+40\cdot 2001+80\cdot 39040=5\,204\,240,$$
ve bu değer programın brute-force kontrolüyle birebir uyuşur.
C++ çözümünde iki ana yardımcı fonksiyon vardır. F_closed(n, a, b, c) tek bir \(n\) değeri için kapalı formu hesaplar, S_closed_mod_1e9(a, b, c) ise toplam formülünü doğrudan \(10^9\) modunda değerlendirir. Aynı cebir Python ve Java sürümlerinde de kullanılır. Ayrıca C++ kodu, \((50,2000,40)\) dahil olmak üzere küçük brute-force kontrolleri yaparak türetilen formülün orijinal özyineleme ile uyuştuğunu sınar.
Ara çarpımlar 64-bit sınırını aşabildiği için C++ tarafı __int128, Java tarafı floor-toplamı için BigInteger, Python tarafı ise yerleşik keyfi hassasiyetli tamsayıları kullanır.
Kapalı form elde edildikten sonra hem \(F(n)\) hem de \(S(a,b,c)\) yalnızca sabit sayıda aritmetik işlem gerektirir: \(O(1)\) zaman ve \(O(1)\) ek bellek. Buna karşılık tüm \(0 \le n \le b\) değerleri için doğrudan özyinelemeli hesap yapmak Euler boyutlarında tamamen uygulanamazdır.
La función \(F(n)\) está definida por una recursión anidada en cuatro niveles con parámetros \((a,b,c)\). Se pide calcular
$$S(a,b,c)=\sum_{n=0}^{b}F(n)$$
para entradas enormes. En el caso de Project Euler, \(a=21^7\), \(b=7^{21}\) y \(c=12^7\), así que ni la recursión directa ni iterar sobre todos los \(0 \le n \le b\) es viable. La solución funciona porque la recursión se derrumba en una forma cerrada.
Partimos de la definición
$$F(n)=\begin{cases} n-c, & n \gt b, \\ F\bigl(a+F(a+F(a+F(a+n)))\bigr), & n \le b. \end{cases}$$
Definimos
$$d=a-c,$$
de modo que \(d \gt 0\). Esta diferencia es la cantidad que simplifica toda la derivación.
Cuando un argumento \(x\) ya es mayor que \(b\), la recursión se detiene de inmediato y la regla pasa a ser lineal:
$$F(x)=x-c,\qquad x \gt b.$$
Cada capa exterior de la expresión tiene la forma \(F(a+\text{algo})\). Si el valor interior ya superó \(b\), entonces
$$F(a+y)=a+y-c=y+d.$$
Es decir, una vez que el cálculo ha escapado por encima de \(b\), cada capa exterior restante añade exactamente \(d\). Por eso el problema real consiste en determinar en qué momento se cruza esa frontera.
Si \(n\) está en la franja superior inmediatamente debajo de \(b\), entonces \(n+a \gt b\). Por lo tanto, la llamada más interna ya sale de la zona recursiva:
$$F(n+a)=n+a-c=n+d.$$
Las tres capas exteriores siguientes también reciben argumentos \(>b\), así que cada una añade otro \(d\). En consecuencia,
$$F(n)=n+4d,\qquad b-a \lt n \le b.$$
Este es el caso base del patrón general.
Para un \(n \le b\) general, definimos el índice de franja
$$s(n)=\left\lfloor\frac{b-n}{a}\right\rfloor.$$
Este valor cuenta cuántas veces podemos sumar \(a\) a \(n\) antes de superar \(b\). Los números con el mismo \(s(n)\) pertenecen a la misma franja de ancho \(a\).
Supongamos \(s(n)=k \ge 1\). Entonces \(n+a\) está una franja más arriba, es decir, \(s(n+a)=k-1\). Por hipótesis inductiva,
$$F(n+a)=n+a+4d+(a+3d)(k-1).$$
Al simplificar, obtenemos
$$F(n+a)=n+ak+3dk+d.$$
Como \(k=\left\lfloor\frac{b-n}{a}\right\rfloor\), se cumple \(n+ak \le b\). Y como \(d \gt 0\), el término adicional \(3dk+d\) es positivo, así que \(F(n+a) \gt b\). Eso implica que las tres capas exteriores restantes ya no son recursivas; cada una añade un \(d\) más. Por tanto,
$$F(n)=F(n+a)+3d.$$
Sustituyendo la hipótesis inductiva,
$$F(n)=n+a+4d+(a+3d)(k-1)+3d=n+4d+(a+3d)k.$$
Luego, para todo \(n \le b\),
$$\boxed{F(n)=n+4d+(a+3d)\left\lfloor\frac{b-n}{a}\right\rfloor.}$$
La recursión profunda se convierte así en una expresión afín muy simple más un término con piso.
Ahora sumamos para \(0 \le n \le b\):
$$S(a,b,c)=\sum_{n=0}^{b}\left(n+4d+(a+3d)\left\lfloor\frac{b-n}{a}\right\rfloor\right).$$
Se separa en tres partes estándar:
$$S=\sum_{n=0}^{b}n+4d(b+1)+(a+3d)\sum_{n=0}^{b}\left\lfloor\frac{b-n}{a}\right\rfloor.$$
El primer término es la suma triangular clásica:
$$\sum_{n=0}^{b}n=\frac{b(b+1)}{2}.$$
Para el término con piso, hacemos el cambio \(m=b-n\). Entonces \(m\) también recorre \(0\) hasta \(b\), y queda
$$\sum_{n=0}^{b}\left\lfloor\frac{b-n}{a}\right\rfloor=\sum_{m=0}^{b}\left\lfloor\frac{m}{a}\right\rfloor.$$
Escribimos la división euclídea de \(b\) entre \(a\) como
$$b=aq+r,\qquad 0 \le r \lt a.$$
Entonces los valores de \(\left\lfloor\frac{m}{a}\right\rfloor\) aparecen por bloques:
\(0\) aparece \(a\) veces, \(1\) aparece \(a\) veces, y así sucesivamente hasta \(q-1\), que también aparece \(a\) veces; el valor final \(q\) aparece \(r+1\) veces.
Por ello,
$$\sum_{m=0}^{b}\left\lfloor\frac{m}{a}\right\rfloor=a\sum_{j=0}^{q-1}j+(r+1)q=\frac{aq(q-1)}{2}+(r+1)q.$$
Al sustituir, obtenemos la forma cerrada completa
$$\boxed{S(a,b,c)=\frac{b(b+1)}{2}+4d(b+1)+(a+3d)\left(\frac{aq(q-1)}{2}+(r+1)q\right),}$$
donde \(d=a-c\), \(q=\left\lfloor\frac{b}{a}\right\rfloor\) y \(r=b\bmod a\).
Este es el punto de control usado en la solución en C++. Aquí \(d=10\).
En la franja superior \(1951 \le n \le 2000\), se obtiene \(F(n)=n+40\).
En la franja siguiente \(1901 \le n \le 1950\), el índice es \(1\), así que
$$F(n)=n+40+80=n+120.$$
En la parte inferior, para \(n=0\),
$$s(0)=\left\lfloor\frac{2000}{50}\right\rfloor=40,$$
y por tanto
$$F(0)=0+40+80\cdot 40=3240.$$
Para la suma total, \(q=40\) y \(r=0\), luego
$$\sum_{m=0}^{2000}\left\lfloor\frac{m}{50}\right\rfloor=\frac{50\cdot 40\cdot 39}{2}+40=39040.$$
Así,
$$S(50,2000,40)=\frac{2000\cdot 2001}{2}+40\cdot 2001+80\cdot 39040=5\,204\,240,$$
exactamente el mismo valor que confirma la verificación por fuerza bruta del programa.
La implementación en C++ tiene dos auxiliares principales. F_closed(n, a, b, c) evalúa la forma cerrada para un solo valor, y S_closed_mod_1e9(a, b, c) calcula directamente la suma cerrada módulo \(10^9\). La misma álgebra aparece en las versiones de Python y Java. Además, el código en C++ ejecuta pequeñas verificaciones por fuerza bruta, incluida \((50,2000,40)\), para comprobar que la fórmula derivada coincide con la recursión original.
Como los productos intermedios pueden superar 64 bits, C++ usa __int128, Java emplea BigInteger para el término de la suma piso y Python se apoya en enteros de precisión arbitraria.
Una vez conocida la forma cerrada, tanto \(F(n)\) como \(S(a,b,c)\) requieren solo un número constante de operaciones aritméticas: \(O(1)\) en tiempo y \(O(1)\) en memoria adicional. Una evaluación recursiva ingenua para todos los \(0 \le n \le b\) sería totalmente inviable con los tamaños de Project Euler.
函数 \(F(n)\) 由参数 \((a,b,c)\) 决定，并且具有四层嵌套递归结构。目标是计算
$$S(a,b,c)=\sum_{n=0}^{b}F(n)$$
在超大输入下的值。Project Euler 的参数是 \(a=21^7\)、\(b=7^{21}\)、\(c=12^7\)，因此无论是直接递归还是枚举全部 \(0 \le n \le b\) 都不可行。整个解法的关键在于把递归压缩成闭式。
原始定义为
$$F(n)=\begin{cases} n-c, & n \gt b, \\ F\bigl(a+F(a+F(a+F(a+n)))\bigr), & n \le b. \end{cases}$$
记
$$d=a-c,$$
于是 \(d \gt 0\)。后面的所有化简都围绕这个差值展开。
一旦某个参数 \(x\) 已经大于 \(b\)，递归立刻停止，函数直接退化成线性形式：
$$F(x)=x-c,\qquad x \gt b.$$
而外层结构总是长成 \(F(a+\text{某个值})\) 的样子。如果内部值已经超过 \(b\)，那么这一层就变成
$$F(a+y)=a+y-c=y+d.$$
这意味着，一旦计算过程越过了边界 \(b\)，后面每剩下一层外壳，就只会再增加一个 \(d\)。所以问题真正的核心，是判断什么时候首次越界。
如果 \(n\) 落在紧贴 \(b\) 的最上层条带里，那么 \(n+a \gt b\)。因此最内层调用已经不再递归：
$$F(n+a)=n+a-c=n+d.$$
后面三层外调用接收到的参数也都大于 \(b\)，所以每层再多加一个 \(d\)。于是
$$F(n)=n+4d,\qquad b-a \lt n \le b.$$
这就是整个闭式的基例。
对一般的 \(n \le b\)，定义条带编号
$$s(n)=\left\lfloor\frac{b-n}{a}\right\rfloor.$$
它表示从 \(n\) 开始最多还能加多少次 \(a\) 而不越过 \(b\)。具有相同 \(s(n)\) 的数落在同一条宽度为 \(a\) 的条带中。
设 \(s(n)=k \ge 1\)。那么 \(n+a\) 位于上一条带，所以 \(s(n+a)=k-1\)。归纳假设为
$$F(n+a)=n+a+4d+(a+3d)(k-1).$$
化简得到
$$F(n+a)=n+ak+3dk+d.$$
由于 \(k=\left\lfloor\frac{b-n}{a}\right\rfloor\)，有 \(n+ak \le b\)。又因为 \(d \gt 0\)，所以附加项 \(3dk+d\) 为正，从而 \(F(n+a) \gt b\)。这说明剩下的三层外调用都已经落在线性分支里，每层只再增加一个 \(d\)。因此
$$F(n)=F(n+a)+3d.$$
代入归纳假设，得到
$$F(n)=n+a+4d+(a+3d)(k-1)+3d=n+4d+(a+3d)k.$$
于是对所有 \(n \le b\) 都成立
$$\boxed{F(n)=n+4d+(a+3d)\left\lfloor\frac{b-n}{a}\right\rfloor.}$$
原本很深的递归，最终被压缩成了关于 \(n\) 的一个仿射表达式再加一个 floor 项。
接下来把它在 \(0 \le n \le b\) 上求和：
$$S(a,b,c)=\sum_{n=0}^{b}\left(n+4d+(a+3d)\left\lfloor\frac{b-n}{a}\right\rfloor\right).$$
可以拆成三部分：
$$S=\sum_{n=0}^{b}n+4d(b+1)+(a+3d)\sum_{n=0}^{b}\left\lfloor\frac{b-n}{a}\right\rfloor.$$
第一项是普通的三角和：
$$\sum_{n=0}^{b}n=\frac{b(b+1)}{2}.$$
对于 floor 项，令 \(m=b-n\)。此时 \(m\) 也从 \(0\) 走到 \(b\)，因此
$$\sum_{n=0}^{b}\left\lfloor\frac{b-n}{a}\right\rfloor=\sum_{m=0}^{b}\left\lfloor\frac{m}{a}\right\rfloor.$$
把 \(b\) 对 \(a\) 做欧几里得除法：
$$b=aq+r,\qquad 0 \le r \lt a.$$
那么 \(\left\lfloor\frac{m}{a}\right\rfloor\) 的取值呈块状分布：
\(0\) 出现 \(a\) 次，\(1\) 出现 \(a\) 次，依此类推，直到 \(q-1\) 也出现 \(a\) 次；最后的 \(q\) 出现 \(r+1\) 次。
所以
$$\sum_{m=0}^{b}\left\lfloor\frac{m}{a}\right\rfloor=a\sum_{j=0}^{q-1}j+(r+1)q=\frac{aq(q-1)}{2}+(r+1)q.$$
代回去就得到完整闭式
$$\boxed{S(a,b,c)=\frac{b(b+1)}{2}+4d(b+1)+(a+3d)\left(\frac{aq(q-1)}{2}+(r+1)q\right),}$$
其中 \(d=a-c\)、\(q=\left\lfloor\frac{b}{a}\right\rfloor\)、\(r=b\bmod a\)。
这是 C++ 实现里用来校验的样例。此时 \(d=10\)。
在最上层条带 \(1951 \le n \le 2000\) 中，有 \(F(n)=n+40\)。
再下一层条带 \(1901 \le n \le 1950\) 的编号为 \(1\)，于是
$$F(n)=n+40+80=n+120.$$
在最底端 \(n=0\) 时，
$$s(0)=\left\lfloor\frac{2000}{50}\right\rfloor=40,$$
因此
$$F(0)=0+40+80\cdot 40=3240.$$
对于总和，\(q=40\)、\(r=0\)，于是
$$\sum_{m=0}^{2000}\left\lfloor\frac{m}{50}\right\rfloor=\frac{50\cdot 40\cdot 39}{2}+40=39040.$$
所以
$$S(50,2000,40)=\frac{2000\cdot 2001}{2}+40\cdot 2001+80\cdot 39040=5\,204\,240,$$
与程序的暴力校验完全一致。
C++ 版本有两个核心辅助函数。F_closed(n, a, b, c) 计算单个 \(n\) 的闭式值，S_closed_mod_1e9(a, b, c) 直接按闭式求总和并对 \(10^9\) 取模。Python 和 Java 版本使用的是同一套代数公式。C++ 代码还会运行若干小规模暴力检查，包括 \((50,2000,40)\)，以确认推导出的闭式与原始递归完全一致。
由于中间乘积可能超出 64 位范围，C++ 使用 __int128，Java 对 floor 和部分使用 BigInteger，而 Python 直接依赖内建的大整数。
一旦闭式推导完成，\(F(n)\) 和 \(S(a,b,c)\) 都只需要常数次算术运算，因此时间复杂度为 \(O(1)\)，额外空间复杂度也为 \(O(1)\)。如果对所有 \(0 \le n \le b\) 直接做递归求值，在 Euler 规模下是完全不可执行的。
Функция \(F(n)\) задается четырехуровневой вложенной рекурсией с параметрами \((a,b,c)\). Требуется вычислить
$$S(a,b,c)=\sum_{n=0}^{b}F(n)$$
для огромных значений параметров. В задаче Project Euler используются \(a=21^7\), \(b=7^{21}\), \(c=12^7\), поэтому ни прямой рекурсивный расчет, ни перебор всех \(0 \le n \le b\) невозможны на практике. Решение существует только потому, что рекурсия сводится к закрытой формуле.
Исходим из определения
$$F(n)=\begin{cases} n-c, & n \gt b, \\ F\bigl(a+F(a+F(a+F(a+n)))\bigr), & n \le b. \end{cases}$$
Обозначим
$$d=a-c,$$
тогда \(d \gt 0\). Именно эта разность делает дальнейшие преобразования простыми.
Если аргумент \(x\) уже больше \(b\), рекурсия немедленно прекращается, и остается линейное правило
$$F(x)=x-c,\qquad x \gt b.$$
Каждый внешний слой вложения имеет вид \(F(a+\text{что-то})\). Если внутреннее значение уже превысило \(b\), то на этой стадии получаем
$$F(a+y)=a+y-c=y+d.$$
Иными словами, после выхода за границу \(b\) каждый оставшийся внешний слой просто добавляет еще одно \(d\). Значит, вся задача сводится к тому, чтобы понять, когда именно происходит первый выход за порог.
Если \(n\) лежит в верхней полосе непосредственно под \(b\), то \(n+a \gt b\). Поэтому самый внутренний вызов уже не рекурсивен:
$$F(n+a)=n+a-c=n+d.$$
Следующие три внешних слоя тоже получают аргументы \(>b\), поэтому каждый добавляет еще одно \(d\). Отсюда
$$F(n)=n+4d,\qquad b-a \lt n \le b.$$
Это базовый случай для всей конструкции.
Для общего \(n \le b\) введем индекс полосы
$$s(n)=\left\lfloor\frac{b-n}{a}\right\rfloor.$$
Он показывает, сколько раз можно прибавить к \(n\) число \(a\), не превысив \(b\). Числа с одинаковым \(s(n)\) лежат в одной и той же полосе ширины \(a\).
Пусть \(s(n)=k \ge 1\). Тогда \(n+a\) находится полосой выше, то есть \(s(n+a)=k-1\). По индукционному предположению
$$F(n+a)=n+a+4d+(a+3d)(k-1).$$
После упрощения получаем
$$F(n+a)=n+ak+3dk+d.$$
Так как \(k=\left\lfloor\frac{b-n}{a}\right\rfloor\), имеем \(n+ak \le b\). Поскольку \(d \gt 0\), добавка \(3dk+d\) положительна, значит \(F(n+a) \gt b\). Следовательно, оставшиеся три внешних слоя уже не рекурсивны и каждый прибавляет еще одно \(d\). Поэтому
$$F(n)=F(n+a)+3d.$$
Подставляя индукционное предположение, получаем
$$F(n)=n+a+4d+(a+3d)(k-1)+3d=n+4d+(a+3d)k.$$
Итак, для всех \(n \le b\) верно
$$\boxed{F(n)=n+4d+(a+3d)\left\lfloor\frac{b-n}{a}\right\rfloor.}$$
Глубокая рекурсия превратилась в простое аффинное выражение по \(n\) и один floor-терм.
Теперь суммируем по всем \(0 \le n \le b\):
$$S(a,b,c)=\sum_{n=0}^{b}\left(n+4d+(a+3d)\left\lfloor\frac{b-n}{a}\right\rfloor\right).$$
Разбиваем сумму на три стандартные части:
$$S=\sum_{n=0}^{b}n+4d(b+1)+(a+3d)\sum_{n=0}^{b}\left\lfloor\frac{b-n}{a}\right\rfloor.$$
Первая часть есть обычная треугольная сумма
$$\sum_{n=0}^{b}n=\frac{b(b+1)}{2}.$$
Для floor-суммы делаем замену \(m=b-n\). Тогда \(m\) также пробегает значения от \(0\) до \(b\), и
$$\sum_{n=0}^{b}\left\lfloor\frac{b-n}{a}\right\rfloor=\sum_{m=0}^{b}\left\lfloor\frac{m}{a}\right\rfloor.$$
Запишем деление \(b\) на \(a\) с остатком:
$$b=aq+r,\qquad 0 \le r \lt a.$$
Тогда значения \(\left\lfloor\frac{m}{a}\right\rfloor\) распределяются блоками:
значение \(0\) встречается \(a\) раз, значение \(1\) встречается \(a\) раз и так далее до \(q-1\), которое тоже встречается \(a\) раз; последнее значение \(q\) встречается \(r+1\) раз.
Следовательно,
$$\sum_{m=0}^{b}\left\lfloor\frac{m}{a}\right\rfloor=a\sum_{j=0}^{q-1}j+(r+1)q=\frac{aq(q-1)}{2}+(r+1)q.$$
После подстановки получаем полную закрытую формулу
$$\boxed{S(a,b,c)=\frac{b(b+1)}{2}+4d(b+1)+(a+3d)\left(\frac{aq(q-1)}{2}+(r+1)q\right),}$$
где \(d=a-c\), \(q=\left\lfloor\frac{b}{a}\right\rfloor\), \(r=b\bmod a\).
Именно этот пример используется в C++-коде для проверки. Здесь \(d=10\).
В верхней полосе \(1951 \le n \le 2000\) имеем \(F(n)=n+40\).
В следующей полосе \(1901 \le n \le 1950\) индекс равен \(1\), поэтому
$$F(n)=n+40+80=n+120.$$
В нижней точке \(n=0\)
$$s(0)=\left\lfloor\frac{2000}{50}\right\rfloor=40,$$
откуда
$$F(0)=0+40+80\cdot 40=3240.$$
Для общей суммы \(q=40\) и \(r=0\), следовательно
$$\sum_{m=0}^{2000}\left\lfloor\frac{m}{50}\right\rfloor=\frac{50\cdot 40\cdot 39}{2}+40=39040.$$
Значит,
$$S(50,2000,40)=\frac{2000\cdot 2001}{2}+40\cdot 2001+80\cdot 39040=5\,204\,240,$$
что точно совпадает с брутфорс-проверкой в программе.
В C++-реализации есть две основные вспомогательные функции. F_closed(n, a, b, c) вычисляет закрытую формулу для одного значения, а S_closed_mod_1e9(a, b, c) напрямую считает итоговую сумму по модулю \(10^9\). Та же алгебра используется в версиях на Python и Java. Кроме того, C++-код запускает небольшие брутфорс-проверки, включая \((50,2000,40)\), чтобы убедиться, что выведенная формула полностью совпадает с исходной рекурсией.
Поскольку промежуточные произведения могут выходить за пределы 64 бит, версия на C++ использует __int128, Java применяет BigInteger для floor-суммы, а Python опирается на встроенные длинные целые.
После вывода закрытой формы и \(F(n)\), и \(S(a,b,c)\) вычисляются за постоянное число арифметических операций: \(O(1)\) по времени и \(O(1)\) по дополнительной памяти. Наивный рекурсивный расчет для всех \(0 \le n \le b\) был бы полностью непрактичен для масштабов Project Euler.
الدالة \(F(n)\) معرّفة بعلاقة عودية متداخلة من أربع طبقات وتعتمد على المعاملات \((a,b,c)\). المطلوب حساب
$$S(a,b,c)=\sum_{n=0}^{b}F(n)$$
لقيم ضخمة جدًا. في نسخة Project Euler لدينا \(a=21^7\)، و\(b=7^{21}\)، و\(c=12^7\)، لذلك لا يمكن لا العودية المباشرة ولا المرور على كل القيم \(0 \le n \le b\). الفكرة كلها أن هذه العودية تنهار إلى صيغة مغلقة.
نبدأ من التعريف
$$F(n)=\begin{cases} n-c, & n \gt b, \\ F\bigl(a+F(a+F(a+F(a+n)))\bigr), & n \le b. \end{cases}$$
ولنضع
$$d=a-c,$$
ومن ثم \(d \gt 0\). هذا الفرق هو العنصر الذي يبسط الاشتقاق كله.
إذا كان الوسيط \(x\) أكبر من \(b\) أصلًا، تتوقف العودية فورًا ويصبح لدينا
$$F(x)=x-c,\qquad x \gt b.$$
كل طبقة خارجية في التعبير المتداخل تأخذ الصورة \(F(a+\text{شيء})\). فإذا كانت القيمة الداخلية قد تجاوزت \(b\) بالفعل، فإن تلك الطبقة تعطي
$$F(a+y)=a+y-c=y+d.$$
أي أنه بمجرد أن يتجاوز الحساب الحد \(b\)، فإن كل طبقة خارجية متبقية تضيف \(d\) واحدًا فقط. لذلك يصبح السؤال الحقيقي: متى نعبر هذا الحد أول مرة؟
إذا كان \(n\) في الشريط الأعلى مباشرة أسفل \(b\)، فإن \(n+a \gt b\). ولذلك تكون الدعوة الأعمق قد خرجت أصلًا من المنطقة العودية:
$$F(n+a)=n+a-c=n+d.$$
الطبقات الخارجية الثلاث الباقية تستقبل أيضًا قيمًا أكبر من \(b\)، لذا تضيف كل واحدة \(d\) إضافية. ومن ثم
$$F(n)=n+4d,\qquad b-a \lt n \le b.$$
وهذا هو أساس النمط العام.
لأي \(n \le b\) نعرّف رقم الشريط
$$s(n)=\left\lfloor\frac{b-n}{a}\right\rfloor.$$
هذا الرقم يبين عدد المرات التي يمكن فيها إضافة \(a\) إلى \(n\) قبل تجاوز \(b\). وكل القيم ذات \(s(n)\) نفسه تقع في الشريط نفسه بعرض \(a\).
افترض أن \(s(n)=k \ge 1\). عندئذ يكون \(n+a\) في الشريط الأعلى مباشرة، أي \(s(n+a)=k-1\). وبفرضية الاستقراء
$$F(n+a)=n+a+4d+(a+3d)(k-1).$$
وبالتبسيط نحصل على
$$F(n+a)=n+ak+3dk+d.$$
ولأن \(k=\left\lfloor\frac{b-n}{a}\right\rfloor\)، فإن \(n+ak \le b\). وبما أن \(d \gt 0\)، فالحد \(3dk+d\) موجب، وبالتالي \(F(n+a) \gt b\). هذا يعني أن الطبقات الخارجية الثلاث المتبقية لم تعد عودية؛ كل واحدة منها تضيف \(d\) آخر. لذلك
$$F(n)=F(n+a)+3d.$$
وبالتعويض من فرضية الاستقراء نحصل على
$$F(n)=n+a+4d+(a+3d)(k-1)+3d=n+4d+(a+3d)k.$$
إذن لكل \(n \le b\) لدينا
$$\boxed{F(n)=n+4d+(a+3d)\left\lfloor\frac{b-n}{a}\right\rfloor.}$$
وهكذا تتحول العودية العميقة إلى تعبير خطي بسيط في \(n\) مع حد واحد من نوع floor.
الآن نجمع هذه الصيغة على كل \(0 \le n \le b\):
$$S(a,b,c)=\sum_{n=0}^{b}\left(n+4d+(a+3d)\left\lfloor\frac{b-n}{a}\right\rfloor\right).$$
وهذا ينفصل إلى ثلاثة حدود قياسية:
$$S=\sum_{n=0}^{b}n+4d(b+1)+(a+3d)\sum_{n=0}^{b}\left\lfloor\frac{b-n}{a}\right\rfloor.$$
أما الحد الأول فهو المجموع المثلثي المعروف:
$$\sum_{n=0}^{b}n=\frac{b(b+1)}{2}.$$
وبالنسبة لحد floor نضع \(m=b-n\)، فيسير \(m\) أيضًا من \(0\) إلى \(b\)، وبالتالي
$$\sum_{n=0}^{b}\left\lfloor\frac{b-n}{a}\right\rfloor=\sum_{m=0}^{b}\left\lfloor\frac{m}{a}\right\rfloor.$$
نكتب القسمة الإقليدية لـ \(b\) على \(a\) بالشكل
$$b=aq+r,\qquad 0 \le r \lt a.$$
وعندها تظهر قيم \(\left\lfloor\frac{m}{a}\right\rfloor\) على شكل كتل:
القيمة \(0\) تتكرر \(a\) مرة، والقيمة \(1\) تتكرر \(a\) مرة، وهكذا حتى \(q-1\) الذي يتكرر أيضًا \(a\) مرة، ثم القيمة الأخيرة \(q\) تتكرر \(r+1\) مرة.
إذن
$$\sum_{m=0}^{b}\left\lfloor\frac{m}{a}\right\rfloor=a\sum_{j=0}^{q-1}j+(r+1)q=\frac{aq(q-1)}{2}+(r+1)q.$$
وبالتعويض نحصل على الصيغة المغلقة الكاملة
$$\boxed{S(a,b,c)=\frac{b(b+1)}{2}+4d(b+1)+(a+3d)\left(\frac{aq(q-1)}{2}+(r+1)q\right),}$$
حيث \(d=a-c\)، و\(q=\left\lfloor\frac{b}{a}\right\rfloor\)، و\(r=b\bmod a\).
هذا هو مثال التحقق المستخدم داخل حل C++. هنا \(d=10\).
في الشريط الأعلى \(1951 \le n \le 2000\) نحصل على \(F(n)=n+40\).
وفي الشريط التالي \(1901 \le n \le 1950\) يكون رقم الشريط \(1\)، لذا
$$F(n)=n+40+80=n+120.$$
أما عند \(n=0\)، فإن
$$s(0)=\left\lfloor\frac{2000}{50}\right\rfloor=40,$$
ومن ثم
$$F(0)=0+40+80\cdot 40=3240.$$
وبالنسبة للمجموع الكلي، لدينا \(q=40\) و\(r=0\)، ولذلك
$$\sum_{m=0}^{2000}\left\lfloor\frac{m}{50}\right\rfloor=\frac{50\cdot 40\cdot 39}{2}+40=39040.$$
وعليه
$$S(50,2000,40)=\frac{2000\cdot 2001}{2}+40\cdot 2001+80\cdot 39040=5\,204\,240,$$
وهو تمامًا نفس الناتج الذي تؤكده المراجعة brute-force في البرنامج.
يحتوي تنفيذ C++ على دالتين مساعدتين أساسيتين. الدالة F_closed(n, a, b, c) تحسب الصيغة المغلقة لقيمة واحدة، بينما تحسب S_closed_mod_1e9(a, b, c) المجموع مباشرة modulo \(10^9\). ونفس الجبر مستخدم في نسختي Python وJava. كما يشغّل كود C++ مجموعة من اختبارات brute-force الصغيرة، ومنها \((50,2000,40)\)، للتأكد من أن الصيغة المشتقة تطابق العودية الأصلية.
ولأن الضربات الوسيطة قد تتجاوز مدى 64-بت، تستخدم نسخة C++ النوع __int128، وتستخدم Java النوع BigInteger لحد مجموع floor، بينما تعتمد Python على الأعداد الصحيحة ذات الدقة غير المحدودة.
بعد اشتقاق الصيغة المغلقة، يصبح حساب \(F(n)\) و\(S(a,b,c)\) بحاجة إلى عدد ثابت فقط من العمليات الحسابية: زمن \(O(1)\) وذاكرة إضافية \(O(1)\). أما الحساب العودي المباشر لكل القيم \(0 \le n \le b\) فهو غير عملي تمامًا على أحجام Project Euler.