The problem asks for
$$U(10^4)=\sum_{n=1}^{10^4}u(n^3),$$
where the arithmetic function \(u(m)\) is determined by a 2-adic valuation. If we set \(k=m+1\) and define the 2-adically convergent series
$$S_k=\sum_{j\ge 0}(-2)^j\binom{2(k+j)}{k+j},$$
then the required quantity is
$$u(m)=k+v_2(-3S_k).$$
Here \(v_2(x)\) denotes the exponent of 2 dividing \(x\). The difficulty is not the outer sum itself but recovering the power of 2 in this series for many large cubic inputs without expanding enormous exact integers.
The key idea is to stay inside \(\mathbb{Z}/2^{64}\mathbb{Z}\). At that precision the relevant 2-adic valuation is still visible, while every arithmetic step fits into machine-word computations.
Let \(C_r=\binom{2r}{r}\). A standard fact for central binomial coefficients is
$$v_2(C_r)=s_2(r),$$
where \(s_2(r)\) is the number of 1-bits in the binary expansion of \(r\). Therefore
$$v_2\!\left((-2)^j C_{k+j}\right)=j+s_2(k+j)\ge j+1.$$
So modulo \(2^{64}\), all sufficiently late terms vanish automatically. A 64-step accumulation is enough at the chosen precision, which converts an infinite 2-adic series into a fixed-size computation.
For any nonzero integer define its odd part by
$$\operatorname{Odd}(x)=\frac{x}{2^{v_2(x)}}.$$
Then every central binomial coefficient splits as
$$C_r=\operatorname{Odd}(C_r)\,2^{s_2(r)}.$$
The power of 2 is therefore known immediately from the binary digit count of \(r\). The remaining task is to evaluate the odd part efficiently. Using factorials,
$$\operatorname{Odd}(C_r)=\frac{\operatorname{Odd}((2r)!)}{\operatorname{Odd}(r!)^2}.$$
Because the denominator is odd, it is invertible modulo \(2^{64}\), so division can be replaced by multiplication with odd modular inverses.
Introduce the odd prefix product
$$F(u)=\prod_{t=0}^{u-1}(2t+1)=1\cdot 3\cdot 5\cdots (2u-1).$$
Every factor in \(n!\) is either odd or twice a smaller integer. After stripping away powers of 2, this gives
$$\operatorname{Odd}(n!)=\operatorname{Odd}\!\left(\left\lfloor\frac{n}{2}\right\rfloor!\right)\,F\!\left(\left\lceil\frac{n}{2}\right\rceil\right).$$
Iterating the recursion yields
$$\operatorname{Odd}(n!)=\prod_{a\ge 0}F\!\left(\left\lfloor\frac{n+2^a}{2^{a+1}}\right\rfloor\right),$$
with only \(O(\log n)\) nontrivial factors. This is why the implementation can evaluate the odd part of very large factorials without ever materializing the factorial itself.
In the working 2-adic setting, the implementation evaluates \(F(u)\) from a forward-difference expansion
$$F(u)\equiv \sum_{t=0}^{126}\Delta^tF(0)\binom{u}{t}\pmod{2^{64}}.$$
Only the first 127 coefficients are needed at this precision, so they are precomputed once from \(F(0),F(1),\dots,F(126)\). The generalized binomial coefficients \(\binom{u}{t}\) are also formed modulo \(2^{64}\) by separating powers of 2 from odd numerator and denominator parts.
Whenever an odd denominator must be inverted, Newton's method in the 2-adic world is used:
$$x_{r+1}=x_r(2-ax_r)\pmod{2^{64}},\qquad a\text{ odd}.$$
Each iteration doubles the number of correct low bits, so six rounds already reach full 64-bit precision.
Once the odd part of \(C_k\) is known, the next one follows from
$$\frac{C_{r+1}}{C_r}=\frac{2(2r+1)}{r+1}.$$
After removing powers of 2, the odd parts satisfy
$$\operatorname{Odd}(C_{r+1})=\operatorname{Odd}(C_r)\,\frac{2r+1}{\operatorname{Odd}(r+1)}.$$
So the implementation computes the first central binomial term at \(r=k\), then advances through \(r=k,k+1,\dots\) with a short recurrence. At each step it restores the full coefficient by shifting the odd part by \(s_2(r)\), multiplies by the appropriate power of \(-2\), and accumulates modulo \(2^{64}\).
Here \(k=m+1=5\). The first central binomial coefficients are
$$\binom{10}{5}=252=2^2\cdot 63,\qquad \binom{12}{6}=924=2^2\cdot 231,\qquad \binom{14}{7}=3432=2^3\cdot 429.$$
Hence the first terms of the series have valuations
$$v_2\!\left(\binom{10}{5}\right)=2,\qquad v_2\!\left(-2\binom{12}{6}\right)=3,\qquad v_2\!\left(4\binom{14}{7}\right)=5.$$
Modulo \(8\), only the first term survives, so
$$S_5\equiv \binom{10}{5}\equiv 4\pmod{8}.$$
Multiplication by \(-3\) does not change the 2-adic valuation because 3 is odd. Therefore
$$v_2(-3S_5)=2,$$
and thus
$$u(4)=5+2=7.$$
This matches the small checkpoint used by the implementation and shows why the low 2-adic valuation, not the exact integer magnitude, is the critical object.
The C++, Python, and Java implementations follow the same pipeline. First they precompute the odd prefix products \(F(0),\dots,F(126)\), the associated forward differences, and the inverses of the small odd numbers needed in the Newton expansion. Then, for each cube input \(m=n^3\), the implementation constructs the odd part of the first central binomial coefficient at \(k=m+1\), restores its full power of 2 from the binary digit count, and evaluates the fixed-length alternating series modulo \(2^{64}\).
After the series has been accumulated, the implementation multiplies by \(-3\), counts the exponent of 2 in the resulting residue, adds \(k\), and obtains \(u(m)\). The outer loop sums these values for \(n=1,2,\dots,10^4\). The direct compiled implementations also split that outer range across available processor cores, while the Python version delegates to the same optimized core computation.
The precomputation phase is constant-sized: it stores only 127 forward-difference entries and a matching set of small odd inverses, so its cost is \(O(1)\) for this problem. For one value \(u(m)\), the odd-factorial formula needs \(O(\log m)\) evaluations of \(F\), each performed in constant time with the fixed Newton expansion, and the series summation always uses 64 iterations. Thus one query costs \(O(\log m)\) word operations, and summing \(u(n^3)\) for \(1\le n\le N\) costs
$$O\!\left(\sum_{n=1}^{N}\log(n^3)\right)=O(N\log N)$$
total time with \(O(1)\) extra memory beyond the fixed tables. In practice the constants are small because all arithmetic is carried out modulo \(2^{64}\).
Gesucht ist
$$U(10^4)=\sum_{n=1}^{10^4}u(n^3),$$
wobei die arithmetische Funktion \(u(m)\) durch eine 2-adische Bewertung bestimmt wird. Setzt man \(k=m+1\) und definiert die 2-adisch konvergente Reihe
$$S_k=\sum_{j\ge 0}(-2)^j\binom{2(k+j)}{k+j},$$
dann ist die gesuchte Größe
$$u(m)=k+v_2(-3S_k).$$
Dabei bezeichnet \(v_2(x)\) den Exponenten der größten Zweierpotenz, die \(x\) teilt. Die eigentliche Schwierigkeit liegt also nicht in der äußeren Summe, sondern darin, für viele kubische Eingaben die Zweierbewertung dieser Reihe zu bestimmen, ohne riesige exakte Ganzzahlen auszurechnen.
Der zentrale Trick besteht darin, komplett in \(\mathbb{Z}/2^{64}\mathbb{Z}\) zu arbeiten. Bei dieser Präzision bleibt die relevante 2-adische Bewertung sichtbar, während alle Rechenschritte in Maschinenwort-Arithmetik bleiben.
Sei \(C_r=\binom{2r}{r}\). Für zentrale Binomialkoeffizienten gilt
$$v_2(C_r)=s_2(r),$$
wobei \(s_2(r)\) die Anzahl der Einsen in der Binärdarstellung von \(r\) ist. Also folgt
$$v_2\!\left((-2)^j C_{k+j}\right)=j+s_2(k+j)\ge j+1.$$
Somit verschwinden modulo \(2^{64}\) alle hinreichend späten Terme automatisch. Bei dieser Präzision reicht daher eine Schleife mit 64 Schritten aus; die unendliche 2-adische Reihe wird zu einer Rechnung fester Größe.
Für jede von null verschiedene ganze Zahl definieren wir den ungeraden Anteil durch
$$\operatorname{Odd}(x)=\frac{x}{2^{v_2(x)}}.$$
Dann zerfällt jeder zentrale Binomialkoeffizient in
$$C_r=\operatorname{Odd}(C_r)\,2^{s_2(r)}.$$
Die Zweierpotenz ist also sofort aus der Binärziffernsumme von \(r\) bekannt. Übrig bleibt die effiziente Bestimmung des ungeraden Anteils. Mit Fakultäten erhält man
$$\operatorname{Odd}(C_r)=\frac{\operatorname{Odd}((2r)!)}{\operatorname{Odd}(r!)^2}.$$
Da der Nenner ungerade ist, besitzt er modulo \(2^{64}\) ein Inverses. Division wird daher durch Multiplikation mit einem ungeraden modularen Inversen ersetzt.
Wir führen das ungerade Präfixprodukt ein:
$$F(u)=\prod_{t=0}^{u-1}(2t+1)=1\cdot 3\cdot 5\cdots (2u-1).$$
Jeder Faktor in \(n!\) ist entweder ungerade oder das Doppelte einer kleineren Zahl. Entfernt man alle Zweierpotenzen, so ergibt sich
$$\operatorname{Odd}(n!)=\operatorname{Odd}\!\left(\left\lfloor\frac{n}{2}\right\rfloor!\right)\,F\!\left(\left\lceil\frac{n}{2}\right\rceil\right).$$
Durch Iteration folgt
$$\operatorname{Odd}(n!)=\prod_{a\ge 0}F\!\left(\left\lfloor\frac{n+2^a}{2^{a+1}}\right\rfloor\right),$$
wobei nur \(O(\log n)\) Faktoren ungleich trivial sind. Genau deshalb kann die Implementierung den ungeraden Anteil sehr großer Fakultäten berechnen, ohne die Fakultät selbst jemals auszuschreiben.
In der verwendeten 2-adischen Darstellung wird \(F(u)\) über eine Vorwärtsdifferenzen-Entwicklung berechnet:
$$F(u)\equiv \sum_{t=0}^{126}\Delta^tF(0)\binom{u}{t}\pmod{2^{64}}.$$
Bei dieser Präzision werden nur die ersten 127 Koeffizienten benötigt; sie werden einmal aus \(F(0),F(1),\dots,F(126)\) vorab berechnet. Auch die verallgemeinerten Binomialkoeffizienten \(\binom{u}{t}\) werden modulo \(2^{64}\) gebildet, indem Zweierpotenzen abgespalten und in Zähler und Nenner nur die ungeraden Teile dividiert werden.
Muss ein ungerader Nenner invertiert werden, verwendet die Implementierung Newton-Iteration im 2-adischen Sinn:
$$x_{r+1}=x_r(2-ax_r)\pmod{2^{64}},\qquad a\text{ ungerade}.$$
Jeder Schritt verdoppelt die Zahl der korrekten niederwertigen Bits; sechs Iterationen reichen daher bereits für volle 64-Bit-Präzision.
Ist der ungerade Anteil von \(C_k\) bekannt, folgt der nächste aus
$$\frac{C_{r+1}}{C_r}=\frac{2(2r+1)}{r+1}.$$
Nach dem Entfernen der Zweierpotenzen gilt damit
$$\operatorname{Odd}(C_{r+1})=\operatorname{Odd}(C_r)\,\frac{2r+1}{\operatorname{Odd}(r+1)}.$$
Die Implementierung berechnet also zuerst den zentralen Binomialterm für \(r=k\) und schreitet dann mit einer kurzen Rekursion durch \(r=k,k+1,\dots\). In jedem Schritt wird der volle Koeffizient durch Verschieben um \(s_2(r)\) rekonstruiert, mit der passenden Potenz von \(-2\) multipliziert und modulo \(2^{64}\) aufsummiert.
Hier ist \(k=m+1=5\). Die ersten zentralen Binomialkoeffizienten sind
$$\binom{10}{5}=252=2^2\cdot 63,\qquad \binom{12}{6}=924=2^2\cdot 231,\qquad \binom{14}{7}=3432=2^3\cdot 429.$$
Damit haben die ersten Reihenterme die Bewertungen
$$v_2\!\left(\binom{10}{5}\right)=2,\qquad v_2\!\left(-2\binom{12}{6}\right)=3,\qquad v_2\!\left(4\binom{14}{7}\right)=5.$$
Modulo \(8\) überlebt nur der erste Term, also
$$S_5\equiv \binom{10}{5}\equiv 4\pmod{8}.$$
Die Multiplikation mit \(-3\) ändert die 2-adische Bewertung nicht, weil 3 ungerade ist. Folglich
$$v_2(-3S_5)=2,$$
und daher
$$u(4)=5+2=7.$$
Das stimmt mit dem kleinen Kontrollwert der Implementierung überein und zeigt, warum nicht die exakte Größe der Zahlen, sondern ihre Zweierbewertung entscheidend ist.
Die C++-, Python- und Java-Implementierungen folgen alle derselben mathematischen Pipeline. Zuerst werden die ungeraden Präfixprodukte \(F(0),\dots,F(126)\), die zugehörigen Vorwärtsdifferenzen und die Inversen der kleinen ungeraden Zahlen für die Newton-Entwicklung vorab berechnet. Danach konstruiert die Implementierung für jede kubische Eingabe \(m=n^3\) den ungeraden Anteil des ersten zentralen Binomialkoeffizienten bei \(k=m+1\), ergänzt dessen Zweierpotenz aus der Binärziffernsumme und wertet die Alternating-Summe fester Länge modulo \(2^{64}\) aus.
Nach der Summation wird mit \(-3\) multipliziert, die Zweierbewertung des resultierenden Restes bestimmt und \(k\) addiert. So entsteht \(u(m)\). Die äußere Schleife summiert diese Werte für \(n=1,2,\dots,10^4\). Die direkt kompilierten Implementierungen verteilen diesen äußeren Bereich zusätzlich auf mehrere Prozessorkerne, während die Python-Version dieselbe optimierte Kernberechnung aufruft.
Die Vorberechnung hat konstante Größe: Es werden nur 127 Vorwärtsdifferenzwerte und ebenso viele kleine ungerade Inverse gespeichert. Für ein einzelnes \(u(m)\) benötigt die Formel für den ungeraden Fakultätsanteil \(O(\log m)\) Auswertungen von \(F\), wobei jede Auswertung wegen der festen Newton-Entwicklung in konstanter Zeit erfolgt; die Reihensumme selbst hat immer 64 Schritte. Damit kostet eine Anfrage \(O(\log m)\) Wortoperationen, und die Summe über \(u(n^3)\) für \(1\le n\le N\) kostet insgesamt
$$O\!\left(\sum_{n=1}^{N}\log(n^3)\right)=O(N\log N)$$
Zeit bei \(O(1)\) Zusatzspeicher über die festen Tabellen hinaus. Praktisch sind die Konstanten klein, weil sämtliche Arithmetik modulo \(2^{64}\) stattfindet.
İstenen büyüklük
$$U(10^4)=\sum_{n=1}^{10^4}u(n^3)$$
toplamıdır. Buradaki \(u(m)\) fonksiyonu 2-adik bir değerleme ile tanımlanır. \(k=m+1\) yazıp
$$S_k=\sum_{j\ge 0}(-2)^j\binom{2(k+j)}{k+j}$$
2-adik yakınsak serisini tanımlarsak, aranan değer
$$u(m)=k+v_2(-3S_k)$$
olur. Burada \(v_2(x)\), \(x\)'i bölen en büyük 2 kuvvetinin üssüdür. Dolayısıyla asıl zorluk dış toplam değil, çok sayıda küp girdi için bu serideki 2 kuvvetini devasa tam sayılar oluşturmadan çıkarmaktır.
Ana fikir tüm hesabı \(\mathbb{Z}/2^{64}\mathbb{Z}\) içinde yapmaktır. Bu hassasiyette gerekli 2-adik değerleme hâlâ görünür durumdadır ve bütün işlemler makine sözcüğü boyutunda kalır.
\(C_r=\binom{2r}{r}\) olsun. Merkezi binom katsayıları için bilinen gerçek şudur:
$$v_2(C_r)=s_2(r),$$
burada \(s_2(r)\), \(r\)'nin ikili gösterimindeki 1 bitlerinin sayısıdır. Bu yüzden
$$v_2\!\left((-2)^j C_{k+j}\right)=j+s_2(k+j)\ge j+1$$
elde edilir. Böylece \(2^{64}\) modunda yeterince geç gelen tüm terimler otomatik olarak yok olur. Pratikte 64 adımlık birikim yeterlidir; sonsuz 2-adik seri sabit boyutlu bir hesaba dönüşür.
Sıfır olmayan her tam sayı için tek kısmı
$$\operatorname{Odd}(x)=\frac{x}{2^{v_2(x)}}$$
diye tanımlayalım. O zaman her merkezi binom katsayısı
$$C_r=\operatorname{Odd}(C_r)\,2^{s_2(r)}$$
şeklinde ayrılır. Yani 2 kuvveti, \(r\)'nin ikili bit sayısından hemen gelir. Geriye tek kısmı verimli biçimde hesaplamak kalır. Faktöriyel üzerinden
$$\operatorname{Odd}(C_r)=\frac{\operatorname{Odd}((2r)!)}{\operatorname{Odd}(r!)^2}$$
olur. Payda tek olduğu için \(2^{64}\) modunda terslenebilir; böylece bölme, tek sayıların modüler tersi ile çarpmaya dönüşür.
Tek önek çarpımını
$$F(u)=\prod_{t=0}^{u-1}(2t+1)=1\cdot 3\cdot 5\cdots (2u-1)$$
şeklinde tanımlayalım. \(n!\) içindeki her çarpan ya tektir ya da daha küçük bir sayının iki katıdır. 2 kuvvetleri çıkarılınca
$$\operatorname{Odd}(n!)=\operatorname{Odd}\!\left(\left\lfloor\frac{n}{2}\right\rfloor!\right)\,F\!\left(\left\lceil\frac{n}{2}\right\rceil\right)$$
elde edilir. Bunu yineleyince
$$\operatorname{Odd}(n!)=\prod_{a\ge 0}F\!\left(\left\lfloor\frac{n+2^a}{2^{a+1}}\right\rfloor\right)$$
olur ve anlamlı çarpan sayısı yalnızca \(O(\log n)\) kadardır. Bu nedenle uygulama, faktöriyel değerin kendisini hiç kurmadan çok büyük \(n\)'ler için tek kısmı hesaplayabilir.
Kullanılan 2-adik yapıda \(F(u)\), ileri fark açılımı ile değerlendirilir:
$$F(u)\equiv \sum_{t=0}^{126}\Delta^tF(0)\binom{u}{t}\pmod{2^{64}}.$$
Bu hassasiyette yalnızca ilk 127 katsayı gerekir; bunlar \(F(0),F(1),\dots,F(126)\) değerlerinden bir kez önceden üretilir. Genelleştirilmiş binom katsayıları \(\binom{u}{t}\) da aynı mod altında hesaplanır; pay ve paydadaki 2 kuvvetleri ayrılır, bölme ise sadece tek parçalarda yapılır.
Tek bir paydanın tersini almak gerektiğinde 2-adik Newton iterasyonu kullanılır:
$$x_{r+1}=x_r(2-ax_r)\pmod{2^{64}},\qquad a\text{ tek}.$$
Her adım doğru düşük bit sayısını iki katına çıkarır; bu yüzden altı iterasyon tam 64 bit hassasiyet için yeterlidir.
\(C_k\)'nin tek kısmı biliniyorsa bir sonraki katsayı
$$\frac{C_{r+1}}{C_r}=\frac{2(2r+1)}{r+1}$$
oranından gelir. 2 kuvvetleri çıkarıldığında
$$\operatorname{Odd}(C_{r+1})=\operatorname{Odd}(C_r)\,\frac{2r+1}{\operatorname{Odd}(r+1)}$$
olur. Böylece uygulama önce \(r=k\) için ilk merkezi binom terimini hesaplar, sonra \(r=k,k+1,\dots\) boyunca kısa bir yineleme ile ilerler. Her adımda tek kısım \(s_2(r)\) kadar sola kaydırılarak tam katsayı geri kurulur, uygun \((-2)\) kuvveti ile çarpılır ve sonuç \(2^{64}\) modunda biriktirilir.
Burada \(k=m+1=5\) olur. İlk merkezi binom katsayıları
$$\binom{10}{5}=252=2^2\cdot 63,\qquad \binom{12}{6}=924=2^2\cdot 231,\qquad \binom{14}{7}=3432=2^3\cdot 429$$
şeklindedir. Bu yüzden serinin ilk terimlerinin değerlemeleri
$$v_2\!\left(\binom{10}{5}\right)=2,\qquad v_2\!\left(-2\binom{12}{6}\right)=3,\qquad v_2\!\left(4\binom{14}{7}\right)=5$$
olur. \(8\) modunda yalnızca ilk terim kalır, dolayısıyla
$$S_5\equiv \binom{10}{5}\equiv 4\pmod{8}.$$
\(-3\) ile çarpmak 2-adik değerlemeyi değiştirmez çünkü 3 tektir. O halde
$$v_2(-3S_5)=2,$$
ve sonuç olarak
$$u(4)=5+2=7$$
bulunur. Bu küçük kontrol değeriyle uyuşur ve önemli olanın tam sayı büyüklüğü değil, düşük seviyedeki 2-adik bilgi olduğunu gösterir.
C++, Python ve Java uygulamaları aynı matematiksel hattı izler. Önce \(F(0),\dots,F(126)\) tek önek çarpımları, bunların ileri farkları ve Newton açılımında gereken küçük tek sayıların modüler tersleri önceden hazırlanır. Daha sonra her \(m=n^3\) için uygulama \(k=m+1\) noktasındaki ilk merkezi binom katsayısının tek kısmını kurar, ikili bit sayısından gelen 2 kuvvetini geri ekler ve sabit uzunluktaki alternatif toplamı \(2^{64}\) modunda hesaplar.
Seri tamamlandıktan sonra sonuç \(-3\) ile çarpılır, elde edilen kalandaki 2 üssü sayılır ve buna \(k\) eklenerek \(u(m)\) bulunur. Dış döngü bu değerleri \(n=1,2,\dots,10^4\) için toplar. Doğrudan derlenen uygulamalar bu dış aralığı mevcut çekirdeklere paylaştırır; Python sürümü ise aynı optimize edilmiş çekirdek hesabı çağırır.
Ön hesaplama sabit boyutludur: yalnızca 127 ileri fark değeri ve buna karşılık gelen küçük tek sayı tersleri tutulur. Tek bir \(u(m)\) hesabında faktöriyel tek kısmı formülü \(F\) fonksiyonunun \(O(\log m)\) kez değerlendirilmesini gerektirir; her değerlendirme sabit dereceli Newton açılımı sayesinde sabit zamanda yapılır. Seri toplamı ise her zaman 64 adımdır. Bu nedenle tek sorgu \(O(\log m)\) sözcük işlemi ister; \(1\le n\le N\) için \(u(n^3)\) toplamı da
$$O\!\left(\sum_{n=1}^{N}\log(n^3)\right)=O(N\log N)$$
zamanda ve sabit tablolar dışında \(O(1)\) ek bellekle tamamlanır. Pratikte sabitler küçüktür çünkü tüm aritmetik \(2^{64}\) modunda yürütülür.
La cantidad pedida es
$$U(10^4)=\sum_{n=1}^{10^4}u(n^3).$$
La función aritmética \(u(m)\) está definida por una valoración 2-ádica. Si escribimos \(k=m+1\) y consideramos la serie 2-ádicamente convergente
$$S_k=\sum_{j\ge 0}(-2)^j\binom{2(k+j)}{k+j},$$
entonces la magnitud buscada es
$$u(m)=k+v_2(-3S_k).$$
Aquí \(v_2(x)\) es el exponente de la mayor potencia de 2 que divide a \(x\). Por tanto, la dificultad real no está en la suma exterior, sino en extraer la potencia de 2 de esta serie para muchos valores cúbicos grandes sin construir enteros gigantescos de forma exacta.
La idea central es trabajar siempre dentro de \(\mathbb{Z}/2^{64}\mathbb{Z}\). Con esa precisión la valoración 2-ádica relevante sigue siendo visible y todas las operaciones permanecen en aritmética de palabra de máquina.
Sea \(C_r=\binom{2r}{r}\). Para los coeficientes binomiales centrales se cumple
$$v_2(C_r)=s_2(r),$$
donde \(s_2(r)\) es el número de bits iguales a 1 en la expansión binaria de \(r\). En consecuencia,
$$v_2\!\left((-2)^j C_{k+j}\right)=j+s_2(k+j)\ge j+1.$$
Así, módulo \(2^{64}\), todos los términos suficientemente tardíos desaparecen automáticamente. Con la precisión usada basta una acumulación de 64 pasos; la serie 2-ádica infinita se convierte en un cálculo de tamaño fijo.
Para cualquier entero no nulo definimos su parte impar por
$$\operatorname{Odd}(x)=\frac{x}{2^{v_2(x)}}.$$
Entonces cada coeficiente binomial central se descompone como
$$C_r=\operatorname{Odd}(C_r)\,2^{s_2(r)}.$$
La potencia de 2 queda determinada de inmediato por el conteo de bits de \(r\). El trabajo restante es evaluar con rapidez la parte impar. Usando factoriales,
$$\operatorname{Odd}(C_r)=\frac{\operatorname{Odd}((2r)!)}{\operatorname{Odd}(r!)^2}.$$
Como el denominador es impar, es invertible módulo \(2^{64}\), de modo que la división se sustituye por multiplicación por inversos modulares impares.
Introduzcamos el producto prefijo impar
$$F(u)=\prod_{t=0}^{u-1}(2t+1)=1\cdot 3\cdot 5\cdots (2u-1).$$
Cada factor de \(n!\) es impar o bien el doble de un entero más pequeño. Al eliminar las potencias de 2, obtenemos
$$\operatorname{Odd}(n!)=\operatorname{Odd}\!\left(\left\lfloor\frac{n}{2}\right\rfloor!\right)\,F\!\left(\left\lceil\frac{n}{2}\right\rceil\right).$$
Al iterar esta relación resulta
$$\operatorname{Odd}(n!)=\prod_{a\ge 0}F\!\left(\left\lfloor\frac{n+2^a}{2^{a+1}}\right\rfloor\right),$$
con solo \(O(\log n)\) factores no triviales. Por eso la implementación puede tratar factoriales enormes sin construir nunca el factorial completo.
En el entorno 2-ádico de trabajo, la implementación evalúa \(F(u)\) mediante una expansión por diferencias hacia adelante:
$$F(u)\equiv \sum_{t=0}^{126}\Delta^tF(0)\binom{u}{t}\pmod{2^{64}}.$$
A esta precisión solo hacen falta los primeros 127 coeficientes, que se precalculan una sola vez a partir de \(F(0),F(1),\dots,F(126)\). Los coeficientes binomiales generalizados \(\binom{u}{t}\) también se forman módulo \(2^{64}\), separando las potencias de 2 del numerador y del denominador y dividiendo solo las partes impares.
Cuando hay que invertir un denominador impar, se usa el método de Newton en versión 2-ádica:
$$x_{r+1}=x_r(2-ax_r)\pmod{2^{64}},\qquad a\text{ impar}.$$
Cada iteración duplica el número de bits bajos correctos, así que seis iteraciones bastan para alcanzar la precisión completa de 64 bits.
Si ya se conoce la parte impar de \(C_k\), el siguiente coeficiente se obtiene a partir de
$$\frac{C_{r+1}}{C_r}=\frac{2(2r+1)}{r+1}.$$
Después de separar las potencias de 2, las partes impares satisfacen
$$\operatorname{Odd}(C_{r+1})=\operatorname{Odd}(C_r)\,\frac{2r+1}{\operatorname{Odd}(r+1)}.$$
Por eso la implementación calcula primero el término central para \(r=k\) y luego avanza por \(r=k,k+1,\dots\) con una recurrencia corta. En cada paso reconstruye el coeficiente completo desplazando la parte impar por \(s_2(r)\), multiplica por la potencia adecuada de \(-2\) y acumula módulo \(2^{64}\).
Aquí \(k=m+1=5\). Los primeros coeficientes binomiales centrales son
$$\binom{10}{5}=252=2^2\cdot 63,\qquad \binom{12}{6}=924=2^2\cdot 231,\qquad \binom{14}{7}=3432=2^3\cdot 429.$$
Por tanto, las valoraciones de los primeros términos de la serie son
$$v_2\!\left(\binom{10}{5}\right)=2,\qquad v_2\!\left(-2\binom{12}{6}\right)=3,\qquad v_2\!\left(4\binom{14}{7}\right)=5.$$
Módulo \(8\) solo sobrevive el primer término, así que
$$S_5\equiv \binom{10}{5}\equiv 4\pmod{8}.$$
Multiplicar por \(-3\) no cambia la valoración 2-ádica porque 3 es impar. Luego
$$v_2(-3S_5)=2,$$
y por consiguiente
$$u(4)=5+2=7.$$
Esto coincide con la pequeña comprobación usada por la implementación y deja claro que lo importante es la valoración 2-ádica baja, no el tamaño exacto del entero.
Las implementaciones en C++, Python y Java siguen la misma cadena matemática. Primero precalculan los productos prefijo impares \(F(0),\dots,F(126)\), las diferencias hacia adelante asociadas y los inversos de los pequeños números impares necesarios en la expansión de Newton. Después, para cada entrada cúbica \(m=n^3\), la implementación construye la parte impar del primer coeficiente binomial central en \(k=m+1\), restaura la potencia de 2 completa a partir del conteo de bits y evalúa la suma alternante de longitud fija módulo \(2^{64}\).
Una vez formada la serie, la implementación multiplica por \(-3\), cuenta el exponente de 2 del residuo obtenido, suma \(k\) y obtiene \(u(m)\). El bucle exterior acumula esos valores para \(n=1,2,\dots,10^4\). Las implementaciones compiladas reparten además ese intervalo exterior entre varios núcleos disponibles, mientras que la versión en Python delega en el mismo núcleo optimizado.
La fase de precálculo tiene tamaño constante: solo se almacenan 127 diferencias hacia adelante y un conjunto correspondiente de inversos impares pequeños. Para un valor \(u(m)\), la fórmula de la parte impar del factorial necesita \(O(\log m)\) evaluaciones de \(F\), cada una en tiempo constante gracias a la expansión fija de Newton, y la suma de la serie usa siempre 64 iteraciones. Así, una consulta cuesta \(O(\log m)\) operaciones de palabra, y sumar \(u(n^3)\) para \(1\le n\le N\) requiere
$$O\!\left(\sum_{n=1}^{N}\log(n^3)\right)=O(N\log N)$$
tiempo total con \(O(1)\) memoria extra aparte de las tablas fijas. En la práctica las constantes son pequeñas porque toda la aritmética se hace módulo \(2^{64}\).
题目要求计算
$$U(10^4)=\sum_{n=1}^{10^4}u(n^3).$$
其中函数 \(u(m)\) 由一个 2-adic 赋值决定。令 \(k=m+1\)，再定义 2-adic 收敛级数
$$S_k=\sum_{j\ge 0}(-2)^j\binom{2(k+j)}{k+j},$$
那么所需量就是
$$u(m)=k+v_2(-3S_k).$$
这里 \(v_2(x)\) 表示 2 在 \(x\) 中的指数，也就是最大的 \(2\) 的幂次使得 \(2^{v_2(x)}\mid x\)。真正的难点不在于外层求和，而在于当 \(m=n^3\) 很大时，怎样在不展开巨大精确整数的前提下，稳定地提取这一级数中的 2-adic 信息。
整套做法的核心，是把计算始终放在 \(\mathbb{Z}/2^{64}\mathbb{Z}\) 中进行。这样做的好处是：需要的 2-adic 赋值仍然能够被看见，而所有运算都能限制在固定宽度的机器整数内。
记 \(C_r=\binom{2r}{r}\)。对于中心二项式系数，有一个标准结论：
$$v_2(C_r)=s_2(r),$$
其中 \(s_2(r)\) 是 \(r\) 的二进制表示中 1 的个数。因此
$$v_2\!\left((-2)^j C_{k+j}\right)=j+s_2(k+j)\ge j+1.$$
这说明在模 \(2^{64}\) 的世界里，足够靠后的项会自动消失。实现中只需要固定的 64 步累加，就足以覆盖所需精度；原本的无穷 2-adic 级数于是被压缩成一个定长计算。
对任意非零整数，定义它的奇数部分为
$$\operatorname{Odd}(x)=\frac{x}{2^{v_2(x)}}.$$
于是每个中心二项式系数都能写成
$$C_r=\operatorname{Odd}(C_r)\,2^{s_2(r)}.$$
这意味着 2 的幂次可以直接由二进制位数信息得到，真正要高效计算的是奇数部分。利用阶乘可以写成
$$\operatorname{Odd}(C_r)=\frac{\operatorname{Odd}((2r)!)}{\operatorname{Odd}(r!)^2}.$$
由于分母一定是奇数，它在模 \(2^{64}\) 下可逆，所以“除法”可以改写成与奇数模逆元相乘。
定义奇数前缀乘积
$$F(u)=\prod_{t=0}^{u-1}(2t+1)=1\cdot 3\cdot 5\cdots (2u-1).$$
\(n!\) 中的每个因子，要么本身就是奇数，要么是某个更小整数的两倍。把所有 2 的幂剥掉之后，可以得到递推式
$$\operatorname{Odd}(n!)=\operatorname{Odd}\!\left(\left\lfloor\frac{n}{2}\right\rfloor!\right)\,F\!\left(\left\lceil\frac{n}{2}\right\rceil\right).$$
继续迭代就有
$$\operatorname{Odd}(n!)=\prod_{a\ge 0}F\!\left(\left\lfloor\frac{n+2^a}{2^{a+1}}\right\rfloor\right).$$
其中真正非平凡的因子只有 \(O(\log n)\) 个。这就是为什么实现可以处理非常大的阶乘奇数部分，却从来不需要真的构造整个阶乘值。
在当前的 2-adic 工作框架里，实现把 \(F(u)\) 写成前向差分展开：
$$F(u)\equiv \sum_{t=0}^{126}\Delta^tF(0)\binom{u}{t}\pmod{2^{64}}.$$
在这个精度下，只需要前 127 个系数，所以可以先从 \(F(0),F(1),\dots,F(126)\) 一次性预处理出来。广义二项式系数 \(\binom{u}{t}\) 也是在模 \(2^{64}\) 下计算：先把分子和分母中的 2 的幂剥离，再只对奇数部分做除法。
当需要求某个奇数分母的逆元时，使用的是 2-adic 版本的 Newton 迭代：
$$x_{r+1}=x_r(2-ax_r)\pmod{2^{64}},\qquad a\text{ 为奇数}.$$
每迭代一次，正确的低位比特数都会翻倍，因此六轮迭代就足以达到完整的 64 位精度。
一旦知道了 \(C_k\) 的奇数部分，下一个系数可以由
$$\frac{C_{r+1}}{C_r}=\frac{2(2r+1)}{r+1}$$
得到。把 2 的幂次分离后，奇数部分满足
$$\operatorname{Odd}(C_{r+1})=\operatorname{Odd}(C_r)\,\frac{2r+1}{\operatorname{Odd}(r+1)}.$$
因此，实现只需先算出 \(r=k\) 时的第一个中心二项式项，然后沿着 \(r=k,k+1,\dots\) 做一个很短的递推。每一步先用 \(s_2(r)\) 把奇数部分左移还原成完整系数，再乘上相应的 \((-2)\) 的幂，最后在模 \(2^{64}\) 下累加。
此时 \(k=m+1=5\)。前几个中心二项式系数是
$$\binom{10}{5}=252=2^2\cdot 63,\qquad \binom{12}{6}=924=2^2\cdot 231,\qquad \binom{14}{7}=3432=2^3\cdot 429.$$
于是级数前几项的 2-adic 赋值分别为
$$v_2\!\left(\binom{10}{5}\right)=2,\qquad v_2\!\left(-2\binom{12}{6}\right)=3,\qquad v_2\!\left(4\binom{14}{7}\right)=5.$$
在模 \(8\) 下，只有第一项仍然留下来，因此
$$S_5\equiv \binom{10}{5}\equiv 4\pmod{8}.$$
再乘上 \(-3\) 并不会改变 2-adic 赋值，因为 3 是奇数。所以
$$v_2(-3S_5)=2,$$
从而
$$u(4)=5+2=7.$$
这与实现中的小规模校验完全一致，也说明这个问题真正关心的是低阶 2-adic 赋值，而不是中间整数到底有多大。
C++、Python 和 Java 三个实现遵循同一条数学流程。首先预处理奇数前缀乘积 \(F(0),\dots,F(126)\)、对应的前向差分，以及 Newton 展开中会用到的小奇数逆元。随后，对于每个立方输入 \(m=n^3\)，实现先构造 \(k=m+1\) 处第一个中心二项式系数的奇数部分，再用二进制 1 的个数补回完整的 2 的幂，然后在模 \(2^{64}\) 下计算固定长度的交错和。
当级数和得到后，实现将其乘以 \(-3\)，统计结果中 2 的指数，再加上 \(k\)，于是得到 \(u(m)\)。最外层循环把这些值对 \(n=1,2,\dots,10^4\) 累加起来。直接编译的实现还会把这一外层区间分配给可用的多个处理器核心，而 Python 版本则调用同一个优化后的核心计算。
预处理阶段的规模是常数：只保存 127 个前向差分值和相应数量的小奇数逆元。对单个 \(u(m)\) 而言，阶乘奇数部分公式需要 \(O(\log m)\) 次 \(F\) 的求值；由于 Newton 展开的阶数固定，每次求值都可视为常数时间。级数求和本身恒为 64 步，所以单次查询是 \(O(\log m)\) 个机器字操作。于是对 \(1\le n\le N\) 累加 \(u(n^3)\) 的总代价为
$$O\!\left(\sum_{n=1}^{N}\log(n^3)\right)=O(N\log N).$$
额外内存除固定表外仅为 \(O(1)\)。实际运行时常数也很小，因为所有算术都被限制在模 \(2^{64}\) 的范围内。
Требуется вычислить
$$U(10^4)=\sum_{n=1}^{10^4}u(n^3).$$
Функция \(u(m)\) задается через 2-адическую оценку. Если положить \(k=m+1\) и рассмотреть 2-адически сходящийся ряд
$$S_k=\sum_{j\ge 0}(-2)^j\binom{2(k+j)}{k+j},$$
то искомая величина имеет вид
$$u(m)=k+v_2(-3S_k).$$
Здесь \(v_2(x)\) означает показатель наибольшей степени двойки, делящей \(x\). Значит, главная трудность состоит не во внешнем суммировании, а в том, чтобы для многих больших кубических аргументов извлечь степень двойки из этого ряда, не разворачивая гигантские точные целые числа.
Ключевая идея состоит в том, чтобы все время работать в \(\mathbb{Z}/2^{64}\mathbb{Z}\). При такой точности нужная 2-адическая информация сохраняется, а все вычисления укладываются в машинную арифметику фиксированной ширины.
Обозначим \(C_r=\binom{2r}{r}\). Для центральных биномиальных коэффициентов верно
$$v_2(C_r)=s_2(r),$$
где \(s_2(r)\) - число единиц в двоичной записи \(r\). Поэтому
$$v_2\!\left((-2)^j C_{k+j}\right)=j+s_2(k+j)\ge j+1.$$
Следовательно, по модулю \(2^{64}\) все достаточно поздние члены автоматически исчезают. При выбранной точности достаточно цикла из 64 шагов, и бесконечный 2-адический ряд превращается в вычисление фиксированного размера.
Для любого ненулевого целого числа определим нечетную часть как
$$\operatorname{Odd}(x)=\frac{x}{2^{v_2(x)}}.$$
Тогда каждый центральный биномиальный коэффициент раскладывается так:
$$C_r=\operatorname{Odd}(C_r)\,2^{s_2(r)}.$$
Степень двойки сразу определяется по двоичной записи \(r\). Остается быстро вычислить нечетную часть. Через факториалы имеем
$$\operatorname{Odd}(C_r)=\frac{\operatorname{Odd}((2r)!)}{\operatorname{Odd}(r!)^2}.$$
Поскольку знаменатель нечетен, он обратим по модулю \(2^{64}\), и деление заменяется умножением на нечетный модульный обратный элемент.
Введем нечетное префиксное произведение
$$F(u)=\prod_{t=0}^{u-1}(2t+1)=1\cdot 3\cdot 5\cdots (2u-1).$$
Каждый множитель в \(n!\) либо нечетен, либо равен удвоенному меньшему числу. Если удалить все степени двойки, получится рекурсия
$$\operatorname{Odd}(n!)=\operatorname{Odd}\!\left(\left\lfloor\frac{n}{2}\right\rfloor!\right)\,F\!\left(\left\lceil\frac{n}{2}\right\rceil\right).$$
После итерации выходит
$$\operatorname{Odd}(n!)=\prod_{a\ge 0}F\!\left(\left\lfloor\frac{n+2^a}{2^{a+1}}\right\rfloor\right),$$
где нетривиальных множителей только \(O(\log n)\). Именно поэтому реализация умеет работать с очень большими факториалами, не создавая сам факториал целиком.
В используемой 2-адической схеме функция \(F(u)\) вычисляется из разложения по прямым разностям:
$$F(u)\equiv \sum_{t=0}^{126}\Delta^tF(0)\binom{u}{t}\pmod{2^{64}}.$$
При этой точности нужны только первые 127 коэффициентов, поэтому они один раз предвычисляются из значений \(F(0),F(1),\dots,F(126)\). Обобщенные биномиальные коэффициенты \(\binom{u}{t}\) тоже строятся по модулю \(2^{64}\): степени двойки отделяются, а деление выполняется только по нечетным частям числителя и знаменателя.
Когда требуется обратить нечетный знаменатель, используется 2-адическая версия метода Ньютона:
$$x_{r+1}=x_r(2-ax_r)\pmod{2^{64}},\qquad a\text{ нечетно}.$$
Каждая итерация удваивает число правильных младших битов, поэтому шести шагов уже достаточно для полной 64-битной точности.
Если нечетная часть \(C_k\) уже известна, следующий коэффициент получается из отношения
$$\frac{C_{r+1}}{C_r}=\frac{2(2r+1)}{r+1}.$$
После отделения степеней двойки нечетные части удовлетворяют формуле
$$\operatorname{Odd}(C_{r+1})=\operatorname{Odd}(C_r)\,\frac{2r+1}{\operatorname{Odd}(r+1)}.$$
Поэтому реализация сначала вычисляет первый центральный биномиальный член при \(r=k\), а затем проходит по \(r=k,k+1,\dots\) короткой рекурсией. На каждом шаге полный коэффициент восстанавливается сдвигом нечетной части на \(s_2(r)\), умножается на нужную степень \(-2\) и прибавляется по модулю \(2^{64}\).
Здесь \(k=m+1=5\). Первые центральные биномиальные коэффициенты равны
$$\binom{10}{5}=252=2^2\cdot 63,\qquad \binom{12}{6}=924=2^2\cdot 231,\qquad \binom{14}{7}=3432=2^3\cdot 429.$$
Отсюда оценки первых членов ряда таковы:
$$v_2\!\left(\binom{10}{5}\right)=2,\qquad v_2\!\left(-2\binom{12}{6}\right)=3,\qquad v_2\!\left(4\binom{14}{7}\right)=5.$$
По модулю \(8\) выживает только первый член, поэтому
$$S_5\equiv \binom{10}{5}\equiv 4\pmod{8}.$$
Умножение на \(-3\) не меняет 2-адическую оценку, потому что 3 нечетно. Значит,
$$v_2(-3S_5)=2,$$
и, следовательно,
$$u(4)=5+2=7.$$
Это совпадает с малой контрольной точкой реализации и показывает, что здесь важен именно низкий 2-адический порядок, а не точная величина промежуточных чисел.
Реализации на C++, Python и Java используют одну и ту же математическую схему. Сначала они предвычисляют нечетные префиксные произведения \(F(0),\dots,F(126)\), соответствующие прямые разности и обратные элементы к малым нечетным числам, необходимые для разложения Ньютона. Затем для каждого кубического аргумента \(m=n^3\) реализация строит нечетную часть первого центрального биномиального коэффициента при \(k=m+1\), восстанавливает полную степень двойки по числу единиц в двоичной записи и вычисляет фиксированную по длине знакочередующуюся сумму по модулю \(2^{64}\).
После этого сумма умножается на \(-3\), определяется показатель двойки в полученном остатке, прибавляется \(k\), и получается \(u(m)\). Внешний цикл суммирует эти значения для \(n=1,2,\dots,10^4\). Непосредственно компилируемые реализации дополнительно делят внешний диапазон между доступными ядрами процессора, а Python-версия обращается к тому же оптимизированному вычислительному ядру.
Предвычисление имеет постоянный размер: хранятся лишь 127 значений прямых разностей и соответствующий набор малых нечетных обратных элементов. Для одного значения \(u(m)\) формула для нечетной части факториала требует \(O(\log m)\) вычислений \(F\), причем каждое вычисление занимает постоянное время благодаря фиксированному разложению Ньютона. Само суммирование ряда всегда состоит из 64 шагов. Поэтому один запрос стоит \(O(\log m)\) машинных операций, а суммирование \(u(n^3)\) для \(1\le n\le N\) требует
$$O\!\left(\sum_{n=1}^{N}\log(n^3)\right)=O(N\log N)$$
времени и \(O(1)\) дополнительной памяти сверх фиксированных таблиц. На практике константы малы, потому что вся арифметика выполняется по модулю \(2^{64}\).
المطلوب هو حساب
$$U(10^4)=\sum_{n=1}^{10^4}u(n^3).$$
الدالة \(u(m)\) تُعرَّف بواسطة تقييم 2-adic. إذا وضعنا \(k=m+1\) وعرّفنا السلسلة المتقاربة 2-adic
$$S_k=\sum_{j\ge 0}(-2)^j\binom{2(k+j)}{k+j},$$
فإن الكمية المطلوبة هي
$$u(m)=k+v_2(-3S_k).$$
وهنا \(v_2(x)\) هو أس أكبر قوة للعدد 2 تقسم \(x\). لذلك فالصعوبة الحقيقية ليست في الجمع الخارجي نفسه، بل في استخراج قوة 2 من هذه السلسلة لكثير من المدخلات التكعيبية الكبيرة من دون تكوين أعداد صحيحة هائلة بدقة كاملة.
الفكرة الأساسية هي أن يبقى الحساب كله داخل \(\mathbb{Z}/2^{64}\mathbb{Z}\). عند هذه الدقة تبقى المعلومة 2-adic المهمة ظاهرة، وفي الوقت نفسه تبقى كل العمليات ضمن حسابات كلمات الآلة.
لنكتب \(C_r=\binom{2r}{r}\). بالنسبة إلى المعاملات الثنائية المركزية لدينا الحقيقة المعروفة
$$v_2(C_r)=s_2(r),$$
حيث إن \(s_2(r)\) هو عدد البتات التي تساوي 1 في التمثيل الثنائي للعدد \(r\). ومن ثم
$$v_2\!\left((-2)^j C_{k+j}\right)=j+s_2(k+j)\ge j+1.$$
وعليه، فإن جميع الحدود المتأخرة بما يكفي تختفي تلقائيا بترديد \(2^{64}\). عملياً تكفي عملية تجميع بطول 64 خطوة، وبذلك تتحول السلسلة 2-adic اللانهائية إلى حساب ذي حجم ثابت.
لكل عدد صحيح غير صفري نعرّف جزأه الفردي كما يلي:
$$\operatorname{Odd}(x)=\frac{x}{2^{v_2(x)}}.$$
وعندها ينفك كل معامل ثنائي مركزي إلى الصورة
$$C_r=\operatorname{Odd}(C_r)\,2^{s_2(r)}.$$
أي إن قوة 2 تُعرف مباشرة من عدد البتات في \(r\)، ويبقى فقط حساب الجزء الفردي بكفاءة. وباستخدام المضروبات نحصل على
$$\operatorname{Odd}(C_r)=\frac{\operatorname{Odd}((2r)!)}{\operatorname{Odd}(r!)^2}.$$
وبما أن المقام فردي فهو قابل للعكس بترديد \(2^{64}\)، لذا يمكن استبدال القسمة بالضرب في المعكوس الفردي المناسب.
لنعرّف جداء البادئة الفردية
$$F(u)=\prod_{t=0}^{u-1}(2t+1)=1\cdot 3\cdot 5\cdots (2u-1).$$
كل عامل في \(n!\) هو إما عدد فردي، أو ضعف عدد أصغر. وبعد نزع جميع قوى 2 نحصل على العلاقة
$$\operatorname{Odd}(n!)=\operatorname{Odd}\!\left(\left\lfloor\frac{n}{2}\right\rfloor!\right)\,F\!\left(\left\lceil\frac{n}{2}\right\rceil\right).$$
وبتكرارها نحصل على
$$\operatorname{Odd}(n!)=\prod_{a\ge 0}F\!\left(\left\lfloor\frac{n+2^a}{2^{a+1}}\right\rfloor\right),$$
ولا يبقى إلا \(O(\log n)\) من العوامل غير التافهة. ولهذا تستطيع الشيفرة التعامل مع أجزاء فردية لمضروبات كبيرة جداً من دون إنشاء قيمة المضروب نفسها.
في الإطار 2-adic المستخدم، تُقيَّم \(F(u)\) بواسطة توسع فروق أمامية:
$$F(u)\equiv \sum_{t=0}^{126}\Delta^tF(0)\binom{u}{t}\pmod{2^{64}}.$$
عند هذه الدقة نحتاج فقط إلى أول 127 معاملاً، ولهذا تُحسب مسبقاً مرة واحدة انطلاقاً من القيم \(F(0),F(1),\dots,F(126)\). أما معاملات ذات الحدين المعممة \(\binom{u}{t}\) فتُبنى أيضاً بترديد \(2^{64}\) بعد فصل قوى 2 من البسط والمقام، ثم إجراء القسمة على الأجزاء الفردية فقط.
وعندما نحتاج إلى معكوس مقام فردي تُستخدم نسخة 2-adic من طريقة Newton:
$$x_{r+1}=x_r(2-ax_r)\pmod{2^{64}},\qquad a\equiv 1\pmod{2}.$$
كل تكرار يضاعف عدد البتات الدنيا الصحيحة، ولذلك تكفي ست دورات للوصول إلى دقة 64 بت كاملة.
إذا كان الجزء الفردي لـ \(C_k\) معروفاً، فإن المعامل التالي يأتي من النسبة
$$\frac{C_{r+1}}{C_r}=\frac{2(2r+1)}{r+1}.$$
وبعد فصل قوى 2 تصبح الأجزاء الفردية محكومة بالعلاقة
$$\operatorname{Odd}(C_{r+1})=\operatorname{Odd}(C_r)\,\frac{2r+1}{\operatorname{Odd}(r+1)}.$$
لذلك تحسب الشيفرة أول حد مركزي عند \(r=k\)، ثم تنتقل عبر \(r=k,k+1,\dots\) بعلاقة تكرارية قصيرة. وفي كل خطوة تُستعاد قيمة المعامل الكامل بإزاحة الجزء الفردي بمقدار \(s_2(r)\)، ثم يُضرب الحد في القوة المناسبة لـ \(-2\)، وبعد ذلك يُجمع الناتج بترديد \(2^{64}\).
هنا لدينا \(k=m+1=5\). وأول معاملات ثنائية مركزية هي
$$\binom{10}{5}=252=2^2\cdot 63,\qquad \binom{12}{6}=924=2^2\cdot 231,\qquad \binom{14}{7}=3432=2^3\cdot 429.$$
إذن تقييمات أول حدود السلسلة تساوي
$$v_2\!\left(\binom{10}{5}\right)=2,\qquad v_2\!\left(-2\binom{12}{6}\right)=3,\qquad v_2\!\left(4\binom{14}{7}\right)=5.$$
وبترديد \(8\) لا يبقى إلا الحد الأول، ولذلك
$$S_5\equiv \binom{10}{5}\equiv 4\pmod{8}.$$
والضرب في \(-3\) لا يغيّر التقييم 2-adic لأن العدد 3 فردي. ومن ثم
$$v_2(-3S_5)=2,$$
وبالتالي
$$u(4)=5+2=7.$$
وهذا يطابق نقطة التحقق الصغيرة في التنفيذ، ويبين أن المهم هنا هو الرتبة 2-adic المنخفضة لا الحجم العددي الدقيق للحدود الوسيطة.
تتبع تطبيقات C++ وPython وJava المسار الرياضي نفسه. فهي تبدأ بحساب القيم المسبقة لجداءات البادئة الفردية \(F(0),\dots,F(126)\)، والفروق الأمامية الموافقة، ومعكوسات الأعداد الفردية الصغيرة اللازمة في توسع Newton. بعد ذلك، ولكل مدخل تكعيبي \(m=n^3\)، يبني التنفيذ الجزء الفردي لأول معامل ثنائي مركزي عند \(k=m+1\)، ثم يعيد تركيب قوة 2 الكاملة من عدد الواحدات في التمثيل الثنائي، وبعدها يحسب السلسلة المتناوبة ذات الطول الثابت بترديد \(2^{64}\).
وبعد تكوين السلسلة تُضرب النتيجة في \(-3\)، ثم يُحسب أس العامل 2 في الباقي الناتج، ويُضاف \(k\) للحصول على \(u(m)\). وأخيراً يجمع البرنامج هذه القيم لكل \(n=1,2,\dots,10^4\). أما التنفيذات المترجمة مباشرة فتوزع هذا المدى الخارجي أيضاً على الأنوية المتاحة، في حين أن نسخة Python تستدعي النواة المحسنة نفسها.
مرحلة التهيئة ذات حجم ثابت: إذ لا يجري تخزين سوى 127 قيمة من الفروق الأمامية ومجموعة مماثلة من المعكوسات الفردية الصغيرة. ولكل قيمة \(u(m)\)، تحتاج صيغة الجزء الفردي من المضروب إلى \(O(\log m)\) من تقييمات \(F\)، وكل تقييم يتم في زمن ثابت بفضل توسع Newton ذي الدرجة الثابتة، بينما يبقى جمع السلسلة دائماً ذا 64 خطوة. لذا تكلف الاستعلامات المفردة \(O(\log m)\) من عمليات الكلمات، أما جمع \(u(n^3)\) من أجل \(1\le n\le N\) فيكلف
$$O\!\left(\sum_{n=1}^{N}\log(n^3)\right)=O(N\log N).$$
أما الذاكرة الإضافية فتبقى \(O(1)\) فوق الجداول الثابتة. وعملياً تكون الثوابت صغيرة لأن كل الحسابات تتم بترديد \(2^{64}\).