The task is to evaluate the prefix sum
$$S(n)=\sum_{k=1}^{n} f(k) \pmod{10^9}$$
for
$$n=3^{37}=450283905890997363.$$
The sequence \(f(n)\) is recursive, but the C++, Python, and Java implementations avoid term-by-term generation. They use an equivalent binary description: remove every factor of \(2\) from \(n\), keep the remaining odd part, and reverse its binary digits. This turns the strange recurrence into a family of halving identities that are suitable for memoization.
The built-in checkpoints are
$$S(8)=22,\qquad S(100)=3604.$$
The decisive observation is that the sequence is much easier to understand in base \(2\) than from its original recursive wording.
Write
$$n=2^{\nu_2(n)}u,\qquad \operatorname{odd}(n)=u,$$
where \(u\) is odd. If the binary expansion of \(u\) is
$$u=(a_r a_{r-1}\dots a_1 1)_2,$$
then the implementations use the equivalent closed description
$$f(n)=(1 a_1 a_2 \dots a_r)_2.$$
In words: strip the trailing zeros from the binary expansion of \(n\), then reverse the remaining odd binary word. Since multiplying by \(2\) only appends one trailing zero before that stripping step, we immediately get
$$f(2m)=f(m).$$
This is the first self-similarity that makes fast prefix sums possible.
Let
$$m=2^s u$$
with \(u\) odd, and let \(\ell\) be the bit-length of \(u\). Denote
$$R=f(m).$$
After reversing the relevant binary words, there exists a power of two
$$A=2^{\ell+s}$$
such that
$$f(2m+1)=A+R,\qquad f(4m+1)=2A+R,\qquad f(4m+3)=3A+R.$$
Eliminating \(A\) yields exact identities:
$$f(4m+1)=2f(2m+1)-f(m),$$
$$f(4m+3)=3f(2m+1)-2f(m).$$
These are precisely the relations needed to group odd arguments into pairs and blocks.
Define the main prefix sum and an auxiliary odd-index prefix sum by
$$S(n)=\sum_{k=1}^{n} f(k),\qquad O(n)=\sum_{k=1}^{n} f(2k-1).$$
The second quantity is the sum of the first \(n\) odd-indexed terms of the sequence. Because even arguments collapse under the rule \(f(2m)=f(m)\), the main sum satisfies
$$\begin{aligned} S(2m) &=\sum_{k=1}^{m} f(2k)+\sum_{k=1}^{m} f(2k-1)\\ &=S(m)+O(m), \end{aligned}$$
and therefore
$$S(2m+1)=S(2m)+f(2m+1).$$
So the main problem reduces to computing \(O(n)\) quickly.
For an odd upper limit, only one new odd term is added:
$$O(2m+1)=O(2m)+f(4m+1)=O(2m)+2f(2m+1)-f(m).$$
For an even upper limit, pair the odd arguments as \((4t+1,4t+3)\):
$$\begin{aligned} O(2m) &=\sum_{t=0}^{m-1}\bigl(f(4t+1)+f(4t+3)\bigr). \end{aligned}$$
Using the identities from Step 2, for every \(t\ge 1\) we have
$$f(4t+1)+f(4t+3)=5f(2t+1)-3f(t).$$
The case \(t=0\) must be handled separately, because it contributes
$$f(1)+f(3)=1+3=4.$$
Hence
$$\begin{aligned} O(2m) &=4+\sum_{t=1}^{m-1}\bigl(5f(2t+1)-3f(t)\bigr)\\ &=4+5\sum_{t=1}^{m-1}f(2t+1)-3\sum_{t=1}^{m-1}f(t)\\ &=4+5\bigl(O(m)-1\bigr)-3S(m-1)\\ &=-1+5O(m)-3S(m-1). \end{aligned}$$
Together with
$$S(0)=0,\qquad S(1)=1,\qquad O(0)=0,\qquad O(1)=1,$$
these recurrences determine all required prefix sums.
The first few sequence values are
$$f(1),\dots,f(8)=1,1,3,1,5,3,7,1,$$
so a direct sum gives \(22\). The recursive method reaches the same result much more systematically:
$$S(1)=1,\qquad O(1)=1.$$
Then
$$S(2)=S(1)+O(1)=2,$$
$$O(2)=-1+5O(1)-3S(0)=4,$$
$$S(4)=S(2)+O(2)=6,$$
$$O(4)=-1+5O(2)-3S(1)=16,$$
$$S(8)=S(4)+O(4)=22.$$
The same framework also produces the second checkpoint \(S(100)=3604\) without iterating through all one hundred terms one by one.
Every recurrence replaces the current argument by either \(n-1\), \(\lfloor n/2\rfloor\), or \(\lfloor n/2\rfloor-1\). An odd step is followed immediately by an even step, so the size drops by roughly a factor of \(2\) after at most one subtraction. That means the state graph is very small compared with the enormous target value \(3^{37}\), and memoization can reuse almost every nontrivial subproblem.
The C++, Python, and Java implementations all follow the same plan. They store two memo tables: one for \(S(n)\) and one for \(O(n)\). The base entries are the four values listed above.
Whenever a single term \(f(n)\) is needed, the implementation removes all powers of \(2\) from \(n\), reverses the binary digits of the remaining odd integer, and then reduces the result modulo \(10^9\).
To evaluate \(S(n)\), the implementation checks parity. For even \(n\), it applies
$$S(n)=S\!\left(\frac{n}{2}\right)+O\!\left(\frac{n}{2}\right);$$
for odd \(n\), it uses
$$S(n)=S(n-1)+f(n).$$
The auxiliary sum is handled analogously: for even \(n\), the code uses
$$O(n)=-1+5O\!\left(\frac{n}{2}\right)-3S\!\left(\frac{n}{2}-1\right),$$
and for odd \(n\), it adds the next odd contribution through
$$O(n)=O(n-1)+2f(n)-f\!\left(\frac{n-1}{2}\right).$$
Each result is normalized modulo \(10^9\) before being stored. Because the same arguments recur many times, caching is what turns the mathematical identities into a fast program.
The important point is that fresh states are created only along a halving-style recursion. After at most one subtraction, every branch moves to an argument of about half the previous size. As a result, the number of memoized states grows near-logarithmically in \(n\), not linearly.
At the machine-integer level, each new state performs only constant many modular additions and subtractions, plus one binary reversal whose cost is proportional to the bit-length of the odd core. Therefore the total running time stays far below \(O(n)\), and the memory usage is proportional to the small number of cached states.
Gesucht ist die Präfixsumme
$$S(n)=\sum_{k=1}^{n} f(k) \pmod{10^9}$$
für
$$n=3^{37}=450283905890997363.$$
Die Folge \(f(n)\) ist rekursiv definiert, aber die C++-, Python- und Java-Implementierungen erzeugen sie nicht Glied für Glied. Stattdessen benutzen sie eine äquivalente binäre Beschreibung: Man entfernt alle Zweierfaktoren aus \(n\), behält den verbleibenden ungeraden Kern und spiegelt dessen Binärdarstellung. Dadurch wird aus der merkwürdigen Rekursion eine Familie von Halbierungsformeln, die sich sehr gut memoisieren lässt.
Die eingebauten Kontrollwerte sind
$$S(8)=22,\qquad S(100)=3604.$$
Der entscheidende Schritt ist, die Folge in Basis \(2\) zu verstehen und daraus Summenrekurrenzen abzuleiten.
Schreibe
$$n=2^{\nu_2(n)}u,\qquad \operatorname{odd}(n)=u,$$
wobei \(u\) ungerade ist. Hat \(u\) die Binärdarstellung
$$u=(a_r a_{r-1}\dots a_1 1)_2,$$
dann verwenden die Implementierungen die äquivalente geschlossene Beschreibung
$$f(n)=(1 a_1 a_2 \dots a_r)_2.$$
Mit anderen Worten: Alle nachgestellten Nullen werden abgeschnitten, danach wird das verbleibende ungerade Bitwort umgedreht. Da das Multiplizieren mit \(2\) vor diesem Schritt nur eine weitere Endnull anhängt, folgt sofort
$$f(2m)=f(m).$$
Das ist die erste Selbstähnlichkeit, auf der die schnelle Summation beruht.
Sei
$$m=2^s u$$
mit ungeradem \(u\), und sei \(\ell\) die Bitlänge von \(u\). Setze
$$R=f(m).$$
Nach dem Spiegeln der passenden Binärwörter gibt es eine Zweierpotenz
$$A=2^{\ell+s}$$
mit
$$f(2m+1)=A+R,\qquad f(4m+1)=2A+R,\qquad f(4m+3)=3A+R.$$
Eliminiert man \(A\), so erhält man exakte Identitäten:
$$f(4m+1)=2f(2m+1)-f(m),$$
$$f(4m+3)=3f(2m+1)-2f(m).$$
Genau diese Formeln erlauben es später, ungerade Argumente blockweise zusammenzufassen.
Definiere die Hauptsumme und eine Hilfssumme über ungerade Indizes durch
$$S(n)=\sum_{k=1}^{n} f(k),\qquad O(n)=\sum_{k=1}^{n} f(2k-1).$$
Die zweite Größe summiert also die ersten \(n\) Folgenglieder an ungeraden Positionen. Wegen \(f(2m)=f(m)\) gilt für die Hauptsumme
$$\begin{aligned} S(2m) &=\sum_{k=1}^{m} f(2k)+\sum_{k=1}^{m} f(2k-1)\\ &=S(m)+O(m), \end{aligned}$$
und damit
$$S(2m+1)=S(2m)+f(2m+1).$$
Somit reduziert sich das Problem auf die schnelle Berechnung von \(O(n)\).
Für eine ungerade obere Grenze kommt nur ein neuer ungerader Term hinzu:
$$O(2m+1)=O(2m)+f(4m+1)=O(2m)+2f(2m+1)-f(m).$$
Für eine gerade obere Grenze paaren wir die ungeraden Argumente als \((4t+1,4t+3)\):
$$\begin{aligned} O(2m) &=\sum_{t=0}^{m-1}\bigl(f(4t+1)+f(4t+3)\bigr). \end{aligned}$$
Mit den Formeln aus Schritt 2 gilt für jedes \(t\ge 1\)
$$f(4t+1)+f(4t+3)=5f(2t+1)-3f(t).$$
Der Fall \(t=0\) muss separat behandelt werden, denn er liefert
$$f(1)+f(3)=1+3=4.$$
Daher
$$\begin{aligned} O(2m) &=4+\sum_{t=1}^{m-1}\bigl(5f(2t+1)-3f(t)\bigr)\\ &=4+5\sum_{t=1}^{m-1}f(2t+1)-3\sum_{t=1}^{m-1}f(t)\\ &=4+5\bigl(O(m)-1\bigr)-3S(m-1)\\ &=-1+5O(m)-3S(m-1). \end{aligned}$$
Zusammen mit
$$S(0)=0,\qquad S(1)=1,\qquad O(0)=0,\qquad O(1)=1$$
bestimmen diese Rekursionen alle benötigten Präfixsummen.
Die ersten Folgenglieder sind
$$f(1),\dots,f(8)=1,1,3,1,5,3,7,1,$$
also ist die direkte Summe gleich \(22\). Rekursiv erhält man denselben Wert so:
$$S(1)=1,\qquad O(1)=1.$$
Dann
$$S(2)=S(1)+O(1)=2,$$
$$O(2)=-1+5O(1)-3S(0)=4,$$
$$S(4)=S(2)+O(2)=6,$$
$$O(4)=-1+5O(2)-3S(1)=16,$$
$$S(8)=S(4)+O(4)=22.$$
Mit genau demselben Schema entsteht auch der zweite Kontrollwert \(S(100)=3604\), ohne dass man alle hundert Glieder einzeln auflisten muss.
Jede Rekursion ersetzt das aktuelle Argument durch \(n-1\), \(\lfloor n/2\rfloor\) oder \(\lfloor n/2\rfloor-1\). Auf einen ungeraden Schritt folgt sofort ein gerader, sodass die Größe nach höchstens einer Subtraktion ungefähr halbiert wird. Deshalb ist der Zustandsgraph im Vergleich zum riesigen Zielwert \(3^{37}\) sehr klein, und Memoisierung kann fast jede nichttriviale Teilaufgabe wiederverwenden.
Die C++-, Python- und Java-Implementierungen folgen demselben Plan. Sie halten zwei Memo-Tabellen: eine für \(S(n)\) und eine für \(O(n)\). Als Basis dienen die vier Anfangswerte oben.
Wenn ein einzelner Term \(f(n)\) benötigt wird, entfernt die Implementierung alle Zweierpotenzen aus \(n\), spiegelt die Bits des verbleibenden ungeraden Werts und reduziert anschließend modulo \(10^9\).
Zur Berechnung von \(S(n)\) wird die Parität geprüft. Für gerade \(n\) gilt
$$S(n)=S\!\left(\frac{n}{2}\right)+O\!\left(\frac{n}{2}\right),$$
für ungerade \(n\) dagegen
$$S(n)=S(n-1)+f(n).$$
Die Hilfssumme wird analog behandelt: Für gerade \(n\) nutzt der Code
$$O(n)=-1+5O\!\left(\frac{n}{2}\right)-3S\!\left(\frac{n}{2}-1\right),$$
und für ungerade \(n\)
$$O(n)=O(n-1)+2f(n)-f\!\left(\frac{n-1}{2}\right).$$
Jedes Ergebnis wird vor dem Speichern modulo \(10^9\) normalisiert. Der eigentliche Geschwindigkeitsschub kommt daher, dass dieselben Argumente immer wieder auftreten und deshalb nur einmal berechnet werden müssen.
Neue Zustände entstehen nur entlang einer Halbierungsrekursion. Nach höchstens einer Subtraktion gelangt jeder Zweig zu einem Argument von ungefähr halber Größe. Daher wächst die Anzahl memoiserter Zustände näherungsweise logarithmisch in \(n\), nicht linear.
Auf Maschinenwort-Ebene braucht jeder neue Zustand nur konstant viele modulare Additionen und Subtraktionen sowie eine Bitspiegelung, deren Kosten proportional zur Bitlänge des ungeraden Kerns sind. Damit bleibt die Gesamtlaufzeit weit unter \(O(n)\), und der Speicherbedarf ist proportional zur kleinen Anzahl zwischengespeicherter Zustände.
İstenen büyüklük
$$S(n)=\sum_{k=1}^{n} f(k) \pmod{10^9}$$
olup burada
$$n=3^{37}=450283905890997363.$$
\(f(n)\) dizisi özyinelemeli tanımlanır; ancak C++, Python ve Java uygulamaları terimleri tek tek üretmez. Bunun yerine eşdeğer bir ikilik taban tanımı kullanırlar: \(n\)'den tüm \(2\) çarpanlarını çıkar, geriye kalan tek kısmı al ve bu sayının ikilik basamaklarını ters çevir. Böylece problem, yarıya indirme temelli ve belleğe alınabilir bir yapıya dönüşür.
Uygulamalarda kullanılan kontrol değerleri şunlardır:
$$S(8)=22,\qquad S(100)=3604.$$
Ana fikir, diziyi doğrudan garip özyinelemesinden değil, ikilik yapıdaki öz-benzerliğinden okumaktır.
Şöyle yazalım:
$$n=2^{\nu_2(n)}u,\qquad \operatorname{odd}(n)=u,$$
burada \(u\) tektir. Eğer \(u\)'nun ikilik açılımı
$$u=(a_r a_{r-1}\dots a_1 1)_2$$
ise, uygulamaların kullandığı eşdeğer kapalı tanım
$$f(n)=(1 a_1 a_2 \dots a_r)_2$$
şeklindedir. Yani \(n\)'nin ikilik yazımındaki sondaki sıfırlar atılır, kalan tek bit dizisi ters çevrilir. \(2\) ile çarpmak bu işlemden önce sadece sona bir sıfır eklediği için hemen
$$f(2m)=f(m)$$
elde edilir. Hızlı toplamın ilk dayanağı budur.
\(m\) için
$$m=2^s u$$
yazalım; burada \(u\) tektir. \(u\)'nun bit uzunluğu \(\ell\) olsun ve
$$R=f(m)$$
tanımlayalım. İlgili ikilik kelimeler ters çevrildiğinde bir \(2\) kuvveti
$$A=2^{\ell+s}$$
için
$$f(2m+1)=A+R,\qquad f(4m+1)=2A+R,\qquad f(4m+3)=3A+R$$
olduğu görülür. Buradan \(A\)'yı yok edersek tam özdeşlikler elde ederiz:
$$f(4m+1)=2f(2m+1)-f(m),$$
$$f(4m+3)=3f(2m+1)-2f(m).$$
Bu formüller, tek indisleri bloklar halinde toplamamızı sağlar.
Ana ön toplamı ve tek indisli yardımcı toplamı
$$S(n)=\sum_{k=1}^{n} f(k),\qquad O(n)=\sum_{k=1}^{n} f(2k-1)$$
olarak tanımlayalım. İkinci ifade, dizinin ilk \(n\) tek indisli teriminin toplamıdır. \(f(2m)=f(m)\) olduğundan
$$\begin{aligned} S(2m) &=\sum_{k=1}^{m} f(2k)+\sum_{k=1}^{m} f(2k-1)\\ &=S(m)+O(m), \end{aligned}$$
ve dolayısıyla
$$S(2m+1)=S(2m)+f(2m+1).$$
Böylece asıl sorun \(O(n)\)'yi hızlı hesaplamaya iner.
Üst sınır tek olduğunda yalnızca bir yeni tek terim eklenir:
$$O(2m+1)=O(2m)+f(4m+1)=O(2m)+2f(2m+1)-f(m).$$
Üst sınır çift olduğunda tek argümanları \((4t+1,4t+3)\) çiftleri halinde gruplarız:
$$\begin{aligned} O(2m) &=\sum_{t=0}^{m-1}\bigl(f(4t+1)+f(4t+3)\bigr). \end{aligned}$$
Adım 2'deki özdeşliklerden, her \(t\ge 1\) için
$$f(4t+1)+f(4t+3)=5f(2t+1)-3f(t)$$
çıkar. \(t=0\) durumu ayrı alınmalıdır; çünkü katkısı
$$f(1)+f(3)=1+3=4$$
olur. O halde
$$\begin{aligned} O(2m) &=4+\sum_{t=1}^{m-1}\bigl(5f(2t+1)-3f(t)\bigr)\\ &=4+5\sum_{t=1}^{m-1}f(2t+1)-3\sum_{t=1}^{m-1}f(t)\\ &=4+5\bigl(O(m)-1\bigr)-3S(m-1)\\ &=-1+5O(m)-3S(m-1). \end{aligned}$$
Başlangıç değerleri
$$S(0)=0,\qquad S(1)=1,\qquad O(0)=0,\qquad O(1)=1$$
ile birlikte bu bağıntılar gereken tüm ön toplamları belirler.
İlk sekiz terim
$$f(1),\dots,f(8)=1,1,3,1,5,3,7,1$$
olduğu için doğrudan toplam \(22\)'dir. Özyinelemeli yöntem aynı sonuca şu şekilde ulaşır:
$$S(1)=1,\qquad O(1)=1.$$
Ardından
$$S(2)=S(1)+O(1)=2,$$
$$O(2)=-1+5O(1)-3S(0)=4,$$
$$S(4)=S(2)+O(2)=6,$$
$$O(4)=-1+5O(2)-3S(1)=16,$$
$$S(8)=S(4)+O(4)=22.$$
Aynı çerçeve, yüz terimi tek tek toplamadan ikinci kontrol değeri olan \(S(100)=3604\)'ü de üretir.
Her bağıntı mevcut argümanı \(n-1\), \(\lfloor n/2\rfloor\) veya \(\lfloor n/2\rfloor-1\) biçimine indirir. Tek bir adımı hemen bir çift adım izlediğinden, büyüklük en geç bir çıkarma sonra yaklaşık yarıya düşer. Bu nedenle \(3^{37}\) kadar büyük bir hedefe rağmen durum grafiği küçüktür ve memoization neredeyse bütün alt problemleri yeniden kullanır.
C++, Python ve Java uygulamalarının planı aynıdır. Biri \(S(n)\), diğeri \(O(n)\) için olmak üzere iki ayrı önbellek tutulur. Başlangıçta yukarıdaki dört taban değeri yerleştirilir.
Tek bir \(f(n)\) terimi gerektiğinde uygulama önce \(n\)'den tüm \(2\) kuvvetlerini çıkarır, sonra kalan tek sayının ikilik basamaklarını ters çevirir ve sonucu \(10^9\) modunda normalleştirir.
\(S(n)\) hesabında parite kontrol edilir. \(n\) çiftse
$$S(n)=S\!\left(\frac{n}{2}\right)+O\!\left(\frac{n}{2}\right),$$
\(n\) tekse
$$S(n)=S(n-1)+f(n)$$
kullanılır. Yardımcı toplam için de benzer biçimde, çift durumda
$$O(n)=-1+5O\!\left(\frac{n}{2}\right)-3S\!\left(\frac{n}{2}-1\right),$$
tek durumda ise
$$O(n)=O(n-1)+2f(n)-f\!\left(\frac{n-1}{2}\right)$$
uygulanır. Her sonuç kaydedilmeden önce \(10^9\) moduna göre düzenlenir. Hız kazancı, aynı argümanların tekrar tekrar gelmesi ve bu yüzden yalnızca bir kez hesaplanması sayesinde oluşur.
Yeni durumlar sadece yarılama temelli bir özyineleme boyunca oluşur. En geç bir çıkarma sonra her dal yaklaşık yarı büyüklükte bir argümana iner. Bu nedenle belleğe alınan durum sayısı \(n\)'e göre lineer değil, yaklaşık logaritmik büyür.
Makine tamsayısı düzeyinde her yeni durum sabit sayıda modüler toplama ve çıkarma ile, tek çekirdeğin bit uzunluğu kadar maliyetli bir bit terslemesi yapar. Böylece toplam çalışma süresi doğrudan \(O(n)\) toplamadan çok daha küçüktür; bellek kullanımı da küçük önbellek boyutuyla orantılıdır.
Debemos evaluar la suma prefija
$$S(n)=\sum_{k=1}^{n} f(k) \pmod{10^9}$$
para
$$n=3^{37}=450283905890997363.$$
La sucesión \(f(n)\) está definida recursivamente, pero las implementaciones en C++, Python y Java no la generan término a término. En su lugar usan una descripción binaria equivalente: se eliminan todos los factores de \(2\) de \(n\), se toma la parte impar restante y se invierten sus bits. Esa reformulación convierte la recurrencia extraña en un sistema de identidades por bisección que se presta muy bien a la memoización.
Los valores de control son
$$S(8)=22,\qquad S(100)=3604.$$
La clave es leer la sucesión en base \(2\) y luego trasladar esa estructura a sumas prefijas.
Escribimos
$$n=2^{\nu_2(n)}u,\qquad \operatorname{odd}(n)=u,$$
donde \(u\) es impar. Si la expansión binaria de \(u\) es
$$u=(a_r a_{r-1}\dots a_1 1)_2,$$
entonces la descripción cerrada equivalente usada por las implementaciones es
$$f(n)=(1 a_1 a_2 \dots a_r)_2.$$
Dicho de otro modo: se quitan los ceros finales de la representación binaria de \(n\) y luego se invierte la palabra binaria impar que queda. Como multiplicar por \(2\) solo añade un cero final antes de ese recorte, se obtiene de inmediato
$$f(2m)=f(m).$$
Esa es la primera autosimilitud fundamental.
Sea
$$m=2^s u$$
con \(u\) impar, y sea \(\ell\) la longitud binaria de \(u\). Denotemos
$$R=f(m).$$
Al invertir las palabras binarias correspondientes aparece una potencia de dos
$$A=2^{\ell+s}$$
tal que
$$f(2m+1)=A+R,\qquad f(4m+1)=2A+R,\qquad f(4m+3)=3A+R.$$
Eliminando \(A\) obtenemos identidades exactas:
$$f(4m+1)=2f(2m+1)-f(m),$$
$$f(4m+3)=3f(2m+1)-2f(m).$$
Estas relaciones son las que permiten reagrupar los términos impares en bloques manejables.
Definimos la suma principal y una suma auxiliar sobre índices impares:
$$S(n)=\sum_{k=1}^{n} f(k),\qquad O(n)=\sum_{k=1}^{n} f(2k-1).$$
La segunda cantidad suma los primeros \(n\) términos situados en posiciones impares. Como \(f(2m)=f(m)\), la suma principal cumple
$$\begin{aligned} S(2m) &=\sum_{k=1}^{m} f(2k)+\sum_{k=1}^{m} f(2k-1)\\ &=S(m)+O(m), \end{aligned}$$
y por tanto
$$S(2m+1)=S(2m)+f(2m+1).$$
Así, el problema se reduce a calcular \(O(n)\) con rapidez.
Si el límite es impar, solo se añade un nuevo término impar:
$$O(2m+1)=O(2m)+f(4m+1)=O(2m)+2f(2m+1)-f(m).$$
Si el límite es par, agrupamos los argumentos impares como \((4t+1,4t+3)\):
$$\begin{aligned} O(2m) &=\sum_{t=0}^{m-1}\bigl(f(4t+1)+f(4t+3)\bigr). \end{aligned}$$
Aplicando las identidades del Paso 2, para cada \(t\ge 1\) se tiene
$$f(4t+1)+f(4t+3)=5f(2t+1)-3f(t).$$
El caso \(t=0\) debe separarse, porque aporta
$$f(1)+f(3)=1+3=4.$$
Entonces
$$\begin{aligned} O(2m) &=4+\sum_{t=1}^{m-1}\bigl(5f(2t+1)-3f(t)\bigr)\\ &=4+5\sum_{t=1}^{m-1}f(2t+1)-3\sum_{t=1}^{m-1}f(t)\\ &=4+5\bigl(O(m)-1\bigr)-3S(m-1)\\ &=-1+5O(m)-3S(m-1). \end{aligned}$$
Junto con
$$S(0)=0,\qquad S(1)=1,\qquad O(0)=0,\qquad O(1)=1,$$
estas recurrencias determinan todas las sumas necesarias.
Los primeros ocho términos son
$$f(1),\dots,f(8)=1,1,3,1,5,3,7,1,$$
así que la suma directa vale \(22\). El método recursivo llega al mismo punto de esta manera:
$$S(1)=1,\qquad O(1)=1.$$
Luego
$$S(2)=S(1)+O(1)=2,$$
$$O(2)=-1+5O(1)-3S(0)=4,$$
$$S(4)=S(2)+O(2)=6,$$
$$O(4)=-1+5O(2)-3S(1)=16,$$
$$S(8)=S(4)+O(4)=22.$$
El mismo mecanismo produce también el segundo valor de verificación \(S(100)=3604\) sin recorrer uno por uno los cien términos.
Cada recurrencia sustituye el argumento actual por \(n-1\), \(\lfloor n/2\rfloor\) o \(\lfloor n/2\rfloor-1\). Un paso impar va seguido enseguida por un paso par, de modo que el tamaño baja aproximadamente a la mitad tras como mucho una resta. Por eso el grafo de estados es diminuto en comparación con el objetivo enorme \(3^{37}\), y la memoización reutiliza casi todos los subproblemas no triviales.
Las implementaciones en C++, Python y Java siguen exactamente el mismo esquema. Mantienen dos tablas de memoización: una para \(S(n)\) y otra para \(O(n)\). Se inicializan con los cuatro valores base indicados arriba.
Cuando hace falta un término individual \(f(n)\), la implementación elimina primero todas las potencias de \(2\) de \(n\), invierte los bits del entero impar restante y luego reduce el resultado módulo \(10^9\).
Para evaluar \(S(n)\), se distingue por paridad. Si \(n\) es par, se aplica
$$S(n)=S\!\left(\frac{n}{2}\right)+O\!\left(\frac{n}{2}\right);$$
si \(n\) es impar, se usa
$$S(n)=S(n-1)+f(n).$$
La suma auxiliar se trata de forma paralela: para \(n\) par, el código utiliza
$$O(n)=-1+5O\!\left(\frac{n}{2}\right)-3S\!\left(\frac{n}{2}-1\right),$$
mientras que para \(n\) impar emplea
$$O(n)=O(n-1)+2f(n)-f\!\left(\frac{n-1}{2}\right).$$
Cada resultado se normaliza módulo \(10^9\) antes de guardarse. La eficiencia real viene de que los mismos argumentos aparecen muchas veces y, gracias al caché, solo se resuelven una vez.
Los estados nuevos solo aparecen a lo largo de una recursión de tipo “dividir entre \(2\)”. Tras como mucho una resta, cada rama pasa a un argumento de tamaño aproximadamente mitad. Por eso el número de estados memoizados crece de forma casi logarítmica en \(n\), no lineal.
A nivel de enteros de máquina, cada estado nuevo realiza un número constante de sumas y restas modulares, más una inversión binaria cuyo coste es proporcional a la longitud en bits de la parte impar. En consecuencia, el tiempo total queda muy por debajo de \(O(n)\), y la memoria usada es proporcional al pequeño conjunto de estados almacenados.
题目要求计算前缀和
$$S(n)=\sum_{k=1}^{n} f(k) \pmod{10^9}$$
其中
$$n=3^{37}=450283905890997363.$$
\(f(n)\) 原本是一个递归定义的数列，但 C++、Python 和 Java 三个实现都没有按顺序把所有项算出来。它们使用了一个等价而且更容易利用的二进制描述：把 \(n\) 中所有的 \(2\) 因子去掉，得到它的奇数核心，然后把这个奇数的二进制位反转。这样一来，题目就不再像“硬递推”，而是变成了一个非常适合按二进制分块、反复折半求解的问题。
实现中使用的校验点是
$$S(8)=22,\qquad S(100)=3604.$$
核心思路是先把数列 \(f\) 的结构看清楚，再把这种结构转写成前缀和的递推式。
把 \(n\) 写成
$$n=2^{\nu_2(n)}u,\qquad \operatorname{odd}(n)=u,$$
其中 \(u\) 是奇数。若 \(u\) 的二进制写成
$$u=(a_r a_{r-1}\dots a_1 1)_2,$$
那么实现实际上用的是下面这个等价定义：
$$f(n)=(1 a_1 a_2 \dots a_r)_2.$$
也就是说，先把 \(n\) 的二进制末尾所有零去掉，再把剩下的奇数二进制串完全反过来。由于乘以 \(2\) 只会在二进制末尾增加一个零，而这些零在取奇数核心时都会被删掉，所以立刻得到
$$f(2m)=f(m).$$
这是整道题最基本的自相似性，也是后面所有折半递推的起点。
设
$$m=2^s u$$
且 \(u\) 为奇数。记 \(u\) 的二进制长度为 \(\ell\)，再记
$$R=f(m).$$
把与 \(2m+1\)、\(4m+1\)、\(4m+3\) 对应的二进制串反转后，可以发现存在一个二的幂
$$A=2^{\ell+s}$$
使得
$$f(2m+1)=A+R,\qquad f(4m+1)=2A+R,\qquad f(4m+3)=3A+R.$$
这个结论的直观含义是：在奇数核心后面补上不同的二进制尾巴，反转以后只是“最高位块”的系数发生了变化，而与 \(m\) 本身相关的那部分仍然是同一个 \(R\)。把 \(A\) 消去以后，就得到两个非常重要的恒等式：
$$f(4m+1)=2f(2m+1)-f(m),$$
$$f(4m+3)=3f(2m+1)-2f(m).$$
这些等式是把原题中的“怪递推”转化成可求和公式的桥梁。
定义
$$S(n)=\sum_{k=1}^{n} f(k),\qquad O(n)=\sum_{k=1}^{n} f(2k-1).$$
这里 \(S(n)\) 是通常的前缀和，而 \(O(n)\) 是前 \(n\) 个奇数下标项的和。因为已经知道 \(f(2m)=f(m)\)，所以偶数长度的主前缀和可以直接拆成“偶数位置部分”和“奇数位置部分”：
$$\begin{aligned} S(2m) &=\sum_{k=1}^{m} f(2k)+\sum_{k=1}^{m} f(2k-1)\\ &=S(m)+O(m). \end{aligned}$$
于是立刻得到
$$S(2m+1)=S(2m)+f(2m+1).$$
也就是说，只要能够快速算出 \(O(n)\)，主目标 \(S(n)\) 就会随之解决。
先看奇数上界。因为从 \(O(2m)\) 到 \(O(2m+1)\) 只多出一个新的奇数位置项，所以
$$O(2m+1)=O(2m)+f(4m+1)=O(2m)+2f(2m+1)-f(m).$$
再看偶数上界。把奇数参数配成 \((4t+1,4t+3)\) 这一对：
$$\begin{aligned} O(2m) &=\sum_{t=0}^{m-1}\bigl(f(4t+1)+f(4t+3)\bigr). \end{aligned}$$
对于每个 \(t\ge 1\)，利用步骤 2 的恒等式可以得到
$$f(4t+1)+f(4t+3)=5f(2t+1)-3f(t).$$
但是 \(t=0\) 不能机械代入这个公式，而要单独拿出来，因为它实际贡献的是
$$f(1)+f(3)=1+3=4.$$
因此
$$\begin{aligned} O(2m) &=4+\sum_{t=1}^{m-1}\bigl(5f(2t+1)-3f(t)\bigr)\\ &=4+5\sum_{t=1}^{m-1}f(2t+1)-3\sum_{t=1}^{m-1}f(t)\\ &=4+5\bigl(O(m)-1\bigr)-3S(m-1)\\ &=-1+5O(m)-3S(m-1). \end{aligned}$$
再配上初值
$$S(0)=0,\qquad S(1)=1,\qquad O(0)=0,\qquad O(1)=1,$$
整个求和系统就闭合了。此时我们已经不需要从 \(1\) 一直加到 \(n\)，只需要不断访问更小的子问题。
直接把前八项写出来，有
$$f(1),\dots,f(8)=1,1,3,1,5,3,7,1,$$
它们的和确实是 \(22\)。但更重要的是，递推公式本身也能很快推出同样的结果：
$$S(1)=1,\qquad O(1)=1.$$
于是
$$S(2)=S(1)+O(1)=2,$$
$$O(2)=-1+5O(1)-3S(0)=4,$$
$$S(4)=S(2)+O(2)=6,$$
$$O(4)=-1+5O(2)-3S(1)=16,$$
$$S(8)=S(4)+O(4)=22.$$
同样的递推体系继续往上走，就会得到第二个校验点 \(S(100)=3604\)。这说明公式不仅在小例子上正确，而且已经足以支撑真正的大输入。
观察所有递推式可以发现，新的参数只会变成 \(n-1\)、\(\lfloor n/2\rfloor\) 或 \(\lfloor n/2\rfloor-1\)。如果先遇到奇数步，下一步立刻就会回到偶数并进入折半。换句话说，参数规模最多经过一次减一，就会缩小到原来的一半左右。因此，对 \(3^{37}\) 这样极大的目标值，真正会被访问到的状态仍然很少，适合用记忆化搜索来完成。
C++、Python 和 Java 三个实现的框架完全一致。它们维护两张缓存表，一张保存 \(S(n)\)，另一张保存 \(O(n)\)。初始时先放入上面给出的四个基本值。
当需要单个 \(f(n)\) 时，程序先不断除以 \(2\)，直到得到奇数核心；然后把这个奇数的二进制位反转，并在需要存储到和式时对 \(10^9\) 取模。
求 \(S(n)\) 时先看奇偶性。若 \(n\) 为偶数，就使用
$$S(n)=S\!\left(\frac{n}{2}\right)+O\!\left(\frac{n}{2}\right);$$
若 \(n\) 为奇数，就退一步到前一个偶数，再补上最后一项：
$$S(n)=S(n-1)+f(n).$$
求 \(O(n)\) 也是同样的思路。若 \(n\) 为偶数，应用
$$O(n)=-1+5O\!\left(\frac{n}{2}\right)-3S\!\left(\frac{n}{2}-1\right);$$
若 \(n\) 为奇数，则加入一个新的奇数块：
$$O(n)=O(n-1)+2f(n)-f\!\left(\frac{n-1}{2}\right).$$
每次加减之后都会先规范到模 \(10^9\) 的范围内，再写入缓存。由于很多子问题会反复出现，缓存可以把它们的成本压缩为“只算一次”。
整个算法的新状态只沿着一种“折半为主”的递归树生成。最多经过一次减一操作，参数就会下降到大约一半，所以缓存中的状态数量相对于 \(n\) 来说是近似对数级的，而不是线性的。
在机器整数模型下，每个新状态只需要常数次模加减，再加上一轮与奇数核心位长成正比的二进制反转操作。因此总时间远小于逐项累加到 \(n\) 的 \(O(n)\) 方法，空间开销则与缓存状态数成正比，也同样很小。
Требуется вычислить префиксную сумму
$$S(n)=\sum_{k=1}^{n} f(k) \pmod{10^9}$$
для значения
$$n=3^{37}=450283905890997363.$$
Последовательность \(f(n)\) задана рекурсивно, однако реализации на C++, Python и Java не строят ее поэлементно. Вместо этого используется эквивалентное двоичное описание: из \(n\) удаляются все множители \(2\), затем у оставшегося нечетного ядра разворачиваются двоичные биты. Такая интерпретация превращает странную рекурсию в систему тождеств с делением аргумента примерно пополам, а значит делает задачу удобной для мемоизации.
Контрольные значения таковы:
$$S(8)=22,\qquad S(100)=3604.$$
Вся идея состоит в том, чтобы понять структуру \(f(n)\) в двоичной записи и затем перенести эту структуру на суммы.
Запишем
$$n=2^{\nu_2(n)}u,\qquad \operatorname{odd}(n)=u,$$
где \(u\) нечетно. Если двоичная запись \(u\) имеет вид
$$u=(a_r a_{r-1}\dots a_1 1)_2,$$
то в реализациях используется эквивалентное замкнутое описание
$$f(n)=(1 a_1 a_2 \dots a_r)_2.$$
То есть сначала отбрасываются все конечные нули в двоичной записи \(n\), а затем оставшееся нечетное двоичное слово читается в обратном порядке. Поскольку умножение на \(2\) лишь добавляет один конечный ноль перед этим отбрасыванием, сразу получается
$$f(2m)=f(m).$$
Это и есть первая самоподобная закономерность последовательности.
Пусть
$$m=2^s u$$
с нечетным \(u\), а \(\ell\) обозначает длину двоичной записи \(u\). Положим
$$R=f(m).$$
После разворота соответствующих двоичных слов существует степень двойки
$$A=2^{\ell+s}$$
такая, что
$$f(2m+1)=A+R,\qquad f(4m+1)=2A+R,\qquad f(4m+3)=3A+R.$$
Если исключить \(A\), получаются точные тождества:
$$f(4m+1)=2f(2m+1)-f(m),$$
$$f(4m+3)=3f(2m+1)-2f(m).$$
Именно они позволяют объединять нечетные аргументы в удобные блоки при суммировании.
Определим основную сумму и вспомогательную сумму по нечетным позициям:
$$S(n)=\sum_{k=1}^{n} f(k),\qquad O(n)=\sum_{k=1}^{n} f(2k-1).$$
Величина \(O(n)\) равна сумме первых \(n\) членов с нечетными индексами. Так как \(f(2m)=f(m)\), для основной суммы имеем
$$\begin{aligned} S(2m) &=\sum_{k=1}^{m} f(2k)+\sum_{k=1}^{m} f(2k-1)\\ &=S(m)+O(m), \end{aligned}$$
а значит
$$S(2m+1)=S(2m)+f(2m+1).$$
Следовательно, вся задача сводится к быстрому вычислению \(O(n)\).
Для нечетного верхнего предела появляется ровно один новый нечетный член:
$$O(2m+1)=O(2m)+f(4m+1)=O(2m)+2f(2m+1)-f(m).$$
Для четного предела сгруппируем нечетные аргументы в пары \((4t+1,4t+3)\):
$$\begin{aligned} O(2m) &=\sum_{t=0}^{m-1}\bigl(f(4t+1)+f(4t+3)\bigr). \end{aligned}$$
Из формул шага 2 для каждого \(t\ge 1\) следует
$$f(4t+1)+f(4t+3)=5f(2t+1)-3f(t).$$
Случай \(t=0\) нужно вынести отдельно, потому что он дает вклад
$$f(1)+f(3)=1+3=4.$$
Поэтому
$$\begin{aligned} O(2m) &=4+\sum_{t=1}^{m-1}\bigl(5f(2t+1)-3f(t)\bigr)\\ &=4+5\sum_{t=1}^{m-1}f(2t+1)-3\sum_{t=1}^{m-1}f(t)\\ &=4+5\bigl(O(m)-1\bigr)-3S(m-1)\\ &=-1+5O(m)-3S(m-1). \end{aligned}$$
Вместе с начальными условиями
$$S(0)=0,\qquad S(1)=1,\qquad O(0)=0,\qquad O(1)=1$$
эти рекурсии полностью задают все нужные префиксные суммы.
Первые восемь членов последовательности равны
$$f(1),\dots,f(8)=1,1,3,1,5,3,7,1,$$
поэтому прямая сумма действительно дает \(22\). Рекурсивный подход получает тот же результат так:
$$S(1)=1,\qquad O(1)=1.$$
Далее
$$S(2)=S(1)+O(1)=2,$$
$$O(2)=-1+5O(1)-3S(0)=4,$$
$$S(4)=S(2)+O(2)=6,$$
$$O(4)=-1+5O(2)-3S(1)=16,$$
$$S(8)=S(4)+O(4)=22.$$
Тот же самый механизм приводит и ко второму контрольному значению \(S(100)=3604\), не требуя линейного перебора ста членов.
Каждая рекурсия заменяет текущий аргумент на \(n-1\), \(\lfloor n/2\rfloor\) или \(\lfloor n/2\rfloor-1\). После нечетного шага сразу следует четный, так что максимум через одно вычитание размер аргумента падает примерно вдвое. Поэтому даже для колоссального значения \(3^{37}\) реально посещается совсем немного состояний, и мемоизация оказывается чрезвычайно эффективной.
Реализации на C++, Python и Java устроены одинаково. Они хранят две таблицы кеша: одну для \(S(n)\), другую для \(O(n)\). С самого начала в них помещаются четыре базовых значения, приведенные выше.
Когда нужен отдельный член \(f(n)\), реализация делит \(n\) на \(2\), пока не останется нечетное ядро, затем разворачивает двоичные биты этого нечетного числа и уже после этого приводит результат по модулю \(10^9\).
Для вычисления \(S(n)\) сначала проверяется четность. Если \(n\) четно, используется
$$S(n)=S\!\left(\frac{n}{2}\right)+O\!\left(\frac{n}{2}\right);$$
если \(n\) нечетно, применяется
$$S(n)=S(n-1)+f(n).$$
Вспомогательная сумма считается аналогично: для четного \(n\) код использует
$$O(n)=-1+5O\!\left(\frac{n}{2}\right)-3S\!\left(\frac{n}{2}-1\right),$$
а для нечетного \(n\)
$$O(n)=O(n-1)+2f(n)-f\!\left(\frac{n-1}{2}\right).$$
После каждой операции значение нормализуется по модулю \(10^9\) и записывается в кеш. Благодаря этому один и тот же подзадачный аргумент вычисляется не более одного раза.
Новые состояния возникают только вдоль рекурсии, основанной на делении аргумента примерно пополам. После максимум одного шага вида \(n \mapsto n-1\) каждая ветвь переходит к аргументу порядка \(n/2\). Поэтому число кешируемых состояний растет близко к логарифму от \(n\), а не линейно.
На уровне машинных целых каждое новое состояние требует лишь константного числа модульных сложений и вычитаний плюс один разворот битов, стоимость которого пропорциональна длине двоичной записи нечетного ядра. В итоге метод работает несравнимо быстрее прямого суммирования до \(n\), а память расходуется только на небольшой набор сохраненных состояний.
المطلوب هو حساب المجموع التراكمي
$$S(n)=\sum_{k=1}^{n} f(k) \pmod{10^9}$$
عندما يكون
$$n=3^{37}=450283905890997363.$$
المتتالية \(f(n)\) معرفة بعلاقة عودية، لكن تطبيقات C++ وPython وJava لا تولد الحدود واحدًا واحدًا. بدلًا من ذلك فهي تستعمل وصفًا ثنائيًا مكافئًا: نحذف جميع عوامل \(2\) من \(n\)، ثم نأخذ الجزء الفردي المتبقي ونقلب بتاته الثنائية. هذا الوصف يحول العلاقة الغريبة إلى مجموعة من الهويات التي تعتمد على التنصيف المتكرر، وهو ما يجعل التخزين المؤقت فعالًا جدًا.
قيم التحقق المضمّنة هي
$$S(8)=22,\qquad S(100)=3604.$$
الفكرة الحاسمة هي فهم بنية \(f(n)\) في النظام الثنائي أولًا، ثم تحويل تلك البنية إلى علاقات خاصة بالمجاميع التراكمية.
نكتب
$$n=2^{\nu_2(n)}u,\qquad \operatorname{odd}(n)=u,$$
حيث إن \(u\) عدد فردي. وإذا كانت الكتابة الثنائية لـ \(u\) هي
$$u=(a_r a_{r-1}\dots a_1 1)_2,$$
فإن الصياغة المكافئة التي تعتمدها التطبيقات هي
$$f(n)=(1 a_1 a_2 \dots a_r)_2.$$
أي أننا نحذف الأصفار النهائية من الكتابة الثنائية لـ \(n\)، ثم نعكس الكلمة الثنائية الفردية الباقية. وبما أن الضرب في \(2\) لا يفعل قبل هذه العملية إلا إضافة صفر نهائي واحد، فإننا نحصل مباشرة على
$$f(2m)=f(m).$$
وهذه هي أول خاصية تشابه ذاتي يعتمد عليها الحل السريع.
لنفترض أن
$$m=2^s u$$
مع \(u\) فردي، ولتكن \(\ell\) هي طول التمثيل الثنائي لـ \(u\). ونعرّف
$$R=f(m).$$
بعد قلب الكلمات الثنائية المناسبة يظهر لدينا ثابت من شكل قوة للعدد \(2\):
$$A=2^{\ell+s}$$
بحيث
$$f(2m+1)=A+R,\qquad f(4m+1)=2A+R,\qquad f(4m+3)=3A+R.$$
وبحذف \(A\) نحصل على علاقتين دقيقتين مهمتين جدًا:
$$f(4m+1)=2f(2m+1)-f(m),$$
$$f(4m+3)=3f(2m+1)-2f(m).$$
هاتان العلاقتان هما الأداة التي تسمح بتجميع الحدود الفردية في كتل يسهل التعامل معها.
نعرّف المجموع الرئيسي ومجموعًا مساعدًا لحدود الفهارس الفردية كما يلي:
$$S(n)=\sum_{k=1}^{n} f(k),\qquad O(n)=\sum_{k=1}^{n} f(2k-1).$$
المقدار \(O(n)\) هو مجموع أول \(n\) حدود تقع عند فهارس فردية. وبما أن \(f(2m)=f(m)\)، فإننا نستطيع تفكيك المجموع الرئيسي عند القيم الزوجية:
$$\begin{aligned} S(2m) &=\sum_{k=1}^{m} f(2k)+\sum_{k=1}^{m} f(2k-1)\\ &=S(m)+O(m), \end{aligned}$$
ومن ثم
$$S(2m+1)=S(2m)+f(2m+1).$$
إذن لبّ المسألة هو حساب \(O(n)\) بسرعة.
إذا كان الحد الأعلى فرديًا، فنحن نضيف حدًا فرديًا جديدًا واحدًا فقط:
$$O(2m+1)=O(2m)+f(4m+1)=O(2m)+2f(2m+1)-f(m).$$
أما إذا كان الحد الأعلى زوجيًا، فنجمّع الفهارس الفردية في الأزواج \((4t+1,4t+3)\):
$$\begin{aligned} O(2m) &=\sum_{t=0}^{m-1}\bigl(f(4t+1)+f(4t+3)\bigr). \end{aligned}$$
وباستخدام علاقات الخطوة 2، نجد لكل \(t\ge 1\) أن
$$f(4t+1)+f(4t+3)=5f(2t+1)-3f(t).$$
لكن الحالة \(t=0\) يجب فصلها عن الباقي لأنها تعطي مباشرة
$$f(1)+f(3)=1+3=4.$$
ومن ثم نحصل على
$$\begin{aligned} O(2m) &=4+\sum_{t=1}^{m-1}\bigl(5f(2t+1)-3f(t)\bigr)\\ &=4+5\sum_{t=1}^{m-1}f(2t+1)-3\sum_{t=1}^{m-1}f(t)\\ &=4+5\bigl(O(m)-1\bigr)-3S(m-1)\\ &=-1+5O(m)-3S(m-1). \end{aligned}$$
ومع القيم الابتدائية
$$S(0)=0,\qquad S(1)=1,\qquad O(0)=0,\qquad O(1)=1,$$
تصبح لدينا منظومة مغلقة تحدد كل المجاميع المطلوبة دون حاجة إلى المرور الخطي على جميع الحدود.
الحدود الثمانية الأولى هي
$$f(1),\dots,f(8)=1,1,3,1,5,3,7,1,$$
وبالتالي فالمجموع المباشر يساوي \(22\). لكن الأهم هو أن العلاقات العودية نفسها تعطي النتيجة بسرعة:
$$S(1)=1,\qquad O(1)=1.$$
ثم
$$S(2)=S(1)+O(1)=2,$$
$$O(2)=-1+5O(1)-3S(0)=4,$$
$$S(4)=S(2)+O(2)=6,$$
$$O(4)=-1+5O(2)-3S(1)=16,$$
$$S(8)=S(4)+O(4)=22.$$
وبالأسلوب نفسه نحصل أيضًا على قيمة التحقق الثانية \(S(100)=3604\) من غير حاجة إلى جمع مئة حد على نحو مباشر.
كل علاقة عودية تستبدل الوسيط الحالي بأحد الأشكال \(n-1\) أو \(\lfloor n/2\rfloor\) أو \(\lfloor n/2\rfloor-1\). وإذا دخلنا حالة فردية فسرعان ما ننتقل بعدها إلى حالة زوجية، أي إن الحجم ينخفض إلى نحو النصف بعد طرح واحد على الأكثر. لذلك يبقى عدد الحالات التي تُزار فعليًا صغيرًا جدًا مقارنة بالقيمة الهائلة \(3^{37}\)، ويصبح التخزين المؤقت هو العامل الحاسم في السرعة.
التطبيقات الثلاثة، في C++ وPython وJava، تتبع الخطة نفسها. فهي تحتفظ بجدولي تخزين مؤقت: أحدهما لقيم \(S(n)\) والآخر لقيم \(O(n)\). وتوضع القيم الابتدائية الأربع المذكورة أعلاه منذ البداية.
عندما يحتاج التنفيذ إلى حد منفرد \(f(n)\)، فإنه يزيل أولًا جميع قوى \(2\) من \(n\)، ثم يعكس البتات الثنائية للعدد الفردي المتبقي، وبعد ذلك يطبع النتيجة ضمن الحسابات بترديد \(10^9\).
وعند حساب \(S(n)\) يبدأ التنفيذ بفحص الزوجية. إذا كان \(n\) زوجيًا فإنه يستخدم
$$S(n)=S\!\left(\frac{n}{2}\right)+O\!\left(\frac{n}{2}\right);$$
أما إذا كان \(n\) فرديًا فإنه يستعمل
$$S(n)=S(n-1)+f(n).$$
وبالمثل، عند حساب \(O(n)\)، إذا كان \(n\) زوجيًا تُستخدم العلاقة
$$O(n)=-1+5O\!\left(\frac{n}{2}\right)-3S\!\left(\frac{n}{2}-1\right),$$
وإذا كان \(n\) فرديًا تُستخدم العلاقة
$$O(n)=O(n-1)+2f(n)-f\!\left(\frac{n-1}{2}\right).$$
بعد كل عملية جمع أو طرح، تُعاد القيمة إلى المجال الصحيح modulo \(10^9\) قبل تخزينها. وبما أن الوسائط نفسها تظهر مرارًا، فإن التخزين المؤقت يضمن ألا تُحل المسألة الفرعية نفسها أكثر من مرة واحدة.
الحالات الجديدة لا تنشأ إلا على طول شجرة عودية أساسها التنصيف. وبعد طرح واحد على الأكثر، تنتقل كل شعبة إلى وسيط حجمه يقارب النصف. لهذا فإن عدد الحالات المخزنة ينمو نموًا قريبًا من اللوغاريتمي بالنسبة إلى \(n\)، وليس نموًا خطيًا.
وعلى مستوى الأعداد الصحيحة الآلية، كل حالة جديدة تحتاج إلى عدد ثابت من عمليات الجمع والطرح المعيارية، بالإضافة إلى عملية قلب ثنائي تكلفتها تتناسب مع طول تمثيل النواة الفردية. لذلك يبقى الزمن الكلي أقل بكثير من \(O(n)\) المباشر، كما أن الذاكرة المستعملة تساوي تقريبًا حجم مجموعة الحالات الصغيرة المخزنة.