We are given a sequence \(a(n)\) modulo \(M=1000062031\) defined by
$$a(0)=1,\qquad a(2m+1)=a(m),\qquad a(2m)=3a(m)+5a\left(2m-2^{\nu_2(m)}\right)\pmod{M}.$$
The required value is
$$a(N),\qquad N=(1+2^t)^r,\quad t=10^{14}+31,\quad r=62.$$
The index \(N\) is far too large for any direct dynamic program or recursion tree that expands all the way up to \(N\). The useful observation is that the recurrence reacts to binary structure, so the problem can be solved by reading the positions of the \(1\)-bits of \(N\) instead of iterating through all smaller integers.
The derivation has two layers. First we understand how the sequence changes when binary digits are appended. Then we apply that rule to the special number \(N=(1+2^t)^r\).
For every \(m\ge 0\),
$$a(2m+1)=a(m).$$
In binary, going from \(m\) to \(2m+1\) means shifting left by one position and appending a final \(1\). So a trailing \(1\)-bit does not contribute a multiplicative factor of its own. It only changes the state of the recursion by increasing the number of \(1\)-bits that have already appeared when we continue scanning toward lower bit positions.
This is why the final formula depends on the runs of zeros between successive \(1\)-bits, not on the \(1\)-bits themselves.
Suppose \(n\) is odd and has exactly \(i\) set bits. Then \(n-1\) has the same higher bits but only \(i-1\) set bits. Let \(v_i\) denote the factor produced by appending one zero while the current prefix already contains \(i\) ones.
We start with
$$v_0=1.$$
Now apply the even recurrence to \(2n\):
$$a(2n)=3a(n)+5a(n-1).$$
Because \(n\) is odd, we also have
$$a(n)=a\left(\frac{n-1}{2}\right).$$
The number \(n-1\) is obtained from \(\frac{n-1}{2}\) by appending one zero in a state with \(i-1\) ones, hence
$$a(n-1)=v_{i-1}a(n).$$
Substituting this into the even recurrence gives
$$a(2n)=\left(3+5v_{i-1}\right)a(n).$$
Therefore the multipliers satisfy
$$v_i=5v_{i-1}+3\qquad (i\ge 1).$$
The first values are
$$v_1=8,\qquad v_2=43,\qquad v_3=218,\qquad v_4=1093.$$
Before reduction modulo \(M\), the recurrence has the exact closed form
$$v_i=\frac{7\cdot 5^i-3}{4},$$
although the implementation only needs the recurrence modulo \(M\).
Let the set-bit positions of a positive integer \(n\) be
$$p_1>p_2>\cdots>p_s\ge 0.$$
Define the zero gaps by
$$g_i=\begin{cases} p_i-p_{i+1}-1,&1\le i<s,\\ p_s,&i=s. \end{cases}$$
When we scan the binary expansion from the most significant \(1\) downward, the leading \(1\) just starts the process. After the first \(1\), every zero contributes a factor \(v_1\) until the second \(1\) is reached. After the second \(1\), every zero contributes \(v_2\), and so on. Encountering a new \(1\) changes the state from \(i\) seen ones to \(i+1\) seen ones, but does not multiply the value.
Hence the exact evaluation formula is
$$a(n)=\prod_{i=1}^{s} v_i^{g_i}\pmod{M}.$$
This transforms the original recursion into a finite product determined solely by the locations of the \(1\)-bits.
Now write
$$N=(1+2^t)^r=\sum_{k=0}^{r}\binom{r}{k}2^{kt}.$$
If every binomial coefficient satisfies
$$\binom{r}{k}<2^t,$$
then the binary digits of \(\binom{r}{k}2^{kt}\) stay entirely inside the block of positions \(kt,kt+1,\dots,kt+t-1\). Distinct values of \(k\) occupy disjoint blocks, so their sum produces no carries between blocks.
That is exactly what happens here, because \(t=10^{14}+31\) is vastly larger than the bit-length of every coefficient in row \(r=62\). Therefore the set-bit positions of \(N\) are simply
$$\left\{\,kt+b \;:\; 0\le k\le r,\ b\in B_k\,\right\}.$$
Here \(B_k\) denotes the set of positions of the \(1\)-bits in \(\binom{r}{k}\).
Once these positions are sorted in descending order, Step 3 gives \(a(N)\) immediately.
This is the small checkpoint used by the implementation.
First expand the target:
$$N=(1+2^3)^2=1+2\cdot 2^3+2^6=1+2^4+2^6=81.$$
Its binary form is
$$81=1010001_2,$$
so the descending set-bit positions are \(6,4,0\). The corresponding gaps are
$$g_1=6-4-1=1,\qquad g_2=4-0-1=3,\qquad g_3=0.$$
Using
$$v_1=8,\qquad v_2=43,\qquad v_3=218,$$
we obtain
$$a(81)=8^1\cdot 43^3\cdot 218^0\pmod{M}=636056.$$
This small case already shows the general pattern: once the set-bit positions are known, the enormous recursion collapses into a short product.
The C++ implementation contains the full arithmetic. It builds the binomial row for \(r=62\) iteratively, using exact integer division with wide intermediate arithmetic so that every coefficient is computed exactly. For each coefficient, it enumerates the positions of its set bits, shifts them by \(kt\), and stores all resulting positions in one list.
Next, the implementation sorts those positions in descending order, precomputes the multipliers \(v_i\) modulo \(M\), and evaluates
$$\prod_{i=1}^{s} v_i^{g_i}\pmod{M}$$
by binary modular exponentiation. The Python and Java implementations invoke the same compiled solver, so all three language versions follow the same mathematical logic and produce the same residue.
The program also performs two local consistency checks. It compares the bit-position formula against a direct dynamic-programming computation for all \(n\le 5000\), and it verifies the example \(a\left((1+2^3)^2\right)=636056\). Those checks do not change the algorithm, but they confirm that the product formula matches the original recurrence.
Let
$$s=\sum_{k=0}^{r}\operatorname{popcount}\!\left(\binom{r}{k}\right),$$
the total number of set bits appearing across the binomial coefficients. Building the row costs \(O(r)\) arithmetic steps. Enumerating the set bits costs \(O(s)\). Sorting the positions costs \(O(s\log s)\), and evaluating the modular powers costs \(O(s\log t)\).
So the total running time is
$$O(r+s\log s+s\log t),$$
with memory usage \(O(s)\). In the actual problem \(r=62\) is tiny, so the huge size of \(t\) never creates a huge loop; it only appears as the exponent size inside fast modular exponentiation.
Gegeben ist eine Folge \(a(n)\) modulo \(M=1000062031\) mit
$$a(0)=1,\qquad a(2m+1)=a(m),\qquad a(2m)=3a(m)+5a\left(2m-2^{\nu_2(m)}\right)\pmod{M}.$$
Gesucht ist
$$a(N),\qquad N=(1+2^t)^r,\quad t=10^{14}+31,\quad r=62.$$
Der Index \(N\) ist astronomisch groß. Deshalb darf man die Rekursion nicht naiv bis zu diesem Wert ausrollen. Der entscheidende Punkt ist, dass die Vorschrift auf die Binärstruktur reagiert; man kann also mit den Positionen der gesetzten Bits arbeiten, statt alle kleineren Zahlen zu durchlaufen.
Die Herleitung besteht aus zwei Ebenen. Zuerst analysieren wir, wie sich \(a(n)\) ändert, wenn man an eine Binärdarstellung weitere Stellen anhängt. Danach wenden wir dieses Ergebnis auf die spezielle Zahl \(N=(1+2^t)^r\) an.
Für jedes \(m\ge 0\) gilt
$$a(2m+1)=a(m).$$
Binär bedeutet der Übergang von \(m\) zu \(2m+1\): nach links schieben und hinten eine \(1\) anhängen. Diese abschließende \(1\) liefert also keinen eigenen Multiplikationsfaktor. Sie verändert nur den Zustand, nämlich wie viele Einsen bereits gesehen wurden, wenn man später zu kleineren Bitpositionen weitergeht.
Darum hängt die Endformel von den Nullblöcken zwischen den Einsen ab und nicht von den Einsen selbst.
Sei \(n\) ungerade und habe genau \(i\) gesetzte Bits. Dann besitzt \(n-1\) dieselben höheren Bits, aber nur \(i-1\) gesetzte Bits. Bezeichne mit \(v_i\) den Faktor, der entsteht, wenn man in einem Zustand mit bereits \(i\) gesehenen Einsen eine Null anhängt.
Wir beginnen mit
$$v_0=1.$$
Auf die gerade Zahl \(2n\) angewendet liefert die Rekursion
$$a(2n)=3a(n)+5a(n-1).$$
Da \(n\) ungerade ist, gilt außerdem
$$a(n)=a\left(\frac{n-1}{2}\right).$$
Die Zahl \(n-1\) entsteht aus \(\frac{n-1}{2}\), indem man in einem Zustand mit \(i-1\) Einsen eine Null anhängt. Also
$$a(n-1)=v_{i-1}a(n).$$
Damit folgt
$$a(2n)=\left(3+5v_{i-1}\right)a(n),$$
und somit die Rekursion
$$v_i=5v_{i-1}+3\qquad (i\ge 1).$$
Die ersten Werte sind
$$v_1=8,\qquad v_2=43,\qquad v_3=218,\qquad v_4=1093.$$
Vor der Reduktion modulo \(M\) besitzt diese Folge sogar die geschlossene Form
$$v_i=\frac{7\cdot 5^i-3}{4},$$
doch für die Implementierung genügt die modulare Rekursion.
Seien die Positionen der gesetzten Bits einer positiven Zahl \(n\)
$$p_1>p_2>\cdots>p_s\ge 0.$$
Definiere die Nullabstände durch
$$g_i=\begin{cases} p_i-p_{i+1}-1,&1\le i<s,\\ p_s,&i=s. \end{cases}$$
Liest man die Binärdarstellung vom höchstwertigen Bit nach unten, startet die führende \(1\) nur den Prozess. Nach der ersten \(1\) trägt jede Null einen Faktor \(v_1\) bei, bis die zweite \(1\) erreicht ist. Danach trägt jede weitere Null den Faktor \(v_2\) bei und so weiter. Eine neue \(1\) erhöht nur den Zustand von \(i\) bereits gesehenen Einsen auf \(i+1\), multipliziert aber nicht selbst.
Daher gilt exakt
$$a(n)=\prod_{i=1}^{s} v_i^{g_i}\pmod{M}.$$
Damit wird die ursprüngliche Rekursion auf ein Produkt reduziert, das nur noch von den Bitpositionen abhängt.
Nun schreiben wir
$$N=(1+2^t)^r=\sum_{k=0}^{r}\binom{r}{k}2^{kt}.$$
Falls für alle \(k\)
$$\binom{r}{k}<2^t$$
gilt, dann liegen die Bits von \(\binom{r}{k}2^{kt}\) vollständig im Block \(kt,kt+1,\dots,kt+t-1\). Verschiedene \(k\) belegen disjunkte Blöcke, also entstehen beim Addieren keine Überträge zwischen diesen Blöcken.
Genau das ist hier der Fall, denn \(t=10^{14}+31\) ist viel größer als die Bitlänge aller Koeffizienten in der Zeile \(r=62\). Deshalb sind die gesetzten Bitpositionen von \(N\) einfach
$$\left\{\,kt+b \;:\; 0\le k\le r,\ b\in B_k\,\right\}.$$
Dabei bezeichnet \(B_k\) die Menge der Positionen der gesetzten Bits von \(\binom{r}{k}\).
Sobald diese Positionen absteigend sortiert sind, liefert Schritt 3 direkt den Wert von \(a(N)\).
Dies ist der kleine Kontrollfall aus der Implementierung.
Zuerst expandieren wir
$$N=(1+2^3)^2=1+2\cdot 2^3+2^6=1+2^4+2^6=81.$$
Die Binärdarstellung lautet
$$81=1010001_2,$$
also sind die gesetzten Positionen \(6,4,0\). Daraus folgen die Abstände
$$g_1=6-4-1=1,\qquad g_2=4-0-1=3,\qquad g_3=0.$$
Mit
$$v_1=8,\qquad v_2=43,\qquad v_3=218$$
erhält man
$$a(81)=8^1\cdot 43^3\cdot 218^0\pmod{M}=636056.$$
Schon dieses kleine Beispiel zeigt die Methode vollständig: Kennt man die Bitpositionen, verschwindet die große Rekursion zugunsten eines kurzen Produkts.
Die vollständige Arithmetik steht in der C++-Implementierung. Dort wird die Binomialzeile für \(r=62\) iterativ aufgebaut, mit exakter Ganzzahldivision und breiten Zwischenwerten, sodass jeder Koeffizient exakt berechnet wird. Für jeden Koeffizienten werden die Positionen seiner gesetzten Bits bestimmt, anschließend um \(kt\) verschoben und in einer gemeinsamen Liste gesammelt.
Danach sortiert die Implementierung diese Positionen absteigend, berechnet die Faktoren \(v_i\) modulo \(M\) vor und wertet
$$\prod_{i=1}^{s} v_i^{g_i}\pmod{M}$$
mit schneller modularer Exponentiation aus. Die Python- und Java-Implementierungen rufen denselben kompilierten Solver auf, daher folgen alle drei Sprachversionen derselben mathematischen Logik und liefern denselben Restwert.
Zusätzlich gibt es zwei Plausibilitätsprüfungen. Einerseits wird die Bitpositionsformel für alle \(n\le 5000\) mit einer direkten dynamischen Berechnung verglichen. Andererseits wird das Beispiel \(a\left((1+2^3)^2\right)=636056\) überprüft. Diese Tests ändern den Algorithmus nicht, bestätigen aber die Produktformel.
Sei
$$s=\sum_{k=0}^{r}\operatorname{popcount}\!\left(\binom{r}{k}\right)$$
die Gesamtzahl der gesetzten Bits in allen Binomialkoeffizienten. Der Aufbau der Zeile kostet \(O(r)\) Rechenschritte. Das Auflisten aller gesetzten Bits kostet \(O(s)\). Das Sortieren der Positionen kostet \(O(s\log s)\), und die modularen Potenzen kosten \(O(s\log t)\).
Damit ergibt sich insgesamt
$$O(r+s\log s+s\log t)$$
Zeit und \(O(s)\) Speicher. Für den tatsächlichen Fall ist \(r=62\) sehr klein, also führt die riesige Größe von \(t\) nicht zu einer riesigen Schleife; sie erscheint nur als Exponent in schneller modularer Potenzierung.
Bize \(M=1000062031\) modunda tanımlı şu dizi veriliyor:
$$a(0)=1,\qquad a(2m+1)=a(m),\qquad a(2m)=3a(m)+5a\left(2m-2^{\nu_2(m)}\right)\pmod{M}.$$
İstenen değer
$$a(N),\qquad N=(1+2^t)^r,\quad t=10^{14}+31,\quad r=62.$$
\(N\) o kadar büyüktür ki diziyi doğrudan \(0\)'dan başlayıp bu indekse kadar ilerletmek mümkün değildir. Kritik gözlem şudur: rekürans doğrudan sayının büyüklüğüne değil, ikili yazımına tepki verir. Bu yüzden çözüm, tüm ara değerleri üretmek yerine \(N\)'nin \(1\)-bit konumlarını okuyarak ilerler.
Türetim iki parçadan oluşur. Önce ikili yazıma yeni basamak eklendiğinde \(a(n)\)'nin nasıl davrandığını anlarız. Sonra bu kuralı özel sayı \(N=(1+2^t)^r\) için uygularız.
Her \(m\ge 0\) için
$$a(2m+1)=a(m)$$
olur. İkili yazım açısından \(m\)'den \(2m+1\)'e geçmek, sola kaydırıp en sona bir \(1\) eklemek demektir. Dolayısıyla sondaki bir \(1\)-bit kendi başına çarpan üretmez. Sadece daha aşağı bitlere inerken şimdiye kadar kaç tane \(1\) gördüğümüz bilgisini değiştirir.
Bu nedenle son formül, \(1\)-bitlerin kendisinden çok, ardışık \(1\)-bitler arasındaki sıfır bloklarına bağlıdır.
\(n\) tek olsun ve tam olarak \(i\) tane \(1\)-bit içersin. O zaman \(n-1\), aynı üst bitlere sahip olup sadece \(i-1\) tane \(1\)-bit içerir. Mevcut önekte daha önce \(i\) tane \(1\) görülmüşken bir sıfır eklemenin oluşturduğu çarpanı \(v_i\) ile gösterelim.
Başlangıç değeri
$$v_0=1$$
olsun. Şimdi \(2n\) için çift durum reküransını kullanalım:
$$a(2n)=3a(n)+5a(n-1).$$
\(n\) tek olduğu için ayrıca
$$a(n)=a\left(\frac{n-1}{2}\right)$$
yazabiliriz. \(n-1\) sayısı, \(\frac{n-1}{2}\) sayısına \(i-1\) durumunda bir sıfır eklenerek elde edildiğinden
$$a(n-1)=v_{i-1}a(n)$$
olur. Bunu yerine koyarsak
$$a(2n)=\left(3+5v_{i-1}\right)a(n)$$
ve dolayısıyla
$$v_i=5v_{i-1}+3\qquad (i\ge 1)$$
sonucunu elde ederiz. İlk birkaç değer
$$v_1=8,\qquad v_2=43,\qquad v_3=218,\qquad v_4=1093$$
şeklindedir. Mod almadan önce kapalı biçim de vardır:
$$v_i=\frac{7\cdot 5^i-3}{4}.$$
Fakat uygulama için modüler rekürans yeterlidir.
Pozitif bir \(n\) sayısının \(1\)-bit konumları azalan sırayla
$$p_1>p_2>\cdots>p_s\ge 0$$
olsun. Sıfır boşluklarını
$$g_i=\begin{cases} p_i-p_{i+1}-1,&1\le i<s,\\ p_s,&i=s \end{cases}$$
ile tanımlayalım. İkili yazımı en soldaki \(1\)'den başlayarak aşağı doğru okuduğumuzda, ilk \(1\) yalnızca süreci başlatır. Birinci \(1\)'den sonra gelen her sıfır \(v_1\) çarpanı üretir; ikinci \(1\)'den sonra gelen her sıfır \(v_2\) üretir; bu böyle devam eder. Yeni bir \(1\) görmek, çarpan üretmeden sadece durum numarasını \(i\)'den \(i+1\)'e çıkarır.
Böylece tam formül
$$a(n)=\prod_{i=1}^{s} v_i^{g_i}\pmod{M}$$
olur. Yani asıl rekürans, sadece \(1\)-bit konumlarına bağlı sonlu bir çarpıma indirgenmiş olur.
Şimdi
$$N=(1+2^t)^r=\sum_{k=0}^{r}\binom{r}{k}2^{kt}$$
yazalım. Eğer her \(k\) için
$$\binom{r}{k}<2^t$$
ise, \(\binom{r}{k}2^{kt}\) teriminin tüm bitleri yalnızca \(kt,kt+1,\dots,kt+t-1\) aralığında kalır. Farklı \(k\) değerleri ayrık bloklar kullandığı için toplama sırasında bloklar arasında elde oluşmaz.
Bu problemde tam olarak böyle olur; çünkü \(t=10^{14}+31\), \(r=62\) satırındaki tüm binom katsayılarının bit uzunluğundan inanılmaz derecede büyüktür. O halde \(N\)'nin \(1\)-bit konumları doğrudan
$$\left\{\,kt+b \;:\; 0\le k\le r,\ b\in B_k\,\right\}$$
Burada \(B_k\), \(\binom{r}{k}\) katsayısındaki \(1\)-bit konumlarının kümesini gösterir.
kümesidir. Bu konumlar azalan sıraya konduktan sonra Adım 3, \(a(N)\)'yi hemen verir.
Bu, uygulamanın doğruladığı küçük kontrol örneğidir.
Önce açılımı yazalım:
$$N=(1+2^3)^2=1+2\cdot 2^3+2^6=1+2^4+2^6=81.$$
İkili gösterim
$$81=1010001_2$$
olduğu için azalan \(1\)-bit konumları \(6,4,0\) olur. Buna göre boşluklar
$$g_1=6-4-1=1,\qquad g_2=4-0-1=3,\qquad g_3=0$$
şeklindedir. Ayrıca
$$v_1=8,\qquad v_2=43,\qquad v_3=218.$$
Dolayısıyla
$$a(81)=8^1\cdot 43^3\cdot 218^0\pmod{M}=636056.$$
Bu küçük örnek, genel yöntemi tamamen gösterir: bit konumları biliniyorsa büyük rekürans kısa bir çarpıma dönüşür.
C++ uygulaması asıl aritmetiği içerir. Önce \(r=62\) için binom satırını yinelemeli olarak kurar; her katsayı tam sayı bölmesi ve geniş ara aritmetik kullanılarak hatasız hesaplanır. Sonra her katsayının \(1\)-bit konumlarını çıkarır, bunlara \(kt\) kaydırmasını ekler ve hepsini tek bir listede toplar.
Daha sonra bu konumlar azalan sırada sıralanır, \(v_i\) çarpanları \(M\) modunda önceden hesaplanır ve
$$\prod_{i=1}^{s} v_i^{g_i}\pmod{M}$$
ifadesi hızlı modüler üs alma ile değerlendirilir. Python ve Java uygulamaları da aynı derlenmiş çözücüyü çağırdığı için üç dilde de aynı matematiksel yol izlenir ve aynı kalan elde edilir.
Program ayrıca iki yerel doğrulama yapar. Birincisi, bit konumu formülünü \(n\le 5000\) için doğrudan dinamik hesapla karşılaştırır. İkincisi, \(a\left((1+2^3)^2\right)=636056\) örneğini kontrol eder. Bu kontroller algoritmayı değiştirmez; sadece çarpım formülünün özgün reküransla gerçekten uyuştuğunu gösterir.
Şu büyüklüğü tanımlayalım:
$$s=\sum_{k=0}^{r}\operatorname{popcount}\!\left(\binom{r}{k}\right).$$
Bu, bütün binom katsayılarında görülen toplam \(1\)-bit sayısıdır. Satırı kurmak \(O(r)\) zaman alır. Tüm \(1\)-bitleri çıkarmak \(O(s)\) sürer. Konumları sıralamak \(O(s\log s)\), modüler üs hesapları ise \(O(s\log t)\) maliyetlidir.
Toplam zaman
$$O(r+s\log s+s\log t)$$
ve bellek kullanımı \(O(s)\) olur. Gerçek problemde \(r=62\) çok küçük olduğundan, \(t\)'nin devasa olması devasa bir döngü yaratmaz; yalnızca hızlı üs alma içinde üs uzunluğu olarak görünür.
Se nos da una sucesión \(a(n)\) módulo \(M=1000062031\) definida por
$$a(0)=1,\qquad a(2m+1)=a(m),\qquad a(2m)=3a(m)+5a\left(2m-2^{\nu_2(m)}\right)\pmod{M}.$$
Hay que calcular
$$a(N),\qquad N=(1+2^t)^r,\quad t=10^{14}+31,\quad r=62.$$
El índice \(N\) es gigantesco, así que una recursión ingenua o una programación dinámica que avance hasta \(N\) es imposible. La clave es que la definición depende de la estructura binaria del índice; por eso la solución trabaja con las posiciones de los bits encendidos de \(N\), no con todos los enteros intermedios.
La idea se divide en dos partes. Primero estudiamos qué ocurre cuando se añaden dígitos binarios al final. Después aplicamos esa regla al número especial \(N=(1+2^t)^r\).
Para todo \(m\ge 0\),
$$a(2m+1)=a(m).$$
En binario, pasar de \(m\) a \(2m+1\) significa desplazar una posición a la izquierda y añadir un \(1\) final. Ese \(1\) no introduce ningún factor multiplicativo nuevo. Lo único que hace es cambiar el estado: a partir de ese momento ya se ha visto un bit \(1\) más al seguir leyendo posiciones inferiores.
Por eso la fórmula final depende de los bloques de ceros entre bits \(1\) consecutivos y no de los bits \(1\) por sí mismos.
Supongamos que \(n\) es impar y tiene exactamente \(i\) bits encendidos. Entonces \(n-1\) conserva los bits altos, pero tiene solo \(i-1\) bits encendidos. Denotemos por \(v_i\) el factor que aparece al añadir un cero cuando el prefijo actual ya contiene \(i\) unos.
Tomamos como inicio
$$v_0=1.$$
Aplicando la recurrencia par a \(2n\), obtenemos
$$a(2n)=3a(n)+5a(n-1).$$
Como \(n\) es impar, también se cumple
$$a(n)=a\left(\frac{n-1}{2}\right).$$
El número \(n-1\) se obtiene a partir de \(\frac{n-1}{2}\) añadiendo un cero en un estado con \(i-1\) unos, así que
$$a(n-1)=v_{i-1}a(n).$$
Sustituyendo, resulta
$$a(2n)=\left(3+5v_{i-1}\right)a(n),$$
de donde sale la recurrencia
$$v_i=5v_{i-1}+3\qquad (i\ge 1).$$
Los primeros valores son
$$v_1=8,\qquad v_2=43,\qquad v_3=218,\qquad v_4=1093.$$
Antes de reducir módulo \(M\), incluso existe la forma cerrada
$$v_i=\frac{7\cdot 5^i-3}{4},$$
aunque la implementación solo necesita la versión modular.
Sean las posiciones de los bits encendidos de un entero positivo \(n\)
$$p_1>p_2>\cdots>p_s\ge 0.$$
Definimos los huecos de ceros como
$$g_i=\begin{cases} p_i-p_{i+1}-1,&1\le i<s,\\ p_s,&i=s. \end{cases}$$
Si recorremos la expansión binaria desde el bit más significativo hacia abajo, el primer \(1\) solo inicia el proceso. Después del primer \(1\), cada cero aporta un factor \(v_1\) hasta llegar al segundo \(1\). Después del segundo \(1\), cada cero aporta \(v_2\), y así sucesivamente. Encontrar un nuevo \(1\) solo cambia el estado de \(i\) unos vistos a \(i+1\), pero no multiplica el valor.
Así obtenemos la fórmula exacta
$$a(n)=\prod_{i=1}^{s} v_i^{g_i}\pmod{M}.$$
La recursión original queda reemplazada por un producto finito que depende únicamente de las posiciones de los bits \(1\).
Ahora escribimos
$$N=(1+2^t)^r=\sum_{k=0}^{r}\binom{r}{k}2^{kt}.$$
Si para todo \(k\)
$$\binom{r}{k}<2^t,$$
entonces los bits de \(\binom{r}{k}2^{kt}\) quedan completamente dentro del bloque de posiciones \(kt,kt+1,\dots,kt+t-1\). Distintos valores de \(k\) ocupan bloques separados, de modo que al sumar no aparecen acarreamientos entre bloques.
Eso ocurre aquí porque \(t=10^{14}+31\) es inmensamente mayor que la longitud en bits de cualquier coeficiente de la fila \(r=62\). Por tanto, las posiciones de los bits encendidos de \(N\) son exactamente
$$\left\{\,kt+b \;:\; 0\le k\le r,\ b\in B_k\,\right\}.$$
Aquí \(B_k\) denota el conjunto de posiciones de los bits iguales a \(1\) en \(\binom{r}{k}\).
Una vez ordenadas esas posiciones de mayor a menor, el Paso 3 da \(a(N)\) de inmediato.
Este es el caso pequeño comprobado por la implementación.
Primero expandimos:
$$N=(1+2^3)^2=1+2\cdot 2^3+2^6=1+2^4+2^6=81.$$
En binario,
$$81=1010001_2,$$
así que las posiciones encendidas son \(6,4,0\). Por tanto,
$$g_1=6-4-1=1,\qquad g_2=4-0-1=3,\qquad g_3=0.$$
Usando
$$v_1=8,\qquad v_2=43,\qquad v_3=218,$$
obtenemos
$$a(81)=8^1\cdot 43^3\cdot 218^0\pmod{M}=636056.$$
Este ejemplo muestra la idea completa: una vez conocidas las posiciones de los bits \(1\), la recursión gigantesca se convierte en un producto corto.
La implementación en C++ contiene toda la aritmética principal. Construye iterativamente la fila binomial para \(r=62\), usando división entera exacta y aritmética intermedia amplia para que cada coeficiente salga sin error. Luego enumera las posiciones de los bits encendidos de cada coeficiente, las desplaza en \(kt\) y guarda todas las posiciones resultantes en una sola lista.
Después, la implementación ordena esas posiciones de mayor a menor, precalcula los multiplicadores \(v_i\) módulo \(M\) y evalúa
$$\prod_{i=1}^{s} v_i^{g_i}\pmod{M}$$
mediante exponenciación modular binaria. Las implementaciones en Python y Java invocan el mismo solucionador compilado, así que las tres versiones siguen exactamente la misma lógica matemática y producen el mismo residuo.
Además, el programa hace dos comprobaciones locales. Compara la fórmula basada en posiciones de bits con una programación dinámica directa para todos los \(n\le 5000\), y verifica el ejemplo \(a\left((1+2^3)^2\right)=636056\). Estas comprobaciones no alteran el algoritmo; solo confirman que el producto cerrado coincide con la recurrencia original.
Sea
$$s=\sum_{k=0}^{r}\operatorname{popcount}\!\left(\binom{r}{k}\right),$$
el número total de bits encendidos presentes en todos los coeficientes binomiales. Construir la fila cuesta \(O(r)\). Enumerar todos los bits encendidos cuesta \(O(s)\). Ordenar las posiciones cuesta \(O(s\log s)\), y evaluar las potencias modulares cuesta \(O(s\log t)\).
En consecuencia, el tiempo total es
$$O(r+s\log s+s\log t),$$
y la memoria usada es \(O(s)\). En el problema real, \(r=62\) es pequeño, así que el tamaño enorme de \(t\) no provoca un bucle enorme; solo aparece como longitud del exponente dentro de la exponenciación rápida.
题目给出一个模 \(M=1000062031\) 的递归序列：
$$a(0)=1,\qquad a(2m+1)=a(m),\qquad a(2m)=3a(m)+5a\left(2m-2^{\nu_2(m)}\right)\pmod{M}.$$
要求计算
$$a(N),\qquad N=(1+2^t)^r,\quad t=10^{14}+31,\quad r=62.$$
\(N\) 大到无法直接从 \(0\) 递推到目标下标，也不可能把原始递归树一路展开到 \(N\)。真正可用的结构来自二进制表示：这个递归对“最低的 \(1\)-bit 在哪里”“末尾附加的是 \(0\) 还是 \(1\)”非常敏感，因此可以完全绕开巨大的整数本身，改为研究 \(N\) 的所有 \(1\)-bit 位置。
整个推导分成两层。第一层先弄清楚：当我们给一个二进制前缀继续往右添加比特时，\(a(n)\) 会怎样变化。第二层再把这个结论应用到特殊的数 \(N=(1+2^t)^r\) 上。
对任意 \(m\ge 0\)，都有
$$a(2m+1)=a(m).$$
从二进制角度看，从 \(m\) 变成 \(2m+1\) 就是整体左移一位，然后在最低位补上一个 \(1\)。这说明“补上一个末尾的 \(1\)”本身不会引入任何新的乘法因子。它只会改变后续分析时的状态，也就是告诉我们：继续向更低位扫描时，已经见过的 \(1\)-bit 数量增加了一个。
因此，最终公式真正关心的不是每个 \(1\)-bit 本身，而是相邻两个 \(1\)-bit 之间隔了多少个 \(0\)。
设 \(n\) 是奇数，并且它的二进制表示里恰好有 \(i\) 个 \(1\)-bit。于是 \(n-1\) 具有相同的高位结构，但 \(1\)-bit 数量减少为 \(i-1\)。定义 \(v_i\) 为这样一个因子：当当前前缀中已经出现了 \(i\) 个 \(1\) 时，再向右追加一个 \(0\)，对应的值会被乘上 \(v_i\)。
先规定
$$v_0=1.$$
接着对偶数 \(2n\) 使用递归式：
$$a(2n)=3a(n)+5a(n-1).$$
因为 \(n\) 是奇数，还满足
$$a(n)=a\left(\frac{n-1}{2}\right).$$
而 \(n-1\) 正是从 \(\frac{n-1}{2}\) 出发，在“已经看见 \(i-1\) 个 \(1\)”的状态下追加一个 \(0\) 得到的，所以
$$a(n-1)=v_{i-1}a(n).$$
代回去以后得到
$$a(2n)=\left(3+5v_{i-1}\right)a(n).$$
因此乘子满足递推
$$v_i=5v_{i-1}+3\qquad (i\ge 1).$$
前几项分别是
$$v_1=8,\qquad v_2=43,\qquad v_3=218,\qquad v_4=1093.$$
在还没有模 \(M\) 之前，这个递推甚至可以写成闭式：
$$v_i=\frac{7\cdot 5^i-3}{4}.$$
不过实现时只需要按模 \(M\) 递推这些值即可。
设正整数 \(n\) 的所有 \(1\)-bit 位置按从高到低排列为
$$p_1>p_2>\cdots>p_s\ge 0.$$
定义对应的零间隔
$$g_i=\begin{cases} p_i-p_{i+1}-1,&1\le i<s,\\ p_s,&i=s. \end{cases}$$
也就是说，\(g_i\) 表示第 \(i\) 个 \(1\)-bit 与下一个 \(1\)-bit 之间隔了多少个零；最后一个 \(g_s\) 则表示最低位的 \(1\)-bit 后面还有多少个尾随零。
现在从最高位向最低位扫描二进制表示。最左边的第一个 \(1\) 只负责“启动过程”。在它后面遇到的每一个零都会贡献一个 \(v_1\)；直到碰到第二个 \(1\) 为止。随后，在第二个 \(1\) 之后遇到的每一个零都会贡献一个 \(v_2\)；再往后则依次对应 \(v_3,v_4,\dots\)。而每次真正遇到新的 \(1\)-bit，只是把“已经见过的 \(1\)-bit 数量”从 \(i\) 更新到 \(i+1\)，并不会直接乘上新的因子。
因此可以得到完全精确的公式
$$a(n)=\prod_{i=1}^{s} v_i^{g_i}\pmod{M}.$$
这一点非常重要：原题中的递归虽然看起来复杂，但一旦转写成比特位置语言，问题就变成了一个由零间隔决定的有限乘积。
把目标数写成二项式展开：
$$N=(1+2^t)^r=\sum_{k=0}^{r}\binom{r}{k}2^{kt}.$$
如果对所有 \(k\) 都有
$$\binom{r}{k}<2^t,$$
那么 \(\binom{r}{k}2^{kt}\) 的全部二进制位只会落在区间 \(kt,kt+1,\dots,kt+t-1\) 内。不同的 \(k\) 对应不同的区间，这些区间彼此不重叠，因此相加时不会产生跨区间进位。
本题中这件事显然成立，因为 \(t=10^{14}+31\) 大得离谱，而 \(r=62\) 这一行所有二项式系数的二进制长度都很小。于是 \(N\) 的 \(1\)-bit 位置就是一个直接并集：
$$\left\{\,kt+b \;:\; 0\le k\le r,\ b\in B_k\,\right\}.$$
这里 \(B_k\) 表示 \(\binom{r}{k}\) 中所有 \(1\)-bit 的位置集合。
只要把这些位置按降序排好，就可以立刻套用步骤 3 的乘积公式。
实现里专门验证了这个小检查点，因为它足够小，可以手工看清全部结构。
先展开：
$$N=(1+2^3)^2=1+2\cdot 2^3+2^6=1+2^4+2^6=81.$$
它的二进制表示为
$$81=1010001_2,$$
所以从高到低的 \(1\)-bit 位置是 \(6,4,0\)。于是零间隔为
$$g_1=6-4-1=1,\qquad g_2=4-0-1=3,\qquad g_3=0.$$
另一方面，前面已经算出
$$v_1=8,\qquad v_2=43,\qquad v_3=218.$$
于是
$$a(81)=8^1\cdot 43^3\cdot 218^0\pmod{M}=636056.$$
这个结果和程序中的校验值完全一致，也直观展示了整套方法：先找 \(1\)-bit 位置，再把问题转成短小的模幂乘积。
C++ 实现包含完整的核心算法。它先迭代构造 \(r=62\) 的二项式系数行，使用精确整数除法和足够宽的中间算术来保证每个系数都精确无误。接着，对每个系数枚举所有 \(1\)-bit 的位置，再统一加上对应的位移 \(kt\)，把得到的全部位置放入同一张表中。
之后，程序把这些位置按降序排序，预先计算模 \(M\) 下的 \(v_i\)，再用快速模幂来求
$$\prod_{i=1}^{s} v_i^{g_i}\pmod{M}.$$
Python 和 Java 实现调用的是同一个已编译求解器，因此三种语言走的是完全相同的数学路径，最终得到同一个模结果。
程序还包含两个一致性检查。第一个是把“按比特位置求值”的公式与直接动态规划在所有 \(n\le 5000\) 上逐一对比。第二个是验证示例 \(a\left((1+2^3)^2\right)=636056\)。这些检查不会改变算法，只是用来确认闭式乘积与原始递归完全一致。
记
$$s=\sum_{k=0}^{r}\operatorname{popcount}\!\left(\binom{r}{k}\right),$$
即整行二项式系数中所有 \(1\)-bit 的总数。构造整行系数需要 \(O(r)\) 次算术操作；枚举这些 \(1\)-bit 需要 \(O(s)\)；把所有位置排序需要 \(O(s\log s)\)；计算所有模幂需要 \(O(s\log t)\)。
因此总时间复杂度为
$$O(r+s\log s+s\log t),$$
空间复杂度为 \(O(s)\)。在实际参数下，\(r=62\) 很小，所以真正的成本主要来自少量快速模幂；\(t\) 虽然巨大，但它不会导致巨大的线性循环。
Задана последовательность \(a(n)\) по модулю \(M=1000062031\):
$$a(0)=1,\qquad a(2m+1)=a(m),\qquad a(2m)=3a(m)+5a\left(2m-2^{\nu_2(m)}\right)\pmod{M}.$$
Нужно вычислить
$$a(N),\qquad N=(1+2^t)^r,\quad t=10^{14}+31,\quad r=62.$$
Индекс \(N\) настолько велик, что прямой расчёт по всем значениям до \(N\) невозможен. Полезная структура здесь не арифметическая, а двоичная: рекурсия зависит от младшего установленного бита и от того, что происходит при дописывании новых двоичных разрядов. Поэтому задачу можно решить через позиции единичных битов числа \(N\).
Вывод состоит из двух частей. Сначала нужно понять, как ведёт себя \(a(n)\), когда к двоичной записи справа добавляют новый бит. Затем это правило применяется к специальному числу \(N=(1+2^t)^r\).
Для любого \(m\ge 0\) имеем
$$a(2m+1)=a(m).$$
С точки зрения двоичной записи переход от \(m\) к \(2m+1\) означает сдвиг влево на один разряд и дописывание справа единицы. Значит, такая конечная единица сама по себе не даёт нового множителя. Она только меняет состояние процесса: при дальнейшем движении к младшим разрядам мы уже увидели ещё один бит, равный \(1\).
Именно поэтому итоговая формула зависит не от самих единиц, а от длин блоков нулей между соседними единичными битами.
Пусть \(n\) нечётно и содержит ровно \(i\) единичных битов. Тогда число \(n-1\) имеет те же старшие биты, но только \(i-1\) единичных битов. Обозначим через \(v_i\) множитель, возникающий при дописывании одного нуля в состоянии, когда в текущем префиксе уже встретилось \(i\) единиц.
Положим
$$v_0=1.$$
Для чётного числа \(2n\) рекурсия даёт
$$a(2n)=3a(n)+5a(n-1).$$
Так как \(n\) нечётно, дополнительно верно
$$a(n)=a\left(\frac{n-1}{2}\right).$$
Число \(n-1\) получается из \(\frac{n-1}{2}\) дописыванием нуля в состоянии с \(i-1\) уже увиденными единицами, поэтому
$$a(n-1)=v_{i-1}a(n).$$
Подстановка даёт
$$a(2n)=\left(3+5v_{i-1}\right)a(n),$$
а значит,
$$v_i=5v_{i-1}+3\qquad (i\ge 1).$$
Первые значения таковы:
$$v_1=8,\qquad v_2=43,\qquad v_3=218,\qquad v_4=1093.$$
До взятия по модулю \(M\) эта последовательность даже имеет точную явную форму
$$v_i=\frac{7\cdot 5^i-3}{4},$$
но в программе достаточно рекуррентного вычисления по модулю.
Пусть позиции единичных битов положительного числа \(n\) равны
$$p_1>p_2>\cdots>p_s\ge 0.$$
Определим промежутки нулей:
$$g_i=\begin{cases} p_i-p_{i+1}-1,&1\le i<s,\\ p_s,&i=s. \end{cases}$$
При чтении двоичной записи от старшего бита к младшему первая единица лишь запускает процесс. После первой единицы каждый ноль даёт множитель \(v_1\), пока не встретится вторая единица. После второй единицы каждый ноль даёт \(v_2\), и так далее. Встреча новой единицы переводит состояние из «увидено \(i\) единиц» в «увидено \(i+1\) единиц», но не умножает значение напрямую.
Отсюда получается точная формула
$$a(n)=\prod_{i=1}^{s} v_i^{g_i}\pmod{M}.$$
То есть исходная рекурсия заменяется конечным произведением, которое зависит только от расположения единичных битов.
Запишем
$$N=(1+2^t)^r=\sum_{k=0}^{r}\binom{r}{k}2^{kt}.$$
Если для каждого \(k\)
$$\binom{r}{k}<2^t,$$
то все биты числа \(\binom{r}{k}2^{kt}\) лежат внутри блока позиций \(kt,kt+1,\dots,kt+t-1\). Для разных \(k\) эти блоки не пересекаются, поэтому при сложении не возникает переносов между блоками.
В данной задаче именно так и происходит, потому что \(t=10^{14}+31\) несравнимо больше двоичной длины любого биномиального коэффициента в строке \(r=62\). Следовательно, позиции единичных битов числа \(N\) равны
$$\left\{\,kt+b \;:\; 0\le k\le r,\ b\in B_k\,\right\}.$$
Здесь \(B_k\) обозначает множество позиций единичных битов коэффициента \(\binom{r}{k}\).
После сортировки этих позиций по убыванию формула из шага 3 сразу даёт значение \(a(N)\).
Это малый контрольный случай, проверяемый программой.
Сначала раскроем скобки:
$$N=(1+2^3)^2=1+2\cdot 2^3+2^6=1+2^4+2^6=81.$$
В двоичной системе
$$81=1010001_2,$$
поэтому единичные биты стоят в позициях \(6,4,0\). Значит,
$$g_1=6-4-1=1,\qquad g_2=4-0-1=3,\qquad g_3=0.$$
Используя
$$v_1=8,\qquad v_2=43,\qquad v_3=218,$$
получаем
$$a(81)=8^1\cdot 43^3\cdot 218^0\pmod{M}=636056.$$
Этот пример уже полностью показывает идею: как только известны позиции единичных битов, огромная рекурсия схлопывается в короткое произведение.
Полная арифметика находится в реализации на C++. Сначала итеративно строится строка биномиальных коэффициентов для \(r=62\); при этом используются точное целочисленное деление и широкая промежуточная арифметика, чтобы каждый коэффициент вычислялся без ошибок. Затем для каждого коэффициента перечисляются позиции его единичных битов, к ним прибавляется сдвиг \(kt\), и все полученные позиции собираются в один список.
После этого реализация сортирует позиции по убыванию, заранее вычисляет множители \(v_i\) по модулю \(M\) и оценивает
$$\prod_{i=1}^{s} v_i^{g_i}\pmod{M}$$
с помощью быстрого модульного возведения в степень. Реализации на Python и Java вызывают тот же скомпилированный решатель, поэтому все три языковые версии следуют одной и той же математике и возвращают один и тот же остаток.
В программе есть и две локальные проверки. Первая сравнивает формулу по позициям битов с прямым динамическим вычислением для всех \(n\le 5000\). Вторая проверяет пример \(a\left((1+2^3)^2\right)=636056\). Эти проверки не меняют метод, но подтверждают корректность полученной формулы.
Обозначим через
$$s=\sum_{k=0}^{r}\operatorname{popcount}\!\left(\binom{r}{k}\right)$$
общее число единичных битов во всех биномиальных коэффициентах. Построение строки стоит \(O(r)\) арифметических шагов. Перечисление единичных битов стоит \(O(s)\). Сортировка позиций занимает \(O(s\log s)\), а вычисление модульных степеней занимает \(O(s\log t)\).
Следовательно, суммарное время равно
$$O(r+s\log s+s\log t),$$
а память равна \(O(s)\). В реальной задаче \(r=62\) мало, поэтому гигантский параметр \(t\) не порождает гигантского цикла; он влияет только на длину показателя степени в быстром возведении.
لدينا متتالية \(a(n)\) بترديد \(M=1000062031\) معرفة بالعلاقات
$$a(0)=1,\qquad a(2m+1)=a(m),\qquad a(2m)=3a(m)+5a\left(2m-2^{\nu_2(m)}\right)\pmod{M}.$$
والمطلوب هو حساب
$$a(N),\qquad N=(1+2^t)^r,\quad t=10^{14}+31,\quad r=62.$$
العدد \(N\) هائل للغاية، لذلك لا يمكن توسيع العودية مباشرة حتى هذا الفهرس ولا بناء برنامج ديناميكي يمر على جميع القيم الأصغر منه. الفكرة الحاسمة هي أن العلاقات تعتمد على البنية الثنائية للعدد، ولهذا يمكن استبدال التعامل مع العدد الضخم نفسه بالتعامل مع مواضع البتات التي تساوي \(1\) فيه.
الاشتقاق يتكون من طبقتين. أولًا نفهم كيف تتغير \(a(n)\) عندما نضيف بتات جديدة إلى الطرف الأيمن من التمثيل الثنائي. ثم نطبق هذه القاعدة على العدد الخاص \(N=(1+2^t)^r\).
لكل \(m\ge 0\) لدينا
$$a(2m+1)=a(m).$$
وباللغة الثنائية، الانتقال من \(m\) إلى \(2m+1\) يعني إزاحة جميع البتات خانة إلى اليسار ثم إلحاق \(1\) في النهاية. هذا يعني أن البت \(1\) الأخير لا يولد عامل ضرب جديدًا بنفسه. كل ما يفعله هو تغيير الحالة: عند متابعة القراءة نحو البتات الأدنى نكون قد رأينا عددًا أكبر من البتات التي تساوي \(1\).
ولهذا تعتمد الصيغة النهائية على كتل الأصفار بين البتات \(1\) المتتالية، لا على البتات \(1\) نفسها.
افترض أن \(n\) عدد فردي وله بالضبط \(i\) بتات تساوي \(1\). عندئذ يكون \(n-1\) ذا البنية العليا نفسها، لكنه يحتوي على \(i-1\) بتات مساوية لـ \(1\). نرمز بـ \(v_i\) إلى العامل الناتج عن إضافة صفر واحد عندما يكون المقطع الثنائي الحالي قد احتوى بالفعل على \(i\) واحدات.
نبدأ بالقيمة
$$v_0=1.$$
ثم نطبق علاقة الحالة الزوجية على \(2n\):
$$a(2n)=3a(n)+5a(n-1).$$
ولأن \(n\) فردي، فلدينا أيضًا
$$a(n)=a\left(\frac{n-1}{2}\right).$$
أما العدد \(n-1\) فهو ينتج من \(\frac{n-1}{2}\) بإضافة صفر واحد في حالة فيها \(i-1\) واحدات سابقة، ولذلك
$$a(n-1)=v_{i-1}a(n).$$
وبالتعويض نحصل على
$$a(2n)=\left(3+5v_{i-1}\right)a(n),$$
ومن ثم تتبع المتتالية المساعدة العلاقة
$$v_i=5v_{i-1}+3\qquad (i\ge 1).$$
وأول القيم هي
$$v_1=8,\qquad v_2=43,\qquad v_3=218,\qquad v_4=1093.$$
وقبل أخذ الترديد \(M\)، توجد صيغة مغلقة أيضًا:
$$v_i=\frac{7\cdot 5^i-3}{4}.$$
لكن التنفيذ العملي يكتفي بالعلاقة العودية تحت الترديد.
لتكن مواضع البتات التي تساوي \(1\) في عدد موجب \(n\) مرتبة تنازليًا بالشكل
$$p_1>p_2>\cdots>p_s\ge 0.$$
ونعرّف فجوات الأصفار كما يلي:
$$g_i=\begin{cases} p_i-p_{i+1}-1,&1\le i<s,\\ p_s,&i=s. \end{cases}$$
إذا قرأنا التمثيل الثنائي من البت الأعلى إلى الأدنى، فإن أول \(1\) يطلق العملية فقط. بعد أول \(1\)، كل صفر نصادفه يضيف عاملًا \(v_1\) حتى نصل إلى \(1\) الثاني. بعد \(1\) الثاني، كل صفر يضيف \(v_2\)، وهكذا. أما رؤية \(1\) جديد فوظيفتها فقط نقل الحالة من «رأينا \(i\) واحدات» إلى «رأينا \(i+1\) واحدات»، من دون ضرب مباشر.
لذلك نحصل على الصيغة الدقيقة
$$a(n)=\prod_{i=1}^{s} v_i^{g_i}\pmod{M}.$$
وبهذا تختفي العودية الأصلية وتتحول المسألة إلى حاصل ضرب قصير يعتمد فقط على مواضع البتات المفعلة.
نكتب الآن
$$N=(1+2^t)^r=\sum_{k=0}^{r}\binom{r}{k}2^{kt}.$$
إذا تحقق لكل \(k\) أن
$$\binom{r}{k}<2^t,$$
فإن جميع بتات \(\binom{r}{k}2^{kt}\) تبقى داخل المجال \(kt,kt+1,\dots,kt+t-1\). وبما أن المجالات الخاصة بقيم \(k\) المختلفة منفصلة، فلا تظهر أي نقلات حمل بين هذه الكتل عند الجمع.
وهذا هو الوضع هنا تمامًا، لأن \(t=10^{14}+31\) أكبر بكثير من طول أي معامل ثنائي في الصف \(r=62\). لذلك تصبح مواضع البتات \(1\) في \(N\) ببساطة
$$\left\{\,kt+b \;:\; 0\le k\le r,\ b\in B_k\,\right\}.$$
وهنا يرمز \(B_k\) إلى مجموعة المواضع التي تكون فيها بتات \(\binom{r}{k}\) مساوية لـ \(1\).
ومتى رُتِّبت هذه المواضع تنازليًا، تعطي الخطوة الثالثة قيمة \(a(N)\) مباشرة.
هذا هو المثال الصغير الذي يتحقق منه التنفيذ صراحة.
أولًا نوسع التعبير:
$$N=(1+2^3)^2=1+2\cdot 2^3+2^6=1+2^4+2^6=81.$$
وفي النظام الثنائي
$$81=1010001_2,$$
فتكون مواضع البتات \(1\) هي \(6,4,0\). ومن ثم
$$g_1=6-4-1=1,\qquad g_2=4-0-1=3,\qquad g_3=0.$$
وباستخدام
$$v_1=8,\qquad v_2=43,\qquad v_3=218,$$
نحصل على
$$a(81)=8^1\cdot 43^3\cdot 218^0\pmod{M}=636056.$$
هذا المثال الصغير يوضح الفكرة كلها: بمجرد معرفة مواضع البتات \(1\)، تتحول العودية الكبيرة إلى حاصل ضرب قصير من قوى معيارية.
التنفيذ بلغة C++ يحتوي على الحساب الكامل. يبدأ ببناء صف معاملات ذي الحدين من أجل \(r=62\) بطريقة تكرارية، مع استخدام قسمة صحيحة دقيقة وحسابات وسيطة واسعة لضمان أن كل معامل يُحسب بلا خطأ. بعد ذلك تُستخرج مواضع البتات \(1\) لكل معامل، ثم يُضاف إليها الإزاحة \(kt\)، وتُجمع جميع المواضع الناتجة في قائمة واحدة.
بعدها ترتب الشفرة هذه المواضع ترتيبًا تنازليًا، وتحسب مسبقًا قيم \(v_i\) بترديد \(M\)، ثم تقيم
$$\prod_{i=1}^{s} v_i^{g_i}\pmod{M}$$
باستخدام الأس المعياري السريع. أما التنفيذان بلغة Python و Java فيستدعيان المُحلِّل المترجَم نفسه، ولذلك تتبع الإصدارات الثلاثة المنطق الرياضي نفسه وتنتج الباقي نفسه.
وتوجد أيضًا فحوص محلية للاتساق. الفحص الأول يقارن صيغة مواضع البتات بحساب ديناميكي مباشر لكل \(n\le 5000\). والفحص الثاني يتحقق من المثال \(a\left((1+2^3)^2\right)=636056\). هذه الفحوص لا تغيّر الخوارزمية، لكنها تؤكد أن الصيغة المغلقة مطابقة للعودية الأصلية.
لنعرّف
$$s=\sum_{k=0}^{r}\operatorname{popcount}\!\left(\binom{r}{k}\right),$$
وهو العدد الكلي للبتات \(1\) الموجودة في جميع معاملات ذي الحدين. بناء الصف يكلف \(O(r)\) خطوة حسابية. استخراج جميع البتات \(1\) يكلف \(O(s)\). ترتيب المواضع يكلف \(O(s\log s)\)، وتقييم القوى المعيارية يكلف \(O(s\log t)\).
إذن زمن التنفيذ الكلي هو
$$O(r+s\log s+s\log t),$$
واستهلاك الذاكرة هو \(O(s)\). وفي الحالة الفعلية للمسألة يكون \(r=62\) صغيرًا، لذلك لا يؤدي الحجم الهائل لـ \(t\) إلى حلقة هائلة؛ بل يظهر فقط في طول الأس داخل الرفع السريع للأس.