The problem asks for the number of ways to write \(10^{25}\) as a sum of powers of 2 when each power may be used at most twice. Equivalently, we want the number of digit strings \((c_0,c_1,c_2,\dots)\) with
$$10^{25}=\sum_{i\ge 0} c_i2^i,\qquad c_i\in\{0,1,2\}.$$
This is a bounded binary expansion problem, often called a hyperbinary representation problem. Ordinary binary expansion is unique because the digits are restricted to \(\{0,1\}\); here the digit 2 is also allowed, so uniqueness disappears and the task becomes a counting question.
Let \(F(n)\) denote the number of admissible representations of a nonnegative integer \(n\) in the form
$$n=\sum_{i\ge 0} c_i2^i,\qquad c_i\in\{0,1,2\}.$$
The implementations solve the problem entirely through a parity-based recurrence. The important point is that after the lowest coefficient is fixed, the rest of the expression has exactly the same shape as the original problem.
Every valid representation is determined by choosing how many copies of \(1,2,4,8,\dots\) appear, with each count limited to 0, 1, or 2. Since only finitely many powers can contribute to a fixed \(n\), this is a finite combinatorial object even though the summation index is written as \(i\ge 0\).
The crucial invariant is that if we peel off the contribution of \(2^0\), then every remaining term is divisible by 2. Dividing by 2 simply shifts the coefficient sequence one position to the right, and the new coefficients are still in the same set \(\{0,1,2\}\). That self-similarity is exactly what makes the recurrence so short.
The parity of \(n\) is determined entirely by the coefficient \(c_0\), because all higher powers of 2 are even.
If \(n\) is odd, then \(c_0\) must be 1. There is no other possibility: \(c_0=0\) or \(c_0=2\) would make the whole sum even. So every odd representation has the form
$$n=1+2\sum_{i\ge 0} d_i2^i,$$
where \(d_i=c_{i+1}\in\{0,1,2\}\). After subtracting 1 and dividing by 2, we obtain a bijection with representations of \((n-1)/2\). Therefore, for odd \(n\),
$$F(n)=F\left(\frac{n-1}{2}\right).$$
If \(n\) is even, then \(c_0\) cannot be 1. The only legal choices are \(c_0=0\) and \(c_0=2\), and they lead to two disjoint families of representations.
When \(n\) is even and \(c_0=0\), the representation looks like
$$n=2\sum_{i\ge 0} d_i2^i,$$
so dividing by 2 gives a valid representation of \(n/2\). Conversely, any representation of \(n/2\) can be doubled to recover a representation of \(n\) with \(c_0=0\).
When \(n\) is even and \(c_0=2\), the representation looks like
$$n=2+2\sum_{i\ge 0} d_i2^i,$$
so after subtracting 2 and dividing by 2 we obtain a valid representation of \(n/2-1\). Again this is a bijection: every representation of \(n/2-1\) lifts uniquely to a representation of \(n\) with two copies of \(2^0\).
Because these two families are exhaustive and disjoint, even inputs satisfy
$$F(n)=F\left(\frac n2\right)+F\left(\frac n2-1\right).$$
The empty sum gives the unique representation of 0, so
$$F(0)=1.$$
It is also convenient to define
$$F(-1)=0,$$
so that the even case remains valid all the way down to \(n=0\) without extra branching. The complete recurrence is therefore
$$ F(n)= \begin{cases} 1, & n=0,\\ 0, & n=-1,\\ F\left(\frac{n-1}{2}\right), & n\ge 1,\ n\equiv 1 \pmod 2,\\ F\left(\frac n2\right)+F\left(\frac n2-1\right), & n\ge 2,\ n\equiv 0 \pmod 2. \end{cases} $$
This formula is the whole mathematics used by the implementations. There is no search over partitions and no explicit generation of representations of \(10^{25}\).
The recurrence immediately gives
$$F(10)=F(5)+F(4).$$
Since \(5\) is odd, \(F(5)=F(2)\). Since \(2\) is even, \(F(2)=F(1)+F(0)=1+1=2\). Also,
$$F(4)=F(2)+F(1)=2+1=3.$$
Hence \(F(10)=2+3=5\).
The five actual representations are
$$10=8+2=8+1+1=4+4+2=4+4+1+1=4+2+2+1+1.$$
This example also illustrates the recurrence structurally. The two representations of 5, namely \(5=4+1\) and \(5=2+2+1\), become the two representations of 10 with \(c_0=0\) after doubling. The three representations of 4, namely \(4=4\), \(4=2+2\), and \(4=2+1+1\), become the three representations of 10 with \(c_0=2\) after doubling and then adding two copies of 1.
The C++, Python, and Java implementations all store previously computed values of \(F(n)\) in a memo table. Each call first checks whether the current argument has already been solved. If so, the stored value is reused immediately. Otherwise, the implementation inspects the parity of \(n\): odd inputs make one recursive call, and even inputs make two recursive calls. After the value is computed once, it is inserted into the memo table.
The initial memo table contains the two boundary values \(F(0)=1\) and \(F(-1)=0\). That choice keeps the recursive logic uniform and prevents awkward special cases near the bottom of the recursion tree.
The target input is \(10^{25}\), which is far beyond ordinary 32-bit arithmetic. The implementations therefore use arbitrary-precision integer support where the language needs it, while Python relies on its built-in big integers. The arithmetic performed on this large input is still very mild: parity tests, subtraction by 1 or 2, and right shifts by one bit.
The C++ implementation also includes small checkpoint evaluations, such as \(F(10)=5\) and \(F(5)=2\), before processing the full target. Those checks verify that the recurrence and the memoization logic agree with known small cases.
Every recursive step removes the lowest binary digit of the current argument, because the next state is either \((n-1)/2\), \(n/2\), or \(n/2-1\). As a result, the depth of the recursion is proportional to the number of bits of \(n\).
With memoization, each distinct state is evaluated only once, and the reachable state graph remains very small compared with \(n\) itself. In practice the running time is proportional to the number of memoized states, which grows on the order of the bit-length of the input, so the algorithm is effectively \(O(\log n)\) states and \(O(\log n)\) memory. The important qualitative fact is that the implementation scales with the number of binary digits of \(n\), not with the enormous magnitude of \(10^{25}\).
Gesucht ist die Anzahl der Möglichkeiten, \(10^{25}\) als Summe von Zweierpotenzen zu schreiben, wobei jede Potenz höchstens zweimal vorkommen darf. Äquivalent zählen wir Folgen \((c_0,c_1,c_2,\dots)\) mit
$$10^{25}=\sum_{i\ge 0} c_i2^i,\qquad c_i\in\{0,1,2\}.$$
Man kann das als beschränkte Binärdarstellung auffassen. Bei der gewöhnlichen Binärdarstellung sind nur die Ziffern 0 und 1 erlaubt, daher ist die Darstellung eindeutig. Hier ist auch die Ziffer 2 erlaubt, also verschwindet die Eindeutigkeit und das Problem wird zu einer reinen Zählaufgabe.
Sei \(F(n)\) die Anzahl aller zulässigen Darstellungen eines nichtnegativen Integers \(n\) in der Form
$$n=\sum_{i\ge 0} c_i2^i,\qquad c_i\in\{0,1,2\}.$$
Die gesamte Lösung beruht auf einer Rekursion, die nur von der Parität abhängt. Der entscheidende Invariant ist: Sobald der Koeffizient vor \(2^0\) festliegt, hat der restliche Ausdruck nach dem Halbieren wieder exakt dieselbe Struktur wie das Ausgangsproblem.
Jede gültige Darstellung wird dadurch beschrieben, wie oft \(1,2,4,8,\dots\) benutzt werden, wobei jede dieser Häufigkeiten nur 0, 1 oder 2 sein darf. Für festes \(n\) tragen nur endlich viele Potenzen überhaupt bei, daher ist das ein endliches kombinatorisches Objekt.
Der wichtige Selbstähnlichkeitsgedanke lautet: Entfernt man den Beitrag von \(2^0\), dann sind alle übrigen Summanden durch 2 teilbar. Durch Division durch 2 verschieben sich die Koeffizienten nur um eine Stelle, bleiben aber weiterhin in \(\{0,1,2\}\). Genau daraus entsteht die kurze Rekursion.
Die Parität von \(n\) wird vollständig durch \(c_0\) bestimmt, denn alle höheren Zweierpotenzen sind gerade.
Ist \(n\) ungerade, dann muss \(c_0=1\) gelten. Die Werte 0 oder 2 würden die gesamte Summe gerade machen. Also hat jede Darstellung einer ungeraden Zahl die Form
$$n=1+2\sum_{i\ge 0} d_i2^i,$$
wobei \(d_i=c_{i+1}\in\{0,1,2\}\). Nach Subtraktion von 1 und Division durch 2 erhält man eine bijektive Zuordnung zu den Darstellungen von \((n-1)/2\). Damit gilt für ungerades \(n\)
$$F(n)=F\left(\frac{n-1}{2}\right).$$
Ist \(n\) dagegen gerade, dann kann \(c_0\) nicht 1 sein. Zulässig bleiben nur \(c_0=0\) und \(c_0=2\), und genau diese beiden Möglichkeiten liefern zwei disjunkte Familien von Darstellungen.
Im geraden Fall mit \(c_0=0\) hat die Darstellung die Form
$$n=2\sum_{i\ge 0} d_i2^i.$$
Nach Division durch 2 bleibt also eine zulässige Darstellung von \(n/2\). Umgekehrt wird jede Darstellung von \(n/2\) durch Verdoppeln zu einer Darstellung von \(n\) mit \(c_0=0\).
Im geraden Fall mit \(c_0=2\) hat die Darstellung die Form
$$n=2+2\sum_{i\ge 0} d_i2^i.$$
Nach Subtraktion von 2 und anschließender Division durch 2 entsteht deshalb eine zulässige Darstellung von \(n/2-1\). Auch hier liegt eine Bijektion vor: Jede Darstellung von \(n/2-1\) hebt sich eindeutig zu einer Darstellung von \(n\) mit zwei Exemplaren von \(2^0\).
Weil diese beiden Familien vollständig und disjunkt sind, gilt für gerade Eingaben
$$F(n)=F\left(\frac n2\right)+F\left(\frac n2-1\right).$$
Die leere Summe ist die einzige Darstellung von 0, also
$$F(0)=1.$$
Zusätzlich ist es nützlich,
$$F(-1)=0$$
zu setzen. Dann bleibt der gerade Fall auch nahe bei 0 ohne Sonderbehandlung korrekt. Insgesamt erhält man
$$ F(n)= \begin{cases} 1, & n=0,\\ 0, & n=-1,\\ F\left(\frac{n-1}{2}\right), & n\ge 1,\ n\equiv 1 \pmod 2,\\ F\left(\frac n2\right)+F\left(\frac n2-1\right), & n\ge 2,\ n\equiv 0 \pmod 2. \end{cases} $$
Mehr Mathematik verwenden die Implementierungen nicht. Es wird nichts explizit erzeugt; die Zahl der Darstellungen fällt direkt aus dieser Rekursion heraus.
Aus der Rekursion folgt sofort
$$F(10)=F(5)+F(4).$$
Weil \(5\) ungerade ist, gilt \(F(5)=F(2)\). Und weil \(2\) gerade ist, folgt \(F(2)=F(1)+F(0)=1+1=2\). Außerdem ist
$$F(4)=F(2)+F(1)=2+1=3.$$
Somit ergibt sich \(F(10)=2+3=5\).
Die fünf Darstellungen lauten
$$10=8+2=8+1+1=4+4+2=4+4+1+1=4+2+2+1+1.$$
Hier sieht man die Rekursion auch konstruktiv. Die beiden Darstellungen von 5, also \(5=4+1\) und \(5=2+2+1\), werden durch Verdoppeln zu den beiden Darstellungen von 10 mit \(c_0=0\). Die drei Darstellungen von 4, nämlich \(4=4\), \(4=2+2\) und \(4=2+1+1\), werden durch Verdoppeln und anschließendes Hinzufügen von zwei Einsen zu den drei Darstellungen von 10 mit \(c_0=2\).
Die Implementierungen in C++, Python und Java speichern bereits berechnete Werte von \(F(n)\) in einer Memo-Tabelle. Bei jedem Aufruf wird zuerst geprüft, ob das aktuelle Argument schon bekannt ist. Falls ja, wird der gespeicherte Wert sofort zurückgegeben. Andernfalls entscheidet die Parität: Für ungerade Zahlen gibt es genau einen rekursiven Aufruf, für gerade Zahlen genau zwei. Das Ergebnis wird anschließend in der Tabelle abgelegt.
Die Anfangstabelle enthält die beiden Randwerte \(F(0)=1\) und \(F(-1)=0\). Dadurch bleibt die Rekursionslogik elegant und einheitlich.
Der Zielwert ist \(10^{25}\) und passt damit nicht in gewöhnliche 32-Bit-Arithmetik. Deshalb verwenden die Implementierungen dort, wo es sprachabhängig nötig ist, Ganzzahlen mit beliebiger Präzision; Python bringt diese Fähigkeit bereits mit. Trotz der Größe des Eingabewerts sind die tatsächlichen Operationen sehr einfach: Paritätstest, Subtraktion von 1 oder 2 und Halbierung per Bitverschiebung.
Die C++-Version überprüft zusätzlich kleine Kontrollwerte wie \(F(10)=5\) und \(F(5)=2\), bevor sie den großen Zielwert auswertet. So wird bestätigt, dass Rekursion und Memoisierung die bekannten kleinen Fälle korrekt wiedergeben.
Jeder Rekursionsschritt entfernt im Wesentlichen die niederwertigste Binärstelle des aktuellen Arguments, denn der nächste Zustand ist \((n-1)/2\), \(n/2\) oder \(n/2-1\). Deshalb ist die Rekursionstiefe proportional zur Bitlänge von \(n\).
Durch Memoisierung wird jeder tatsächlich erreichte Zustand nur einmal ausgewertet, und der entstehende Zustandsgraph bleibt im Vergleich zur Größe von \(n\) sehr klein. Praktisch ist die Laufzeit proportional zur Zahl der gespeicherten Zustände, also von der Größenordnung der Bitlänge des Eingabewerts. Man kann den Aufwand daher als effektiv \(O(\log n)\) Zustände und \(O(\log n)\) Speicher beschreiben. Entscheidend ist: Der Algorithmus skaliert mit der Anzahl der Binärstellen, nicht mit der riesigen Größenordnung von \(10^{25}\).
İstenen şey, \(10^{25}\) sayısının 2 kuvvetlerinin toplamı olarak kaç farklı biçimde yazılabildiğini bulmaktır; ancak her kuvvet en fazla iki kez kullanılabilir. Başka bir deyişle,
$$10^{25}=\sum_{i\ge 0} c_i2^i,\qquad c_i\in\{0,1,2\}$$
eşitliğini sağlayan tüm katsayı dizilerini sayıyoruz. Bu, sıradan ikili gösterimin kısıtlı ama tekil olmayan bir çeşididir. Normal ikili yazımda rakamlar sadece 0 ve 1 olduğu için gösterim tektir; burada 2 rakamı da serbest olduğu için aynı sayı birden fazla biçimde yazılabilir.
\(F(n)\), \(n\) sayısının
$$n=\sum_{i\ge 0} c_i2^i,\qquad c_i\in\{0,1,2\}$$
şeklindeki geçerli temsillerinin sayısı olsun. Çözüm tamamen pariteye dayalı kısa bir rekürans üzerine kuruludur. Asıl fikir şu: \(2^0\) katsayısını belirledikten sonra kalan toplam, ikiye bölündüğünde yine aynı tipte bir probleme dönüşür.
Her geçerli temsil, \(1,2,4,8,\dots\) terimlerinden her birinin kaç kez kullanıldığını belirler ve bu kullanım sayısı yalnızca 0, 1 veya 2 olabilir. Sabit bir \(n\) için yalnızca sonlu sayıda kuvvet katkı verdiğinden, bu gerçekten sonlu bir kombinatorik nesnedir.
Kilit değişmez şudur: \(2^0\) terimini ayırdıktan sonra kalan bütün terimler 2'ye bölünür. İkiye bölme işlemi katsayıları sadece bir basamak sağa kaydırır; katsayı kümesi yine \(\{0,1,2\}\) olarak kalır. Reküransın bu kadar kısa olmasının nedeni tam olarak bu öz-benzerliktir.
\(n\)'in tek mi çift mi olduğu yalnızca \(c_0\) katsayısına bağlıdır; çünkü daha yüksek bütün 2 kuvvetleri çifttir.
\(n\) tek ise \(c_0\) zorunlu olarak 1 olmalıdır. \(c_0=0\) ya da \(c_0=2\) seçimi toplamı çift yapar. O halde tek bir sayının her gösterimi
$$n=1+2\sum_{i\ge 0} d_i2^i$$
biçimindedir; burada \(d_i=c_{i+1}\in\{0,1,2\}\). 1 çıkarıp 2'ye böldüğümüzde \((n-1)/2\)'nin aynı türden bir temsiline bire bir karşılık elde ederiz. Dolayısıyla tek \(n\) için
$$F(n)=F\left(\frac{n-1}{2}\right)$$
olur.
\(n\) çift ise \(c_0=1\) mümkün değildir. Bu kez yalnızca iki seçenek kalır: \(c_0=0\) ve \(c_0=2\). Bunlar da birbirinden ayrık iki temsil ailesi üretir.
\(n\) çift ve \(c_0=0\) ise temsil
$$n=2\sum_{i\ge 0} d_i2^i$$
şeklindedir. Dolayısıyla 2'ye bölünce doğrudan \(n/2\)'nin geçerli bir temsili kalır. Tersi de doğrudur: \(n/2\)'nin her temsili ikiyle çarpılarak \(n\)'in \(c_0=0\) olan bir temsiline döner.
\(n\) çift ve \(c_0=2\) ise temsil
$$n=2+2\sum_{i\ge 0} d_i2^i$$
biçimindedir. Önce 2 çıkarıp sonra 2'ye bölersek \(n/2-1\)'in geçerli bir temsiline ulaşırız. Yine bire bir eşleme vardır: \(n/2-1\)'in her temsili, ikiyle çarpılıp iki adet 1 eklenerek \(n\)'in \(c_0=2\) olan tek bir temsiline yükselir.
Bu iki aile hem bütün olasılıkları kapsadığı hem de çakışmadığı için çift girdilerde
$$F(n)=F\left(\frac n2\right)+F\left(\frac n2-1\right)$$
elde edilir.
Boş toplam, 0'ın tek temsilidir; bu yüzden
$$F(0)=1.$$
Ayrıca
$$F(-1)=0$$
tanımını yapmak kullanışlıdır. Böylece rekürans alt seviyelerde ek özel durumlara ihtiyaç duymadan çalışır. Sonuç olarak tam formül
$$ F(n)= \begin{cases} 1, & n=0,\\ 0, & n=-1,\\ F\left(\frac{n-1}{2}\right), & n\ge 1,\ n\equiv 1 \pmod 2,\\ F\left(\frac n2\right)+F\left(\frac n2-1\right), & n\ge 2,\ n\equiv 0 \pmod 2 \end{cases} $$
olur. Uygulamaların kullandığı matematik tam olarak budur; \(10^{25}\)'in temsilleri tek tek üretilmez.
Rekürans doğrudan
$$F(10)=F(5)+F(4)$$
verir. \(5\) tek olduğu için \(F(5)=F(2)\). \(2\) çift olduğundan \(F(2)=F(1)+F(0)=1+1=2\). Ayrıca
$$F(4)=F(2)+F(1)=2+1=3.$$
Böylece \(F(10)=2+3=5\) bulunur.
Bu beş temsil açıkça şunlardır:
$$10=8+2=8+1+1=4+4+2=4+4+1+1=4+2+2+1+1.$$
Örnek, reküransın yapısını da gösterir. \(5\)'in iki temsili olan \(5=4+1\) ve \(5=2+2+1\), ikiyle çarpılınca \(10\)'un \(c_0=0\) olan iki temsiline dönüşür. \(4\)'ün üç temsili olan \(4=4\), \(4=2+2\) ve \(4=2+1+1\) ise önce ikiyle çarpılıp sonra iki adet 1 eklenince \(10\)'un \(c_0=2\) olan üç temsiline dönüşür.
C++, Python ve Java uygulamaları, daha önce hesaplanmış \(F(n)\) değerlerini bir bellek tablosunda tutar. Her yeni çağrıda önce bu tabloda kayıt olup olmadığına bakılır. Varsa değer doğrudan kullanılır. Yoksa \(n\)'in paritesi incelenir: tekse tek bir alt çağrı, çiftse iki alt çağrı yapılır. Hesaplanan sonuç daha sonra tabloya eklenir.
Başlangıçta tabloda \(F(0)=1\) ve \(F(-1)=0\) bulunur. Bu tercih, özellikle küçük değerlere inerken reküransı sade ve düzgün tutar.
Hedef değer \(10^{25}\) olduğundan sıradan küçük tamsayı tipleri yeterli değildir. Bu nedenle uygulamalar, dilin gerektirdiği yerlerde keyfi uzunlukta tamsayı desteği kullanır; Python bunu zaten yerleşik olarak sağlar. Buna rağmen yapılan işlemler son derece hafiftir: tek-çift testi, 1 veya 2 çıkarma ve bir bit sağa kaydırma.
C++ sürümü, büyük hedefi çözmeden önce \(F(10)=5\) ve \(F(5)=2\) gibi küçük kontrol noktalarını da doğrular. Böylece reküransla memoization mantığının bilinen küçük örneklerle uyumlu olduğu sınanır.
Her rekürans adımı mevcut sayının en düşük anlamlı ikili basamağını fiilen atar; çünkü sonraki durum \((n-1)/2\), \(n/2\) veya \(n/2-1\) biçimindedir. Bu yüzden rekürans derinliği \(n\)'in bit uzunluğu ile orantılıdır.
Memoization sayesinde her farklı durum en fazla bir kez çözülür ve erişilen durum grafiği \(n\)'in büyüklüğüne göre son derece incedir. Pratikte çalışma süresi, saklanan durum sayısı ile orantılıdır; bu da girdinin bit sayısı mertebesindedir. Bu nedenle yöntem etkin biçimde \(O(\log n)\) durum ve \(O(\log n)\) bellek kullanır. Buradaki esas nokta şudur: maliyet \(10^{25}\)'in büyüklüğüyle değil, bu sayının ikili yazımındaki basamak sayısıyla ölçeklenir.
Hay que contar cuántas formas existen de escribir \(10^{25}\) como suma de potencias de 2, con la restricción de que cada potencia puede usarse como máximo dos veces. En otras palabras, se buscan todas las sucesiones \((c_0,c_1,c_2,\dots)\) tales que
$$10^{25}=\sum_{i\ge 0} c_i2^i,\qquad c_i\in\{0,1,2\}.$$
Esto puede verse como una expansión binaria acotada. La expansión binaria ordinaria es única porque solo admite dígitos 0 y 1; aquí también se permite el dígito 2, así que la unicidad desaparece y el problema pasa a ser puramente de conteo.
Sea \(F(n)\) el número de representaciones válidas de un entero no negativo \(n\) de la forma
$$n=\sum_{i\ge 0} c_i2^i,\qquad c_i\in\{0,1,2\}.$$
Toda la solución se apoya en una recurrencia muy corta gobernada por la paridad. La idea central es que, una vez fijado el coeficiente de \(2^0\), el resto del sumando conserva exactamente la misma estructura después de dividir entre 2.
Cada representación válida especifica cuántas copias de \(1,2,4,8,\dots\) aparecen, y cada cantidad solo puede ser 0, 1 o 2. Como para un \(n\) fijo solo intervienen finitamente muchas potencias, estamos ante un objeto combinatorio finito.
El invariante decisivo es el siguiente: si se separa la contribución de \(2^0\), todos los términos restantes son divisibles por 2. Al dividir por 2, la secuencia de coeficientes simplemente se desplaza una posición y sigue perteneciendo al mismo conjunto \(\{0,1,2\}\). Esa auto-semejanza es la fuente directa de la recurrencia.
La paridad de \(n\) depende por completo de \(c_0\), porque todas las potencias superiores de 2 son pares.
Si \(n\) es impar, entonces necesariamente \(c_0=1\). Los valores \(0\) y \(2\) harían que toda la suma fuese par. Así, toda representación de un número impar tiene la forma
$$n=1+2\sum_{i\ge 0} d_i2^i,$$
donde \(d_i=c_{i+1}\in\{0,1,2\}\). Al restar 1 y dividir entre 2 obtenemos una biyección con las representaciones de \((n-1)/2\). Por tanto, para \(n\) impar,
$$F(n)=F\left(\frac{n-1}{2}\right).$$
Si \(n\) es par, entonces \(c_0\) no puede ser 1. Solo quedan \(c_0=0\) y \(c_0=2\), y esas dos posibilidades producen dos familias disjuntas de representaciones.
Cuando \(n\) es par y \(c_0=0\), la representación tiene la forma
$$n=2\sum_{i\ge 0} d_i2^i.$$
Dividir entre 2 deja entonces una representación válida de \(n/2\). A la inversa, cualquier representación de \(n/2\) puede duplicarse para reconstruir una representación de \(n\) con \(c_0=0\).
Cuando \(n\) es par y \(c_0=2\), la representación tiene la forma
$$n=2+2\sum_{i\ge 0} d_i2^i.$$
Al restar 2 y dividir entre 2 obtenemos una representación válida de \(n/2-1\). También aquí hay una biyección: cada representación de \(n/2-1\) se eleva de manera única a una representación de \(n\) con dos copias de \(2^0\).
Como ambas familias son exhaustivas y no se solapan, para entradas pares se cumple
$$F(n)=F\left(\frac n2\right)+F\left(\frac n2-1\right).$$
La suma vacía da la única representación de 0, de modo que
$$F(0)=1.$$
Además, resulta útil definir
$$F(-1)=0,$$
para que el caso par siga siendo correcto hasta el fondo de la recursión sin introducir ramas especiales. La fórmula completa queda así:
$$ F(n)= \begin{cases} 1, & n=0,\\ 0, & n=-1,\\ F\left(\frac{n-1}{2}\right), & n\ge 1,\ n\equiv 1 \pmod 2,\\ F\left(\frac n2\right)+F\left(\frac n2-1\right), & n\ge 2,\ n\equiv 0 \pmod 2. \end{cases} $$
Esa es exactamente la matemática usada por las implementaciones. No se enumeran particiones ni se generan explícitamente las representaciones de \(10^{25}\).
La recurrencia da inmediatamente
$$F(10)=F(5)+F(4).$$
Como \(5\) es impar, \(F(5)=F(2)\). Y como \(2\) es par, \(F(2)=F(1)+F(0)=1+1=2\). Además,
$$F(4)=F(2)+F(1)=2+1=3.$$
Por lo tanto, \(F(10)=2+3=5\).
Las cinco representaciones concretas son
$$10=8+2=8+1+1=4+4+2=4+4+1+1=4+2+2+1+1.$$
El ejemplo también explica la estructura de la recurrencia. Las dos representaciones de 5, \(5=4+1\) y \(5=2+2+1\), al duplicarse producen las dos representaciones de 10 con \(c_0=0\). Las tres representaciones de 4, \(4=4\), \(4=2+2\) y \(4=2+1+1\), al duplicarse y añadir después dos unos, producen las tres representaciones de 10 con \(c_0=2\).
Las implementaciones en C++, Python y Java guardan en una tabla los valores de \(F(n)\) ya calculados. Cada llamada comienza consultando esa tabla. Si el valor ya está disponible, se reutiliza de inmediato. Si no, la implementación mira si \(n\) es impar o par: en el caso impar hace una sola llamada recursiva, y en el caso par hace dos. Después almacena el resultado recién obtenido.
La tabla inicial contiene \(F(0)=1\) y \(F(-1)=0\). Esa decisión mantiene uniforme la lógica recursiva y evita condiciones especiales incómodas cerca del final.
La entrada objetivo es \(10^{25}\), demasiado grande para la aritmética entera pequeña. Por eso las implementaciones emplean soporte de enteros de precisión arbitraria allí donde el lenguaje lo necesita, mientras que Python utiliza sus enteros grandes incorporados. Aun así, las operaciones sobre ese valor son suaves: pruebas de paridad, restas de 1 o 2, y desplazamientos de un bit.
La implementación en C++ también incluye comprobaciones pequeñas, como \(F(10)=5\) y \(F(5)=2\), antes de evaluar el objetivo completo. Esas verificaciones confirman que la recurrencia y la memoización coinciden con casos conocidos.
Cada paso recursivo elimina esencialmente el bit menos significativo del argumento actual, porque el siguiente estado es \((n-1)/2\), \(n/2\) o \(n/2-1\). Por eso la profundidad de la recursión es proporcional al número de bits de \(n\).
Con memoización, cada estado distinto se evalúa una sola vez, y el grafo de estados alcanzables es minúsculo comparado con el propio valor de \(n\). En la práctica, el tiempo de ejecución es proporcional al número de estados memorizados, que crece en el orden de la longitud binaria de la entrada. En ese sentido, el algoritmo usa de forma efectiva \(O(\log n)\) estados y \(O(\log n)\) memoria. Lo importante es que el costo crece con el número de bits, no con la magnitud gigantesca de \(10^{25}\).
题目要求计算：把 \(10^{25}\) 写成若干个 2 的幂之和时，一共有多少种不同写法，并且每个幂次最多只能使用两次。换句话说，我们要统计所有满足
$$10^{25}=\sum_{i\ge 0} c_i2^i,\qquad c_i\in\{0,1,2\}$$
的系数序列。这可以看成一种“受限二进制展开”。普通二进制展开之所以唯一，是因为每一位只能取 0 或 1；本题还允许取 2，因此同一个整数就可能对应多种不同的展开方式。
记 \(F(n)\) 为非负整数 \(n\) 的所有合法表示个数，其中合法表示指
$$n=\sum_{i\ge 0} c_i2^i,\qquad c_i\in\{0,1,2\}.$$
这道题的全部数学核心就是一个按奇偶性分裂的递推。最关键的观察在于：一旦最低位系数 \(c_0\) 被确定，剩下的部分在除以 2 之后又回到了完全同型的问题。
每一个合法表示都对应着这样一个选择：\(1,2,4,8,\dots\) 这些幂各自用了几次，而每个使用次数只能是 0、1 或 2。对于固定的 \(n\)，真正能出现的幂次只有有限个，所以这不是无限展开上的分析问题，而是一个有限的计数问题。
真正起作用的不变量是：把 \(2^0\) 这一项单独拿出来以后，其余所有项都含有因子 2。于是把余下部分整体除以 2，只会让系数序列整体右移一位，而新的系数仍然落在同一个集合 \(\{0,1,2\}\) 中。正是这个自相似结构，使得递推关系极其紧凑。
\(n\) 的奇偶性完全由 \(c_0\) 决定，因为更高次的所有 \(2^i\) 都是偶数。
如果 \(n\) 是奇数，那么 \(c_0\) 只能等于 1。因为如果 \(c_0=0\) 或 \(c_0=2\)，整个和一定是偶数。因此，任意一个奇数表示都可以写成
$$n=1+2\sum_{i\ge 0} d_i2^i,$$
其中 \(d_i=c_{i+1}\in\{0,1,2\}\)。把 1 移到左边再整体除以 2，就与 \((n-1)/2\) 的合法表示建立起双射。因此，当 \(n\) 为奇数时，
$$F(n)=F\left(\frac{n-1}{2}\right).$$
如果 \(n\) 是偶数，那么 \(c_0\) 不可能等于 1。这时只剩下两种合法情况：\(c_0=0\) 或 \(c_0=2\)。这两种情况分别对应两类互不重叠的表示。
当 \(n\) 为偶数且 \(c_0=0\) 时，表示一定形如
$$n=2\sum_{i\ge 0} d_i2^i.$$
于是除以 2 后直接得到 \(n/2\) 的一个合法表示。反过来，\(n/2\) 的任意合法表示都可以整体乘以 2，恢复成 \(n\) 的一个 \(c_0=0\) 的表示。
当 \(n\) 为偶数且 \(c_0=2\) 时，表示形如
$$n=2+2\sum_{i\ge 0} d_i2^i.$$
这时先减去 2，再除以 2，就得到 \(n/2-1\) 的一个合法表示。反过来，\(n/2-1\) 的每个合法表示也都能唯一地提升成 \(n\) 的一个 \(c_0=2\) 的表示，也就是把所有幂次整体升一位，并额外加上两个 \(1\)。
因为这两类表示既覆盖了所有偶数情形，又彼此不重合，所以对偶数输入有
$$F(n)=F\left(\frac n2\right)+F\left(\frac n2-1\right).$$
空和是 0 的唯一表示，因此
$$F(0)=1.$$
另外再定义
$$F(-1)=0,$$
就能让偶数分支在递归下降到底部时仍然统一成立，而不用额外写特殊判断。于是完整递推就是
$$ F(n)= \begin{cases} 1, & n=0,\\ 0, & n=-1,\\ F\left(\frac{n-1}{2}\right), & n\ge 1,\ n\equiv 1 \pmod 2,\\ F\left(\frac n2\right)+F\left(\frac n2-1\right), & n\ge 2,\ n\equiv 0 \pmod 2. \end{cases} $$
实现所依赖的数学内容到这里就结束了。程序不会生成 \(10^{25}\) 的所有表示，而是只沿着这个递推不断缩小问题规模。
由递推立刻得到
$$F(10)=F(5)+F(4).$$
因为 \(5\) 是奇数，所以 \(F(5)=F(2)\)。而 \(2\) 是偶数，因此 \(F(2)=F(1)+F(0)=1+1=2\)。再看
$$F(4)=F(2)+F(1)=2+1=3.$$
所以 \(F(10)=2+3=5\)。
这五种表示具体就是
$$10=8+2=8+1+1=4+4+2=4+4+1+1=4+2+2+1+1.$$
这个例子还能把递推结构看得更清楚。5 的两个表示 \(5=4+1\) 与 \(5=2+2+1\)，整体乘以 2 后，正好得到 10 中所有 \(c_0=0\) 的表示。4 的三个表示 \(4=4\)、\(4=2+2\)、\(4=2+1+1\)，整体乘以 2 以后再补上两个 \(1\)，就得到 10 中所有 \(c_0=2\) 的表示。递推并不是抽象的公式，而是对表示集合本身的精确拆分。
C++、Python 和 Java 三个实现都会维护一张记忆表，保存已经算出的 \(F(n)\)。每次要求某个新值时，先查询它是否已经存在；如果存在就直接复用。如果不存在，就根据奇偶性套用上面的递推：奇数只需要递归到一个更小状态，偶数则需要递归到两个更小状态。得到结果后，再把它写回记忆表。
记忆表最开始就放入两个边界值 \(F(0)=1\) 与 \(F(-1)=0\)。这样做的好处是，递归逻辑从头到尾都保持统一，不需要在接近底部时不断加特殊判断。
目标数字是 \(10^{25}\)，显然超出了普通小整数范围。因此，在需要的语言里，程序使用任意精度整数来保存输入；Python 则直接依赖内建的大整数能力。虽然输入本身很大，但程序对它做的操作非常简单，只包括奇偶判断、减去 1 或 2，以及右移一位。
C++ 版本在计算最终目标前，还会先验证几个小型检验点，例如 \(F(10)=5\) 和 \(F(5)=2\)。这能确保递推与记忆化实现和已知小例子完全一致。
每走一步递归，当前参数本质上都会丢掉最低的一位二进制信息，因为下一状态总是 \((n-1)/2\)、\(n/2\) 或 \(n/2-1\) 这三种形式之一。因此，递归深度与 \(n\) 的二进制位数成正比。
有了记忆化以后，每个不同状态只会被计算一次，而真正可达的状态图相对于 \(n\) 的数值大小非常稀薄。实际运行时间因此主要取决于记忆表中状态的个数，这个数量按数量级来说与输入的比特长度相同，所以可以把算法理解为有效的 \(O(\log n)\) 状态和 \(O(\log n)\) 空间。关键结论是：它的代价跟 \(10^{25}\) 有多少个二进制位有关，而不是跟这个天文级数值本身成正比。
Нужно посчитать, сколькими способами можно представить \(10^{25}\) в виде суммы степеней двойки, если каждую степень разрешено использовать не более двух раз. То есть мы считаем все последовательности коэффициентов \((c_0,c_1,c_2,\dots)\), удовлетворяющие равенству
$$10^{25}=\sum_{i\ge 0} c_i2^i,\qquad c_i\in\{0,1,2\}.$$
Это можно рассматривать как ограниченную двоичную запись. Обычная двоичная запись единственна, потому что в ней разрешены только цифры 0 и 1. Здесь добавляется цифра 2, поэтому единственность исчезает и задача превращается в подсчет числа допустимых разложений.
Обозначим через \(F(n)\) число всех допустимых представлений неотрицательного целого \(n\) в виде
$$n=\sum_{i\ge 0} c_i2^i,\qquad c_i\in\{0,1,2\}.$$
Вся математика решения сводится к короткой рекурсии, зависящей только от четности. Главная идея такова: если зафиксировать коэффициент при \(2^0\), то после деления оставшейся части на 2 получается точно такая же задача, только для меньшего числа.
Каждое допустимое представление определяется тем, сколько раз используются числа \(1,2,4,8,\dots\), причем каждое количество может быть только 0, 1 или 2. Для фиксированного \(n\) участвует лишь конечное число степеней двойки, так что перед нами конечный комбинаторный объект.
Ключевой инвариант состоит в следующем: если отделить вклад \(2^0\), то все остальные слагаемые делятся на 2. Деление на 2 просто сдвигает последовательность коэффициентов на одну позицию, а новые коэффициенты по-прежнему лежат в множестве \(\{0,1,2\}\). Именно эта самоподобная структура и порождает рекурсию.
Четность числа \(n\) определяется только коэффициентом \(c_0\), потому что все более высокие степени двойки четны.
Если \(n\) нечетно, то обязательно \(c_0=1\). Значения 0 и 2 сделали бы всю сумму четной. Поэтому всякое представление нечетного числа имеет вид
$$n=1+2\sum_{i\ge 0} d_i2^i,$$
где \(d_i=c_{i+1}\in\{0,1,2\}\). После вычитания 1 и деления на 2 мы получаем биекцию с представлениями числа \((n-1)/2\). Следовательно, для нечетного \(n\)
$$F(n)=F\left(\frac{n-1}{2}\right).$$
Если \(n\) четно, то \(c_0\) уже не может быть равно 1. Остаются ровно два допустимых варианта: \(c_0=0\) и \(c_0=2\). Они образуют две непересекающиеся семьи представлений.
В четном случае с \(c_0=0\) представление имеет вид
$$n=2\sum_{i\ge 0} d_i2^i.$$
Тогда после деления на 2 остается допустимое представление числа \(n/2\). И наоборот, любое представление \(n/2\) можно удвоить и получить представление \(n\) с \(c_0=0\).
В четном случае с \(c_0=2\) имеем
$$n=2+2\sum_{i\ge 0} d_i2^i.$$
После вычитания 2 и деления на 2 получается допустимое представление числа \(n/2-1\). Здесь тоже возникает биекция: каждое представление \(n/2-1\) единственным образом поднимается до представления \(n\) с двумя копиями \(2^0\).
Поскольку эти две семьи исчерпывают все возможности и не пересекаются, для четных чисел выполняется
$$F(n)=F\left(\frac n2\right)+F\left(\frac n2-1\right).$$
Пустая сумма дает единственное представление нуля, поэтому
$$F(0)=1.$$
Также удобно положить
$$F(-1)=0,$$
чтобы четная ветвь оставалась корректной вплоть до самого низа рекурсии без отдельных исключений. В итоге получаем полную формулу
$$ F(n)= \begin{cases} 1, & n=0,\\ 0, & n=-1,\\ F\left(\frac{n-1}{2}\right), & n\ge 1,\ n\equiv 1 \pmod 2,\\ F\left(\frac n2\right)+F\left(\frac n2-1\right), & n\ge 2,\ n\equiv 0 \pmod 2. \end{cases} $$
Это и есть вся математика, используемая в реализациях. Никакие разложения числа \(10^{25}\) явно не строятся.
Сразу получаем
$$F(10)=F(5)+F(4).$$
Так как \(5\) нечетно, имеем \(F(5)=F(2)\). А поскольку \(2\) четно,
$$F(2)=F(1)+F(0)=1+1=2.$$
Кроме того,
$$F(4)=F(2)+F(1)=2+1=3.$$
Следовательно, \(F(10)=2+3=5\).
Пять конкретных представлений таковы:
$$10=8+2=8+1+1=4+4+2=4+4+1+1=4+2+2+1+1.$$
Этот пример полезен и конструктивно. Два представления числа 5, а именно \(5=4+1\) и \(5=2+2+1\), после удвоения становятся двумя представлениями числа 10 с \(c_0=0\). Три представления числа 4, то есть \(4=4\), \(4=2+2\) и \(4=2+1+1\), после удвоения и добавления двух единиц становятся тремя представлениями числа 10 с \(c_0=2\).
Реализации на C++, Python и Java хранят уже найденные значения \(F(n)\) в таблице мемоизации. При каждом новом обращении сначала проверяется, был ли этот аргумент вычислен раньше. Если да, используется сохраненный результат. Если нет, программа смотрит на четность числа: для нечетного аргумента вызывается одна меньшая подзадача, для четного две. После вычисления результат заносится в таблицу.
Изначально в таблице уже лежат значения \(F(0)=1\) и \(F(-1)=0\). Благодаря этому нижняя часть рекурсии остается совершенно однородной.
Целевое число равно \(10^{25}\), так что обычных маленьких целых типов недостаточно. Поэтому там, где это требуется языком, реализации используют целые числа произвольной точности, а Python опирается на встроенные большие целые. При этом сами операции над входом очень просты: проверка четности, вычитание 1 или 2 и сдвиг вправо на один бит.
В версии на C++ перед вычислением основного ответа дополнительно проверяются небольшие контрольные значения, например \(F(10)=5\) и \(F(5)=2\). Это подтверждает корректность рекурсии и мемоизации на известных малых примерах.
Каждый шаг рекурсии по существу убирает младший двоичный разряд текущего аргумента, потому что следующий аргумент всегда имеет вид \((n-1)/2\), \(n/2\) или \(n/2-1\). Поэтому глубина рекурсии пропорциональна числу двоичных разрядов \(n\).
Благодаря мемоизации каждое различное состояние вычисляется только один раз, а граф достижимых состояний оказывается очень маленьким по сравнению с самим значением \(n\). На практике время работы пропорционально числу сохраненных состояний, а это величина порядка длины двоичной записи входа. В этом смысле алгоритм использует эффективно \(O(\log n)\) состояний и \(O(\log n)\) памяти. Главный вывод: стоимость определяется числом битов, а не чудовищной величиной \(10^{25}\).
المطلوب هو حساب عدد الطرق المختلفة لكتابة \(10^{25}\) على صورة مجموع لقوى العدد 2، مع القيد أن كل قوة يمكن استعمالها في أقصى حد مرتين فقط. أي إننا نعد جميع المتتاليات \((c_0,c_1,c_2,\dots)\) التي تحقق
$$10^{25}=\sum_{i\ge 0} c_i2^i,\qquad c_i\in\{0,1,2\}.$$
يمكن النظر إلى هذا بوصفه تمثيلًا ثنائيًا مقيَّدًا. فالتمثيل الثنائي العادي وحيد لأن كل خانة لا تأخذ إلا 0 أو 1، أما هنا فالسماح بالقيمة 2 يزيل هذه الأحادية ويحوّل السؤال إلى مسألة عدّ.
لنرمز بـ \(F(n)\) إلى عدد التمثيلات المسموح بها للعدد الصحيح غير السالب \(n\) على الصورة
$$n=\sum_{i\ge 0} c_i2^i,\qquad c_i\in\{0,1,2\}.$$
كل الحل الرياضي يعتمد على علاقة عودية قصيرة تحددها الفردية والزوجية. الفكرة الأساسية هي أن تثبيت معامل \(2^0\) يجعل ما يبقى من المجموع، بعد القسمة على 2، مسألة من النوع نفسه تمامًا ولكن بحجم أصغر.
كل تمثيل صحيح يحدد عدد المرات التي تُستعمل فيها الحدود \(1,2,4,8,\dots\)، وكل عدد استعمال لا يمكن أن يكون إلا 0 أو 1 أو 2. وبما أن أي \(n\) ثابت لا يحتاج إلا إلى عدد منته من قوى 2، فإننا أمام كائن تركيبي منتهٍ بالفعل.
الثابت المهم هنا هو التالي: إذا عزلنا مساهمة \(2^0\)، فإن جميع الحدود الباقية تكون قابلة للقسمة على 2. وعند القسمة على 2 لا يحدث إلا انتقال معاملات السلسلة خانة واحدة، مع بقاء كل معامل داخل المجموعة نفسها \(\{0,1,2\}\). هذه البنية ذاتية التشابه هي التي تنتج العلاقة العودية مباشرة.
فردية \(n\) أو زوجيته تتحدد بالكامل بواسطة \(c_0\)، لأن كل قوى 2 الأعلى زوجية.
إذا كان \(n\) فرديًا، فلا بد أن يكون \(c_0=1\). فلو كان \(c_0=0\) أو \(c_0=2\) لصار المجموع كله زوجيًا. إذن كل تمثيل لعدد فردي يكتب على الصورة
$$n=1+2\sum_{i\ge 0} d_i2^i,$$
حيث \(d_i=c_{i+1}\in\{0,1,2\}\). وبعد طرح 1 والقسمة على 2 نحصل على تقابل واحد لواحد مع تمثيلات \((n-1)/2\). لذلك عندما يكون \(n\) فرديًا نحصل على
$$F(n)=F\left(\frac{n-1}{2}\right).$$
أما إذا كان \(n\) زوجيًا، فإن \(c_0\) لا يمكن أن يساوي 1. ولا يبقى إلا احتمالان قانونيان: \(c_0=0\) أو \(c_0=2\). وهذان الاحتمالان يعطيان عائلتين منفصلتين من التمثيلات.
عندما يكون \(n\) زوجيًا و\(c_0=0\)، يكون التمثيل من الشكل
$$n=2\sum_{i\ge 0} d_i2^i.$$
وعند القسمة على 2 يتبقى مباشرة تمثيل صحيح للعدد \(n/2\). وبالعكس، فإن كل تمثيل للعدد \(n/2\) يمكن مضاعفته ليعطي تمثيلًا للعدد \(n\) مع \(c_0=0\).
وعندما يكون \(n\) زوجيًا و\(c_0=2\)، يصبح التمثيل
$$n=2+2\sum_{i\ge 0} d_i2^i.$$
وبعد طرح 2 ثم القسمة على 2 نحصل على تمثيل صحيح للعدد \(n/2-1\). وهنا أيضًا يوجد تقابل واحد لواحد: كل تمثيل للعدد \(n/2-1\) يرتفع بصورة وحيدة إلى تمثيل للعدد \(n\) يحتوي على نسختين من \(2^0\).
ولأن هاتين العائلتين تستوعبان كل الحالات الزوجية ولا تتداخلان، فإننا نحصل على
$$F(n)=F\left(\frac n2\right)+F\left(\frac n2-1\right).$$
المجموع الفارغ هو التمثيل الوحيد للصفر، ومن ثم
$$F(0)=1.$$
ومن المفيد أيضًا أن نعرّف
$$F(-1)=0,$$
حتى تبقى الحالة الزوجية صحيحة حتى قاع الاستدعاء العودي من غير فروع خاصة إضافية. وبذلك تصبح الصيغة الكاملة
$$ F(n)= \begin{cases} 1, & n=0,\\ 0, & n=-1,\\ F\left(\frac{n-1}{2}\right), & n\ge 1,\ n\equiv 1 \pmod 2,\\ F\left(\frac n2\right)+F\left(\frac n2-1\right), & n\ge 2,\ n\equiv 0 \pmod 2. \end{cases} $$
هذا هو كل المحتوى الرياضي الذي تستخدمه التطبيقات. لا يجري توليد تمثيلات \(10^{25}\) واحدة تلو الأخرى، بل يُختزل السؤال مباشرة عبر هذه العلاقة.
العلاقة العودية تعطي فورًا
$$F(10)=F(5)+F(4).$$
وبما أن \(5\) فردي، فإن \(F(5)=F(2)\). ولأن \(2\) زوجي، نحصل على
$$F(2)=F(1)+F(0)=1+1=2.$$
وكذلك
$$F(4)=F(2)+F(1)=2+1=3.$$
إذًا \(F(10)=2+3=5\).
والتمثيلات الخمسة الفعلية هي
$$10=8+2=8+1+1=4+4+2=4+4+1+1=4+2+2+1+1.$$
ويشرح هذا المثال أيضًا البنية الداخلية للعلاقة العودية. فتمثيلا العدد 5، أي \(5=4+1\) و\(5=2+2+1\)، يتحولان بعد المضاعفة إلى تمثيلي العدد 10 من النوع الذي فيه \(c_0=0\). أما تمثيلات العدد 4 الثلاثة، وهي \(4=4\) و\(4=2+2\) و\(4=2+1+1\)، فتتحول بعد المضاعفة ثم إضافة وحدتين إلى تمثيلات العدد 10 من النوع الذي فيه \(c_0=2\).
تحتفظ تطبيقات C++ وPython وJava بجدول تخزين مؤقت للقيم التي سبق حسابها من \(F(n)\). كل طلب جديد يبدأ بفحص ما إذا كانت القيمة موجودة سلفًا. إن كانت موجودة يُعاد استخدامها فورًا، وإن لم تكن موجودة تُطبَّق قاعدة الفردي أو الزوجي: حالة واحدة أصغر للأعداد الفردية، وحالتان أصغر للأعداد الزوجية. بعد ذلك يُخزن الناتج في الجدول.
يبدأ الجدول بالقيمتين الأساسيتين \(F(0)=1\) و\(F(-1)=0\). وهذا يجعل منطق الاستدعاء العودي موحدًا من البداية إلى النهاية.
العدد الهدف \(10^{25}\) أكبر من أن تحتويه الأنواع الصغيرة المعتادة. لذلك تستخدم التطبيقات دعم الأعداد الصحيحة ذات الدقة غير المحدودة حيث تكون اللغة بحاجة إلى ذلك، بينما يستفيد Python من أعداده الكبيرة المدمجة. ومع ذلك، فإن العمليات المطلوبة على هذا المدخل تبقى بسيطة جدًا: فحص الفردية، طرح 1 أو 2، ثم إزاحة بت واحدة إلى اليمين.
ويقوم تنفيذ C++ أيضًا بفحص نقاط تحقق صغيرة مثل \(F(10)=5\) و\(F(5)=2\) قبل حساب الهدف الكامل. هذه الاختبارات تؤكد أن العلاقة العودية وآلية التخزين المؤقت تتفقان مع حالات صغيرة معروفة.
كل خطوة عودية تزيل فعليًا الخانة الثنائية الأقل أهمية من الوسيط الحالي، لأن الحالة التالية تكون دائمًا من الشكل \((n-1)/2\) أو \(n/2\) أو \(n/2-1\). ولهذا فإن عمق العودية يتناسب مع عدد البتات في \(n\).
وبفضل التخزين المؤقت، فإن كل حالة مميزة تُحسب مرة واحدة فقط، كما أن مخطط الحالات الممكن الوصول إليها يبقى صغيرًا جدًا مقارنةً بقيمة \(n\) نفسها. عمليًا، زمن التنفيذ يتناسب مع عدد الحالات المخزنة، وهذا العدد ينمو على رتبة طول التمثيل الثنائي للمدخل. لذلك يمكن وصف الطريقة بأنها تستخدم فعليًا \(O(\log n)\) من الحالات و\(O(\log n)\) من الذاكرة. والخلاصة المهمة هي أن الكلفة ترتبط بعدد البتات، لا بالحجم الهائل لـ \(10^{25}\) نفسه.