Let \(z(n)\) be the number of Fibonacci terms used in the Zeckendorf representation of \(n\). The solver computes the prefix sum
$$S(N)=\sum_{0 \le n < N} z(n),$$
with \(z(0)=0\), and the Project Euler target is \(S(10^{17})\).
The code uses the shifted Fibonacci basis
$$F_1=1,\qquad F_2=2,\qquad F_{k+2}=F_{k+1}+F_k,$$
so the sequence is \(1,2,3,5,8,\dots\). Zeckendorf's theorem says that every positive integer has a unique expansion
$$n = F_{i_1}+F_{i_2}+\cdots+F_{i_t}, \qquad i_{j+1}\ge i_j+2,$$
meaning that no two consecutive Fibonacci numbers are used. The quantity \(z(n)\) is exactly the number \(t\) of summands in that unique expansion.
Fix \(k\ge 2\). Because
$$F_{k+1}=F_k+F_{k-1},$$
every integer in the half-open interval \([F_k,F_{k+1})\) can be written uniquely as
$$n = F_k + r,\qquad 0 \le r < F_{k-1}.$$
Now \(r < F_{k-1}\), so the Zeckendorf representation of \(r\) cannot contain \(F_{k-1}\). Therefore adding \(F_k\) creates no adjacency conflict, and we get the exact identity
$$z(F_k+r)=1+z(r).$$
This is the key bijection behind the whole solution: the block \([F_k,F_{k+1})\) is just the smaller block \([0,F_{k-1})\) with one extra leading term \(F_k\).
Define
$$A_k = S(F_k).$$
Summing the previous identity over all \(r\in[0,F_{k-1})\) gives
$$A_{k+1}-A_k = \sum_{r=0}^{F_{k-1}-1}(1+z(r)) = F_{k-1}+A_{k-1}.$$
So the boundary values satisfy
$$A_{k+1}=A_k+F_{k-1}+A_{k-1}.$$
The first values are
$$A_1=0,\quad A_2=1,\quad A_3=2,\quad A_4=5,\quad A_5=10,\quad A_6=20.$$
For example, \([8,13)=\{8,9,10,11,12\}\) has Zeckendorf term counts
$$1,2,2,2,3,$$
whose sum is \(10\). Since \(A_5=S(8)=10\), we obtain \(A_6=S(13)=20\).
Let \(p\) be the largest Fibonacci number strictly smaller than \(N\), say \(p=F_k\). Then \(N \le F_{k+1}\), hence
$$0 \le N-p \le F_{k-1}.$$
So the same block argument works on the truncated interval \([p,N)\): for every \(0\le r < N-p\),
$$z(p+r)=1+z(r).$$
Summing over \([0,N)\) gives
$$S(N)=S(p)+(N-p)+S(N-p).$$
This is exactly the formula implemented in S(n). The binary search only exists to find that largest \(p\).
The largest Fibonacci below \(10\) is \(p=8\). Therefore
$$S(10)=S(8)+(10-8)+S(2)=10+2+1=13.$$
Direct inspection confirms it. The numbers \(8\) and \(9\) have Zeckendorf term counts \(1\) and \(2\), so the extra contribution beyond \(S(8)\) is \(3\), exactly as the formula predicts.
Every recursive step replaces \(N\) by the pair \((p,N-p)\), where both values are smaller and lie on lower Fibonacci scales. In fact the arguments that ever appear are exactly the suffix remainders in the greedy Zeckendorf decomposition of the original \(N\). Since Fibonacci numbers grow exponentially, the number of relevant scales is only \(O(\log N)\), so memoization is enough to make the recursion extremely small.
The C++ implementation verifies the checkpoint
$$S(10^6)=7894453.$$
Useful smaller values are
$$S(5)=5,\qquad S(8)=10,\qquad S(13)=20,\qquad S(100)=261.$$
These checkpoints test both Fibonacci-boundary values and non-boundary values, so they validate the recurrence rather well.
The solver first precomputes the Fibonacci list up to \(10^{18}\), which safely covers the target \(10^{17}\). For each query \(N\), it finds the largest \(p<N\), applies
$$S(N)=S(p)+(N-p)+S(N-p),$$
stores the result in a hash map, and returns it. The wrapper solve(limit) only clears the memo table and starts this recursion.
If \(F_k \le N < F_{k+1}\), then the recursion depth is at most \(k\), and with memoization the number of distinct states is also \(O(k)\). Because \(F_k\) grows exponentially, \(k=O(\log N)\). Thus both time and memory are \(O(\log N)\).
Sei \(z(n)\) die Anzahl der Fibonacci-Summanden in der Zeckendorf-Darstellung von \(n\). Das Programm berechnet die Präfixsumme
$$S(N)=\sum_{0 \le n < N} z(n),$$
wobei \(z(0)=0\) gesetzt wird. Das Ziel der Aufgabe ist \(S(10^{17})\).
Verwendet wird die verschobene Fibonacci-Basis
$$F_1=1,\qquad F_2=2,\qquad F_{k+2}=F_{k+1}+F_k,$$
also \(1,2,3,5,8,\dots\). Nach dem Satz von Zeckendorf besitzt jede positive Zahl eine eindeutige Darstellung
$$n = F_{i_1}+F_{i_2}+\cdots+F_{i_t}, \qquad i_{j+1}\ge i_j+2,$$
bei der niemals zwei benachbarte Fibonacci-Zahlen zugleich auftreten. Die Zahl \(z(n)\) ist genau die Anzahl \(t\) dieser Summanden.
Fixiere \(k\ge 2\). Wegen
$$F_{k+1}=F_k+F_{k-1}$$
lässt sich jede Zahl im halboffenen Intervall \([F_k,F_{k+1})\) eindeutig als
$$n = F_k + r,\qquad 0 \le r < F_{k-1}$$
schreiben. Weil \(r < F_{k-1}\), kann die Zeckendorf-Darstellung von \(r\) den Summanden \(F_{k-1}\) nicht enthalten. Daher erzeugt das Hinzufügen von \(F_k\) keinen Konflikt mit benachbarten Fibonacci-Zahlen, und es gilt exakt
$$z(F_k+r)=1+z(r).$$
Genau diese Bijektion treibt die gesamte Lösung: Der Block \([F_k,F_{k+1})\) ist dasselbe wie \([0,F_{k-1})\), nur mit einem zusätzlichen führenden Summanden \(F_k\).
Setze
$$A_k = S(F_k).$$
Summiert man die vorige Identität über alle \(r\in[0,F_{k-1})\), erhält man
$$A_{k+1}-A_k = \sum_{r=0}^{F_{k-1}-1}(1+z(r)) = F_{k-1}+A_{k-1}.$$
Also erfüllen die Randwerte die Rekursion
$$A_{k+1}=A_k+F_{k-1}+A_{k-1}.$$
Die ersten Werte sind
$$A_1=0,\quad A_2=1,\quad A_3=2,\quad A_4=5,\quad A_5=10,\quad A_6=20.$$
Zum Beispiel hat \([8,13)=\{8,9,10,11,12\}\) die Anzahlen
$$1,2,2,2,3,$$
deren Summe \(10\) ergibt. Weil \(A_5=S(8)=10\), folgt \(A_6=S(13)=20\).
Sei \(p\) die größte Fibonacci-Zahl mit \(p<N\), also \(p=F_k\). Dann gilt \(N \le F_{k+1}\) und damit
$$0 \le N-p \le F_{k-1}.$$
Darum funktioniert das gleiche Blockargument auch auf dem abgeschnittenen Intervall \([p,N)\): Für jedes \(0\le r < N-p\) gilt
$$z(p+r)=1+z(r).$$
Nach Summation folgt
$$S(N)=S(p)+(N-p)+S(N-p).$$
Genau diese Formel steht in S(n). Die binäre Suche dient nur dazu, das passende größte \(p\) zu finden.
Die größte Fibonacci-Zahl unter \(10\) ist \(p=8\). Also
$$S(10)=S(8)+(10-8)+S(2)=10+2+1=13.$$
Direkte Kontrolle: Die Zahlen \(8\) und \(9\) haben \(1\) bzw. \(2\) Summanden in ihrer Zeckendorf-Darstellung. Der Zusatzbeitrag gegenüber \(S(8)\) ist also \(3\), genau wie vorhergesagt.
Jeder Rekursionsschritt ersetzt \(N\) durch \((p,N-p)\), wobei beide Werte kleiner sind und auf niedrigeren Fibonacci-Skalen liegen. Tatsächlich treten nur die Suffix-Reste der gierigen Zeckendorf-Zerlegung von \(N\) auf. Da Fibonacci-Zahlen exponentiell wachsen, gibt es nur \(O(\log N)\) relevante Skalen. Deshalb reicht eine kleine Memo-Tabelle völlig aus.
Die C++-Implementierung prüft den Kontrollwert
$$S(10^6)=7894453.$$
Nützliche kleinere Werte sind
$$S(5)=5,\qquad S(8)=10,\qquad S(13)=20,\qquad S(100)=261.$$
Diese Tests decken sowohl Fibonacci-Grenzen als auch allgemeine Grenzen ab und bestätigen daher die Rekursion sehr gut.
Zuerst wird die Fibonacci-Liste bis \(10^{18}\) vorab berechnet; das deckt das Ziel \(10^{17}\) sicher ab. Für eine Anfrage \(N\) sucht der Code das größte \(p<N\), wendet
$$S(N)=S(p)+(N-p)+S(N-p)$$
an, speichert das Ergebnis in einer Hash-Map und gibt es zurück. Die Hülle solve(limit) leert nur die Memo-Tabelle und startet diese Rekursion.
Gilt \(F_k \le N < F_{k+1}\), dann ist die Rekursionstiefe höchstens \(k\), und mit Memoisierung ist auch die Zahl der verschiedenen Zustände \(O(k)\). Wegen des exponentiellen Wachstums der Fibonacci-Zahlen ist \(k=O(\log N)\). Laufzeit und Speicher liegen also beide in \(O(\log N)\).
\(z(n)\), \(n\) sayısının Zeckendorf gösteriminde kullanılan Fibonacci terimlerinin sayısı olsun. Kod şu önek toplamı hesaplıyor:
$$S(N)=\sum_{0 \le n < N} z(n),$$
burada \(z(0)=0\) kabul edilir. Project Euler hedefi de \(S(10^{17})\) değeridir.
Kod şu kaydırılmış Fibonacci tabanını kullanır:
$$F_1=1,\qquad F_2=2,\qquad F_{k+2}=F_{k+1}+F_k,$$
yani dizi \(1,2,3,5,8,\dots\) olur. Zeckendorf teoremi, her pozitif tam sayının
$$n = F_{i_1}+F_{i_2}+\cdots+F_{i_t}, \qquad i_{j+1}\ge i_j+2$$
şeklinde, ardışık iki Fibonacci kullanılmadan tekil biçimde yazılabildiğini söyler. \(z(n)\) tam olarak bu gösterimdeki terim sayısı \(t\)'dir.
\(k\ge 2\) için
$$F_{k+1}=F_k+F_{k-1}$$
olduğundan \([F_k,F_{k+1})\) aralığındaki her sayı tekil olarak
$$n = F_k + r,\qquad 0 \le r < F_{k-1}$$
biçiminde yazılır. Şimdi \(r < F_{k-1}\) olduğundan, \(r\)'nin Zeckendorf gösterimi \(F_{k-1}\) terimini içeremez. Bu yüzden başa \(F_k\) eklemek ardışıklık ihlali yaratmaz ve tam olarak
$$z(F_k+r)=1+z(r)$$
eşitliği elde edilir. Çözümün özü budur: \([F_k,F_{k+1})\) bloğu, \([0,F_{k-1})\) bloğunun başına bir tane ek \(F_k\) takılmış halidir.
$$A_k = S(F_k)$$
tanımını yapalım. Bir önceki özdeşliği tüm \(r\in[0,F_{k-1})\) üzerinde toplarsak
$$A_{k+1}-A_k = \sum_{r=0}^{F_{k-1}-1}(1+z(r)) = F_{k-1}+A_{k-1}$$
çıkar. Yani sınır değerleri
$$A_{k+1}=A_k+F_{k-1}+A_{k-1}$$
yinelemesine uyar. İlk birkaç değer
$$A_1=0,\quad A_2=1,\quad A_3=2,\quad A_4=5,\quad A_5=10,\quad A_6=20$$
şeklindedir. Örneğin \([8,13)=\{8,9,10,11,12\}\) aralığındaki Zeckendorf terim sayıları
$$1,2,2,2,3$$
olur ve toplamları \(10\)'dur. \(A_5=S(8)=10\) olduğundan \(A_6=S(13)=20\) bulunur.
\(N\)'den küçük en büyük Fibonacci sayısı \(p\) olsun; yani \(p=F_k\). O zaman \(N \le F_{k+1}\) olduğundan
$$0 \le N-p \le F_{k-1}$$
elde edilir. Böylece aynı blok mantığı kesilmiş \([p,N)\) aralığında da geçerlidir: her \(0\le r < N-p\) için
$$z(p+r)=1+z(r).$$
Toplayınca
$$S(N)=S(p)+(N-p)+S(N-p)$$
çıkar. Kodun S(n) fonksiyonu tam olarak bunu uygular; ikili arama sadece doğru \(p\)'yi bulmak içindir.
\(10\)'dan küçük en büyük Fibonacci sayısı \(p=8\)'dir. Bu yüzden
$$S(10)=S(8)+(10-8)+S(2)=10+2+1=13.$$
Doğrudan bakarsak \(8\) ve \(9\) sayılarının Zeckendorf terim sayıları sırasıyla \(1\) ve \(2\)'dir. Yani \(S(8)\)'in üstüne gelen ek katkı gerçekten \(3\) olur.
Her özyineleme adımı \(N\)'yi \((p,N-p)\) çiftine indirger; bu iki sayı da daha küçüktür ve daha alt Fibonacci ölçeklerine aittir. Aslında ortaya çıkan argümanlar, \(N\)'nin greedy Zeckendorf ayrışımındaki kuyruk kalıntılarından ibarettir. Fibonacci sayıları üstel büyüdüğü için dokunulan ölçek sayısı yalnızca \(O(\log N)\)'dir. Bu nedenle küçük bir önbellek bütün tekrar hesapları kesmeye yeter.
C++ çözümü şu checkpoint'i doğrular:
$$S(10^6)=7894453.$$
Daha küçük faydalı değerler de
$$S(5)=5,\qquad S(8)=10,\qquad S(13)=20,\qquad S(100)=261$$
şeklindedir. Bu değerler hem Fibonacci sınırlarını hem de genel sınırları test ettiği için recurrence'in doğru kurulduğunu güçlü biçimde destekler.
Çözücü önce Fibonacci listesini \(10^{18}\)'e kadar önceden üretir; bu, hedef \(10^{17}\) için fazlasıyla yeterlidir. Her sorguda \(N\)'den küçük en büyük \(p\) bulunur,
$$S(N)=S(p)+(N-p)+S(N-p)$$
uygulanır, sonuç hash map içine yazılır ve geri döndürülür. Dıştaki solve(limit) fonksiyonu sadece memo tablosunu temizleyip bu özyinelemeyi başlatır.
\(F_k \le N < F_{k+1}\) olsun. O zaman özyineleme derinliği en fazla \(k\), memoization ile farklı durum sayısı da \(O(k)\) olur. Fibonacci sayıları üstel büyüdüğü için \(k=O(\log N)\). Dolayısıyla hem zaman hem bellek karmaşıklığı \(O(\log N)\)'dir.
Sea \(z(n)\) el número de términos de Fibonacci usados en la representación de Zeckendorf de \(n\). El programa calcula la suma prefijo
$$S(N)=\sum_{0 \le n < N} z(n),$$
con \(z(0)=0\), y el objetivo de Project Euler es \(S(10^{17})\).
Se usa la base de Fibonacci desplazada
$$F_1=1,\qquad F_2=2,\qquad F_{k+2}=F_{k+1}+F_k,$$
es decir, \(1,2,3,5,8,\dots\). El teorema de Zeckendorf afirma que todo entero positivo admite una descomposición única
$$n = F_{i_1}+F_{i_2}+\cdots+F_{i_t}, \qquad i_{j+1}\ge i_j+2,$$
sin usar dos Fibonacci consecutivos. La cantidad \(z(n)\) es exactamente ese número \(t\) de sumandos.
Fijemos \(k\ge 2\). Como
$$F_{k+1}=F_k+F_{k-1},$$
todo entero en el intervalo semiabierto \([F_k,F_{k+1})\) se escribe de manera única como
$$n = F_k + r,\qquad 0 \le r < F_{k-1}.$$
Ahora bien, \(r < F_{k-1}\), así que la representación de Zeckendorf de \(r\) no puede contener \(F_{k-1}\). Por eso añadir \(F_k\) no crea conflicto de adyacencia y obtenemos la identidad exacta
$$z(F_k+r)=1+z(r).$$
Esta biyección es el corazón de la solución: el bloque \([F_k,F_{k+1})\) es el bloque pequeño \([0,F_{k-1})\) con un término líder adicional \(F_k\).
Definimos
$$A_k = S(F_k).$$
Al sumar la identidad anterior sobre todos los \(r\in[0,F_{k-1})\), sale
$$A_{k+1}-A_k = \sum_{r=0}^{F_{k-1}-1}(1+z(r)) = F_{k-1}+A_{k-1}.$$
Por tanto, los valores de frontera cumplen
$$A_{k+1}=A_k+F_{k-1}+A_{k-1}.$$
Los primeros valores son
$$A_1=0,\quad A_2=1,\quad A_3=2,\quad A_4=5,\quad A_5=10,\quad A_6=20.$$
Por ejemplo, \([8,13)=\{8,9,10,11,12\}\) tiene números de términos
$$1,2,2,2,3,$$
cuya suma es \(10\). Como \(A_5=S(8)=10\), se obtiene \(A_6=S(13)=20\).
Sea \(p\) el mayor Fibonacci estrictamente menor que \(N\), es decir, \(p=F_k\). Entonces \(N \le F_{k+1}\), así que
$$0 \le N-p \le F_{k-1}.$$
La misma idea del bloque vale en el intervalo truncado \([p,N)\): para todo \(0\le r < N-p\),
$$z(p+r)=1+z(r).$$
Al sumar, obtenemos
$$S(N)=S(p)+(N-p)+S(N-p).$$
Esa es exactamente la fórmula usada en S(n). La búsqueda binaria sólo sirve para localizar el \(p\) correcto.
El mayor Fibonacci menor que \(10\) es \(p=8\). Por tanto,
$$S(10)=S(8)+(10-8)+S(2)=10+2+1=13.$$
La comprobación directa coincide: los números \(8\) y \(9\) usan \(1\) y \(2\) términos, así que la contribución adicional sobre \(S(8)\) es \(3\).
Cada paso recursivo reemplaza \(N\) por \((p,N-p)\), dos valores más pequeños y en escalas Fibonacci inferiores. De hecho, los argumentos que aparecen son exactamente los restos de cola en la descomposición voraz de Zeckendorf de \(N\). Como los Fibonacci crecen exponencialmente, sólo hay \(O(\log N)\) escalas relevantes. Por eso una tabla memo pequeña es suficiente.
La implementación en C++ verifica
$$S(10^6)=7894453.$$
Algunos valores menores útiles son
$$S(5)=5,\qquad S(8)=10,\qquad S(13)=20,\qquad S(100)=261.$$
Estos puntos de control comprueban tanto valores en fronteras Fibonacci como valores generales, así que validan bien la recurrencia.
Primero se precalcula la lista de Fibonacci hasta \(10^{18}\), suficiente para cubrir el objetivo \(10^{17}\). Para una consulta \(N\), el programa encuentra el mayor \(p<N\), aplica
$$S(N)=S(p)+(N-p)+S(N-p),$$
guarda el resultado en un mapa hash y lo devuelve. La función externa solve(limit) sólo limpia la memoización y lanza esa recursión.
Si \(F_k \le N < F_{k+1}\), la profundidad recursiva es a lo sumo \(k\), y con memoización el número de estados distintos también es \(O(k)\). Como \(F_k\) crece exponencialmente, \(k=O(\log N)\). Por lo tanto, tiempo y memoria son \(O(\log N)\).
记 \(z(n)\) 为整数 \(n\) 的 Zeckendorf 表示中所用 Fibonacci 项的个数。代码计算前缀和
$$S(N)=\sum_{0 \le n < N} z(n),$$
并约定 \(z(0)=0\)。Project Euler 要求的是 \(S(10^{17})\)。
代码使用平移后的 Fibonacci 基底
$$F_1=1,\qquad F_2=2,\qquad F_{k+2}=F_{k+1}+F_k,$$
也就是 \(1,2,3,5,8,\dots\)。Zeckendorf 定理说明，每个正整数都能唯一写成
$$n = F_{i_1}+F_{i_2}+\cdots+F_{i_t}, \qquad i_{j+1}\ge i_j+2,$$
即不会同时使用相邻的两个 Fibonacci 数。于是 \(z(n)\) 就是这个唯一分解中的项数 \(t\)。
固定 \(k\ge 2\)。因为
$$F_{k+1}=F_k+F_{k-1},$$
所以区间 \([F_k,F_{k+1})\) 中的每个整数都能唯一写成
$$n = F_k + r,\qquad 0 \le r < F_{k-1}.$$
又因为 \(r < F_{k-1}\)，所以 \(r\) 的 Zeckendorf 表示不可能包含 \(F_{k-1}\)。因此在前面加上一个 \(F_k\) 不会产生相邻冲突，于是得到精确恒等式
$$z(F_k+r)=1+z(r).$$
这就是整套算法的核心双射：区块 \([F_k,F_{k+1})\) 本质上就是较小区块 \([0,F_{k-1})\) 的每个表示前面再加一个 \(F_k\)。
定义
$$A_k = S(F_k).$$
把上面的恒等式对全部 \(r\in[0,F_{k-1})\) 求和，得到
$$A_{k+1}-A_k = \sum_{r=0}^{F_{k-1}-1}(1+z(r)) = F_{k-1}+A_{k-1}.$$
所以边界值满足递推
$$A_{k+1}=A_k+F_{k-1}+A_{k-1}.$$
前几个值为
$$A_1=0,\quad A_2=1,\quad A_3=2,\quad A_4=5,\quad A_5=10,\quad A_6=20.$$
例如 \([8,13)=\{8,9,10,11,12\}\) 的项数分别是
$$1,2,2,2,3,$$
总和正好是 \(10\)。因为 \(A_5=S(8)=10\)，所以 \(A_6=S(13)=20\)。
设 \(p\) 是严格小于 \(N\) 的最大 Fibonacci 数，即 \(p=F_k\)。那么 \(N \le F_{k+1}\)，于是
$$0 \le N-p \le F_{k-1}.$$
因此同样的区块论证也适用于截断区间 \([p,N)\)：对每个 \(0\le r < N-p\)，都有
$$z(p+r)=1+z(r).$$
把它加起来便得到
$$S(N)=S(p)+(N-p)+S(N-p).$$
这正是 S(n) 中实现的公式；二分查找只是为了找到这个最大的 \(p\)。
小于 \(10\) 的最大 Fibonacci 数是 \(p=8\)。因此
$$S(10)=S(8)+(10-8)+S(2)=10+2+1=13.$$
直接检查也完全一致：\(8\) 与 \(9\) 的 Zeckendorf 项数分别是 \(1\) 和 \(2\)，所以在 \(S(8)\) 之上确实多出 \(3\)。
每一步递归都会把 \(N\) 替换成 \((p,N-p)\)，而这两个数都更小，并且落在更低的 Fibonacci 尺度上。实际上，所有出现的参数正是原始 \(N\) 的贪心 Zeckendorf 分解里的那些尾部余量。由于 Fibonacci 数按指数增长，相关尺度只有 \(O(\log N)\) 个，所以一个很小的缓存表就足够了。
C++ 实现验证了
$$S(10^6)=7894453.$$
一些更小的参考值是
$$S(5)=5,\qquad S(8)=10,\qquad S(13)=20,\qquad S(100)=261.$$
这些检查点同时覆盖了 Fibonacci 边界和一般位置，因此对递推的正确性是很有力的验证。
程序先预生成到 \(10^{18}\) 为止的 Fibonacci 列表，这足以覆盖目标 \(10^{17}\)。对于输入 \(N\)，它先找出最大的 \(p<N\)，然后应用
$$S(N)=S(p)+(N-p)+S(N-p),$$
把结果存入哈希表并返回。外层 solve(limit) 只是清空缓存并启动这套递归。
若 \(F_k \le N < F_{k+1}\)，则递归深度至多为 \(k\)，而在 memoization 之后，不同状态的个数也是 \(O(k)\)。因为 Fibonacci 数指数增长，所以 \(k=O(\log N)\)。因此时间和空间复杂度都为 \(O(\log N)\)。
Пусть \(z(n)\) обозначает число чисел Фибоначчи в представлении Цекендорфа числа \(n\). Программа вычисляет префиксную сумму
$$S(N)=\sum_{0 \le n < N} z(n),$$
где принято \(z(0)=0\). Целевой ответ Project Euler равен \(S(10^{17})\).
Код использует сдвинутую базу Фибоначчи
$$F_1=1,\qquad F_2=2,\qquad F_{k+2}=F_{k+1}+F_k,$$
то есть последовательность \(1,2,3,5,8,\dots\). Теорема Цекендорфа утверждает, что каждое положительное целое имеет единственное разложение
$$n = F_{i_1}+F_{i_2}+\cdots+F_{i_t}, \qquad i_{j+1}\ge i_j+2,$$
в котором не используются два соседних числа Фибоначчи. Величина \(z(n)\) и есть число \(t\) слагаемых в этом разложении.
Зафиксируем \(k\ge 2\). Поскольку
$$F_{k+1}=F_k+F_{k-1},$$
каждое число из полуинтервала \([F_k,F_{k+1})\) единственным образом записывается как
$$n = F_k + r,\qquad 0 \le r < F_{k-1}.$$
Но \(r < F_{k-1}\), значит, в представлении Цекендорфа числа \(r\) слагаемое \(F_{k-1}\) появиться не может. Поэтому добавление \(F_k\) не создаёт запретной соседней пары, и мы получаем точное равенство
$$z(F_k+r)=1+z(r).$$
Это и есть центральная биекция решения: блок \([F_k,F_{k+1})\) равен блоку \([0,F_{k-1})\), только с одним дополнительным ведущим слагаемым \(F_k\).
Обозначим
$$A_k = S(F_k).$$
Суммируя предыдущее равенство по всем \(r\in[0,F_{k-1})\), получаем
$$A_{k+1}-A_k = \sum_{r=0}^{F_{k-1}-1}(1+z(r)) = F_{k-1}+A_{k-1}.$$
Следовательно, граничные значения удовлетворяют рекурсии
$$A_{k+1}=A_k+F_{k-1}+A_{k-1}.$$
Первые значения таковы:
$$A_1=0,\quad A_2=1,\quad A_3=2,\quad A_4=5,\quad A_5=10,\quad A_6=20.$$
Например, в интервале \([8,13)=\{8,9,10,11,12\}\) числа слагаемых равны
$$1,2,2,2,3,$$
их сумма равна \(10\). Так как \(A_5=S(8)=10\), отсюда получается \(A_6=S(13)=20\).
Пусть \(p\) — наибольшее число Фибоначчи, строго меньшее \(N\), то есть \(p=F_k\). Тогда \(N \le F_{k+1}\), а значит
$$0 \le N-p \le F_{k-1}.$$
Поэтому тот же аргумент работает на усечённом интервале \([p,N)\): для любого \(0\le r < N-p\)
$$z(p+r)=1+z(r).$$
После суммирования получаем
$$S(N)=S(p)+(N-p)+S(N-p).$$
Именно эта формула и реализована в S(n). Двоичный поиск нужен только для нахождения нужного максимального \(p\).
Наибольшее число Фибоначчи меньше \(10\) — это \(p=8\). Поэтому
$$S(10)=S(8)+(10-8)+S(2)=10+2+1=13.$$
Прямая проверка совпадает: числа \(8\) и \(9\) используют \(1\) и \(2\) слагаемых соответственно, так что добавка к \(S(8)\) действительно равна \(3\).
Каждый рекурсивный шаг заменяет \(N\) на пару \((p,N-p)\), где оба числа меньше и лежат на более низких Fibonacci-масштабах. Более того, реально встречаются только хвостовые остатки жадного разложения Цекендорфа исходного \(N\). Поскольку числа Фибоначчи растут экспоненциально, число relevant-масштабов равно лишь \(O(\log N)\), и небольшой кэш полностью решает задачу повторных вычислений.
Реализация на C++ проверяет
$$S(10^6)=7894453.$$
Полезные меньшие значения:
$$S(5)=5,\qquad S(8)=10,\qquad S(13)=20,\qquad S(100)=261.$$
Они покрывают и границы Fibonacci, и обычные точки, поэтому хорошо подтверждают правильность рекурсии.
Сначала строится список чисел Фибоначчи до \(10^{18}\); этого достаточно для цели \(10^{17}\). Для запроса \(N\) программа находит наибольшее \(p<N\), применяет
$$S(N)=S(p)+(N-p)+S(N-p),$$
сохраняет ответ в hash map и возвращает его. Внешняя функция solve(limit) лишь очищает кэш и запускает эту рекурсию.
Если \(F_k \le N < F_{k+1}\), то глубина рекурсии не превосходит \(k\), и при мемоизации число различных состояний также равно \(O(k)\). Поскольку числа Фибоначчи растут экспоненциально, имеем \(k=O(\log N)\). Значит, и время, и память равны \(O(\log N)\).
لتكن \(z(n)\) هي عدد حدود فيبوناتشي المستخدمة في تمثيل Zeckendorf للعدد \(n\). البرنامج يحسب مجموع البادئة
$$S(N)=\sum_{0 \le n < N} z(n),$$
مع الاتفاق على أن \(z(0)=0\). والهدف في المسألة هو إيجاد \(S(10^{17})\).
الكود يستخدم أساس فيبوناتشي المزاح
$$F_1=1,\qquad F_2=2,\qquad F_{k+2}=F_{k+1}+F_k,$$
أي المتتالية \(1,2,3,5,8,\dots\). تنص نظرية Zeckendorf على أن كل عدد صحيح موجب يملك كتابة وحيدة من الشكل
$$n = F_{i_1}+F_{i_2}+\cdots+F_{i_t}, \qquad i_{j+1}\ge i_j+2,$$
بحيث لا يظهر حدّان متتاليان من فيبوناتشي معًا. إذن \(z(n)\) هو بالضبط عدد الحدود \(t\) في هذا التمثيل الوحيد.
ثبّت \(k\ge 2\). بما أن
$$F_{k+1}=F_k+F_{k-1},$$
فإن كل عدد في المجال نصف المفتوح \([F_k,F_{k+1})\) يكتب بصورة وحيدة على الشكل
$$n = F_k + r,\qquad 0 \le r < F_{k-1}.$$
والآن بما أن \(r < F_{k-1}\)، فإن تمثيل \(r\) لا يمكن أن يحتوي الحد \(F_{k-1}\). لذلك فإن إضافة \(F_k\) في المقدمة لا تولد تعارضًا مع شرط عدم التجاور، ونحصل على الهوية الدقيقة
$$z(F_k+r)=1+z(r).$$
وهذه هي البنية الأساسية للحل كله: الكتلة \([F_k,F_{k+1})\) هي ببساطة الكتلة الأصغر \([0,F_{k-1})\) بعد إضافة حد قائد واحد هو \(F_k\).
لنعرّف
$$A_k = S(F_k).$$
بجمع الهوية السابقة على جميع \(r\in[0,F_{k-1})\) نحصل على
$$A_{k+1}-A_k = \sum_{r=0}^{F_{k-1}-1}(1+z(r)) = F_{k-1}+A_{k-1}.$$
إذن قيم الحدود تحقق
$$A_{k+1}=A_k+F_{k-1}+A_{k-1}.$$
وأول القيم هي
$$A_1=0,\quad A_2=1,\quad A_3=2,\quad A_4=5,\quad A_5=10,\quad A_6=20.$$
مثلًا، المجال \([8,13)=\{8,9,10,11,12\}\) يملك أعداد حدود
$$1,2,2,2,3,$$
ومجموعها \(10\). وبما أن \(A_5=S(8)=10\)، نستنتج أن \(A_6=S(13)=20\).
ليكن \(p\) أكبر عدد فيبوناتشي أصغر تمامًا من \(N\)، أي \(p=F_k\). عندئذ \(N \le F_{k+1}\)، وبالتالي
$$0 \le N-p \le F_{k-1}.$$
إذن نفس فكرة الكتلة تعمل على المجال المقتطع \([p,N)\): لكل \(0\le r < N-p\) لدينا
$$z(p+r)=1+z(r).$$
وبالجمع نحصل على
$$S(N)=S(p)+(N-p)+S(N-p).$$
وهذه هي الصيغة التي يطبقها التابع S(n) حرفيًا. أما البحث الثنائي فمهمته فقط إيجاد هذا \(p\).
أكبر عدد فيبوناتشي أصغر من \(10\) هو \(p=8\). لذلك
$$S(10)=S(8)+(10-8)+S(2)=10+2+1=13.$$
والفحص المباشر يطابق ذلك: العددان \(8\) و\(9\) يملكان \(1\) و\(2\) حدين على الترتيب، لذا فالزيادة فوق \(S(8)\) تساوي فعلًا \(3\).
كل خطوة في الاستدعاء الذاتي تستبدل \(N\) بالزوج \((p,N-p)\)، وكلاهما أصغر وينتمي إلى مستوى أدنى من مستويات فيبوناتشي. في الحقيقة، جميع القيم التي تظهر هي البواقي الذيلية في التحليل الجشع لتمثيل Zeckendorf للعدد الأصلي \(N\). وبما أن أعداد فيبوناتشي تنمو أسيًا، فعدد المستويات المهمة هو فقط \(O(\log N)\)، ولذلك يكفي جدول memo صغير جدًا.
تنفذ نسخة C++ نقطة الفحص التالية:
$$S(10^6)=7894453.$$
ومن القيم الصغيرة المفيدة أيضًا
$$S(5)=5,\qquad S(8)=10,\qquad S(13)=20,\qquad S(100)=261.$$
وهذه القيم تختبر الحدود Fibonacci وغير الحدود معًا، ولذلك فهي فحص جيد جدًا لصحة العلاقة التراجعية.
يبني الحل أولًا قائمة Fibonacci حتى \(10^{18}\)، وهي أكثر من كافية لهدف \(10^{17}\). ثم لكل \(N\) يبحث عن أكبر \(p<N\)، ويطبق
$$S(N)=S(p)+(N-p)+S(N-p),$$
ويخزن النتيجة في hash map ثم يعيدها. الدالة الخارجية solve(limit) لا تفعل أكثر من تنظيف جدول memo وبدء هذا الاستدعاء الذاتي.
إذا كان \(F_k \le N < F_{k+1}\)، فإن عمق الاستدعاء لا يتجاوز \(k\)، ومع التخزين المؤقت يصبح عدد الحالات المختلفة أيضًا \(O(k)\). وبما أن أعداد فيبوناتشي تنمو أسيًا، فإن \(k=O(\log N)\). لذلك فكل من الزمن والذاكرة يساويان \(O(\log N)\).