Let \(M(n)\) denote the largest winning first move in the Stone Game III position with \(n\) stones, and define
$$S(N)=\sum_{n=1}^{N} M(n).$$
The Project Euler task asks for \(S(10^{18}) \bmod 10^8\). A direct scan of all positions up to \(10^{18}\) is impossible, so the local solution replaces per-position game search by a recurrence on Fibonacci intervals.
The C++ file contains a slow checker based on Zeckendorf representations. For a positive integer \(m\), let \(z(m)\) be the smallest Fibonacci term appearing in its Zeckendorf decomposition. The checker tests every move \(x\) with \(1 \le x \lt n\) and uses the characterization
$$2x \lt z(n-x).$$
Therefore the game-theoretic quantity implemented in all three language versions is
$$M(n)=\max\left\{x \in \{1,\dots,n-1\}: 2x \lt z(n-x)\right\}.$$
The optimized solver never evaluates this inequality for every \(n\). Instead, it exploits the block pattern that this rule creates when \(n\) is grouped by Fibonacci ranges.
Use the same Fibonacci indexing as the code:
$$F_0=1,\qquad F_1=1,\qquad F_{k+1}=F_k+F_{k-1}.$$
For each \(k\), define the interval
$$I_k=[F_k,\,F_{k+1}-1].$$
Its length is
$$|I_k|=F_{k+1}-F_k=F_{k-1}.$$
Now let \(A_k\) be the sequence of values \(M(n)\) on \(I_k\). Evaluating the slow definition on small intervals gives
$$A_5=(0,1,2,3,1),\qquad A_6=(0,1,2,3,4,5,6,2),$$
$$A_7=(0,1,\dots,10,3,1),\qquad A_8=(0,1,\dots,16,4,5,6,2).$$
This already shows the structure used by the fast solver: each Fibonacci interval starts with a long linear prefix, and the remaining tail is copied recursively from two intervals earlier.
Let \(P_k\) be the length of the initial linear prefix of \(A_k\). Then the first \(P_k\) values in interval \(I_k\) are exactly
$$0,1,2,\dots,P_k-1.$$
After that prefix comes a tail sequence \(B_k\). The base cases visible in the code are
$$B_5=(1),\qquad B_6=(2).$$
For \(k \ge 7\), the tail begins with the consecutive block
$$P_{k-3},\,P_{k-3}+1,\dots,P_{k-2}-1,$$
and after that block it continues with the old tail \(B_{k-2}\).
Comparing lengths gives a recurrence for \(P_k\). Since the full interval has length \(F_{k-1}\), the tail length is \(F_{k-1}-P_k\). On the other hand, the recursive description says that this tail length is
$$\left(P_{k-2}-P_{k-3}\right)+\left(F_{k-3}-P_{k-2}\right)=F_{k-3}-P_{k-3}.$$
Hence
$$F_{k-1}-P_k=F_{k-3}-P_{k-3},$$
so
$$P_k=F_{k-2}+P_{k-3}\qquad (k \ge 6).$$
The implementation uses the initial values
$$P_1=1,\qquad P_2=1,\qquad P_3=2,\qquad P_4=3,\qquad P_5=4.$$
Let \(T_k\) be the sum of the tail \(B_k\). From the recursive tail structure we get
$$T_5=1,\qquad T_6=2,$$
and for \(k \ge 7\),
$$T_k=T_{k-2}+\sum_{i=P_{k-3}}^{P_{k-2}-1} i.$$
Therefore the total contribution of the whole interval \(I_k\) is
$$U_k=\sum_{n=F_k}^{F_{k+1}-1} M(n)=\sum_{i=0}^{P_k-1} i + T_k=\frac{(P_k-1)P_k}{2}+T_k.$$
This is exactly the quantity stored in interval_sum[k] in the C++ code and in the corresponding arrays in Python and Java.
For a general limit \(N\), choose the unique \(k\) such that
$$F_k \le N \lt F_{k+1},$$
and write
$$j=N-F_k.$$
Then
$$S(N)=\sum_{r=1}^{k-1} U_r+\operatorname{Pref}_k(j),$$
where \(\operatorname{Pref}_k(j)\) is the sum of the first \(j+1\) entries of \(A_k\).
If \(j \lt P_k\), we are still inside the linear prefix, so
$$\operatorname{Pref}_k(j)=\sum_{i=0}^{j} i=\frac{j(j+1)}{2}.$$
If \(j \ge P_k\), we first take the whole linear prefix and then continue through the tail. Because the tail itself is built from a consecutive block plus the tail from interval \(k-2\), the prefix calculation descends by \(k \mapsto k-2\). That recursive evaluation is implemented by prefix_interval and prefix_tail.
The slow verifier in the C++ program checks this value explicitly. The complete intervals \(I_1\) through \(I_9=[55,88]\) contribute
$$U_1+\cdots+U_9=662.$$
Now \(100\) lies in \(I_{10}=[89,143]\), so \(j=100-89=11\). Because \(P_{10}=45\), this index is still inside the linear prefix of interval 10. Therefore
$$\operatorname{Pref}_{10}(11)=0+1+\cdots+11=\frac{11 \cdot 12}{2}=66.$$
Thus
$$S(100)=662+66=728,$$
matching the checkpoint used by the repository implementation.
The three solution files implement the same recurrence. They first generate Fibonacci numbers up to \(N\), then precompute the arrays prefix_len, tail_sum, interval_sum, and cumulative interval_prefix_sum. A query \(S(N)\) is answered by locating the last full interval below \(N\), adding the precomputed total before it, and evaluating the remaining partial interval recursively.
The language-specific differences are only numeric types: C++ uses unsigned __int128 for exact sums, Python relies on native big integers, and Java uses BigInteger. The C++ version also keeps the slow Zeckendorf-based verifier, checking \(S(100)=728\) and matching the optimized method against brute force for \(N=1000\).
There are only \(O(\log N)\) Fibonacci levels up to \(N\). Building all tables therefore costs \(O(\log N)\) time and \(O(\log N)\) memory. Answering one query \(S(N)\) also takes \(O(\log N)\) time, because interval lookup and the recursive tail descent both cross only logarithmically many Fibonacci blocks.
Sei \(M(n)\) der größte gewinnbringende erste Zug in einer Stone-Game-III-Position mit \(n\) Steinen. Gesucht ist
$$S(N)=\sum_{n=1}^{N} M(n).$$
Für das Euler-Problem muss \(S(10^{18}) \bmod 10^8\) berechnet werden. Eine direkte Untersuchung aller Positionen bis \(10^{18}\) ist unmöglich, daher ersetzt die lokale Lösung die Spielanalyse pro \(n\) durch eine Rekursion über Fibonacci-Intervalle.
Die C++-Datei enthält einen langsamen Prüfer auf Basis von Zeckendorf-Darstellungen. Für eine positive ganze Zahl \(m\) sei \(z(m)\) der kleinste Fibonacci-Term in ihrer Zeckendorf-Zerlegung. Der Prüfer testet jeden Zug \(x\) mit \(1 \le x \lt n\) und verwendet die Charakterisierung
$$2x \lt z(n-x).$$
Damit ist die in allen drei Sprachversionen implementierte Größe
$$M(n)=\max\left\{x \in \{1,\dots,n-1\}: 2x \lt z(n-x)\right\}.$$
Der schnelle Löser wertet diese Ungleichung nicht für jedes \(n\) einzeln aus, sondern nutzt das Blockmuster, das dadurch auf Fibonacci-Bereichen entsteht.
Verwendet wird dieselbe Fibonacci-Indizierung wie im Code:
$$F_0=1,\qquad F_1=1,\qquad F_{k+1}=F_k+F_{k-1}.$$
Für jedes \(k\) definieren wir
$$I_k=[F_k,\,F_{k+1}-1].$$
Die Länge dieses Intervalls ist
$$|I_k|=F_{k+1}-F_k=F_{k-1}.$$
Sei nun \(A_k\) die Folge der Werte \(M(n)\) auf \(I_k\). Die langsame Definition liefert auf kleinen Intervallen
$$A_5=(0,1,2,3,1),\qquad A_6=(0,1,2,3,4,5,6,2),$$
$$A_7=(0,1,\dots,10,3,1),\qquad A_8=(0,1,\dots,16,4,5,6,2).$$
Genau diese Struktur nutzt der schnelle Algorithmus: Jedes Fibonacci-Intervall beginnt mit einem langen linearen Präfix, und der Rest wird rekursiv aus dem zwei Intervalle früheren Block übernommen.
Sei \(P_k\) die Länge des linearen Anfangspräfixes von \(A_k\). Dann sind die ersten \(P_k\) Werte in \(I_k\) genau
$$0,1,2,\dots,P_k-1.$$
Danach folgt eine Schwanzfolge \(B_k\). Die im Code sichtbaren Basisfälle sind
$$B_5=(1),\qquad B_6=(2).$$
Für \(k \ge 7\) beginnt der Schwanz mit dem zusammenhängenden Block
$$P_{k-3},\,P_{k-3}+1,\dots,P_{k-2}-1,$$
und setzt sich danach mit dem alten Schwanz \(B_{k-2}\) fort.
Aus dem Längenvergleich folgt eine Rekursion für \(P_k\). Das ganze Intervall hat Länge \(F_{k-1}\), also besitzt der Schwanz Länge \(F_{k-1}-P_k\). Nach der rekursiven Beschreibung ist diese Länge aber
$$\left(P_{k-2}-P_{k-3}\right)+\left(F_{k-3}-P_{k-2}\right)=F_{k-3}-P_{k-3}.$$
Somit gilt
$$F_{k-1}-P_k=F_{k-3}-P_{k-3},$$
also
$$P_k=F_{k-2}+P_{k-3}\qquad (k \ge 6).$$
Die Implementierung startet mit
$$P_1=1,\qquad P_2=1,\qquad P_3=2,\qquad P_4=3,\qquad P_5=4.$$
Sei \(T_k\) die Summe des Schwanzes \(B_k\). Aus der Rekursionsstruktur folgt
$$T_5=1,\qquad T_6=2,$$
und für \(k \ge 7\),
$$T_k=T_{k-2}+\sum_{i=P_{k-3}}^{P_{k-2}-1} i.$$
Damit ist der Gesamtbeitrag des vollständigen Intervalls \(I_k\)
$$U_k=\sum_{n=F_k}^{F_{k+1}-1} M(n)=\sum_{i=0}^{P_k-1} i + T_k=\frac{(P_k-1)P_k}{2}+T_k.$$
Genau diese Größe steht im C++-Programm in interval_sum[k] und analog in den Python- und Java-Versionen.
Für eine allgemeine Grenze \(N\) wählen wir das eindeutige \(k\) mit
$$F_k \le N \lt F_{k+1},$$
und setzen
$$j=N-F_k.$$
Dann gilt
$$S(N)=\sum_{r=1}^{k-1} U_r+\operatorname{Pref}_k(j),$$
wobei \(\operatorname{Pref}_k(j)\) die Summe der ersten \(j+1\) Einträge von \(A_k\) bezeichnet.
Falls \(j \lt P_k\), befinden wir uns noch im linearen Präfix, also
$$\operatorname{Pref}_k(j)=\sum_{i=0}^{j} i=\frac{j(j+1)}{2}.$$
Falls \(j \ge P_k\), nimmt man zuerst das komplette lineare Präfix und läuft dann rekursiv durch den Schwanz. Da der Schwanz selbst aus einem zusammenhängenden Block plus dem Schwanz von Intervall \(k-2\) besteht, sinkt die Berechnung jeweils mit \(k \mapsto k-2\). Genau das implementieren prefix_interval und prefix_tail.
Der langsame Prüfer im C++-Programm kontrolliert diesen Wert explizit. Die vollständigen Intervalle \(I_1\) bis \(I_9=[55,88]\) liefern zusammen
$$U_1+\cdots+U_9=662.$$
Die Zahl \(100\) liegt in \(I_{10}=[89,143]\), also ist \(j=100-89=11\). Da \(P_{10}=45\), befindet sich dieser Index noch im linearen Präfix von Intervall 10. Deshalb ist
$$\operatorname{Pref}_{10}(11)=0+1+\cdots+11=\frac{11 \cdot 12}{2}=66.$$
Folglich
$$S(100)=662+66=728,$$
genau der Kontrollwert der Implementierung.
Die drei Lösungsdateien implementieren dieselbe Rekursion. Zuerst werden Fibonacci-Zahlen bis \(N\) erzeugt, danach die Felder prefix_len, tail_sum, interval_sum und das kumulative Feld interval_prefix_sum vorab berechnet. Eine Anfrage \(S(N)\) wird beantwortet, indem man das letzte vollständige Intervall unterhalb von \(N\) findet, den vorberechneten Gesamtbeitrag davor addiert und das verbleibende Teilintervall rekursiv auswertet.
Unterschiede zwischen den Sprachen gibt es nur bei den Zahlentypen: C++ verwendet unsigned __int128 für exakte Summen, Python nutzt eingebaute große Ganzzahlen und Java verwendet BigInteger. Zusätzlich enthält die C++-Version den langsamen Zeckendorf-Prüfer, der \(S(100)=728\) und die Übereinstimmung mit dem schnellen Verfahren für \(N=1000\) testet.
Bis zu \(N\) gibt es nur \(O(\log N)\) Fibonacci-Ebenen. Der Aufbau aller Tabellen kostet daher \(O(\log N)\) Zeit und \(O(\log N)\) Speicher. Auch eine einzelne Anfrage \(S(N)\) benötigt \(O(\log N)\) Zeit, weil sowohl die Intervallsuche als auch die Rekursion im Schwanz nur logarithmisch viele Fibonacci-Blöcke durchlaufen.
\(M(n)\), \(n\) taşlık Stone Game III konumunda ilk oyuncu için kazandıran en büyük ilk hamle olsun. İstenen toplam
$$S(N)=\sum_{n=1}^{N} M(n).$$
Euler probleminde amaç \(S(10^{18}) \bmod 10^8\) değerini bulmaktır. \(10^{18}\)'e kadar bütün konumları tek tek incelemek mümkün olmadığından, yerel çözüm her \(n\) için oyun araması yapmak yerine Fibonacci aralıkları üzerinde çalışan bir özyineleme kurar.
C++ dosyasında Zeckendorf gösterimine dayanan yavaş bir denetleyici vardır. Pozitif bir \(m\) için, \(z(m)\) onun Zeckendorf ayrışımında görünen en küçük Fibonacci terimi olsun. Denetleyici, \(1 \le x \lt n\) aralığındaki bütün hamleleri test eder ve şu karakterizasyonu kullanır:
$$2x \lt z(n-x).$$
Buna göre üç dilde de uygulanan oyun değeri
$$M(n)=\max\left\{x \in \{1,\dots,n-1\}: 2x \lt z(n-x)\right\}.$$
Hızlı çözücü bu eşitsizliği her \(n\) için ayrı ayrı hesaplamaz. Bunun yerine, bu kuralın Fibonacci aralıklarında oluşturduğu blok yapısını kullanır.
Koddakiyle aynı Fibonacci indislemesini kullanalım:
$$F_0=1,\qquad F_1=1,\qquad F_{k+1}=F_k+F_{k-1}.$$
Her \(k\) için
$$I_k=[F_k,\,F_{k+1}-1]$$
aralığını tanımlayalım. Bu aralığın uzunluğu
$$|I_k|=F_{k+1}-F_k=F_{k-1}$$
olur. Şimdi \(A_k\), \(I_k\) üzerindeki \(M(n)\) değerlerinin dizisi olsun. Yavaş tanımı küçük aralıklarda çalıştırınca
$$A_5=(0,1,2,3,1),\qquad A_6=(0,1,2,3,4,5,6,2),$$
$$A_7=(0,1,\dots,10,3,1),\qquad A_8=(0,1,\dots,16,4,5,6,2)$$
elde edilir. Bu, hızlı çözücünün kullandığı yapıyı açıkça gösterir: her Fibonacci aralığı uzun bir doğrusal önekle başlar, kalan kuyruk ise iki aralık önceki bloktan özyinelemeli olarak gelir.
\(P_k\), \(A_k\)'nın başındaki doğrusal önekin uzunluğu olsun. O zaman \(I_k\) aralığındaki ilk \(P_k\) değer tam olarak
$$0,1,2,\dots,P_k-1$$
şeklindedir. Bu önekten sonra bir kuyruk dizisi \(B_k\) gelir. Kodda görülen taban durumları
$$B_5=(1),\qquad B_6=(2)$$
şeklindedir. \(k \ge 7\) için kuyruk önce
$$P_{k-3},\,P_{k-3}+1,\dots,P_{k-2}-1$$
ardışık bloğu ile başlar, sonra da eski kuyruk \(B_{k-2}\) ile devam eder.
Uzunlukları karşılaştırınca \(P_k\) için özyineleme elde edilir. Tüm aralığın uzunluğu \(F_{k-1}\) olduğundan kuyruk uzunluğu \(F_{k-1}-P_k\)'dir. Öte yandan yukarıdaki açıklama bu uzunluğun
$$\left(P_{k-2}-P_{k-3}\right)+\left(F_{k-3}-P_{k-2}\right)=F_{k-3}-P_{k-3}$$
olduğunu söyler. Dolayısıyla
$$F_{k-1}-P_k=F_{k-3}-P_{k-3},$$
buradan da
$$P_k=F_{k-2}+P_{k-3}\qquad (k \ge 6)$$
çıkar. Uygulama şu başlangıç değerlerini kullanır:
$$P_1=1,\qquad P_2=1,\qquad P_3=2,\qquad P_4=3,\qquad P_5=4.$$
\(T_k\), kuyruk \(B_k\)'nın toplamı olsun. Kuyruk yapısından
$$T_5=1,\qquad T_6=2$$
ve \(k \ge 7\) için
$$T_k=T_{k-2}+\sum_{i=P_{k-3}}^{P_{k-2}-1} i$$
elde edilir. Bu nedenle tüm \(I_k\) aralığının katkısı
$$U_k=\sum_{n=F_k}^{F_{k+1}-1} M(n)=\sum_{i=0}^{P_k-1} i + T_k=\frac{(P_k-1)P_k}{2}+T_k$$
olur. C++ kodundaki interval_sum[k] tam olarak bu niceliği tutar; Python ve Java sürümlerinde de aynı mantık vardır.
Genel bir \(N\) için
$$F_k \le N \lt F_{k+1}$$
koşulunu sağlayan tek \(k\)'yı seçelim ve
$$j=N-F_k$$
yazalım. O zaman
$$S(N)=\sum_{r=1}^{k-1} U_r+\operatorname{Pref}_k(j)$$
olur. Burada \(\operatorname{Pref}_k(j)\), \(A_k\) dizisinin ilk \(j+1\) teriminin toplamıdır.
Eğer \(j \lt P_k\) ise hâlâ doğrusal öneğin içindeyiz ve
$$\operatorname{Pref}_k(j)=\sum_{i=0}^{j} i=\frac{j(j+1)}{2}$$
geçerlidir. Eğer \(j \ge P_k\) ise önce tüm doğrusal önek alınır, ardından kuyruk boyunca özyinelemeli olarak ilerlenir. Kuyruğun kendisi bir ardışık blok ve \(k-2\) aralığının kuyruğundan oluştuğu için hesap her adımda \(k \mapsto k-2\) şeklinde iner. Bunu kodda prefix_interval ve prefix_tail fonksiyonları yapar.
C++ programındaki yavaş doğrulayıcı bu değeri açıkça test eder. \(I_1\) ile \(I_9=[55,88]\) arasındaki tam aralıkların katkısı
$$U_1+\cdots+U_9=662$$
eder. \(100\) sayısı \(I_{10}=[89,143]\) aralığındadır; bu yüzden \(j=100-89=11\). Ayrıca \(P_{10}=45\) olduğundan bu indeks hâlâ doğrusal önek içindedir. Dolayısıyla
$$\operatorname{Pref}_{10}(11)=0+1+\cdots+11=\frac{11 \cdot 12}{2}=66.$$
Böylece
$$S(100)=662+66=728,$$
ve bu sonuç depo içindeki kontrol değeriyle tam olarak aynıdır.
Üç çözüm dosyası da aynı özyinelemeyi uygular. Önce \(N\)'ye kadar Fibonacci sayıları üretilir, sonra prefix_len, tail_sum, interval_sum ve kümülatif interval_prefix_sum dizileri önceden hesaplanır. Bir \(S(N)\) sorgusu, \(N\)'den önceki son tam aralığı bularak, ondan önceki hazır toplamı ekleyip son kısmi aralığı özyinelemeli biçimde değerlendirerek cevaplanır.
Diller arasındaki fark sadece sayısal türlerdedir: C++ tam toplamlar için unsigned __int128 kullanır, Python yerleşik büyük tamsayılara dayanır, Java ise BigInteger kullanır. C++ sürümünde ayrıca Zeckendorf tabanlı yavaş doğrulayıcı bulunur; bu doğrulayıcı \(S(100)=728\) değerini ve hızlı yöntemle kaba kuvvetin \(N=1000\) için eşleştiğini test eder.
\(N\)'ye kadar yalnızca \(O(\log N)\) tane Fibonacci seviyesi vardır. Bu yüzden bütün tabloların hazırlanması \(O(\log N)\) zaman ve \(O(\log N)\) bellek gerektirir. Tek bir \(S(N)\) sorgusu da \(O(\log N)\) zamanda biter; çünkü hem aralık bulma hem de kuyruk özyinelemesi yalnızca logaritmik sayıda Fibonacci bloğu gezer.
Sea \(M(n)\) la mayor primera jugada ganadora en una posición de Stone Game III con \(n\) piedras. Debemos calcular
$$S(N)=\sum_{n=1}^{N} M(n).$$
El problema de Euler pide \(S(10^{18}) \bmod 10^8\). Recorrer todas las posiciones hasta \(10^{18}\) es inviable, así que la solución local sustituye la búsqueda jugada por jugada por una recurrencia sobre intervalos de Fibonacci.
El archivo de C++ incluye un verificador lento basado en representaciones de Zeckendorf. Para un entero positivo \(m\), sea \(z(m)\) el menor término de Fibonacci que aparece en la descomposición de Zeckendorf de \(m\). El verificador prueba cada movimiento \(x\) con \(1 \le x \lt n\) y usa la caracterización
$$2x \lt z(n-x).$$
Por tanto, la cantidad implementada en las tres versiones del programa es
$$M(n)=\max\left\{x \in \{1,\dots,n-1\}: 2x \lt z(n-x)\right\}.$$
El solucionador rápido no evalúa esta desigualdad para cada \(n\). En su lugar, aprovecha el patrón por bloques que esta regla induce cuando agrupamos \(n\) por rangos de Fibonacci.
Usamos la misma indexación de Fibonacci que aparece en el código:
$$F_0=1,\qquad F_1=1,\qquad F_{k+1}=F_k+F_{k-1}.$$
Para cada \(k\), definimos
$$I_k=[F_k,\,F_{k+1}-1].$$
La longitud del intervalo es
$$|I_k|=F_{k+1}-F_k=F_{k-1}.$$
Sea \(A_k\) la secuencia de valores \(M(n)\) sobre \(I_k\). Si aplicamos la definición lenta a intervalos pequeños obtenemos
$$A_5=(0,1,2,3,1),\qquad A_6=(0,1,2,3,4,5,6,2),$$
$$A_7=(0,1,\dots,10,3,1),\qquad A_8=(0,1,\dots,16,4,5,6,2).$$
Aquí ya aparece la estructura usada por el algoritmo rápido: cada intervalo de Fibonacci comienza con un prefijo lineal largo, y la cola restante se copia recursivamente desde dos intervalos atrás.
Sea \(P_k\) la longitud del prefijo lineal inicial de \(A_k\). Entonces los primeros \(P_k\) valores del intervalo \(I_k\) son exactamente
$$0,1,2,\dots,P_k-1.$$
Después aparece una cola \(B_k\). Los casos base visibles en el código son
$$B_5=(1),\qquad B_6=(2).$$
Para \(k \ge 7\), la cola empieza con el bloque consecutivo
$$P_{k-3},\,P_{k-3}+1,\dots,P_{k-2}-1,$$
y luego continúa con la cola antigua \(B_{k-2}\).
Comparando longitudes obtenemos la recurrencia de \(P_k\). Como el intervalo completo tiene longitud \(F_{k-1}\), la cola mide \(F_{k-1}-P_k\). Por otra parte, la descripción recursiva dice que esa longitud es
$$\left(P_{k-2}-P_{k-3}\right)+\left(F_{k-3}-P_{k-2}\right)=F_{k-3}-P_{k-3}.$$
Por tanto,
$$F_{k-1}-P_k=F_{k-3}-P_{k-3},$$
y en consecuencia
$$P_k=F_{k-2}+P_{k-3}\qquad (k \ge 6).$$
La implementación usa los valores iniciales
$$P_1=1,\qquad P_2=1,\qquad P_3=2,\qquad P_4=3,\qquad P_5=4.$$
Sea \(T_k\) la suma de la cola \(B_k\). A partir de la estructura anterior se obtiene
$$T_5=1,\qquad T_6=2,$$
y para \(k \ge 7\),
$$T_k=T_{k-2}+\sum_{i=P_{k-3}}^{P_{k-2}-1} i.$$
Entonces la contribución total del intervalo completo \(I_k\) es
$$U_k=\sum_{n=F_k}^{F_{k+1}-1} M(n)=\sum_{i=0}^{P_k-1} i + T_k=\frac{(P_k-1)P_k}{2}+T_k.$$
Esta es exactamente la cantidad almacenada en interval_sum[k] en C++ y en las estructuras equivalentes de Python y Java.
Para un límite general \(N\), elegimos el único \(k\) tal que
$$F_k \le N \lt F_{k+1},$$
y escribimos
$$j=N-F_k.$$
Entonces
$$S(N)=\sum_{r=1}^{k-1} U_r+\operatorname{Pref}_k(j),$$
donde \(\operatorname{Pref}_k(j)\) es la suma de las primeras \(j+1\) entradas de \(A_k\).
Si \(j \lt P_k\), seguimos dentro del prefijo lineal y por tanto
$$\operatorname{Pref}_k(j)=\sum_{i=0}^{j} i=\frac{j(j+1)}{2}.$$
Si \(j \ge P_k\), primero tomamos el prefijo lineal completo y luego seguimos por la cola. Como la cola misma está formada por un bloque consecutivo seguido de la cola del intervalo \(k-2\), la evaluación desciende por la transición \(k \mapsto k-2\). Eso es exactamente lo que hacen prefix_interval y prefix_tail.
El verificador lento del programa en C++ comprueba este valor de forma explícita. Los intervalos completos \(I_1\) hasta \(I_9=[55,88]\) aportan
$$U_1+\cdots+U_9=662.$$
Como \(100\) pertenece a \(I_{10}=[89,143]\), tenemos \(j=100-89=11\). Además, \(P_{10}=45\), así que ese índice todavía cae dentro del prefijo lineal del intervalo 10. Por ello,
$$\operatorname{Pref}_{10}(11)=0+1+\cdots+11=\frac{11 \cdot 12}{2}=66.$$
En consecuencia,
$$S(100)=662+66=728,$$
que coincide con el checkpoint usado por la implementación.
Los tres archivos de solución implementan la misma recurrencia. Primero generan los números de Fibonacci hasta \(N\), luego rellenan las tablas prefix_len, tail_sum, interval_sum y la acumulada interval_prefix_sum. Una consulta \(S(N)\) se responde localizando el último intervalo completo por debajo de \(N\), sumando el total precalculado anterior y evaluando recursivamente el intervalo parcial restante.
Las diferencias entre lenguajes son solo de tipos numéricos: C++ usa unsigned __int128 para las sumas exactas, Python usa enteros grandes nativos y Java emplea BigInteger. La versión en C++ también conserva el verificador lento basado en Zeckendorf, que comprueba \(S(100)=728\) y la coincidencia con la versión rápida para \(N=1000\).
Hasta \(N\) solo existen \(O(\log N)\) niveles de Fibonacci. Por ello, la precomputación completa cuesta \(O(\log N)\) tiempo y \(O(\log N)\) memoria. Una consulta individual \(S(N)\) también requiere \(O(\log N)\), porque tanto la búsqueda del intervalo como el descenso recursivo por la cola atraviesan solo una cantidad logarítmica de bloques de Fibonacci.
设 \(M(n)\) 表示 Stone Game III 在 \(n\) 个石子的局面中，先手能够采取的最大必胜首步，要求计算
$$S(N)=\sum_{n=1}^{N} M(n).$$
本题最终需要的是 \(S(10^{18}) \bmod 10^8\)。如果从 \(1\) 到 \(10^{18}\) 逐个局面做博弈判断，计算量完全不可接受，所以仓库中的解法把逐点分析改写成 Fibonacci 区间上的递推。
C++ 文件里保留了一个基于 Zeckendorf 分解的慢速验证器。对正整数 \(m\)，记 \(z(m)\) 为它的 Zeckendorf 表示中最小的 Fibonacci 项。验证器枚举每个 \(1 \le x \lt n\) 的走法，并使用下面这个判据：
$$2x \lt z(n-x).$$
因此，三种语言版本真正实现的博弈量就是
$$M(n)=\max\left\{x \in \{1,\dots,n-1\}: 2x \lt z(n-x)\right\}.$$
快速算法并不会对每个 \(n\) 都重新检查这条不等式，而是利用这条规则在 Fibonacci 分块上诱导出的稳定结构。
这里采用与程序完全相同的 Fibonacci 编号方式：
$$F_0=1,\qquad F_1=1,\qquad F_{k+1}=F_k+F_{k-1}.$$
对每个 \(k\)，定义区间
$$I_k=[F_k,\,F_{k+1}-1].$$
它的长度为
$$|I_k|=F_{k+1}-F_k=F_{k-1}.$$
再令 \(A_k\) 表示区间 \(I_k\) 上的 \(M(n)\) 序列。把慢速定义实际跑在小范围上，可以得到
$$A_5=(0,1,2,3,1),\qquad A_6=(0,1,2,3,4,5,6,2),$$
$$A_7=(0,1,\dots,10,3,1),\qquad A_8=(0,1,\dots,16,4,5,6,2).$$
这正是快速程序所依赖的规律：每个 Fibonacci 区间先出现很长的线性前缀，后面的尾部则从前面两个区间之前的结构递归复制而来。
记 \(P_k\) 为 \(A_k\) 开头那段线性前缀的长度，那么区间 \(I_k\) 的前 \(P_k\) 个值恰好是
$$0,1,2,\dots,P_k-1.$$
在线性前缀之后还有一个尾序列 \(B_k\)。代码中的基例是
$$B_5=(1),\qquad B_6=(2).$$
当 \(k \ge 7\) 时，尾部先出现一个连续整数块
$$P_{k-3},\,P_{k-3}+1,\dots,P_{k-2}-1,$$
然后再接上旧的尾部 \(B_{k-2}\)。
对长度做比较，就能推出 \(P_k\) 的递推式。整个区间长度是 \(F_{k-1}\)，所以尾部长度为 \(F_{k-1}-P_k\)。另一方面，按上面的尾部结构，这个长度也等于
$$\left(P_{k-2}-P_{k-3}\right)+\left(F_{k-3}-P_{k-2}\right)=F_{k-3}-P_{k-3}.$$
因此有
$$F_{k-1}-P_k=F_{k-3}-P_{k-3},$$
从而得到
$$P_k=F_{k-2}+P_{k-3}\qquad (k \ge 6).$$
实现中使用的初值是
$$P_1=1,\qquad P_2=1,\qquad P_3=2,\qquad P_4=3,\qquad P_5=4.$$
记 \(T_k\) 为尾部 \(B_k\) 的元素和。由尾部递推可得
$$T_5=1,\qquad T_6=2,$$
并且当 \(k \ge 7\) 时，
$$T_k=T_{k-2}+\sum_{i=P_{k-3}}^{P_{k-2}-1} i.$$
于是完整区间 \(I_k\) 的总贡献为
$$U_k=\sum_{n=F_k}^{F_{k+1}-1} M(n)=\sum_{i=0}^{P_k-1} i + T_k=\frac{(P_k-1)P_k}{2}+T_k.$$
这正是程序里 interval_sum[k] 所保存的量，Python 和 Java 版本也完全对应这一公式。
对一般的上界 \(N\)，取满足
$$F_k \le N \lt F_{k+1}$$
的唯一 \(k\)，并记
$$j=N-F_k.$$
则有
$$S(N)=\sum_{r=1}^{k-1} U_r+\operatorname{Pref}_k(j),$$
其中 \(\operatorname{Pref}_k(j)\) 表示序列 \(A_k\) 的前 \(j+1\) 项之和。
如果 \(j \lt P_k\)，说明还处在线性前缀内部，因此
$$\operatorname{Pref}_k(j)=\sum_{i=0}^{j} i=\frac{j(j+1)}{2}.$$
如果 \(j \ge P_k\)，就先取完整的线性前缀，再在尾部中递归向下计算。由于尾部本身又是“一个连续块 + 两级之前的尾部”，所以这个前缀求和会沿着 \(k \mapsto k-2\) 继续下降。这正是 prefix_interval 与 prefix_tail 的职责。
C++ 里的慢速验证器显式检查了这个值。完整区间 \(I_1\) 到 \(I_9=[55,88]\) 的贡献和为
$$U_1+\cdots+U_9=662.$$
而 \(100\) 落在 \(I_{10}=[89,143]\) 中，所以 \(j=100-89=11\)。又因为 \(P_{10}=45\)，这个位置仍在线性前缀内，于是
$$\operatorname{Pref}_{10}(11)=0+1+\cdots+11=\frac{11 \cdot 12}{2}=66.$$
因此
$$S(100)=662+66=728,$$
与仓库实现中的 checkpoint 完全一致。
三个解法文件实现的是同一套递推。它们先生成不超过 \(N\) 的 Fibonacci 数，再预计算 prefix_len、tail_sum、interval_sum 和累加数组 interval_prefix_sum。计算 \(S(N)\) 时，先找到 \(N\) 所在的最后一个区间之前的完整总和，再递归处理最后一个不完整区间。
不同语言之间主要只差数值类型：C++ 用 unsigned __int128 保存精确和，Python 直接使用原生大整数，Java 则使用 BigInteger。此外，C++ 版本还保留了基于 Zeckendorf 的慢速校验器，用来验证 \(S(100)=728\)，并检查快速方法与暴力方法在 \(N=1000\) 时完全一致。
到 \(N\) 为止只会有 \(O(\log N)\) 层 Fibonacci 区间，因此预处理时间是 \(O(\log N)\)，空间也是 \(O(\log N)\)。单次查询 \(S(N)\) 同样只需要 \(O(\log N)\) 时间，因为无论是定位区间还是沿尾部递归下降，都只会经过对数级数量的 Fibonacci 块。
Пусть \(M(n)\) обозначает наибольший выигрышный первый ход в позиции Stone Game III с \(n\) камнями. Требуется вычислить
$$S(N)=\sum_{n=1}^{N} M(n).$$
В задаче Project Euler нужно найти \(S(10^{18}) \bmod 10^8\). Перебирать все позиции до \(10^{18}\) невозможно, поэтому локальное решение заменяет покомпонентный анализ игры рекурсией по интервалам Фибоначчи.
В C++-файле есть медленный проверяющий алгоритм, основанный на разложении Цекендорфа. Для положительного числа \(m\) обозначим через \(z(m)\) наименьший член Фибоначчи, входящий в его представление Цекендорфа. Проверка перебирает все ходы \(x\) с \(1 \le x \lt n\) и использует критерий
$$2x \lt z(n-x).$$
Следовательно, величина, которую реализуют все три версии программы, равна
$$M(n)=\max\left\{x \in \{1,\dots,n-1\}: 2x \lt z(n-x)\right\}.$$
Быстрый алгоритм не вычисляет это неравенство для каждого \(n\) отдельно. Вместо этого он использует блоковую структуру, которую данное правило порождает на фибоначчиевых интервалах.
Используется та же индексация Фибоначчи, что и в коде:
$$F_0=1,\qquad F_1=1,\qquad F_{k+1}=F_k+F_{k-1}.$$
Для каждого \(k\) определим интервал
$$I_k=[F_k,\,F_{k+1}-1].$$
Его длина равна
$$|I_k|=F_{k+1}-F_k=F_{k-1}.$$
Пусть \(A_k\) обозначает последовательность значений \(M(n)\) на интервале \(I_k\). Если применить медленное определение на малых диапазонах, получаем
$$A_5=(0,1,2,3,1),\qquad A_6=(0,1,2,3,4,5,6,2),$$
$$A_7=(0,1,\dots,10,3,1),\qquad A_8=(0,1,\dots,16,4,5,6,2).$$
Именно эта картина и зашита в быстрый метод: каждый интервал Фибоначчи начинается длинным линейным префиксом, а оставшийся хвост рекурсивно копируется из интервала на два шага раньше.
Обозначим через \(P_k\) длину начального линейного префикса в \(A_k\). Тогда первые \(P_k\) значений на интервале \(I_k\) равны
$$0,1,2,\dots,P_k-1.$$
После этого идет хвостовая последовательность \(B_k\). Базовые случаи, видимые в коде, таковы:
$$B_5=(1),\qquad B_6=(2).$$
Для \(k \ge 7\) хвост начинается с непрерывного блока
$$P_{k-3},\,P_{k-3}+1,\dots,P_{k-2}-1,$$
а затем продолжается старым хвостом \(B_{k-2}\).
Сравнение длин дает рекурсию для \(P_k\). Полный интервал имеет длину \(F_{k-1}\), значит длина хвоста равна \(F_{k-1}-P_k\). С другой стороны, по рекурсивному описанию эта длина равна
$$\left(P_{k-2}-P_{k-3}\right)+\left(F_{k-3}-P_{k-2}\right)=F_{k-3}-P_{k-3}.$$
Отсюда
$$F_{k-1}-P_k=F_{k-3}-P_{k-3},$$
и, следовательно,
$$P_k=F_{k-2}+P_{k-3}\qquad (k \ge 6).$$
В реализации используются начальные значения
$$P_1=1,\qquad P_2=1,\qquad P_3=2,\qquad P_4=3,\qquad P_5=4.$$
Пусть \(T_k\) обозначает сумму элементов хвоста \(B_k\). Тогда из его структуры следует
$$T_5=1,\qquad T_6=2,$$
а для \(k \ge 7\),
$$T_k=T_{k-2}+\sum_{i=P_{k-3}}^{P_{k-2}-1} i.$$
Следовательно, вклад полного интервала \(I_k\) равен
$$U_k=\sum_{n=F_k}^{F_{k+1}-1} M(n)=\sum_{i=0}^{P_k-1} i + T_k=\frac{(P_k-1)P_k}{2}+T_k.$$
Именно эта величина сохраняется в interval_sum[k] в C++ и в эквивалентных массивах Python и Java.
Для общего ограничения \(N\) выберем единственное \(k\), для которого
$$F_k \le N \lt F_{k+1},$$
и положим
$$j=N-F_k.$$
Тогда
$$S(N)=\sum_{r=1}^{k-1} U_r+\operatorname{Pref}_k(j),$$
где \(\operatorname{Pref}_k(j)\) означает сумму первых \(j+1\) членов последовательности \(A_k\).
Если \(j \lt P_k\), мы еще находимся в линейном префиксе, поэтому
$$\operatorname{Pref}_k(j)=\sum_{i=0}^{j} i=\frac{j(j+1)}{2}.$$
Если \(j \ge P_k\), сначала берется весь линейный префикс, а затем вычисление рекурсивно спускается по хвосту. Поскольку хвост сам состоит из непрерывного блока и хвоста интервала \(k-2\), рекурсия идет по правилу \(k \mapsto k-2\). Именно это делают функции prefix_interval и prefix_tail.
Медленный проверяющий код в C++ явно проверяет это значение. Полные интервалы от \(I_1\) до \(I_9=[55,88]\) дают вклад
$$U_1+\cdots+U_9=662.$$
Число \(100\) лежит в интервале \(I_{10}=[89,143]\), поэтому \(j=100-89=11\). Так как \(P_{10}=45\), этот индекс все еще находится внутри линейного префикса интервала 10. Следовательно,
$$\operatorname{Pref}_{10}(11)=0+1+\cdots+11=\frac{11 \cdot 12}{2}=66.$$
Значит,
$$S(100)=662+66=728,$$
что полностью совпадает с контрольной проверкой в репозитории.
Все три файла решения реализуют одну и ту же рекуррентную схему. Сначала генерируются числа Фибоначчи до \(N\), затем предварительно вычисляются массивы prefix_len, tail_sum, interval_sum и накопительный массив interval_prefix_sum. Для запроса \(S(N)\) программа находит последний полный интервал ниже \(N\), добавляет заранее посчитанную сумму до него и рекурсивно обрабатывает оставшуюся часть последнего интервала.
Различия между языками касаются только типов чисел: C++ использует unsigned __int128 для точных сумм, Python опирается на встроенные длинные целые, а Java использует BigInteger. Кроме того, в версии C++ сохранен медленный проверяющий код на основе разложения Цекендорфа: он проверяет \(S(100)=728\) и совпадение быстрого метода с перебором при \(N=1000\).
До числа \(N\) существует только \(O(\log N)\) уровней Фибоначчи. Поэтому построение всех таблиц требует \(O(\log N)\) времени и \(O(\log N)\) памяти. Один запрос \(S(N)\) также выполняется за \(O(\log N)\), потому что и поиск интервала, и рекурсивный спуск по хвосту проходят лишь через логарифмическое число фибоначчиевых блоков.
لنرمز بـ \(M(n)\) إلى أكبر حركة افتتاحية رابحة في وضع Stone Game III الذي يحتوي على \(n\) حجرًا. المطلوب هو حساب
$$S(N)=\sum_{n=1}^{N} M(n).$$
في مسألة Project Euler نريد القيمة \(S(10^{18}) \bmod 10^8\). من الواضح أن فحص جميع الأوضاع حتى \(10^{18}\) واحدًا واحدًا غير ممكن، لذلك تستبدل الحلول المحلية تحليل كل وضع على حدة بعلاقة تكرارية على مقاطع فيبوناتشي.
ملف C++ يحتوي على متحقق بطيء يعتمد على تمثيلات Zeckendorf. لكل عدد صحيح موجب \(m\)، نرمز بـ \(z(m)\) إلى أصغر حد فيبوناتشي يظهر في تمثيل Zeckendorf الخاص به. هذا المتحقق يجرّب كل حركة \(x\) حيث \(1 \le x \lt n\)، ويستخدم التوصيف التالي:
$$2x \lt z(n-x).$$
إذن الكمية التي تطبقها النسخ الثلاث من البرنامج هي
$$M(n)=\max\left\{x \in \{1,\dots,n-1\}: 2x \lt z(n-x)\right\}.$$
الحل السريع لا يعيد اختبار هذه المتباينة لكل \(n\)، بل يستفيد من النمط الكتلي الذي تولده عندما نجمع القيم داخل مجالات فيبوناتشي.
نستخدم نفس فهرسة فيبوناتشي الموجودة في الكود:
$$F_0=1,\qquad F_1=1,\qquad F_{k+1}=F_k+F_{k-1}.$$
ولكل \(k\) نعرّف المقطع
$$I_k=[F_k,\,F_{k+1}-1].$$
طول هذا المقطع يساوي
$$|I_k|=F_{k+1}-F_k=F_{k-1}.$$
ولنرمز بـ \(A_k\) إلى متتالية قيم \(M(n)\) على المقطع \(I_k\). عند تشغيل التعريف البطيء على مجالات صغيرة نحصل على
$$A_5=(0,1,2,3,1),\qquad A_6=(0,1,2,3,4,5,6,2),$$
$$A_7=(0,1,\dots,10,3,1),\qquad A_8=(0,1,\dots,16,4,5,6,2).$$
وهذا يوضح البنية التي يعتمد عليها الحل السريع: كل مقطع فيبوناتشي يبدأ ببادئة خطية طويلة، ثم يأتي ذيل يتم نسخه تكراريًا من مقطع أقدم بمقدار درجتين.
لنرمز بـ \(P_k\) إلى طول البادئة الخطية الأولى في \(A_k\). إذًا أول \(P_k\) قيم في المقطع \(I_k\) هي بالضبط
$$0,1,2,\dots,P_k-1.$$
بعد ذلك يظهر ذيل نسميه \(B_k\). حالتا الأساس الظاهرتان في الكود هما
$$B_5=(1),\qquad B_6=(2).$$
وعندما \(k \ge 7\) يبدأ الذيل بالكتلة المتتالية
$$P_{k-3},\,P_{k-3}+1,\dots,P_{k-2}-1,$$
ثم يتابع بذيل المقطع \(B_{k-2}\).
ومن مقارنة الأطوال نستنتج علاقة \(P_k\). فطول المقطع الكامل هو \(F_{k-1}\)، وبالتالي طول الذيل يساوي \(F_{k-1}-P_k\). لكن الوصف التكراري للذيل يقول إن هذا الطول يساوي
$$\left(P_{k-2}-P_{k-3}\right)+\left(F_{k-3}-P_{k-2}\right)=F_{k-3}-P_{k-3}.$$
إذن
$$F_{k-1}-P_k=F_{k-3}-P_{k-3},$$
ومنها نحصل على
$$P_k=F_{k-2}+P_{k-3}\qquad (k \ge 6).$$
وتستخدم الشيفرة القيم الابتدائية التالية:
$$P_1=1,\qquad P_2=1,\qquad P_3=2,\qquad P_4=3,\qquad P_5=4.$$
لنرمز بـ \(T_k\) إلى مجموع عناصر الذيل \(B_k\). ومن بنية الذيل نحصل على
$$T_5=1,\qquad T_6=2,$$
ولكل \(k \ge 7\)،
$$T_k=T_{k-2}+\sum_{i=P_{k-3}}^{P_{k-2}-1} i.$$
وبالتالي فإن مساهمة المقطع الكامل \(I_k\) هي
$$U_k=\sum_{n=F_k}^{F_{k+1}-1} M(n)=\sum_{i=0}^{P_k-1} i + T_k=\frac{(P_k-1)P_k}{2}+T_k.$$
وهذه هي بالضبط الكمية المخزنة في interval_sum[k] في نسخة C++، وبالمعنى نفسه في نسختي Python و Java.
لأي حد عام \(N\)، نختار \(k\) الوحيد الذي يحقق
$$F_k \le N \lt F_{k+1},$$
ثم نكتب
$$j=N-F_k.$$
عندئذٍ
$$S(N)=\sum_{r=1}^{k-1} U_r+\operatorname{Pref}_k(j),$$
حيث تمثل \(\operatorname{Pref}_k(j)\) مجموع أول \(j+1\) عنصرًا من المتتالية \(A_k\).
إذا كان \(j \lt P_k\)، فنحن ما زلنا داخل البادئة الخطية، ولذلك
$$\operatorname{Pref}_k(j)=\sum_{i=0}^{j} i=\frac{j(j+1)}{2}.$$
أما إذا كان \(j \ge P_k\)، فنأخذ أولًا البادئة الخطية كاملة ثم نكمل داخل الذيل بطريقة تكرارية. وبما أن الذيل نفسه مكوّن من كتلة متتالية يتبعها ذيل المقطع \(k-2\)، فإن الحساب يهبط وفق الانتقال \(k \mapsto k-2\). وهذا هو الدور الدقيق للدالتين prefix_interval و prefix_tail.
المتحقق البطيء في برنامج C++ يفحص هذه القيمة صراحة. فالمقاطع الكاملة من \(I_1\) حتى \(I_9=[55,88]\) تعطي
$$U_1+\cdots+U_9=662.$$
والعدد \(100\) يقع داخل \(I_{10}=[89,143]\)، لذلك \(j=100-89=11\). وبما أن \(P_{10}=45\)، فهذا الموضع ما زال داخل البادئة الخطية للمقطع العاشر. لذا
$$\operatorname{Pref}_{10}(11)=0+1+\cdots+11=\frac{11 \cdot 12}{2}=66.$$
ومن ثم
$$S(100)=662+66=728,$$
وهو نفس مقدار التحقق الموجود في هذا المستودع.
الملفات الثلاثة تطبق العلاقة نفسها. في البداية تُولَّد أعداد فيبوناتشي حتى \(N\)، ثم تُحسب مسبقًا المصفوفات prefix_len و tail_sum و interval_sum والمجموع التراكمي interval_prefix_sum. وعند طلب \(S(N)\)، تحدد الشيفرة آخر مقطع كامل قبل \(N\)، وتضيف المجموع المحسوب مسبقًا قبله، ثم تعالج الجزء الجزئي من المقطع الأخير بشكل تكراري.
الاختلاف بين اللغات يقتصر على نوع الأعداد: C++ يستخدم unsigned __int128 للمجاميع الدقيقة، وPython يعتمد على الأعداد الصحيحة الكبيرة المدمجة، وJava يستخدم BigInteger. كما أن نسخة C++ تحتفظ بالمتحقق البطيء المعتمد على Zeckendorf، والذي يفحص \(S(100)=728\) ويقارن الطريقة السريعة بالقوة الغاشمة عند \(N=1000\).
حتى الحد \(N\) لا يوجد إلا \(O(\log N)\) من مستويات فيبوناتشي. لذلك فإن بناء جميع الجداول يحتاج إلى \(O(\log N)\) زمنًا و\(O(\log N)\) ذاكرة. وكذلك فإن استعلامًا واحدًا من النوع \(S(N)\) يُجاب عنه في \(O(\log N)\)، لأن كلًا من البحث عن المقطع والنزول التكراري داخل الذيل يمران عبر عدد لوغاريتمي فقط من كتل فيبوناتشي.