Use the Fibonacci basis
$$F_1=1,\qquad F_2=2,\qquad F_{k+1}=F_k+F_{k-1}.$$
For each positive integer \(n\), repeatedly subtract the largest Fibonacci number not exceeding the current remainder. This greedy process gives the Zeckendorf representation of \(n\), and \(H(n)\) is defined as the smallest Fibonacci number that appears in that representation.
The quantity required by the problem is
$$G(n)=\sum_{m=1}^{n} H(m),$$
and the implementation evaluates this sum for \(n=23416728348467685\). Directly computing \(H(1),H(2),\dots,H(n)\) is impossible at that scale, so the solution reorganizes the summation around Fibonacci intervals.
The whole method comes from understanding what happens on ranges bounded by consecutive Fibonacci numbers. Once those block sums are known, a large query reduces by stripping off one leading Fibonacci term at a time.
Zeckendorf's theorem says that every positive integer can be written uniquely as a sum of nonconsecutive terms from the sequence \(1,2,3,5,\dots\), and the usual greedy subtraction procedure produces exactly that representation.
Therefore \(H(n)\) is well defined: it is simply the smallest summand in that unique decomposition. For instance,
$$18=13+5 \quad\Longrightarrow\quad H(18)=5,$$
while
$$12=8+3+1 \quad\Longrightarrow\quad H(12)=1.$$
The key observation is that after choosing a largest term \(F_m\), the next term can never be \(F_{m-1}\), because Zeckendorf representations forbid consecutive Fibonacci numbers.
Fix \(m\ge 2\). Every integer in the interval
$$F_m \le n \lt F_{m+1}$$
can be written as
$$n=F_m+r,\qquad 0\le r \lt F_{m-1},$$
because \(F_{m+1}=F_m+F_{m-1}\).
Once the leading term \(F_m\) is chosen, the remainder \(r\) is represented independently using Fibonacci numbers at most \(F_{m-2}\). Hence
$$H(F_m)=F_m,$$
and for every \(1\le r \lt F_{m-1}\),
$$H(F_m+r)=H(r).$$
So the entire block \([F_m,F_{m+1}-1]\) is just one exceptional point \(F_m\), followed by a shifted copy of the values \(H(1),H(2),\dots,H(F_{m-1}-1)\).
Define the boundary values
$$P_m = G(F_m-1).$$
The first two are
$$P_1=G(0)=0,\qquad P_2=G(1)=1.$$
Using the block structure from Step 2, the sum over one whole block is
$$\sum_{n=F_m}^{F_{m+1}-1} H(n)=F_m+\sum_{r=1}^{F_{m-1}-1} H(r)=F_m+P_{m-1}.$$
Therefore the boundary prefix sums obey
$$P_{m+1}=P_m+F_m+P_{m-1}\qquad (m\ge 2).$$
This is the central recurrence used by the implementation. It lets us compute \(G(F_m-1)\) for every relevant Fibonacci boundary using only earlier boundaries.
Now take an arbitrary \(x\) and choose the largest Fibonacci number \(F_m\le x\). Then \(x\) lies in the block starting at \(F_m\), so
$$G(x)=G(F_m-1)+\sum_{n=F_m}^{x} H(n).$$
Write \(n=F_m+r\). By the same reasoning as before, the partial block contributes
$$\sum_{n=F_m}^{x} H(n)=F_m+\sum_{r=1}^{x-F_m} H(r)=F_m+G(x-F_m).$$
Hence
$$\boxed{G(x)=P_m+F_m+G(x-F_m).}$$
Repeating this identity removes one Fibonacci term from the Zeckendorf representation of \(x\) at each step. If
$$x=F_{i_1}+F_{i_2}+\cdots+F_{i_t}$$
is its greedy decomposition, then the recursion unfolds to
$$G(x)=\sum_{j=1}^{t}\bigl(P_{i_j}+F_{i_j}\bigr).$$
A useful checkpoint is \(x=13\), because the implementations verify that \(G(13)=43\).
From the recurrence,
$$\begin{aligned} P_1&=0,\\ P_2&=1,\\ P_3&=P_2+F_2+P_1=1+2+0=3,\\ P_4&=P_3+F_3+P_2=3+3+1=7,\\ P_5&=P_4+F_4+P_3=7+5+3=15,\\ P_6&=P_5+F_5+P_4=15+8+7=30. \end{aligned}$$
Because \(13=F_6\), Step 4 gives
$$G(13)=P_6+F_6+G(0)=30+13=43.$$
You can also see this directly from the first values
$$H(1),\dots,H(13)=1,2,3,1,5,1,2,8,1,2,3,1,13,$$
whose sum is again \(43\).
The C++, Python, and Java implementations all follow the same structure. First they build the Fibonacci numbers up to the target \(n\) using the basis \(1,2,3,5,\dots\). Next they precompute the boundary values \(P_m=G(F_m-1)\) with the recurrence
$$P_{m+1}=P_m+F_m+P_{m-1}.$$
After that, they evaluate the target sum by maintaining a current remainder \(x\). At each iteration, the implementation locates the largest Fibonacci number not exceeding \(x\), adds the corresponding contribution
$$P_m+F_m,$$
and replaces \(x\) by \(x-F_m\). This is exactly the reduction formula from Step 4. When the remainder reaches \(0\), the accumulated total is the desired value of \(G(n)\).
Because the same mathematical decomposition is used in all three languages, the code is short: one Fibonacci table, one boundary-sum table, and one loop that walks through the Zeckendorf terms of the target.
Let \(t\) be the number of Fibonacci numbers not exceeding \(n\). Since Fibonacci numbers grow exponentially, \(t=\Theta(\log n)\).
Building the Fibonacci list and the boundary table costs \(O(t)\) time and \(O(t)\) memory. The evaluation phase removes one Fibonacci term per iteration, so it performs at most \(t\) iterations. As written, each iteration uses a binary search on the Fibonacci table, which gives \(O(t\log t)\) query time, i.e.
$$O(\log n\log\log n)$$
time overall and \(O(\log n)\) memory. In practice the table is tiny, so the computation is effectively logarithmic.
Verwendet wird die Fibonacci-Basis
$$F_1=1,\qquad F_2=2,\qquad F_{k+1}=F_k+F_{k-1}.$$
Für jede positive ganze Zahl \(n\) zieht man wiederholt die größte Fibonacci-Zahl ab, die den aktuellen Rest nicht überschreitet. Dieses gierige Verfahren liefert die Zeckendorf-Darstellung von \(n\), und \(H(n)\) ist die kleinste Fibonacci-Zahl, die in dieser Darstellung vorkommt.
Gesucht ist
$$G(n)=\sum_{m=1}^{n} H(m),$$
und die Implementierung berechnet diesen Wert für \(n=23416728348467685\). Eine direkte Auswertung aller \(H(1),H(2),\dots,H(n)\) ist unmöglich, deshalb arbeitet die Lösung mit Summen über Fibonacci-Blöcke.
Die gesamte Methode entsteht aus der Struktur der Intervalle zwischen aufeinanderfolgenden Fibonacci-Zahlen. Kennt man die Summen auf diesen Grenzen, lässt sich jede große Anfrage durch wiederholtes Entfernen des führenden Fibonacci-Terms zerlegen.
Nach dem Satz von Zeckendorf besitzt jede positive ganze Zahl eine eindeutige Darstellung als Summe nichtbenachbarter Zahlen aus der Folge \(1,2,3,5,\dots\), und genau diese Darstellung wird durch das gierige Verfahren erzeugt.
Damit ist \(H(n)\) wohldefiniert: Es ist einfach der kleinste Summand dieser eindeutigen Zerlegung. Zum Beispiel gilt
$$18=13+5 \quad\Longrightarrow\quad H(18)=5,$$
und ebenso
$$12=8+3+1 \quad\Longrightarrow\quad H(12)=1.$$
Wichtig ist dabei, dass nach der Wahl eines größten Terms \(F_m\) der nächste Summand niemals \(F_{m-1}\) sein darf, weil in der Zeckendorf-Darstellung keine benachbarten Fibonacci-Zahlen vorkommen.
Fixiere \(m\ge 2\). Jede Zahl im Intervall
$$F_m \le n \lt F_{m+1}$$
lässt sich schreiben als
$$n=F_m+r,\qquad 0\le r \lt F_{m-1},$$
denn \(F_{m+1}=F_m+F_{m-1}\).
Sobald der führende Term \(F_m\) feststeht, wird der Rest \(r\) unabhängig mit Fibonacci-Zahlen bis höchstens \(F_{m-2}\) dargestellt. Deshalb gilt
$$H(F_m)=F_m,$$
und für jedes \(1\le r \lt F_{m-1}\)
$$H(F_m+r)=H(r).$$
Der ganze Block \([F_m,F_{m+1}-1]\) besteht also aus einem Sonderfall \(F_m\) und danach aus einer verschobenen Kopie der Werte \(H(1),H(2),\dots,H(F_{m-1}-1)\).
Definiere die Randwerte
$$P_m = G(F_m-1).$$
Die ersten beiden lauten
$$P_1=G(0)=0,\qquad P_2=G(1)=1.$$
Mit der Blockstruktur aus Schritt 2 erhält man für die Summe über einen ganzen Block
$$\sum_{n=F_m}^{F_{m+1}-1} H(n)=F_m+\sum_{r=1}^{F_{m-1}-1} H(r)=F_m+P_{m-1}.$$
Daraus folgt die Rekursion
$$P_{m+1}=P_m+F_m+P_{m-1}\qquad (m\ge 2).$$
Genau diese Formel nutzt die Implementierung, um die Werte \(G(F_m-1)\) an allen benötigten Fibonacci-Grenzen aufzubauen.
Für beliebiges \(x\) sei \(F_m\) die größte Fibonacci-Zahl mit \(F_m\le x\). Dann liegt \(x\) im Block, der bei \(F_m\) beginnt, also
$$G(x)=G(F_m-1)+\sum_{n=F_m}^{x} H(n).$$
Schreibt man \(n=F_m+r\), so liefert dieselbe Argumentation wie zuvor
$$\sum_{n=F_m}^{x} H(n)=F_m+\sum_{r=1}^{x-F_m} H(r)=F_m+G(x-F_m).$$
Damit ergibt sich
$$\boxed{G(x)=P_m+F_m+G(x-F_m).}$$
Jede Wiederholung entfernt genau einen Fibonacci-Term aus der Zeckendorf-Darstellung von \(x\). Ist
$$x=F_{i_1}+F_{i_2}+\cdots+F_{i_t},$$
dann entfaltet sich die Rekursion zu
$$G(x)=\sum_{j=1}^{t}\bigl(P_{i_j}+F_{i_j}\bigr).$$
Ein nützlicher Kontrollwert ist \(x=13\), denn die Implementierungen prüfen \(G(13)=43\).
Aus der Rekursion folgt
$$\begin{aligned} P_1&=0,\\ P_2&=1,\\ P_3&=P_2+F_2+P_1=1+2+0=3,\\ P_4&=P_3+F_3+P_2=3+3+1=7,\\ P_5&=P_4+F_4+P_3=7+5+3=15,\\ P_6&=P_5+F_5+P_4=15+8+7=30. \end{aligned}$$
Da \(13=F_6\), liefert Schritt 4
$$G(13)=P_6+F_6+G(0)=30+13=43.$$
Direkt sieht man dasselbe an den ersten Werten
$$H(1),\dots,H(13)=1,2,3,1,5,1,2,8,1,2,3,1,13,$$
deren Summe ebenfalls \(43\) ist.
Die C++-, Python- und Java-Implementierungen folgen derselben Struktur. Zuerst erzeugen sie alle Fibonacci-Zahlen bis zum Zielwert \(n\) in der Basis \(1,2,3,5,\dots\). Danach berechnen sie die Randwerte \(P_m=G(F_m-1)\) mit der Rekursion
$$P_{m+1}=P_m+F_m+P_{m-1}.$$
Anschließend halten sie einen aktuellen Rest \(x\). In jeder Iteration sucht die Implementierung per Binärsuche die größte Fibonacci-Zahl mit \(F_m\le x\), addiert den Beitrag
$$P_m+F_m,$$
und ersetzt \(x\) durch \(x-F_m\). Das ist genau die Reduktionsformel aus Schritt 4. Sobald der Rest \(0\) erreicht, ist die aufsummierte Größe der gesuchte Wert von \(G(n)\).
Weil alle drei Sprachen dieselbe mathematische Zerlegung verwenden, bleibt der Code knapp: eine Fibonacci-Tabelle, eine Tabelle der Randpräfixe und eine Schleife über die Zeckendorf-Terme des Ziels.
Sei \(t\) die Anzahl der Fibonacci-Zahlen, die \(n\) nicht überschreiten. Wegen des exponentiellen Wachstums der Fibonacci-Zahlen gilt \(t=\Theta(\log n)\).
Das Erzeugen der Fibonacci-Liste und der Randtabelle benötigt \(O(t)\) Zeit und \(O(t)\) Speicher. In der Auswertungsphase wird pro Iteration genau ein Fibonacci-Term entfernt, also höchstens \(t\) Iterationen. Wie der Code geschrieben ist, benutzt jede Iteration eine Binärsuche in der Fibonacci-Tabelle, also \(O(t\log t)\) Laufzeit für die Anfrage, das heißt insgesamt
$$O(\log n\log\log n)$$
Zeit und \(O(\log n)\) Speicher. Praktisch ist die Tabelle sehr klein, daher verhält sich das Verfahren nahezu logarithmisch.
Kullanılan Fibonacci tabanı
$$F_1=1,\qquad F_2=2,\qquad F_{k+1}=F_k+F_{k-1}.$$
Her pozitif \(n\) için, kalan değeri aşmayan en büyük Fibonacci sayısı tekrar tekrar çıkarılır. Bu açgözlü süreç \(n\)'in Zeckendorf gösterimini verir ve \(H(n)\), bu gösterimde yer alan en küçük Fibonacci sayısı olarak tanımlanır.
İstenen büyüklük
$$G(n)=\sum_{m=1}^{n} H(m),$$
olup uygulama bu toplamı \(n=23416728348467685\) için hesaplar. Bu ölçekte \(H(1),H(2),\dots,H(n)\) değerlerini tek tek üretmek mümkün değildir; çözüm bunun yerine Fibonacci sınırları arasında oluşan blok toplamlarını kullanır.
Tüm yöntem, ardışık Fibonacci sayıları arasındaki aralıkların nasıl davrandığını anlamaya dayanır. Bu sınır toplamları elde edilince, büyük bir sorgu her adımda öndeki bir Fibonacci terimi sökülerek küçültülebilir.
Zeckendorf teoremine göre her pozitif tamsayı, \(1,2,3,5,\dots\) dizisindeki ardışık olmayan terimlerin toplamı olarak tek bir biçimde yazılır; standart açgözlü çıkarma algoritması da tam olarak bu gösterimi üretir.
Bu yüzden \(H(n)\) iyi tanımlıdır: tekil gösterimdeki en küçük terimdir. Örneğin
$$18=13+5 \quad\Longrightarrow\quad H(18)=5,$$
ve
$$12=8+3+1 \quad\Longrightarrow\quad H(12)=1.$$
Buradaki kritik nokta şudur: en büyük terim \(F_m\) seçildikten sonra sonraki terim \(F_{m-1}\) olamaz; çünkü Zeckendorf gösteriminde ardışık Fibonacci sayıları birlikte kullanılamaz.
\(m\ge 2\) için
$$F_m \le n \lt F_{m+1}$$
aralığındaki her sayı
$$n=F_m+r,\qquad 0\le r \lt F_{m-1}$$
şeklinde yazılır; çünkü \(F_{m+1}=F_m+F_{m-1}\).
Öndeki terim \(F_m\) sabitlendiğinde, kalan \(r\) yalnızca en fazla \(F_{m-2}\) olan Fibonacci sayılarıyla bağımsız biçimde temsil edilir. Dolayısıyla
$$H(F_m)=F_m,$$
ve her \(1\le r \lt F_{m-1}\) için
$$H(F_m+r)=H(r).$$
Yani \([F_m,F_{m+1}-1]\) bloğu, önce tek istisna olan \(F_m\)'den, ardından da \(H(1),H(2),\dots,H(F_{m-1}-1)\) dizisinin kaydırılmış bir kopyasından oluşur.
Şu sınır değerlerini tanımlayalım:
$$P_m = G(F_m-1).$$
İlk iki değer
$$P_1=G(0)=0,\qquad P_2=G(1)=1$$
olur. Adım 2'deki blok yapısını kullanırsak, bir tam bloğun toplamı
$$\sum_{n=F_m}^{F_{m+1}-1} H(n)=F_m+\sum_{r=1}^{F_{m-1}-1} H(r)=F_m+P_{m-1}$$
şeklindedir. Buradan
$$P_{m+1}=P_m+F_m+P_{m-1}\qquad (m\ge 2)$$
reküransı çıkar. Uygulamanın kullandığı ana ilişki budur.
Şimdi herhangi bir \(x\) için \(F_m\le x\) şartını sağlayan en büyük Fibonacci sayısını seçelim. O zaman
$$G(x)=G(F_m-1)+\sum_{n=F_m}^{x} H(n).$$
\(n=F_m+r\) yazılırsa, yine aynı mantıkla
$$\sum_{n=F_m}^{x} H(n)=F_m+\sum_{r=1}^{x-F_m} H(r)=F_m+G(x-F_m)$$
elde edilir. Böylece
$$\boxed{G(x)=P_m+F_m+G(x-F_m).}$$
Bu özdeşliği tekrar tekrar uygulamak, \(x\)'in Zeckendorf açılımındaki her adımda bir Fibonacci terimini kaldırır. Eğer
$$x=F_{i_1}+F_{i_2}+\cdots+F_{i_t}$$
ise sonuç
$$G(x)=\sum_{j=1}^{t}\bigl(P_{i_j}+F_{i_j}\bigr)$$
şeklinde açılır.
Faydalı bir kontrol noktası \(x=13\) değeridir; çünkü uygulamalar \(G(13)=43\) sonucunu doğrular.
Reküranstan
$$\begin{aligned} P_1&=0,\\ P_2&=1,\\ P_3&=P_2+F_2+P_1=1+2+0=3,\\ P_4&=P_3+F_3+P_2=3+3+1=7,\\ P_5&=P_4+F_4+P_3=7+5+3=15,\\ P_6&=P_5+F_5+P_4=15+8+7=30 \end{aligned}$$
elde edilir. \(13=F_6\) olduğu için Adım 4 şunu verir:
$$G(13)=P_6+F_6+G(0)=30+13=43.$$
Aynı sonuç ilk değerler doğrudan toplanarak da görülür:
$$H(1),\dots,H(13)=1,2,3,1,5,1,2,8,1,2,3,1,13.$$
C++, Python ve Java uygulamalarının üçü de aynı yapıyı izler. Önce \(1,2,3,5,\dots\) tabanındaki Fibonacci sayıları hedef \(n\)'ye kadar üretilir. Sonra sınır değerleri \(P_m=G(F_m-1)\),
$$P_{m+1}=P_m+F_m+P_{m-1}$$
reküransı ile önceden hesaplanır.
Ardından mevcut kalan değer \(x\) tutulur. Her döngüde uygulama, \(x\)'i aşmayan en büyük Fibonacci sayısını ikili aramayla bulur, ilgili katkı olan
$$P_m+F_m$$
miktarını toplama ekler ve \(x\)'i \(x-F_m\) ile değiştirir. Bu tam olarak Adım 4'teki indirgeme formülüdür. Kalan \(0\) olduğunda biriken toplam aranan \(G(n)\) değeridir.
Böylece üç dilde de yapı aynıdır: bir Fibonacci tablosu, bir sınır-önek tablosu ve hedefin Zeckendorf terimleri üzerinde ilerleyen kısa bir döngü.
\(n\)'yi aşmayan Fibonacci sayılarının sayısı \(t\) olsun. Fibonacci sayıları üstel büyüdüğü için \(t=\Theta(\log n)\).
Fibonacci listesini ve sınır tablosunu oluşturmak \(O(t)\) zaman ve \(O(t)\) bellek gerektirir. Değerlendirme aşaması her iterasyonda bir Fibonacci terimi kaldırır; yani en fazla \(t\) iterasyon vardır. Kod yazıldığı haliyle her iterasyonda Fibonacci tablosu üzerinde ikili arama yaptığı için sorgu süresi \(O(t\log t)\), yani toplamda
$$O(\log n\log\log n)$$
zamandır. Bellek kullanımı \(O(\log n)\)'dir. Pratikte tablo çok küçük olduğundan çalışma maliyeti fiilen logaritmiktir.
Se usa la base de Fibonacci
$$F_1=1,\qquad F_2=2,\qquad F_{k+1}=F_k+F_{k-1}.$$
Para cada entero positivo \(n\), se resta repetidamente el mayor número de Fibonacci que no supera al resto actual. Ese proceso voraz produce la representación de Zeckendorf de \(n\), y \(H(n)\) es el menor número de Fibonacci que aparece en dicha representación.
La magnitud pedida es
$$G(n)=\sum_{m=1}^{n} H(m),$$
y la implementación la evalúa para \(n=23416728348467685\). Enumerar directamente \(H(1),H(2),\dots,H(n)\) es inviable, así que la solución reorganiza el cálculo en bloques delimitados por Fibonacci consecutivos.
Todo el método nace de entender qué ocurre en los intervalos acotados por dos Fibonacci consecutivos. Una vez conocidas esas sumas de bloque, una consulta grande se reduce eliminando un término líder de Fibonacci en cada paso.
El teorema de Zeckendorf afirma que todo entero positivo puede escribirse de forma única como suma de términos no consecutivos de la sucesión \(1,2,3,5,\dots\), y el procedimiento voraz estándar produce exactamente esa representación.
Por tanto, \(H(n)\) queda bien definido: es simplemente el sumando más pequeño de esa descomposición única. Por ejemplo,
$$18=13+5 \quad\Longrightarrow\quad H(18)=5,$$
mientras que
$$12=8+3+1 \quad\Longrightarrow\quad H(12)=1.$$
La observación clave es que, después de escoger un término máximo \(F_m\), el siguiente término nunca puede ser \(F_{m-1}\), porque las representaciones de Zeckendorf no permiten Fibonacci consecutivos.
Fijemos \(m\ge 2\). Todo entero del intervalo
$$F_m \le n \lt F_{m+1}$$
puede escribirse como
$$n=F_m+r,\qquad 0\le r \lt F_{m-1},$$
porque \(F_{m+1}=F_m+F_{m-1}\).
Una vez elegido el término principal \(F_m\), el resto \(r\) se representa de manera independiente usando Fibonacci de tamaño a lo sumo \(F_{m-2}\). De ahí se obtiene
$$H(F_m)=F_m,$$
y para todo \(1\le r \lt F_{m-1}\),
$$H(F_m+r)=H(r).$$
Así, el bloque completo \([F_m,F_{m+1}-1]\) consta de un punto excepcional \(F_m\) seguido por una copia desplazada de los valores \(H(1),H(2),\dots,H(F_{m-1}-1)\).
Definimos
$$P_m = G(F_m-1).$$
Los dos primeros valores son
$$P_1=G(0)=0,\qquad P_2=G(1)=1.$$
Usando la estructura del bloque del paso anterior, la suma sobre un bloque completo vale
$$\sum_{n=F_m}^{F_{m+1}-1} H(n)=F_m+\sum_{r=1}^{F_{m-1}-1} H(r)=F_m+P_{m-1}.$$
Por tanto, se obtiene la recurrencia
$$P_{m+1}=P_m+F_m+P_{m-1}\qquad (m\ge 2).$$
Esta es la identidad central que usa la implementación para construir los valores \(G(F_m-1)\) en todas las fronteras necesarias.
Tomemos un \(x\) arbitrario y sea \(F_m\) el mayor Fibonacci con \(F_m\le x\). Entonces
$$G(x)=G(F_m-1)+\sum_{n=F_m}^{x} H(n).$$
Si escribimos \(n=F_m+r\), la misma idea de antes da
$$\sum_{n=F_m}^{x} H(n)=F_m+\sum_{r=1}^{x-F_m} H(r)=F_m+G(x-F_m).$$
En consecuencia,
$$\boxed{G(x)=P_m+F_m+G(x-F_m).}$$
Al repetir esta identidad, se elimina un término de Fibonacci de la representación de Zeckendorf de \(x\) en cada paso. Si
$$x=F_{i_1}+F_{i_2}+\cdots+F_{i_t},$$
entonces la expansión completa es
$$G(x)=\sum_{j=1}^{t}\bigl(P_{i_j}+F_{i_j}\bigr).$$
Un punto de comprobación útil es \(x=13\), porque las implementaciones verifican que \(G(13)=43\).
A partir de la recurrencia,
$$\begin{aligned} P_1&=0,\\ P_2&=1,\\ P_3&=P_2+F_2+P_1=1+2+0=3,\\ P_4&=P_3+F_3+P_2=3+3+1=7,\\ P_5&=P_4+F_4+P_3=7+5+3=15,\\ P_6&=P_5+F_5+P_4=15+8+7=30. \end{aligned}$$
Como \(13=F_6\), el paso 4 produce
$$G(13)=P_6+F_6+G(0)=30+13=43.$$
Lo mismo se ve directamente con los primeros valores
$$H(1),\dots,H(13)=1,2,3,1,5,1,2,8,1,2,3,1,13,$$
cuya suma vuelve a ser \(43\).
Las implementaciones en C++, Python y Java siguen exactamente la misma idea. Primero generan todos los números de Fibonacci hasta el objetivo \(n\) usando la base \(1,2,3,5,\dots\). Después precalculan los valores de frontera \(P_m=G(F_m-1)\) con la recurrencia
$$P_{m+1}=P_m+F_m+P_{m-1}.$$
Luego mantienen un resto actual \(x\). En cada iteración, la implementación localiza mediante búsqueda binaria el mayor Fibonacci que no supera a \(x\), añade la contribución
$$P_m+F_m,$$
y sustituye \(x\) por \(x-F_m\). Eso es exactamente la fórmula de reducción del paso 4. Cuando el resto llega a \(0\), el acumulado es el valor deseado de \(G(n)\).
Como las tres versiones comparten la misma descomposición matemática, el código queda muy compacto: una tabla de Fibonacci, una tabla de sumas en fronteras y un bucle que recorre los términos de Zeckendorf del objetivo.
Sea \(t\) el número de Fibonacci no mayores que \(n\). Como la sucesión crece exponencialmente, \(t=\Theta(\log n)\).
Construir la lista de Fibonacci y la tabla de fronteras cuesta \(O(t)\) tiempo y \(O(t)\) memoria. La fase de evaluación elimina un término de Fibonacci por iteración, de modo que hay como mucho \(t\) iteraciones. Tal como está escrito el código, cada una usa una búsqueda binaria sobre la tabla de Fibonacci, así que el coste de la consulta es \(O(t\log t)\), es decir, en conjunto
$$O(\log n\log\log n)$$
tiempo y \(O(\log n)\) memoria. En la práctica, la tabla es muy pequeña y el comportamiento es casi logarítmico.
这里使用的 Fibonacci 基底是
$$F_1=1,\qquad F_2=2,\qquad F_{k+1}=F_k+F_{k-1}.$$
对每个正整数 \(n\)，不断减去当前余量所允许的最大 Fibonacci 数。这个贪心过程恰好给出 \(n\) 的 Zeckendorf 表示，而 \(H(n)\) 定义为该表示中出现的最小 Fibonacci 项。
题目要求计算
$$G(n)=\sum_{m=1}^{n} H(m),$$
实现中求的是 \(n=23416728348467685\) 时的值。由于这个规模远远超过逐项枚举能力，解法必须利用 Fibonacci 边界上的整体结构，而不能逐个计算所有 \(H(m)\)。
整个方法的核心，是把整数区间按相邻 Fibonacci 数之间的块来理解。只要掌握这些块的总贡献，就可以把大问题不断拆成更小的同类问题。
Zeckendorf 定理说明：每个正整数都能唯一写成序列 \(1,2,3,5,\dots\) 中若干个互不相邻的 Fibonacci 数之和，而“每次取不超过当前余量的最大 Fibonacci 数”的贪心算法，正好生成这唯一表示。
因此 \(H(n)\) 没有歧义，它就是这组 Fibonacci 加数中最小的那一个。例如
$$18=13+5 \quad\Longrightarrow\quad H(18)=5,$$
而
$$12=8+3+1 \quad\Longrightarrow\quad H(12)=1.$$
关键点在于：一旦最大的项 \(F_m\) 被选中，下一项就绝不可能是 \(F_{m-1}\)，因为 Zeckendorf 表示禁止使用相邻的 Fibonacci 数。
固定 \(m\ge 2\)。任何满足
$$F_m \le n \lt F_{m+1}$$
的整数，都可以写成
$$n=F_m+r,\qquad 0\le r \lt F_{m-1},$$
因为 \(F_{m+1}=F_m+F_{m-1}\)。
一旦首项 \(F_m\) 已经确定，剩余部分 \(r\) 的表示就只能使用至多 \(F_{m-2}\) 的 Fibonacci 数，因此它与更小规模的问题完全同构。于是有
$$H(F_m)=F_m,$$
并且对所有 \(1\le r \lt F_{m-1}\)，都有
$$H(F_m+r)=H(r).$$
这意味着整个区间 \([F_m,F_{m+1}-1]\) 可以看成两部分：先是一个特殊点 \(F_m\)，其最小项就是它自身；后面则是一段与 \(H(1),H(2),\dots,H(F_{m-1}-1)\) 完全相同的复制序列。
定义边界值
$$P_m = G(F_m-1).$$
最开始两个值是
$$P_1=G(0)=0,\qquad P_2=G(1)=1.$$
根据步骤 2，一个完整块的贡献为
$$\sum_{n=F_m}^{F_{m+1}-1} H(n)=F_m+\sum_{r=1}^{F_{m-1}-1} H(r)=F_m+P_{m-1}.$$
于是立刻得到递推式
$$P_{m+1}=P_m+F_m+P_{m-1}\qquad (m\ge 2).$$
这正是实现真正依赖的数学骨架。它允许我们只沿着 Fibonacci 边界推进，就把所有需要的 \(G(F_m-1)\) 预处理出来。
现在考虑任意 \(x\)，取满足 \(F_m\le x\) 的最大 Fibonacci 数 \(F_m\)。那么
$$G(x)=G(F_m-1)+\sum_{n=F_m}^{x} H(n).$$
把后半段写成 \(n=F_m+r\)，和前面相同的结构给出
$$\sum_{n=F_m}^{x} H(n)=F_m+\sum_{r=1}^{x-F_m} H(r)=F_m+G(x-F_m).$$
因此
$$\boxed{G(x)=P_m+F_m+G(x-F_m).}$$
每应用一次这个公式，就从 \(x\) 的 Zeckendorf 表示中剥掉一个最大的 Fibonacci 项。若
$$x=F_{i_1}+F_{i_2}+\cdots+F_{i_t},$$
那么不断展开后便得到
$$G(x)=\sum_{j=1}^{t}\bigl(P_{i_j}+F_{i_j}\bigr).$$
这也是为什么程序最终只需要顺着贪心分解走一遍即可。
一个很好的校验点是 \(x=13\)，因为实现会验证 \(G(13)=43\)。
先由递推计算边界值：
$$\begin{aligned} P_1&=0,\\ P_2&=1,\\ P_3&=P_2+F_2+P_1=1+2+0=3,\\ P_4&=P_3+F_3+P_2=3+3+1=7,\\ P_5&=P_4+F_4+P_3=7+5+3=15,\\ P_6&=P_5+F_5+P_4=15+8+7=30. \end{aligned}$$
由于 \(13=F_6\)，步骤 4 直接给出
$$G(13)=P_6+F_6+G(0)=30+13=43.$$
如果把前 13 个 \(H\) 值直接列出来，结果也完全一致：
$$H(1),\dots,H(13)=1,2,3,1,5,1,2,8,1,2,3,1,13.$$
这些数相加正好是 \(43\)。这说明边界递推和一般递归确实与逐项定义相吻合。
C++、Python 和 Java 三个实现遵循完全相同的流程。首先，程序生成不超过目标 \(n\) 的全部 Fibonacci 数，也就是 \(1,2,3,5,\dots\) 这条基底。然后利用递推式
$$P_{m+1}=P_m+F_m+P_{m-1}$$
预先计算所有边界前缀和 \(P_m=G(F_m-1)\)。
接下来，程序维护当前余量 \(x\)。每一轮都通过二分查找找到不超过 \(x\) 的最大 Fibonacci 数 \(F_m\)，把对应贡献
$$P_m+F_m$$
加入答案，再把余量更新为 \(x-F_m\)。这一操作与数学部分的递推
$$G(x)=P_m+F_m+G(x-F_m)$$
完全一致。余量降到 \(0\) 时，累计值就是目标 \(G(n)\)。
从结构上看，代码并没有做任何复杂状态搜索，只是维护两张很短的表，再沿着目标值的 Zeckendorf 展开依次累加贡献。
设不超过 \(n\) 的 Fibonacci 数个数为 \(t\)。由于 Fibonacci 数按指数速度增长，所以 \(t=\Theta(\log n)\)。
构造 Fibonacci 表和边界表需要 \(O(t)\) 时间与 \(O(t)\) 空间。求值阶段每次去掉一个 Zeckendorf 项，因此迭代次数至多为 \(t\)。按照当前实现方式，每轮都要在 Fibonacci 表上做一次二分查找，所以查询时间是 \(O(t\log t)\)，也就是总计
$$O(\log n\log\log n)$$
时间和 \(O(\log n)\) 空间。由于表本身非常短，实际运行时它几乎就是对数级成本。
Используется фибоначчиева база
$$F_1=1,\qquad F_2=2,\qquad F_{k+1}=F_k+F_{k-1}.$$
Для каждого положительного числа \(n\) мы многократно вычитаем наибольшее число Фибоначчи, не превосходящее текущий остаток. Этот жадный процесс даёт представление Цекендорфа, а \(H(n)\) определяется как наименьшее число Фибоначчи, вошедшее в это представление.
Требуется вычислить
$$G(n)=\sum_{m=1}^{n} H(m),$$
причём реализация считает это значение для \(n=23416728348467685\). На таком масштабе прямой перебор всех \(H(1),H(2),\dots,H(n)\) невозможен, поэтому решение опирается на суммы по блокам между соседними числами Фибоначчи.
Вся идея строится на понимании интервалов, ограниченных соседними числами Фибоначчи. Если научиться быстро считать вклад таких блоков, то большое значение \(G(n)\) можно разложить, по одному снимая старший фибоначчиев термин.
Теорема Цекендорфа утверждает, что каждое положительное целое имеет единственное представление в виде суммы непоследовательных членов ряда \(1,2,3,5,\dots\), и обычный жадный алгоритм строит именно это представление.
Следовательно, \(H(n)\) определено однозначно: это просто наименьшее слагаемое в таком разложении. Например,
$$18=13+5 \quad\Longrightarrow\quad H(18)=5,$$
а
$$12=8+3+1 \quad\Longrightarrow\quad H(12)=1.$$
Ключевой факт состоит в том, что после выбора максимального члена \(F_m\) следующий член не может быть равен \(F_{m-1}\), поскольку в представлении Цекендорфа нельзя использовать соседние числа Фибоначчи.
Зафиксируем \(m\ge 2\). Любое число из интервала
$$F_m \le n \lt F_{m+1}$$
можно записать в виде
$$n=F_m+r,\qquad 0\le r \lt F_{m-1},$$
поскольку \(F_{m+1}=F_m+F_{m-1}\).
После выбора старшего члена \(F_m\) остаток \(r\) представляется независимо через числа Фибоначчи не больше \(F_{m-2}\). Поэтому
$$H(F_m)=F_m,$$
а для всех \(1\le r \lt F_{m-1}\)
$$H(F_m+r)=H(r).$$
Значит, блок \([F_m,F_{m+1}-1]\) состоит из одной особой точки \(F_m\) и затем из сдвинутой копии последовательности \(H(1),H(2),\dots,H(F_{m-1}-1)\).
Обозначим
$$P_m = G(F_m-1).$$
Первые два значения таковы:
$$P_1=G(0)=0,\qquad P_2=G(1)=1.$$
Из структуры блока сразу следует
$$\sum_{n=F_m}^{F_{m+1}-1} H(n)=F_m+\sum_{r=1}^{F_{m-1}-1} H(r)=F_m+P_{m-1}.$$
Следовательно,
$$P_{m+1}=P_m+F_m+P_{m-1}\qquad (m\ge 2).$$
Это основная рекурсия, на которой держится реализация: она позволяет заранее получить все нужные значения \(G(F_m-1)\) на границах блоков.
Пусть теперь \(F_m\) - наибольшее число Фибоначчи, не превосходящее \(x\). Тогда
$$G(x)=G(F_m-1)+\sum_{n=F_m}^{x} H(n).$$
Если записать \(n=F_m+r\), то тем же рассуждением получаем
$$\sum_{n=F_m}^{x} H(n)=F_m+\sum_{r=1}^{x-F_m} H(r)=F_m+G(x-F_m).$$
Значит,
$$\boxed{G(x)=P_m+F_m+G(x-F_m).}$$
Каждое применение этой формулы убирает один член из представления Цекендорфа числа \(x\). Если
$$x=F_{i_1}+F_{i_2}+\cdots+F_{i_t},$$
то после полного разворачивания имеем
$$G(x)=\sum_{j=1}^{t}\bigl(P_{i_j}+F_{i_j}\bigr).$$
Удобная контрольная точка - \(x=13\), поскольку реализации проверяют равенство \(G(13)=43\).
По рекурсии получаем
$$\begin{aligned} P_1&=0,\\ P_2&=1,\\ P_3&=P_2+F_2+P_1=1+2+0=3,\\ P_4&=P_3+F_3+P_2=3+3+1=7,\\ P_5&=P_4+F_4+P_3=7+5+3=15,\\ P_6&=P_5+F_5+P_4=15+8+7=30. \end{aligned}$$
Так как \(13=F_6\), из шага 4 следует
$$G(13)=P_6+F_6+G(0)=30+13=43.$$
То же самое видно и напрямую из первых значений
$$H(1),\dots,H(13)=1,2,3,1,5,1,2,8,1,2,3,1,13,$$
сумма которых также равна \(43\).
Реализации на C++, Python и Java устроены одинаково. Сначала они строят список чисел Фибоначчи до целевого \(n\) в базе \(1,2,3,5,\dots\). Затем предварительно вычисляют значения \(P_m=G(F_m-1)\) по рекурсии
$$P_{m+1}=P_m+F_m+P_{m-1}.$$
После этого поддерживается текущий остаток \(x\). На каждом шаге реализация бинарным поиском находит наибольшее число Фибоначчи, не превосходящее \(x\), добавляет вклад
$$P_m+F_m,$$
и заменяет \(x\) на \(x-F_m\). Это в точности соответствует формуле редукции из шага 4. Когда остаток становится равным нулю, накопленная сумма и есть нужное значение \(G(n)\).
Таким образом, в коде нет перебора огромного количества состояний: есть короткая таблица Фибоначчи, короткая таблица граничных сумм и цикл по членам представления Цекендорфа целевого числа.
Пусть \(t\) - число Fibonacci-значений, не превосходящих \(n\). Поскольку числа Фибоначчи растут экспоненциально, имеем \(t=\Theta(\log n)\).
Построение таблицы Фибоначчи и таблицы границ требует \(O(t)\) времени и \(O(t)\) памяти. На этапе вычисления на каждой итерации удаляется один член представления Цекендорфа, так что итераций не больше \(t\). В текущей реализации каждая итерация делает бинарный поиск по таблице Fibonacci, поэтому время запроса равно \(O(t\log t)\), то есть суммарно
$$O(\log n\log\log n)$$
при памяти \(O(\log n)\). На практике таблица очень мала, поэтому поведение почти логарифмическое.
تُستعمل قاعدة فيبوناتشي التالية:
$$F_1=1,\qquad F_2=2,\qquad F_{k+1}=F_k+F_{k-1}.$$
لكل عدد صحيح موجب \(n\)، نطرح مراراً أكبر عدد فيبوناتشي لا يتجاوز الباقي الحالي. هذه العملية الجشعة تعطي تمثيل Zeckendorf للعدد \(n\)، وتُعرَّف \(H(n)\) بأنها أصغر قيمة فيبوناتشي تظهر في هذا التمثيل.
المقدار المطلوب هو
$$G(n)=\sum_{m=1}^{n} H(m),$$
والتنفيذ يحسب هذه القيمة عند \(n=23416728348467685\). لا يمكن حساب كل القيم \(H(1),H(2),\dots,H(n)\) مباشرة عند هذا الحجم، لذلك يعيد الحل تنظيم الجمع حول كتل تحددها حدود فيبوناتشي.
جوهر الطريقة هو فهم ما يحدث على الفترات المحصورة بين عددين متتاليين من فيبوناتشي. متى عرفنا مساهمة كل كتلة من هذا النوع، صار من الممكن تفكيك أي قيمة كبيرة عبر إزالة الحد الفيبوناتشي الأكبر مرة بعد مرة.
تنص مبرهنة Zeckendorf على أن كل عدد صحيح موجب يملك تمثيلاً وحيداً بوصفه مجموع حدود غير متجاورة من المتتالية \(1,2,3,5,\dots\)، وأن الخوارزمية الجشعة المعتادة تنتج هذا التمثيل نفسه.
لذلك فإن \(H(n)\) معرفة دون غموض: إنها أصغر حد في هذا التفكيك الوحيد. فمثلاً
$$18=13+5 \quad\Longrightarrow\quad H(18)=5,$$
وكذلك
$$12=8+3+1 \quad\Longrightarrow\quad H(12)=1.$$
والفكرة الحاسمة هنا أن اختيار أكبر حد \(F_m\) يمنع مباشرة استخدام \(F_{m-1}\) بعده، لأن تمثيل Zeckendorf لا يسمح باستعمال عددين متتاليين من فيبوناتشي.
ثبّت \(m\ge 2\). كل عدد في المجال
$$F_m \le n \lt F_{m+1}$$
يمكن كتابته على الصورة
$$n=F_m+r,\qquad 0\le r \lt F_{m-1},$$
لأن \(F_{m+1}=F_m+F_{m-1}\).
وبعد تثبيت الحد الأكبر \(F_m\)، يصبح الجزء الباقي \(r\) تمثيلاً مستقلاً باستعمال أعداد فيبوناتشي لا تتجاوز \(F_{m-2}\). لذلك نحصل على
$$H(F_m)=F_m,$$
ولكل \(1\le r \lt F_{m-1}\) يكون
$$H(F_m+r)=H(r).$$
وهكذا تتكون الكتلة \([F_m,F_{m+1}-1]\) من نقطة خاصة واحدة هي \(F_m\)، ثم نسخة مزاحة من القيم \(H(1),H(2),\dots,H(F_{m-1}-1)\).
لنعرّف
$$P_m = G(F_m-1).$$
وأول قيمتين هما
$$P_1=G(0)=0,\qquad P_2=G(1)=1.$$
ومن بنية الكتلة السابقة نحصل على
$$\sum_{n=F_m}^{F_{m+1}-1} H(n)=F_m+\sum_{r=1}^{F_{m-1}-1} H(r)=F_m+P_{m-1}.$$
إذن تتحقق العلاقة
$$P_{m+1}=P_m+F_m+P_{m-1}\qquad (m\ge 2).$$
وهذه هي العلاقة المركزية التي يعتمد عليها التنفيذ من أجل حساب قيم \(G(F_m-1)\) عند جميع حدود فيبوناتشي المطلوبة.
خذ الآن قيمة عامة \(x\)، واختر أكبر عدد فيبوناتشي \(F_m\) يحقق \(F_m\le x\). عندها
$$G(x)=G(F_m-1)+\sum_{n=F_m}^{x} H(n).$$
وبكتابة \(n=F_m+r\)، يعطينا التحليل نفسه
$$\sum_{n=F_m}^{x} H(n)=F_m+\sum_{r=1}^{x-F_m} H(r)=F_m+G(x-F_m).$$
ومن ثم
$$\boxed{G(x)=P_m+F_m+G(x-F_m).}$$
كل تطبيق لهذه الصيغة يزيل حداً واحداً من تمثيل \(x\) وفق Zeckendorf. وإذا كان
$$x=F_{i_1}+F_{i_2}+\cdots+F_{i_t},$$
فإن التوسيع الكامل يعطي
$$G(x)=\sum_{j=1}^{t}\bigl(P_{i_j}+F_{i_j}\bigr).$$
نقطة فحص مفيدة هي \(x=13\)، لأن التنفيذ يتحقق من أن \(G(13)=43\).
من العلاقة العودية نحصل على
$$\begin{aligned} P_1&=0,\\ P_2&=1,\\ P_3&=P_2+F_2+P_1=1+2+0=3,\\ P_4&=P_3+F_3+P_2=3+3+1=7,\\ P_5&=P_4+F_4+P_3=7+5+3=15,\\ P_6&=P_5+F_5+P_4=15+8+7=30. \end{aligned}$$
وبما أن \(13=F_6\)، فإن الخطوة 4 تعطي مباشرة
$$G(13)=P_6+F_6+G(0)=30+13=43.$$
ويمكن رؤية النتيجة نفسها مباشرة من القيم الأولى
$$H(1),\dots,H(13)=1,2,3,1,5,1,2,8,1,2,3,1,13,$$
ومجموعها يساوي أيضاً \(43\).
تتبع تطبيقات C++ وPython وJava البنية نفسها. أولاً تُبنى جميع أعداد فيبوناتشي حتى القيمة الهدف \(n\) ضمن الأساس \(1,2,3,5,\dots\). ثم تُحسب القيم الحدّية \(P_m=G(F_m-1)\) مسبقاً باستعمال العلاقة
$$P_{m+1}=P_m+F_m+P_{m-1}.$$
بعد ذلك تحتفظ الخوارزمية بباقٍ حالي \(x\). في كل دورة، تحدد الشيفرة بواسطة بحث ثنائي أكبر عدد فيبوناتشي لا يتجاوز \(x\)، ثم تضيف المساهمة
$$P_m+F_m,$$
وتستبدل \(x\) بالقيمة \(x-F_m\). وهذا يطابق تماماً صيغة الاختزال في الخطوة 4. وعندما يصل الباقي إلى \(0\)، يكون المجموع المتراكم هو القيمة المطلوبة \(G(n)\).
لذلك فالبنية العامة للشيفرة بسيطة جداً: جدول قصير لأعداد فيبوناتشي، وجدول قصير للمجاميع الحدّية، وحلقة تمر على حدود تمثيل Zeckendorf للعدد الهدف.
ليكن \(t\) عدد أعداد فيبوناتشي التي لا تتجاوز \(n\). بما أن هذه الأعداد تنمو نمواً أسيّاً، فإن \(t=\Theta(\log n)\).
بناء جدول فيبوناتشي وجدول الحدود يكلف \(O(t)\) زمناً و\(O(t)\) ذاكرة. وفي مرحلة التقييم تُزال قيمة فيبوناتشي واحدة في كل دورة، لذا لا يزيد عدد الدورات على \(t\). وبما أن التنفيذ الحالي يستخدم بحثاً ثنائياً في كل دورة داخل جدول فيبوناتشي، فإن زمن الاستعلام هو \(O(t\log t)\)، أي
$$O(\log n\log\log n)$$
زمنياً مع ذاكرة \(O(\log n)\). عملياً يبقى الجدول قصيراً جداً، ولذلك يكون السلوك قريباً من الزمن اللوغاريتمي.