The Rudin-Shapiro sign sequence used by the solutions is
$$b(n)=(-1)^{\operatorname{popcount}(n \mathbin{\&} (n \gg 1))}\in\{-1,+1\}.$$
The bit count here is exactly the number of overlapping occurrences of the binary pattern \(11\) inside the expansion of \(n\). Its prefix walk is
$$A(n)=\sum_{k=0}^{n} b(k).$$
For integers \(t\ge 1\) and \(1\le c\le t\), define \(g(t,c)\) as the \(c\)-th nonnegative index \(n\) such that \(A(n)=t\). The program evaluates
$$\sum_{t=2}^{45} g(F_t,F_{t-1}),\qquad F_0=F_1=1.$$
A direct simulation would have to generate the walk up to extremely large indices. The local C++, Python, and Java implementations avoid that completely: they count how often level \(t\) has appeared up to a bound \(x\), then invert that monotone counting function by binary search.
Write
$$q(n)=\operatorname{popcount}(n \mathbin{\&} (n \gg 1)) \bmod 2,$$
so that \(b(n)=(-1)^{q(n)}\). Looking at the last two binary digits gives four exact identities:
$$q(4m)=q(m),\qquad q(4m+1)=q(m),$$
$$q(4m+2)\equiv q(m)+m \pmod 2,\qquad q(4m+3)\equiv q(m)+m+1 \pmod 2.$$
Therefore
$$b(4m)=b(m),\qquad b(4m+1)=b(m),$$
$$b(4m+2)=(-1)^m b(m),\qquad b(4m+3)=-(-1)^m b(m).$$
This 4-block structure is the real mathematical source of the recursion in all three solution files.
Summing one whole block gives
$$b(4m)+b(4m+1)+b(4m+2)+b(4m+3)=2b(m).$$
After accumulating blocks from \(0\) to \(m\), we obtain
$$A(4m+3)=2A(m).$$
Using neighboring terms inside the same block then yields the exact formulas used implicitly by the code:
$$A(4m)=2A(m)-b(m),\qquad A(4m+1)=2A(m),$$
$$A(4m+2)=2A(m)+(-1)^m b(m),\qquad A(4m+3)=2A(m).$$
So every recursive call reduces the index scale from \(x\) to roughly \(x/4\).
The implementations memoize two functions:
$$P_t(x)=\#\{0\le n\le x: A(n)=t,\ b(n)=+1\},$$
$$N_t(x)=\#\{0\le n\le x: A(n)=t,\ b(n)=-1\}.$$
The total number of visits to level \(t\) up to \(x\) is then
$$C_t(x)=P_t(x)+N_t(x),$$
and the selector function is recovered by monotone inversion:
$$g(t,c)=\min\{x\ge 0 : C_t(x)\ge c\}.$$
This sign split is essential. The formulas for \(A(4m)\) and \(A(4m+2)\) depend on \(b(m)\), so a single counter for \(A(n)=t\) would discard information needed by the next recursive level.
Every summand \(b(k)\) is odd, hence
$$A(m)\equiv m+1 \pmod 2.$$
So if \(A(m)=u\), then \(m\equiv u-1 \pmod 2\); if \(A(m)=u+1\), then \(m\equiv u \pmod 2\). This observation lets the code replace the parity of the unknown index \(m\) by the parity of the known level parameter.
For compact notation define
$$x_r=\left\lfloor\frac{x-r}{4}\right\rfloor,\qquad r\in\{0,1,2,3\}.$$
If \(t=2u\), then only residues \(1\) and \(3\) can contribute, because \(A(4m)\) and \(A(4m+2)\) are always odd. From \(A(4m+1)=A(4m+3)=2A(m)\) we get
$$P_{2u}(x)=P_u(x_1)+ \begin{cases} P_u(x_3), & u \text{ even},\\ N_u(x_3), & u \text{ odd}, \end{cases}$$
$$N_{2u}(x)=N_u(x_1)+ \begin{cases} N_u(x_3), & u \text{ even},\\ P_u(x_3), & u \text{ odd}. \end{cases}$$
The switch at residue \(3\) comes from
$$b(4m+3)=-(-1)^m b(m)=(-1)^u b(m),$$
because \(A(m)=u\) forces \(m\equiv u-1\pmod 2\). When \(u\) is even, the sign is preserved; when \(u\) is odd, it flips.
If \(t=2u+1\), only residues \(0\) and \(2\) are possible. For \(n=4m\), the equation
$$A(4m)=2A(m)-b(m)=2u+1$$
forces exactly two cases:
$$A(m)=u \text{ with } b(m)=-1,\qquad A(m)=u+1 \text{ with } b(m)=+1.$$
For \(n=4m+2\), the equation
$$A(4m+2)=2A(m)+(-1)^m b(m)=2u+1$$
together with the parity rule determines whether the source state is counted by \(P_u\) or \(N_u\), and likewise for \(u+1\). The final recurrence is
$$P_{2u+1}(x)= \begin{cases} P_u(x_2)+P_{u+1}(x_0), & u \text{ odd},\\ N_u(x_2)+P_{u+1}(x_0), & u \text{ even}, \end{cases}$$
$$N_{2u+1}(x)= \begin{cases} N_u(x_0)+P_{u+1}(x_2), & u \text{ odd},\\ N_u(x_0)+N_{u+1}(x_2), & u \text{ even}. \end{cases}$$
Those are exactly the four branches in prefix_counts / prefixCounts in the local Python, C++, and Java sources.
Let \(T(t)\) be the total number of visits to level \(t\) over the entire infinite walk. Taking \(x\to\infty\) in the recurrences gives
$$T(1)=1,\qquad T(2u)=2T(u),\qquad T(2u+1)=T(u)+T(u+1).$$
The simple function \(T(t)=t\) satisfies the same recurrence and the same base case, so
$$T(t)=t.$$
This explains the guard c > t in the code: level \(t\) is reached exactly \(t\) times, so the \(c\)-th hit exists precisely when \(1\le c\le t\).
The first prefix values are
$$A(0),A(1),A(2),\dots = 1,2,3,2,3,4,3,4,5,6,7,6,\dots$$
Hence level \(5\) is hit at
$$n=8,12,14,16,26,\dots$$
so
$$g(5,3)=14.$$
This also matches the total-count theorem above: level \(5\) appears exactly five times, and the third occurrence is at index \(14\).
The core routine in each language is prefix_counts(t, x) or prefixCounts(t, x). It memoizes the pair \((P_t(x),N_t(x))\) with the boundary conditions \(t=0\), \(x<0\), and \(t=1\). The helper count_total just adds the two components.
The function g(t, c) first doubles an upper bound hi until count_total(t, hi) >= c, then binary-searches the smallest valid index. Finally, solve() builds Fibonacci numbers with \(F_0=F_1=1\) and sums g(F_t, F_{t-1}) for \(2\le t\le 45\).
The C++ version adds two implementation details beyond the bare mathematics: it contains an internal checkpoint g(54321, 12345) = 1220847710, and it can split the 44 independent Fibonacci queries across threads. The Python and Java files are direct single-thread translations of the same recursion.
A single evaluation of \(C_t(x)\) only explores memoized states obtained by replacing \((t,x)\) with smaller arguments such as \((\lfloor t/2\rfloor,\lfloor x/4\rfloor)\) or \((\lfloor t/2\rfloor+1,\lfloor x/4\rfloor)\). The recursion depth is therefore logarithmic in \(x\), and the number of cached states stays tiny compared with scanning every index up to \(x\).
Finding \(g(t,c)\) adds one exponential search for an upper bound and then a binary search, so the number of counter evaluations is \(O(\log g(t,c))\). The whole solve loop performs this process only 44 times, which is why the recursive counting approach is practical while brute force is not.
solutionsCpp/Euler384.cpp, solutionsPython/Euler384.py, solutionsJava/Euler384.java.Die in den Lösungen verwendete Rudin-Shapiro-Vorzeichenfolge lautet
$$b(n)=(-1)^{\operatorname{popcount}(n \mathbin{\&} (n \gg 1))}\in\{-1,+1\}.$$
Die Bitanzahl zählt genau die überlappenden Vorkommen des Musters \(11\) in der Binärdarstellung von \(n\). Der zugehörige Präfixweg ist
$$A(n)=\sum_{k=0}^{n} b(k).$$
Für ganze Zahlen \(t\ge 1\) und \(1\le c\le t\) sei \(g(t,c)\) der \(c\)-te nichtnegative Index \(n\) mit \(A(n)=t\). Das Programm berechnet
$$\sum_{t=2}^{45} g(F_t,F_{t-1}),\qquad F_0=F_1=1.$$
Eine direkte Simulation müsste den Weg bis zu enormen Indizes erzeugen. Die lokalen C++-, Python- und Java-Dateien umgehen das vollständig: Sie zählen zuerst, wie oft das Niveau \(t\) bis zu einer Schranke \(x\) erreicht wurde, und invertieren diese monotone Zählfunktion anschließend per binärer Suche.
Setze
$$q(n)=\operatorname{popcount}(n \mathbin{\&} (n \gg 1)) \bmod 2,$$
dann ist \(b(n)=(-1)^{q(n)}\). Eine Fallunterscheidung nach den letzten zwei Bits liefert
$$q(4m)=q(m),\qquad q(4m+1)=q(m),$$
$$q(4m+2)\equiv q(m)+m \pmod 2,\qquad q(4m+3)\equiv q(m)+m+1 \pmod 2.$$
Also folgt
$$b(4m)=b(m),\qquad b(4m+1)=b(m),$$
$$b(4m+2)=(-1)^m b(m),\qquad b(4m+3)=-(-1)^m b(m).$$
Genau diese 4er-Blockstruktur ist die mathematische Grundlage der Rekursion in allen drei Implementierungen.
Die Summe über einen vollständigen Block ist
$$b(4m)+b(4m+1)+b(4m+2)+b(4m+3)=2b(m).$$
Nach Aufsummieren der Blöcke von \(0\) bis \(m\) erhält man
$$A(4m+3)=2A(m).$$
Daraus ergeben sich die übrigen Werte im selben Block:
$$A(4m)=2A(m)-b(m),\qquad A(4m+1)=2A(m),$$
$$A(4m+2)=2A(m)+(-1)^m b(m),\qquad A(4m+3)=2A(m).$$
Darum reduziert jeder rekursive Schritt die Indexgröße von \(x\) auf ungefähr \(x/4\).
Die Implementierungen memoizieren nicht nur eine einzige Zählfunktion, sondern das Paar
$$P_t(x)=\#\{0\le n\le x: A(n)=t,\ b(n)=+1\},$$
$$N_t(x)=\#\{0\le n\le x: A(n)=t,\ b(n)=-1\}.$$
Die Gesamtzahl der Treffer von Niveau \(t\) bis \(x\) ist dann
$$C_t(x)=P_t(x)+N_t(x),$$
und der Selektor wird durch monotone Inversion gewonnen:
$$g(t,c)=\min\{x\ge 0 : C_t(x)\ge c\}.$$
Diese Aufspaltung nach dem Vorzeichen ist unverzichtbar. Die Formeln für \(A(4m)\) und \(A(4m+2)\) hängen von \(b(m)\) ab; ein einzelner Zähler für \(A(n)=t\) würde genau diese Information verlieren.
Jeder Summand \(b(k)\) ist ungerade, also gilt
$$A(m)\equiv m+1 \pmod 2.$$
Wenn \(A(m)=u\) ist, dann folgt \(m\equiv u-1 \pmod 2\); wenn \(A(m)=u+1\) ist, dann gilt \(m\equiv u \pmod 2\). Damit kann der Code die Parität des unbekannten Index \(m\) durch die Parität des bekannten Niveaus ersetzen.
Zur Abkürzung setzen wir
$$x_r=\left\lfloor\frac{x-r}{4}\right\rfloor,\qquad r\in\{0,1,2,3\}.$$
Für \(t=2u\) kommen nur die Reste \(1\) und \(3\) infrage, denn \(A(4m)\) und \(A(4m+2)\) sind stets ungerade. Aus \(A(4m+1)=A(4m+3)=2A(m)\) folgt
$$P_{2u}(x)=P_u(x_1)+ \begin{cases} P_u(x_3), & u \text{ gerade},\\ N_u(x_3), & u \text{ ungerade}, \end{cases}$$
$$N_{2u}(x)=N_u(x_1)+ \begin{cases} N_u(x_3), & u \text{ gerade},\\ P_u(x_3), & u \text{ ungerade}. \end{cases}$$
Der Wechsel beim Rest \(3\) stammt von
$$b(4m+3)=-(-1)^m b(m)=(-1)^u b(m),$$
weil aus \(A(m)=u\) bereits \(m\equiv u-1\pmod 2\) folgt. Für gerades \(u\) bleibt das Vorzeichen erhalten, für ungerades \(u\) wird es vertauscht.
Für \(t=2u+1\) sind nur die Reste \(0\) und \(2\) möglich. Bei \(n=4m\) erzwingt
$$A(4m)=2A(m)-b(m)=2u+1$$
genau zwei Fälle:
$$A(m)=u \text{ mit } b(m)=-1,\qquad A(m)=u+1 \text{ mit } b(m)=+1.$$
Für \(n=4m+2\) bestimmt
$$A(4m+2)=2A(m)+(-1)^m b(m)=2u+1$$
zusammen mit der Paritätsregel, ob der Beitrag aus \(P_u\) oder \(N_u\) stammt, und entsprechend aus \(u+1\). Damit ergibt sich
$$P_{2u+1}(x)= \begin{cases} P_u(x_2)+P_{u+1}(x_0), & u \text{ ungerade},\\ N_u(x_2)+P_{u+1}(x_0), & u \text{ gerade}, \end{cases}$$
$$N_{2u+1}(x)= \begin{cases} N_u(x_0)+P_{u+1}(x_2), & u \text{ ungerade},\\ N_u(x_0)+N_{u+1}(x_2), & u \text{ gerade}. \end{cases}$$
Dies sind exakt die vier Verzweigungen in prefix_counts beziehungsweise prefixCounts in den lokalen Python-, C++- und Java-Dateien.
Sei \(T(t)\) die Gesamtzahl aller Besuche des Niveaus \(t\) im unendlichen Weg. Lässt man in den Rekursionen \(x\to\infty\) gehen, erhält man
$$T(1)=1,\qquad T(2u)=2T(u),\qquad T(2u+1)=T(u)+T(u+1).$$
Die einfache Funktion \(T(t)=t\) erfüllt dieselbe Rekursion mit demselben Anfangswert, also
$$T(t)=t.$$
Das erklärt die Abfrage c > t im Code: Niveau \(t\) wird genau \(t\)-mal erreicht, also existiert der \(c\)-te Treffer genau für \(1\le c\le t\).
Die ersten Präfixwerte sind
$$A(0),A(1),A(2),\dots = 1,2,3,2,3,4,3,4,5,6,7,6,\dots$$
Niveau \(5\) wird daher an den Stellen
$$n=8,12,14,16,26,\dots$$
erreicht, also
$$g(5,3)=14.$$
Das passt auch zum Satz oben: Niveau \(5\) erscheint insgesamt genau fünfmal, und der dritte Treffer liegt bei Index \(14\).
Die zentrale Routine in jeder Sprache ist prefix_counts(t, x) oder prefixCounts(t, x). Sie memoiziert das Paar \((P_t(x),N_t(x))\) mit den Randfällen \(t=0\), \(x<0\) und \(t=1\). Die Hilfsfunktion count_total addiert lediglich beide Komponenten.
Die Funktion g(t, c) verdoppelt zunächst eine obere Schranke hi, bis count_total(t, hi) >= c gilt, und sucht dann per Binärsuche den kleinsten gültigen Index. Danach baut solve() die Fibonacci-Werte mit \(F_0=F_1=1\) auf und summiert g(F_t, F_{t-1}) für \(2\le t\le 45\).
Die C++-Version ergänzt zwei technische Punkte, die die Mathematik nicht verändern: einen internen Kontrollwert g(54321, 12345) = 1220847710 sowie optionale Parallelisierung der 44 unabhängigen Fibonacci-Anfragen. Python und Java sind direkte einsträngige Übersetzungen derselben Rekursion.
Eine einzelne Auswertung von \(C_t(x)\) besucht nur memoizierte Zustände, die aus \((t,x)\) durch Verkleinern auf Argumente wie \((\lfloor t/2\rfloor,\lfloor x/4\rfloor)\) oder \((\lfloor t/2\rfloor+1,\lfloor x/4\rfloor)\) entstehen. Die Rekursionstiefe ist daher logarithmisch in \(x\), und die Zahl der Cache-Zustände bleibt winzig im Vergleich zu einer vollständigen Enumeration bis \(x\).
Für \(g(t,c)\) kommt eine exponentielle Suche nach einer oberen Schranke und danach eine Binärsuche hinzu; damit ist die Zahl der Zählerauswertungen \(O(\log g(t,c))\). Die gesamte Lösung führt diesen Prozess nur 44-mal aus, weshalb die rekursive Zählmethode praktisch ist, brute force aber nicht.
solutionsCpp/Euler384.cpp, solutionsPython/Euler384.py, solutionsJava/Euler384.java.Çözümlerde kullanılan Rudin-Shapiro işaret dizisi
$$b(n)=(-1)^{\operatorname{popcount}(n \mathbin{\&} (n \gg 1))}\in\{-1,+1\}$$
şeklindedir. Buradaki bit sayımı, \(n\)'in ikilik yazımındaki üst üste binen \(11\) örüntülerinin sayısını verir. Ön ek yürüyüşü
$$A(n)=\sum_{k=0}^{n} b(k)$$
olarak tanımlanır. \(t\ge 1\) ve \(1\le c\le t\) için \(g(t,c)\), \(A(n)=t\) eşitliğini sağlayan \(c\). negatif olmayan indeks olsun. Programın hesapladığı toplam
$$\sum_{t=2}^{45} g(F_t,F_{t-1}),\qquad F_0=F_1=1$$
ifadesidir. Doğrudan simülasyon yapmak, yürüyüşü çok büyük indekslere kadar üretmeyi gerektirir. Yerel C++, Python ve Java çözümleri bunu hiç yapmaz; önce seviye \(t\)'nin \(x\)'e kadar kaç kez görüldüğünü sayar, sonra bu monoton sayım fonksiyonunu ikili arama ile tersler.
Şöyle yazalım:
$$q(n)=\operatorname{popcount}(n \mathbin{\&} (n \gg 1)) \bmod 2,$$
böylece \(b(n)=(-1)^{q(n)}\) olur. Son iki bite göre ayrım yapınca
$$q(4m)=q(m),\qquad q(4m+1)=q(m),$$
$$q(4m+2)\equiv q(m)+m \pmod 2,\qquad q(4m+3)\equiv q(m)+m+1 \pmod 2$$
elde edilir. Dolayısıyla
$$b(4m)=b(m),\qquad b(4m+1)=b(m),$$
$$b(4m+2)=(-1)^m b(m),\qquad b(4m+3)=-(-1)^m b(m).$$
Tüm rekürsiyonun temelinde bu 4-blok yapısı vardır.
Bir tam bloğun toplamı
$$b(4m)+b(4m+1)+b(4m+2)+b(4m+3)=2b(m)$$
olur. \(0\)'dan \(m\)'ye kadar blokları toplayınca
$$A(4m+3)=2A(m)$$
elde edilir. Aynı blok içindeki komşu değerlerden de
$$A(4m)=2A(m)-b(m),\qquad A(4m+1)=2A(m),$$
$$A(4m+2)=2A(m)+(-1)^m b(m),\qquad A(4m+3)=2A(m)$$
çıkar. Kodun sürekli \(\left\lfloor\frac{x-r}{4}\right\rfloor\) biçimindeki alt problemlere inmesinin nedeni budur.
İmplementasyonlar tek bir sayaç değil, şu iki fonksiyonu memoize eder:
$$P_t(x)=\#\{0\le n\le x: A(n)=t,\ b(n)=+1\},$$
$$N_t(x)=\#\{0\le n\le x: A(n)=t,\ b(n)=-1\}.$$
Toplam ziyaret sayısı
$$C_t(x)=P_t(x)+N_t(x)$$
olur ve aranan seçici fonksiyon
$$g(t,c)=\min\{x\ge 0 : C_t(x)\ge c\}$$
şeklinde elde edilir. İşaret ayrımı zorunludur; çünkü \(A(4m)\) ve \(A(4m+2)\) formülleri \(b(m)\)'ye bağlıdır. Sadece \(A(n)=t\) sayısını tutmak, bir sonraki rekürsiyon adımı için gerekli bilgiyi kaybettirir.
Her \(b(k)\) değeri tek olduğundan
$$A(m)\equiv m+1 \pmod 2$$
olur. Dolayısıyla \(A(m)=u\) ise \(m\equiv u-1 \pmod 2\), \(A(m)=u+1\) ise \(m\equiv u \pmod 2\). Böylece bilinmeyen indeks \(m\)'nin paritesi, bilinen seviye parametresinin paritesiyle ifade edilir.
Kısa yazım için
$$x_r=\left\lfloor\frac{x-r}{4}\right\rfloor,\qquad r\in\{0,1,2,3\}$$
tanımını yapalım.
\(t=2u\) olduğunda yalnızca kalan sınıfları \(1\) ve \(3\) katkı yapabilir; çünkü \(A(4m)\) ve \(A(4m+2)\) her zaman tektir. \(A(4m+1)=A(4m+3)=2A(m)\) olduğundan
$$P_{2u}(x)=P_u(x_1)+ \begin{cases} P_u(x_3), & u \text{ çift},\\ N_u(x_3), & u \text{ tek}, \end{cases}$$
$$N_{2u}(x)=N_u(x_1)+ \begin{cases} N_u(x_3), & u \text{ çift},\\ P_u(x_3), & u \text{ tek}. \end{cases}$$
\(x_3\) kolundaki yer değiştirme şu özdeşlikten gelir:
$$b(4m+3)=-(-1)^m b(m)=(-1)^u b(m),$$
çünkü \(A(m)=u\) ise zaten \(m\equiv u-1\pmod 2\) bilinir. \(u\) çiftse işaret korunur, tekse ters döner.
\(t=2u+1\) olduğunda sadece \(0\) ve \(2\) kalanları mümkündür. \(n=4m\) için
$$A(4m)=2A(m)-b(m)=2u+1$$
eşitliği tam olarak iki duruma izin verir:
$$A(m)=u \text{ ve } b(m)=-1,\qquad A(m)=u+1 \text{ ve } b(m)=+1.$$
\(n=4m+2\) için
$$A(4m+2)=2A(m)+(-1)^m b(m)=2u+1$$
eşitliği ve parite kuralı birlikte, katkının \(P_u\) mu \(N_u\) mu tarafından geldiğini belirler; aynı mantık \(u+1\) için de geçerlidir. Sonuç olarak
$$P_{2u+1}(x)= \begin{cases} P_u(x_2)+P_{u+1}(x_0), & u \text{ tek},\\ N_u(x_2)+P_{u+1}(x_0), & u \text{ çift}, \end{cases}$$
$$N_{2u+1}(x)= \begin{cases} N_u(x_0)+P_{u+1}(x_2), & u \text{ tek},\\ N_u(x_0)+N_{u+1}(x_2), & u \text{ çift}. \end{cases}$$
Yerel Python, C++ ve Java dosyalarındaki prefix_counts / prefixCounts dalları birebir bunlardır.
\(T(t)\), sonsuz yürüyüş boyunca seviye \(t\)'nin toplam ziyaret sayısı olsun. Rekürsiyonda \(x\to\infty\) alınırsa
$$T(1)=1,\qquad T(2u)=2T(u),\qquad T(2u+1)=T(u)+T(u+1)$$
elde edilir. \(T(t)=t\) fonksiyonu aynı başlangıç ve aynı rekürsiyonu sağladığı için
$$T(t)=t$$
sonucuna varılır. Kodda görülen c > t kontrolünün nedeni budur: seviye \(t\) tam olarak \(t\) kez ziyaret edilir.
İlk ön ek değerleri
$$A(0),A(1),A(2),\dots = 1,2,3,2,3,4,3,4,5,6,7,6,\dots$$
şeklindedir. Buna göre seviye \(5\)
$$n=8,12,14,16,26,\dots$$
indekslerinde görülür. Dolayısıyla
$$g(5,3)=14.$$
Bu aynı zamanda yukarıdaki toplam-zaman teoremiyle de uyumludur: seviye \(5\) toplam beş kez görünür ve üçüncü görünme \(14\). indextedir.
Her dildeki ana yordam prefix_counts(t, x) ya da prefixCounts(t, x) fonksiyonudur. Bu fonksiyon \((P_t(x),N_t(x))\) çiftini, \(t=0\), \(x<0\) ve \(t=1\) sınır durumlarıyla birlikte önbelleğe alır. count_total yardımcı fonksiyonu ise yalnızca iki bileşeni toplar.
g(t, c) önce count_total(t, hi) >= c olana kadar üst sınır hi'yi iki katına çıkarır, sonra en küçük uygun indeksi ikili arama ile bulur. Son olarak solve(), \(F_0=F_1=1\) kuralıyla Fibonacci sayılarını üretir ve \(2\le t\le 45\) için g(F_t, F_{t-1}) toplamını alır.
C++ sürümünde matematiği değiştirmeyen iki mühendislik ayrıntısı daha vardır: iç kontrol değeri olarak g(54321, 12345) = 1220847710 kullanılır ve birbirinden bağımsız 44 Fibonacci sorgusu istenirse çok iş parçacıklı çalıştırılabilir. Python ve Java dosyaları aynı rekürsiyonun doğrudan tek iş parçacıklı çevirileridir.
Tek bir \(C_t(x)\) değerlendirmesi, \((t,x)\) durumunu \((\lfloor t/2\rfloor,\lfloor x/4\rfloor)\) veya \((\lfloor t/2\rfloor+1,\lfloor x/4\rfloor)\) gibi daha küçük durumlara indiren memoize edilmiş çağrıları ziyaret eder. Bu nedenle özyineleme derinliği \(x\) açısından logaritmiktir ve önbellekte tutulan durum sayısı, \(x\)'e kadar doğrusal taramaya göre çok küçüktür.
\(g(t,c)\) hesaplanırken buna bir üst sınır bulmak için üstel arama ve ardından ikili arama eklenir; dolayısıyla sayaç değerlendirme sayısı \(O(\log g(t,c))\) olur. Tüm çözüm yalnızca 44 sorgu yaptığı için bu yaklaşım pratiktir; kaba kuvvet yaklaşımı ise değildir.
solutionsCpp/Euler384.cpp, solutionsPython/Euler384.py, solutionsJava/Euler384.java.La secuencia de signos de Rudin-Shapiro usada por las soluciones es
$$b(n)=(-1)^{\operatorname{popcount}(n \mathbin{\&} (n \gg 1))}\in\{-1,+1\}.$$
Ese conteo de bits coincide con el número de apariciones solapadas del patrón binario \(11\) en \(n\). Su caminata prefija es
$$A(n)=\sum_{k=0}^{n} b(k).$$
Para enteros \(t\ge 1\) y \(1\le c\le t\), \(g(t,c)\) es el \(c\)-ésimo índice no negativo \(n\) tal que \(A(n)=t\). El programa calcula
$$\sum_{t=2}^{45} g(F_t,F_{t-1}),\qquad F_0=F_1=1.$$
Una simulación directa tendría que generar la caminata hasta índices enormes. Los archivos locales en C++, Python y Java evitan eso por completo: primero cuentan cuántas veces se alcanzó el nivel \(t\) hasta un límite \(x\), y luego invierten esa función monótona mediante búsqueda binaria.
Definamos
$$q(n)=\operatorname{popcount}(n \mathbin{\&} (n \gg 1)) \bmod 2,$$
de modo que \(b(n)=(-1)^{q(n)}\). Al mirar los dos bits menos significativos se obtiene
$$q(4m)=q(m),\qquad q(4m+1)=q(m),$$
$$q(4m+2)\equiv q(m)+m \pmod 2,\qquad q(4m+3)\equiv q(m)+m+1 \pmod 2.$$
Por tanto,
$$b(4m)=b(m),\qquad b(4m+1)=b(m),$$
$$b(4m+2)=(-1)^m b(m),\qquad b(4m+3)=-(-1)^m b(m).$$
Esta estructura en bloques de tamaño 4 es la verdadera fuente matemática de la recursión implementada.
La suma de un bloque completo vale
$$b(4m)+b(4m+1)+b(4m+2)+b(4m+3)=2b(m).$$
Al acumular bloques desde \(0\) hasta \(m\) se obtiene
$$A(4m+3)=2A(m).$$
Y, dentro del mismo bloque, se deduce
$$A(4m)=2A(m)-b(m),\qquad A(4m+1)=2A(m),$$
$$A(4m+2)=2A(m)+(-1)^m b(m),\qquad A(4m+3)=2A(m).$$
Por eso cada llamada recursiva reduce la escala del índice de \(x\) a aproximadamente \(x/4\).
Las implementaciones memoizan el par
$$P_t(x)=\#\{0\le n\le x: A(n)=t,\ b(n)=+1\},$$
$$N_t(x)=\#\{0\le n\le x: A(n)=t,\ b(n)=-1\}.$$
Entonces el número total de visitas al nivel \(t\) hasta \(x\) es
$$C_t(x)=P_t(x)+N_t(x),$$
y el selector buscado se recupera mediante
$$g(t,c)=\min\{x\ge 0 : C_t(x)\ge c\}.$$
Separar por signo es indispensable. Las expresiones de \(A(4m)\) y \(A(4m+2)\) dependen de \(b(m)\), así que un solo contador para \(A(n)=t\) perdería justo la información necesaria en el siguiente nivel recursivo.
Cada sumando \(b(k)\) es impar, de modo que
$$A(m)\equiv m+1 \pmod 2.$$
Por lo tanto, si \(A(m)=u\), entonces \(m\equiv u-1 \pmod 2\); si \(A(m)=u+1\), entonces \(m\equiv u \pmod 2\). Así la implementación sustituye la paridad del índice desconocido \(m\) por la paridad del nivel conocido.
Usaremos la abreviatura
$$x_r=\left\lfloor\frac{x-r}{4}\right\rfloor,\qquad r\in\{0,1,2,3\}.$$
Si \(t=2u\), solo pueden contribuir los residuos \(1\) y \(3\), porque \(A(4m)\) y \(A(4m+2)\) siempre son impares. A partir de \(A(4m+1)=A(4m+3)=2A(m)\) se obtiene
$$P_{2u}(x)=P_u(x_1)+ \begin{cases} P_u(x_3), & u \text{ par},\\ N_u(x_3), & u \text{ impar}, \end{cases}$$
$$N_{2u}(x)=N_u(x_1)+ \begin{cases} N_u(x_3), & u \text{ par},\\ P_u(x_3), & u \text{ impar}. \end{cases}$$
El intercambio en el residuo \(3\) proviene de
$$b(4m+3)=-(-1)^m b(m)=(-1)^u b(m),$$
porque \(A(m)=u\) obliga a \(m\equiv u-1\pmod 2\). Si \(u\) es par el signo se conserva; si \(u\) es impar se invierte.
Si \(t=2u+1\), solo son posibles los residuos \(0\) y \(2\). Para \(n=4m\), la ecuación
$$A(4m)=2A(m)-b(m)=2u+1$$
produce exactamente dos posibilidades:
$$A(m)=u \text{ con } b(m)=-1,\qquad A(m)=u+1 \text{ con } b(m)=+1.$$
Para \(n=4m+2\), la ecuación
$$A(4m+2)=2A(m)+(-1)^m b(m)=2u+1$$
junto con la regla de paridad decide si la contribución proviene de \(P_u\) o de \(N_u\), y del mismo modo para \(u+1\). El resultado final es
$$P_{2u+1}(x)= \begin{cases} P_u(x_2)+P_{u+1}(x_0), & u \text{ impar},\\ N_u(x_2)+P_{u+1}(x_0), & u \text{ par}, \end{cases}$$
$$N_{2u+1}(x)= \begin{cases} N_u(x_0)+P_{u+1}(x_2), & u \text{ impar},\\ N_u(x_0)+N_{u+1}(x_2), & u \text{ par}. \end{cases}$$
Estas son exactamente las ramas implementadas en prefix_counts / prefixCounts en los archivos locales.
Sea \(T(t)\) el número total de visitas al nivel \(t\) en toda la caminata infinita. Tomando \(x\to\infty\) en las recurrencias se obtiene
$$T(1)=1,\qquad T(2u)=2T(u),\qquad T(2u+1)=T(u)+T(u+1).$$
La función simple \(T(t)=t\) satisface la misma recurrencia y la misma condición inicial, así que
$$T(t)=t.$$
Esto explica la condición c > t del código: el nivel \(t\) se visita exactamente \(t\) veces, luego la visita número \(c\) existe si y solo si \(1\le c\le t\).
Los primeros valores de la suma prefija son
$$A(0),A(1),A(2),\dots = 1,2,3,2,3,4,3,4,5,6,7,6,\dots$$
Por tanto, el nivel \(5\) aparece en
$$n=8,12,14,16,26,\dots$$
y entonces
$$g(5,3)=14.$$
Esto también concuerda con el resultado global: el nivel \(5\) aparece exactamente cinco veces y la tercera visita ocurre en el índice \(14\).
La rutina central en cada lenguaje es prefix_counts(t, x) o prefixCounts(t, x). Memoiza el par \((P_t(x),N_t(x))\) con las condiciones frontera \(t=0\), \(x<0\) y \(t=1\). La función auxiliar count_total solo suma ambos componentes.
La función g(t, c) duplica primero una cota superior hi hasta que count_total(t, hi) >= c, y luego hace búsqueda binaria para hallar el menor índice válido. Después, solve() construye los Fibonacci con \(F_0=F_1=1\) y suma g(F_t, F_{t-1}) para \(2\le t\le 45\).
La versión en C++ añade dos detalles de ingeniería que no cambian la matemática: un punto de control interno g(54321, 12345) = 1220847710, y la posibilidad de repartir entre hilos las 44 consultas independientes. Los archivos de Python y Java son traducciones directas y monohilo de la misma recursión.
Una evaluación de \(C_t(x)\) solo visita estados memoizados que sustituyen \((t,x)\) por argumentos más pequeños, como \((\lfloor t/2\rfloor,\lfloor x/4\rfloor)\) o \((\lfloor t/2\rfloor+1,\lfloor x/4\rfloor)\). La profundidad recursiva es por tanto logarítmica en \(x\), y el número de estados en caché es minúsculo comparado con recorrer todos los índices hasta \(x\).
Para hallar \(g(t,c)\) se añade una búsqueda exponencial de una cota superior y después una búsqueda binaria, así que el número de evaluaciones del contador es \(O(\log g(t,c))\). El programa completo solo repite este proceso 44 veces, por eso el método recursivo es práctico y la fuerza bruta no lo es.
solutionsCpp/Euler384.cpp, solutionsPython/Euler384.py, solutionsJava/Euler384.java.本题使用的 Rudin-Shapiro 符号序列为
$$b(n)=(-1)^{\operatorname{popcount}(n \mathbin{\&} (n \gg 1))}\in\{-1,+1\}.$$
这里的位计数，正好等于 \(n\) 的二进制表示中重叠出现的 \(11\) 模式个数。定义前缀和游走
$$A(n)=\sum_{k=0}^{n} b(k).$$
对整数 \(t\ge 1\) 与 \(1\le c\le t\)，记 \(g(t,c)\) 为满足 \(A(n)=t\) 的第 \(c\) 个非负整数 \(n\)。程序计算的是
$$\sum_{t=2}^{45} g(F_t,F_{t-1}),\qquad F_0=F_1=1.$$
如果直接模拟，就必须把整条游走生成到极大的下标。仓库中的 C++、Python、Java 实现都没有这么做，而是先计算“到 \(x\) 为止，层 \(t\) 出现了多少次”，再用二分搜索反求第 \(c\) 次出现的位置。
记
$$q(n)=\operatorname{popcount}(n \mathbin{\&} (n \gg 1)) \bmod 2,$$
于是 \(b(n)=(-1)^{q(n)}\)。考察最低两位，可以得到精确关系
$$q(4m)=q(m),\qquad q(4m+1)=q(m),$$
$$q(4m+2)\equiv q(m)+m \pmod 2,\qquad q(4m+3)\equiv q(m)+m+1 \pmod 2.$$
因此
$$b(4m)=b(m),\qquad b(4m+1)=b(m),$$
$$b(4m+2)=(-1)^m b(m),\qquad b(4m+3)=-(-1)^m b(m).$$
这正是三个解法文件共同利用的 4 块自相似结构。
一个完整四项块的总和为
$$b(4m)+b(4m+1)+b(4m+2)+b(4m+3)=2b(m).$$
把这些块从 \(0\) 累加到 \(m\)，得到
$$A(4m+3)=2A(m).$$
再利用同一块内的相邻项，就有
$$A(4m)=2A(m)-b(m),\qquad A(4m+1)=2A(m),$$
$$A(4m+2)=2A(m)+(-1)^m b(m),\qquad A(4m+3)=2A(m).$$
因此递归每一步都把索引规模从 \(x\) 压缩到大约 \(x/4\)。
程序不是只记一个函数，而是记下面这一对：
$$P_t(x)=\#\{0\le n\le x: A(n)=t,\ b(n)=+1\},$$
$$N_t(x)=\#\{0\le n\le x: A(n)=t,\ b(n)=-1\}.$$
则到 \(x\) 为止层 \(t\) 的总出现次数是
$$C_t(x)=P_t(x)+N_t(x),$$
而所求位置函数满足
$$g(t,c)=\min\{x\ge 0 : C_t(x)\ge c\}.$$
这个正负拆分是必要的，因为 \(A(4m)\) 与 \(A(4m+2)\) 的表达式都依赖 \(b(m)\)。如果只保留“层 \(t\) 出现了多少次”，就会丢掉下一层递归必须知道的信息。
由于每个 \(b(k)\) 都是奇数，所以
$$A(m)\equiv m+1 \pmod 2.$$
于是当 \(A(m)=u\) 时，必有 \(m\equiv u-1 \pmod 2\)；当 \(A(m)=u+1\) 时，必有 \(m\equiv u \pmod 2\)。这样就可以把未知下标 \(m\) 的奇偶性改写成已知层数参数的奇偶性。
记
$$x_r=\left\lfloor\frac{x-r}{4}\right\rfloor,\qquad r\in\{0,1,2,3\}.$$
若 \(t=2u\)，只有余数 \(1\) 与 \(3\) 可能命中该层，因为 \(A(4m)\) 和 \(A(4m+2)\) 恒为奇数。由 \(A(4m+1)=A(4m+3)=2A(m)\) 得
$$P_{2u}(x)=P_u(x_1)+ \begin{cases} P_u(x_3), & u \text{ 为偶数},\\ N_u(x_3), & u \text{ 为奇数}, \end{cases}$$
$$N_{2u}(x)=N_u(x_1)+ \begin{cases} N_u(x_3), & u \text{ 为偶数},\\ P_u(x_3), & u \text{ 为奇数}. \end{cases}$$
其中余数 \(3\) 处分支切换来自
$$b(4m+3)=-(-1)^m b(m)=(-1)^u b(m),$$
因为 \(A(m)=u\) 已经推出 \(m\equiv u-1\pmod 2\)。\(u\) 为偶时符号保持不变，\(u\) 为奇时符号翻转。
若 \(t=2u+1\)，只有余数 \(0\) 和 \(2\) 可能出现。对 \(n=4m\)，方程
$$A(4m)=2A(m)-b(m)=2u+1$$
恰好给出两种可能：
$$A(m)=u \text{ 且 } b(m)=-1,\qquad A(m)=u+1 \text{ 且 } b(m)=+1.$$
对 \(n=4m+2\)，方程
$$A(4m+2)=2A(m)+(-1)^m b(m)=2u+1$$
再结合上面的奇偶规则，就能判断贡献来自 \(P_u\) 还是 \(N_u\)，以及来自 \(u+1\) 的哪一类。最终递推为
$$P_{2u+1}(x)= \begin{cases} P_u(x_2)+P_{u+1}(x_0), & u \text{ 为奇数},\\ N_u(x_2)+P_{u+1}(x_0), & u \text{ 为偶数}, \end{cases}$$
$$N_{2u+1}(x)= \begin{cases} N_u(x_0)+P_{u+1}(x_2), & u \text{ 为奇数},\\ N_u(x_0)+N_{u+1}(x_2), & u \text{ 为偶数}. \end{cases}$$
这与本地三个实现中的 prefix_counts / prefixCounts 分支完全一致。
设 \(T(t)\) 表示无限游走中层 \(t\) 被访问的总次数。令 \(x\to\infty\)，递推化为
$$T(1)=1,\qquad T(2u)=2T(u),\qquad T(2u+1)=T(u)+T(u+1).$$
函数 \(T(t)=t\) 满足同样的初值与递推，因此
$$T(t)=t.$$
这也解释了代码中的 c > t 判断：层 \(t\) 恰好出现 \(t\) 次，所以只有 \(1\le c\le t\) 时第 \(c\) 次出现才存在。
前几个前缀值是
$$A(0),A(1),A(2),\dots = 1,2,3,2,3,4,3,4,5,6,7,6,\dots$$
因此层 \(5\) 出现在
$$n=8,12,14,16,26,\dots$$
所以
$$g(5,3)=14.$$
这也与上面的总访问次数结论一致：层 \(5\) 一共出现五次，而第三次出现在下标 \(14\)。
三种语言里的核心函数都是 prefix_counts(t, x) 或 prefixCounts(t, x)。它对 \((P_t(x),N_t(x))\) 进行记忆化，并处理 \(t=0\)、\(x<0\)、\(t=1\) 这些边界情况。辅助函数 count_total 只负责把两个计数相加。
g(t, c) 先不断把上界 hi 翻倍，直到 count_total(t, hi) >= c，再对最小合法下标做二分搜索。最后 solve() 按 \(F_0=F_1=1\) 构造 Fibonacci 数列，并对 \(2\le t\le 45\) 累加 g(F_t, F_{t-1})。
C++ 版本在数学之外还有两个工程细节：内置检查点 g(54321, 12345) = 1220847710，以及对 44 个彼此独立查询进行可选并行化。Python 和 Java 文件则是同一递推的直接单线程翻译。
一次 \(C_t(x)\) 计算只会访问那些通过 \((t,x)\to(\lfloor t/2\rfloor,\lfloor x/4\rfloor)\) 或 \((\lfloor t/2\rfloor+1,\lfloor x/4\rfloor)\) 等方式得到的更小记忆化状态，因此递归深度对 \(x\) 来说是对数级的，缓存状态数也远小于逐项扫描到 \(x\) 的做法。
求 \(g(t,c)\) 时，还要加上一段指数式扩上界和随后的一次二分，因此计数函数的调用次数为 \(O(\log g(t,c))\)。整个程序只做 44 次这样的查询，所以递归计数方法是可行的，而暴力枚举则不可行。
solutionsCpp/Euler384.cpp, solutionsPython/Euler384.py, solutionsJava/Euler384.java.Используемая в решениях знаковая последовательность Рудина-Шапиро задается формулой
$$b(n)=(-1)^{\operatorname{popcount}(n \mathbin{\&} (n \gg 1))}\in\{-1,+1\}.$$
Подсчет битов здесь равен числу перекрывающихся вхождений шаблона \(11\) в двоичной записи числа \(n\). Ее префиксное блуждание определяется как
$$A(n)=\sum_{k=0}^{n} b(k).$$
Для \(t\ge 1\) и \(1\le c\le t\) обозначим через \(g(t,c)\) \(c\)-й неотрицательный индекс \(n\), для которого \(A(n)=t\). Программа вычисляет
$$\sum_{t=2}^{45} g(F_t,F_{t-1}),\qquad F_0=F_1=1.$$
Прямое моделирование потребовало бы строить блуждание до гигантских индексов. Локальные реализации на C++, Python и Java делают иначе: сначала считают, сколько раз уровень \(t\) встретился до границы \(x\), а затем обращают эту монотонную функцию бинарным поиском.
Положим
$$q(n)=\operatorname{popcount}(n \mathbin{\&} (n \gg 1)) \bmod 2,$$
тогда \(b(n)=(-1)^{q(n)}\). Разбор по двум младшим битам дает точные соотношения
$$q(4m)=q(m),\qquad q(4m+1)=q(m),$$
$$q(4m+2)\equiv q(m)+m \pmod 2,\qquad q(4m+3)\equiv q(m)+m+1 \pmod 2.$$
Отсюда следует
$$b(4m)=b(m),\qquad b(4m+1)=b(m),$$
$$b(4m+2)=(-1)^m b(m),\qquad b(4m+3)=-(-1)^m b(m).$$
Именно эта 4-блочная самоподобная структура лежит в основе рекурсии во всех трех исходниках.
Сумма одного полного блока равна
$$b(4m)+b(4m+1)+b(4m+2)+b(4m+3)=2b(m).$$
Если просуммировать такие блоки от \(0\) до \(m\), получится
$$A(4m+3)=2A(m).$$
Тогда для остальных позиций в том же блоке имеем
$$A(4m)=2A(m)-b(m),\qquad A(4m+1)=2A(m),$$
$$A(4m+2)=2A(m)+(-1)^m b(m),\qquad A(4m+3)=2A(m).$$
Поэтому каждый рекурсивный шаг уменьшает масштаб индекса примерно с \(x\) до \(x/4\).
Реализации мемоизируют не одну функцию, а пару
$$P_t(x)=\#\{0\le n\le x: A(n)=t,\ b(n)=+1\},$$
$$N_t(x)=\#\{0\le n\le x: A(n)=t,\ b(n)=-1\}.$$
Тогда общее число посещений уровня \(t\) до \(x\) равно
$$C_t(x)=P_t(x)+N_t(x),$$
а искомый селектор восстанавливается как
$$g(t,c)=\min\{x\ge 0 : C_t(x)\ge c\}.$$
Разделение по знаку принципиально важно. Формулы для \(A(4m)\) и \(A(4m+2)\) зависят от \(b(m)\), поэтому один только счетчик попаданий в уровень \(t\) потерял бы информацию, необходимую на следующем шаге рекурсии.
Каждое значение \(b(k)\) нечетно, следовательно
$$A(m)\equiv m+1 \pmod 2.$$
Если \(A(m)=u\), то \(m\equiv u-1 \pmod 2\); если \(A(m)=u+1\), то \(m\equiv u \pmod 2\). Тем самым четность неизвестного индекса \(m\) можно заменить четностью известного уровня.
Для краткости обозначим
$$x_r=\left\lfloor\frac{x-r}{4}\right\rfloor,\qquad r\in\{0,1,2,3\}.$$
Если \(t=2u\), подходят только остатки \(1\) и \(3\), поскольку \(A(4m)\) и \(A(4m+2)\) всегда нечетны. Из равенств \(A(4m+1)=A(4m+3)=2A(m)\) получаем
$$P_{2u}(x)=P_u(x_1)+ \begin{cases} P_u(x_3), & u \text{ четно},\\ N_u(x_3), & u \text{ нечетно}, \end{cases}$$
$$N_{2u}(x)=N_u(x_1)+ \begin{cases} N_u(x_3), & u \text{ четно},\\ P_u(x_3), & u \text{ нечетно}. \end{cases}$$
Переключение в ветви с остатком \(3\) объясняется формулой
$$b(4m+3)=-(-1)^m b(m)=(-1)^u b(m),$$
поскольку из \(A(m)=u\) уже следует \(m\equiv u-1\pmod 2\). При четном \(u\) знак сохраняется, при нечетном меняется.
Если \(t=2u+1\), возможны только остатки \(0\) и \(2\). Для \(n=4m\) уравнение
$$A(4m)=2A(m)-b(m)=2u+1$$
дает ровно два варианта:
$$A(m)=u \text{ и } b(m)=-1,\qquad A(m)=u+1 \text{ и } b(m)=+1.$$
Для \(n=4m+2\) уравнение
$$A(4m+2)=2A(m)+(-1)^m b(m)=2u+1$$
вместе с правилом четности определяет, идет ли вклад из \(P_u\) или из \(N_u\), и аналогично для уровня \(u+1\). В итоге
$$P_{2u+1}(x)= \begin{cases} P_u(x_2)+P_{u+1}(x_0), & u \text{ нечетно},\\ N_u(x_2)+P_{u+1}(x_0), & u \text{ четно}, \end{cases}$$
$$N_{2u+1}(x)= \begin{cases} N_u(x_0)+P_{u+1}(x_2), & u \text{ нечетно},\\ N_u(x_0)+N_{u+1}(x_2), & u \text{ четно}. \end{cases}$$
Это в точности соответствует ветвлениям функций prefix_counts / prefixCounts в локальных файлах Python, C++ и Java.
Пусть \(T(t)\) обозначает полное число посещений уровня \(t\) на всей бесконечной траектории. При переходе \(x\to\infty\) рекурсии дают
$$T(1)=1,\qquad T(2u)=2T(u),\qquad T(2u+1)=T(u)+T(u+1).$$
Функция \(T(t)=t\) удовлетворяет тем же соотношениям и тому же базовому случаю, значит
$$T(t)=t.$$
Именно поэтому код сразу отвергает случай c > t: уровень \(t\) встречается ровно \(t\) раз.
Первые значения префиксной суммы таковы:
$$A(0),A(1),A(2),\dots = 1,2,3,2,3,4,3,4,5,6,7,6,\dots$$
Следовательно, уровень \(5\) достигается при
$$n=8,12,14,16,26,\dots$$
и потому
$$g(5,3)=14.$$
Это согласуется и с общей теоремой: уровень \(5\) посещается ровно пять раз, а третье посещение происходит в индексе \(14\).
Центральная процедура на каждом языке называется prefix_counts(t, x) или prefixCounts(t, x). Она мемоизирует пару \((P_t(x),N_t(x))\) с граничными случаями \(t=0\), \(x<0\) и \(t=1\). Вспомогательная функция count_total просто складывает обе компоненты.
Функция g(t, c) сначала удваивает верхнюю границу hi, пока не выполнится count_total(t, hi) >= c, а затем бинарным поиском находит минимальный допустимый индекс. После этого solve() строит числа Фибоначчи с соглашением \(F_0=F_1=1\) и суммирует g(F_t, F_{t-1}) для \(2\le t\le 45\).
Версия на C++ добавляет два инженерных штриха, не меняющих математику: внутреннюю проверку g(54321, 12345) = 1220847710 и возможность распараллелить 44 независимых запроса. Файлы Python и Java представляют собой прямые однопоточные переводы той же рекурсии.
Одно вычисление \(C_t(x)\) посещает только такие мемоизированные состояния, которые получаются из \((t,x)\) переходом к меньшим аргументам вида \((\lfloor t/2\rfloor,\lfloor x/4\rfloor)\) или \((\lfloor t/2\rfloor+1,\lfloor x/4\rfloor)\). Поэтому глубина рекурсии логарифмична по \(x\), а количество состояний в кеше ничтожно по сравнению с полным перебором всех индексов до \(x\).
Для нахождения \(g(t,c)\) добавляются экспоненциальный поиск подходящей верхней границы и затем бинарный поиск, так что число вызовов счетчика равно \(O(\log g(t,c))\). Вся программа делает это только 44 раза, поэтому рекурсивный метод счета практичен, а грубая сила нет.
solutionsCpp/Euler384.cpp, solutionsPython/Euler384.py, solutionsJava/Euler384.java.متتالية الإشارة Rudin-Shapiro المستخدمة في الحلول تُعطى بـ
$$b(n)=(-1)^{\operatorname{popcount}(n \mathbin{\&} (n \gg 1))}\in\{-1,+1\}.$$
هذا العدّ الثنائي يساوي تمامًا عدد مرات ظهور النمط \(11\) بشكل متداخل داخل التمثيل الثنائي للعدد \(n\). ونعرف المجموع التراكمي
$$A(n)=\sum_{k=0}^{n} b(k).$$
وللأعداد الصحيحة \(t\ge 1\) و\(1\le c\le t\)، نرمز بـ \(g(t,c)\) إلى الفهرس غير السالب رقم \(c\) الذي يحقق \(A(n)=t\). البرنامج يحسب
$$\sum_{t=2}^{45} g(F_t,F_{t-1}),\qquad F_0=F_1=1.$$
المحاكاة المباشرة تتطلب توليد المسار حتى فهارس هائلة. ملفات C++ وPython وJava المحلية لا تفعل ذلك أبدًا؛ بل تحسب أولًا كم مرة ظهر المستوى \(t\) حتى حد \(x\)، ثم تعكس دالة العد هذه ببحث ثنائي.
لنكتب
$$q(n)=\operatorname{popcount}(n \mathbin{\&} (n \gg 1)) \bmod 2,$$
وبالتالي \(b(n)=(-1)^{q(n)}\). بالنظر إلى آخر بتين نحصل على العلاقات الدقيقة
$$q(4m)=q(m),\qquad q(4m+1)=q(m),$$
$$q(4m+2)\equiv q(m)+m \pmod 2,\qquad q(4m+3)\equiv q(m)+m+1 \pmod 2.$$
ومن ثم
$$b(4m)=b(m),\qquad b(4m+1)=b(m),$$
$$b(4m+2)=(-1)^m b(m),\qquad b(4m+3)=-(-1)^m b(m).$$
هذه البنية ذات الكتل الأربع هي الأصل الرياضي الحقيقي لكل التكرارات الموجودة في ملفات الحل الثلاثة.
مجموع كتلة كاملة يساوي
$$b(4m)+b(4m+1)+b(4m+2)+b(4m+3)=2b(m).$$
وبجمع هذه الكتل من \(0\) إلى \(m\) نحصل على
$$A(4m+3)=2A(m).$$
ثم نستنتج داخل الكتلة نفسها
$$A(4m)=2A(m)-b(m),\qquad A(4m+1)=2A(m),$$
$$A(4m+2)=2A(m)+(-1)^m b(m),\qquad A(4m+3)=2A(m).$$
ولهذا السبب كل نداء تكراري يهبط بحجم الفهرس من \(x\) إلى نحو \(x/4\).
التنفيذ لا يخزّن دالة واحدة، بل الزوج
$$P_t(x)=\#\{0\le n\le x: A(n)=t,\ b(n)=+1\},$$
$$N_t(x)=\#\{0\le n\le x: A(n)=t,\ b(n)=-1\}.$$
وعندئذ يكون العدد الكلي لزيارات المستوى \(t\) حتى \(x\) هو
$$C_t(x)=P_t(x)+N_t(x),$$
أما الدالة المطلوبة فتستعاد من العلاقة
$$g(t,c)=\min\{x\ge 0 : C_t(x)\ge c\}.$$
هذا الفصل حسب الإشارة ضروري فعلًا، لأن صيغتي \(A(4m)\) و\(A(4m+2)\) تعتمدان على \(b(m)\). ولو احتفظنا بعدد مرات الوصول إلى المستوى \(t\) فقط، لفقدنا المعلومة اللازمة للخطوة التكرارية التالية.
كل قيمة \(b(k)\) عدد فردي، ولذلك
$$A(m)\equiv m+1 \pmod 2.$$
فإذا كان \(A(m)=u\) فإن \(m\equiv u-1 \pmod 2\)، وإذا كان \(A(m)=u+1\) فإن \(m\equiv u \pmod 2\). وبهذا يمكن استبدال زوجية الفهرس المجهول \(m\) بزوجية المستوى المعروف.
وللاختصار نعرّف
$$x_r=\left\lfloor\frac{x-r}{4}\right\rfloor,\qquad r\in\{0,1,2,3\}.$$
إذا كان \(t=2u\)، فلا يمكن أن تساهم إلا البواقي \(1\) و\(3\)، لأن \(A(4m)\) و\(A(4m+2)\) فرديان دائمًا. ومن \(A(4m+1)=A(4m+3)=2A(m)\) نحصل على
$$P_{2u}(x)=P_u(x_1)+ \begin{cases} P_u(x_3), & u \text{ زوجي},\\ N_u(x_3), & u \text{ فردي}, \end{cases}$$
$$N_{2u}(x)=N_u(x_1)+ \begin{cases} N_u(x_3), & u \text{ زوجي},\\ P_u(x_3), & u \text{ فردي}. \end{cases}$$
أما تبديل الإشارة في فرع الباقي \(3\) فيأتي من
$$b(4m+3)=-(-1)^m b(m)=(-1)^u b(m),$$
لأن الشرط \(A(m)=u\) يفرض \(m\equiv u-1\pmod 2\). إذا كان \(u\) زوجيًا تبقى الإشارة كما هي، وإذا كان فرديًا تنقلب.
إذا كان \(t=2u+1\)، فالبواقي الممكنة هي \(0\) و\(2\) فقط. بالنسبة إلى \(n=4m\)، فإن المعادلة
$$A(4m)=2A(m)-b(m)=2u+1$$
تعطي حالتين لا ثالث لهما:
$$A(m)=u \text{ و } b(m)=-1,\qquad A(m)=u+1 \text{ و } b(m)=+1.$$
وبالنسبة إلى \(n=4m+2\)، فإن المعادلة
$$A(4m+2)=2A(m)+(-1)^m b(m)=2u+1$$
مع قاعدة الزوجية تحدد هل يأتي الإسهام من \(P_u\) أم من \(N_u\)، وكذلك بالنسبة إلى \(u+1\). والنتيجة النهائية هي
$$P_{2u+1}(x)= \begin{cases} P_u(x_2)+P_{u+1}(x_0), & u \text{ فردي},\\ N_u(x_2)+P_{u+1}(x_0), & u \text{ زوجي}, \end{cases}$$
$$N_{2u+1}(x)= \begin{cases} N_u(x_0)+P_{u+1}(x_2), & u \text{ فردي},\\ N_u(x_0)+N_{u+1}(x_2), & u \text{ زوجي}. \end{cases}$$
وهذه هي بالضبط الفروع الموجودة في prefix_counts وprefixCounts في الشيفرات المحلية.
لتكن \(T(t)\) هي عدد مرات زيارة المستوى \(t\) على طول المسار اللانهائي كله. بأخذ النهاية \(x\to\infty\) في العلاقات السابقة نحصل على
$$T(1)=1,\qquad T(2u)=2T(u),\qquad T(2u+1)=T(u)+T(u+1).$$
والدالة البسيطة \(T(t)=t\) تحقق نفس العلاقة ونفس القيمة الابتدائية، لذلك
$$T(t)=t.$$
ولهذا يظهر في التنفيذ الشرط c > t: فالمستوى \(t\) يُزار بالضبط \(t\) مرة، لذلك توجد الزيارة رقم \(c\) إذا وفقط إذا كان \(1\le c\le t\).
أول قيم المجموع التراكمي هي
$$A(0),A(1),A(2),\dots = 1,2,3,2,3,4,3,4,5,6,7,6,\dots$$
إذن المستوى \(5\) يظهر عند
$$n=8,12,14,16,26,\dots$$
ومن ثم
$$g(5,3)=14.$$
وهذا ينسجم أيضًا مع النتيجة العامة أعلاه: المستوى \(5\) يظهر خمس مرات بالضبط، والظهور الثالث يقع عند الفهرس \(14\).
الدالة المحورية في كل لغة هي prefix_counts(t, x) أو prefixCounts(t, x). هذه الدالة تخزن الزوج \((P_t(x),N_t(x))\) مع الحالات الحدية \(t=0\) و\(x<0\) و\(t=1\). أما count_total فمهمتها فقط جمع المركبتين.
ثم تقوم الدالة g(t, c) بمضاعفة الحد الأعلى hi حتى يتحقق count_total(t, hi) >= c، وبعد ذلك تستخدم بحثًا ثنائيًا لإيجاد أصغر فهرس صالح. وأخيرًا تبني solve() أعداد فيبوناتشي وفق الاتفاقية \(F_0=F_1=1\)، ثم تجمع g(F_t, F_{t-1}) لكل \(2\le t\le 45\).
نسخة C++ تضيف تفصيلين هندسيين لا يغيران الرياضيات: نقطة تحقق داخلية g(54321, 12345) = 1220847710، وإمكان توزيع الاستعلامات الـ 44 المستقلة على عدة خيوط. أما ملفا Python وJava فهما ترجمتان مباشرتان أحاديتا الخيط للعلاقة نفسها.
كل تقييم لـ \(C_t(x)\) يزور فقط حالات مخزنة أصغر من \((t,x)\)، من النوع \((\lfloor t/2\rfloor,\lfloor x/4\rfloor)\) أو \((\lfloor t/2\rfloor+1,\lfloor x/4\rfloor)\). لذلك يكون عمق العودية لوغاريتميًا بالنسبة إلى \(x\)، ويبقى عدد الحالات في الذاكرة المؤقتة صغيرًا جدًا مقارنة بالمسح المباشر لكل الفهارس حتى \(x\).
أما حساب \(g(t,c)\) فيضيف بحثًا أسيًا لإيجاد حد أعلى مناسب ثم بحثًا ثنائيًا، ولذلك يكون عدد تقييمات دالة العد من رتبة \(O(\log g(t,c))\). وبما أن البرنامج ينفذ هذه العملية 44 مرة فقط، فإن منهج العد التكراري عملي جدًا، بينما القوة الغاشمة ليست كذلك.
solutionsCpp/Euler384.cpp وsolutionsPython/Euler384.py وsolutionsJava/Euler384.java.