Let \(p_m\#=\prod_{i=1}^{m} p_i\) be the primorial of the first \(m\) primes, let \(\tau(n)\) be the divisor-counting function, and define
$$S(N)=\sum_{d \mid N}\tau(d)-\tau(N),\qquad E(m,n)=v_2\!\left(S\!\left((p_m\#)^n\right)\right).$$
The required quantity is the cumulative sum
$$Q(m,N)=\sum_{n=1}^{N}E(m,n).$$
For the actual problem instance, \(m=904961\) and \(N=10^{12}\). Because that \(m\) is odd and \(N\) is enormous, the solution must turn the divisor expression into a closed formula rather than evaluating every term separately.
The key observation is that a primorial power has exactly \(m\) distinct prime factors and all of them appear with the same exponent \(n\). That symmetry makes both the divisor sum and the \(2\)-adic valuation collapse into elementary arithmetic.
For \(N=(p_m\#)^n\), each of the \(m\) primes has exponent \(n\), so
$$\tau\!\left((p_m\#)^n\right)=(n+1)^m.$$
Every divisor is obtained by choosing one exponent from \(0\) to \(n\) independently for each prime. Therefore
$$\sum_{d \mid (p_m\#)^n}\tau(d)=\left(\sum_{k=0}^{n}(k+1)\right)^m=\left(\frac{(n+1)(n+2)}{2}\right)^m.$$
Substituting this into the definition of \(S\) gives
$$S\!\left((p_m\#)^n\right)=\left(\frac{(n+1)(n+2)}{2}\right)^m-(n+1)^m.$$
Let \(n=2k-1\). Then \(n+1=2k\) and \(n+2=2k+1\), so
$$S\!\left((p_m\#)^{2k-1}\right)=\bigl(k(2k+1)\bigr)^m-(2k)^m=k^m\left((2k+1)^m-2^m\right).$$
The bracketed factor is odd, because an odd number minus an even number is odd. Hence the entire \(2\)-adic valuation comes from the factor \(k^m\):
$$E(m,2k-1)=m\,v_2(k)=m\,v_2\!\left(\frac{n+1}{2}\right).$$
Let \(n=2r\). Then \(n+1=2r+1\) is odd, and the same identity becomes
$$S\!\left((p_m\#)^{2r}\right)=\bigl((2r+1)(r+1)\bigr)^m-(2r+1)^m=(2r+1)^m\left((r+1)^m-1\right).$$
Now split according to the residue of \(n\) modulo \(4\).
If \(r\) is odd, then \(n\equiv 2 \pmod 4\) and \(r+1\) is even, so \((r+1)^m-1\) is odd. Therefore
$$E(m,n)=0 \qquad \text{when } n\equiv 2 \pmod 4.$$
If \(r=2t\), then \(n=4t\) and \(r+1=2t+1\) is odd. Since \(m=904961\) is odd,
$$\begin{aligned} (2t+1)^m-1&=(2t)\left((2t+1)^{m-1}+(2t+1)^{m-2}+\cdots+1\right). \end{aligned}$$
The parenthesized sum is odd because it contains an odd number of odd terms. Hence
$$E(m,4t)=v_2(2t)=1+v_2(t)=v_2(n)-1.$$
For this odd \(m\), the valuation rule is therefore
$$E(m,n)= \begin{cases} m\,v_2\!\left(\frac{n+1}{2}\right), & n \text{ odd},\\ 0, & n\equiv 2 \pmod 4,\\ v_2(n)-1, & 4\mid n. \end{cases}$$
We now sum \(E(m,n)\) from \(1\) to \(N\). The class \(n\equiv 2 \pmod 4\) contributes nothing, so only odd numbers and multiples of \(4\) remain.
For odd \(n\), write \(n=2k-1\) with
$$K=\left\lfloor\frac{N+1}{2}\right\rfloor.$$
Then
$$\sum_{\substack{1\le n\le N\\ n\text{ odd}}}E(m,n)=m\sum_{k=1}^{K}v_2(k)=m\,v_2(K!).$$
For multiples of \(4\), write \(n=4t\) with
$$T=\left\lfloor\frac{N}{4}\right\rfloor.$$
Then
$$\sum_{\substack{1\le n\le N\\ 4\mid n}}E(m,n)=\sum_{t=1}^{T}\bigl(1+v_2(t)\bigr)=T+v_2(T!).$$
So the whole cumulative quantity reduces to
$$Q(m,N)=m\,v_2(K!)+T+v_2(T!).$$
Legendre's formula for the prime \(2\) says
$$v_2(x!)=\sum_{j\ge 1}\left\lfloor\frac{x}{2^j}\right\rfloor=x-\operatorname{popcount}(x).$$
This turns the final sum into direct arithmetic:
$$Q(m,N)=m\left(K-\operatorname{popcount}(K)\right)+T+\left(T-\operatorname{popcount}(T)\right).$$
No iteration up to \(N\) survives the derivation.
This checkpoint is small enough to verify by hand and already shows the full mechanism. Here
$$K=\left\lfloor\frac{8+1}{2}\right\rfloor=4,\qquad T=\left\lfloor\frac{8}{4}\right\rfloor=2.$$
Using Legendre,
$$v_2(4!)=4-\operatorname{popcount}(4)=4-1=3,\qquad v_2(2!)=2-\operatorname{popcount}(2)=2-1=1.$$
Therefore
$$Q(m,8)=3m+3.$$
For the actual problem parameter \(m=904961\), this becomes
$$Q(904961,8)=3\cdot 904961+3=2714886,$$
which matches the checkpoint used by the implementations.
The C++, Python, and Java implementations never loop from \(1\) to \(N\). They apply the closed form derived above directly to the odd input \(m=904961\).
Each implementation computes
$$K=\left\lfloor\frac{N+1}{2}\right\rfloor,\qquad T=\left\lfloor\frac{N}{4}\right\rfloor,$$
then evaluates \(v_2(K!)\) and \(v_2(T!)\) via the identity \(x-\operatorname{popcount}(x)\), and finally forms
$$m\,v_2(K!)+T+v_2(T!).$$
The C++ implementation also includes two small sanity checks: one confirms that \(S(6)=5\), and another confirms the checkpoint \(Q(904961,8)=2714886\). After that, the exact decimal answer for \(N=10^{12}\) is printed.
For the fixed-size integer inputs used here, the algorithm runs in \(O(1)\) time and \(O(1)\) memory. The derivation removes every loop over \(n\); only a handful of integer divisions, bit counts, and additions remain.
Sei \(p_m\#=\prod_{i=1}^{m} p_i\) das Primorial der ersten \(m\) Primzahlen, \(\tau(n)\) die Teileranzahlfunktion und
$$S(N)=\sum_{d \mid N}\tau(d)-\tau(N),\qquad E(m,n)=v_2\!\left(S\!\left((p_m\#)^n\right)\right).$$
Gesucht ist die kumulative Summe
$$Q(m,N)=\sum_{n=1}^{N}E(m,n).$$
Im eigentlichen Problem gilt \(m=904961\) und \(N=10^{12}\). Weil dieses \(m\) ungerade ist und \(N\) viel zu groß für direkte Aufzählung wäre, muss man die Formel algebraisch vereinfachen.
Bei einer Primorialpotenz treten genau \(m\) verschiedene Primzahlen auf, und jede hat denselben Exponenten \(n\). Gerade diese Symmetrie macht sowohl die Teilersumme als auch die \(2\)-adische Bewertung beherrschbar.
Für \(N=(p_m\#)^n\) hat jede der \(m\) Primzahlen den Exponenten \(n\), also gilt
$$\tau\!\left((p_m\#)^n\right)=(n+1)^m.$$
Jeder Teiler entsteht, indem man für jede Primzahl unabhängig einen Exponenten zwischen \(0\) und \(n\) wählt. Daher
$$\sum_{d \mid (p_m\#)^n}\tau(d)=\left(\sum_{k=0}^{n}(k+1)\right)^m=\left(\frac{(n+1)(n+2)}{2}\right)^m.$$
Damit wird
$$S\!\left((p_m\#)^n\right)=\left(\frac{(n+1)(n+2)}{2}\right)^m-(n+1)^m.$$
Setze \(n=2k-1\). Dann sind \(n+1=2k\) und \(n+2=2k+1\), also
$$S\!\left((p_m\#)^{2k-1}\right)=\bigl(k(2k+1)\bigr)^m-(2k)^m=k^m\left((2k+1)^m-2^m\right).$$
Der Klammerausdruck ist ungerade, denn eine ungerade Zahl minus eine gerade Zahl bleibt ungerade. Folglich stammt die gesamte \(2\)-adische Bewertung allein aus \(k^m\):
$$E(m,2k-1)=m\,v_2(k)=m\,v_2\!\left(\frac{n+1}{2}\right).$$
Setze \(n=2r\). Dann ist \(n+1=2r+1\) ungerade, und dieselbe Identität liefert
$$S\!\left((p_m\#)^{2r}\right)=\bigl((2r+1)(r+1)\bigr)^m-(2r+1)^m=(2r+1)^m\left((r+1)^m-1\right).$$
Nun entscheidet die Restklasse von \(n\) modulo \(4\).
Ist \(r\) ungerade, dann gilt \(n\equiv 2 \pmod 4\), also ist \(r+1\) gerade und \((r+1)^m-1\) ungerade. Deshalb
$$E(m,n)=0 \qquad \text{if } n\equiv 2 \pmod 4.$$
Ist dagegen \(r=2t\), also \(n=4t\), dann ist \(r+1=2t+1\) ungerade. Weil \(m=904961\) ungerade ist, folgt
$$\begin{aligned} (2t+1)^m-1&=(2t)\left((2t+1)^{m-1}+(2t+1)^{m-2}+\cdots+1\right). \end{aligned}$$
Die Summe in der Klammer ist ungerade, da sie aus einer ungeraden Anzahl ungerader Summanden besteht. Also
$$E(m,4t)=v_2(2t)=1+v_2(t)=v_2(n)-1.$$
Für dieses ungerade \(m\) ergibt sich somit die Stückformel
$$E(m,n)= \begin{cases} m\,v_2\!\left(\frac{n+1}{2}\right), & n \text{ odd},\\ 0, & n\equiv 2 \pmod 4,\\ v_2(n)-1, & 4\mid n. \end{cases}$$
Jetzt wird \(E(m,n)\) von \(1\) bis \(N\) summiert. Die Klasse \(n\equiv 2 \pmod 4\) trägt nichts bei, also bleiben nur ungerade \(n\) und Vielfache von \(4\).
Für ungerade \(n\) schreiben wir \(n=2k-1\) mit
$$K=\left\lfloor\frac{N+1}{2}\right\rfloor.$$
Dann gilt
$$\sum_{\substack{1\le n\le N\\ n\text{ odd}}}E(m,n)=m\sum_{k=1}^{K}v_2(k)=m\,v_2(K!).$$
Für Vielfache von \(4\) schreiben wir \(n=4t\) mit
$$T=\left\lfloor\frac{N}{4}\right\rfloor.$$
Dann folgt
$$\sum_{\substack{1\le n\le N\\ 4\mid n}}E(m,n)=\sum_{t=1}^{T}\bigl(1+v_2(t)\bigr)=T+v_2(T!).$$
Die gesamte Summe reduziert sich also auf
$$Q(m,N)=m\,v_2(K!)+T+v_2(T!).$$
Legendres Formel für die Primzahl \(2\) lautet
$$v_2(x!)=\sum_{j\ge 1}\left\lfloor\frac{x}{2^j}\right\rfloor=x-\operatorname{popcount}(x).$$
Damit wird die Endform zu einer unmittelbaren Ganzzahlrechnung:
$$Q(m,N)=m\left(K-\operatorname{popcount}(K)\right)+T+\left(T-\operatorname{popcount}(T)\right).$$
Es bleibt also keinerlei Schleife bis \(N\) übrig.
Dieser Kontrollwert ist klein genug für Handrechnung und zeigt bereits das ganze Muster. Hier ist
$$K=\left\lfloor\frac{8+1}{2}\right\rfloor=4,\qquad T=\left\lfloor\frac{8}{4}\right\rfloor=2.$$
Mit Legendre erhält man
$$v_2(4!)=4-\operatorname{popcount}(4)=4-1=3,\qquad v_2(2!)=2-\operatorname{popcount}(2)=2-1=1.$$
Daher
$$Q(m,8)=3m+3.$$
Für den eigentlichen Problemwert \(m=904961\) wird daraus
$$Q(904961,8)=3\cdot 904961+3=2714886,$$
genau der Kontrollwert aus den Implementierungen.
Die C++-, Python- und Java-Implementierungen laufen nicht alle Werte von \(1\) bis \(N\) durch. Stattdessen setzen sie die oben hergeleitete geschlossene Formel direkt für das ungerade Eingabe-\(m=904961\) ein.
Dazu werden zunächst
$$K=\left\lfloor\frac{N+1}{2}\right\rfloor,\qquad T=\left\lfloor\frac{N}{4}\right\rfloor$$
berechnet, anschließend \(v_2(K!)\) und \(v_2(T!)\) über die Identität \(x-\operatorname{popcount}(x)\) ausgewertet und schließlich
$$m\,v_2(K!)+T+v_2(T!)$$
gebildet. Die C++-Implementierung enthält zusätzlich zwei kleine Plausibilitätsprüfungen: einmal \(S(6)=5\) und einmal den Kontrollwert \(Q(904961,8)=2714886\). Danach wird die exakte Dezimalzahl für \(N=10^{12}\) ausgegeben.
Für die hier verwendeten Eingaben fester Maschinenwortgröße läuft das Verfahren in \(O(1)\) Zeit und benötigt \(O(1)\) Speicher. Die gesamte Schleife über \(n\) wurde wegtransformiert; übrig bleiben nur einige Ganzzahldivisionen, Bitzählungen und Additionen.
\(p_m\#=\prod_{i=1}^{m} p_i\) ilk \(m\) asalın primoriali, \(\tau(n)\) bölen sayısı fonksiyonu olsun. Problem şu nicelikleri tanımlar:
$$S(N)=\sum_{d \mid N}\tau(d)-\tau(N),\qquad E(m,n)=v_2\!\left(S\!\left((p_m\#)^n\right)\right).$$
İstenen toplam ise
$$Q(m,N)=\sum_{n=1}^{N}E(m,n).$$
Gerçek problem girdisinde \(m=904961\) ve \(N=10^{12}\) alınır. Bu \(m\) tek olduğu ve \(N\) devasa olduğu için çözüm, her terimi tek tek hesaplamak yerine kapalı bir form üretmek zorundadır.
Bir primorial kuvvetinde tam olarak \(m\) farklı asal bulunur ve hepsi aynı üs \(n\) ile gelir. Bu simetri hem bölen toplamını hem de \(2\)-adik değerlemeyi basit cebirsel ifadelere indirir.
\(N=(p_m\#)^n\) için her asalın üssü \(n\) olduğundan
$$\tau\!\left((p_m\#)^n\right)=(n+1)^m.$$
Her bölen, her asal için bağımsız olarak \(0\) ile \(n\) arasında bir üs seçilerek oluşur. Bu yüzden
$$\sum_{d \mid (p_m\#)^n}\tau(d)=\left(\sum_{k=0}^{n}(k+1)\right)^m=\left(\frac{(n+1)(n+2)}{2}\right)^m.$$
Bunu \(S\) tanımına koyunca
$$S\!\left((p_m\#)^n\right)=\left(\frac{(n+1)(n+2)}{2}\right)^m-(n+1)^m$$
elde edilir.
\(n=2k-1\) yazalım. O zaman \(n+1=2k\) ve \(n+2=2k+1\) olur; dolayısıyla
$$S\!\left((p_m\#)^{2k-1}\right)=\bigl(k(2k+1)\bigr)^m-(2k)^m=k^m\left((2k+1)^m-2^m\right).$$
Parantez içi ifade tektir; çünkü tek bir sayıdan çift bir sayı çıkarılmaktadır. Bu nedenle tüm \(2\)-adik değerleme yalnızca \(k^m\) çarpanından gelir:
$$E(m,2k-1)=m\,v_2(k)=m\,v_2\!\left(\frac{n+1}{2}\right).$$
\(n=2r\) yazalım. Böylece \(n+1=2r+1\) tek olur ve aynı özdeşlik
$$S\!\left((p_m\#)^{2r}\right)=\bigl((2r+1)(r+1)\bigr)^m-(2r+1)^m=(2r+1)^m\left((r+1)^m-1\right)$$
şeklini alır. Şimdi \(n\)'in \(4\)'e göre kalanı belirleyicidir.
\(r\) tekse \(n\equiv 2 \pmod 4\) olur. Bu durumda \(r+1\) çift olduğundan \((r+1)^m-1\) tektir ve
$$E(m,n)=0 \qquad \text{if } n\equiv 2 \pmod 4.$$
\(r=2t\) ise \(n=4t\) ve \(r+1=2t+1\) tektir. \(m=904961\) tek olduğu için
$$\begin{aligned} (2t+1)^m-1&=(2t)\left((2t+1)^{m-1}+(2t+1)^{m-2}+\cdots+1\right). \end{aligned}$$
Parantez içindeki toplam, tek sayıda tek terimin toplamı olduğu için tektir. Bu yüzden
$$E(m,4t)=v_2(2t)=1+v_2(t)=v_2(n)-1.$$
Sonuç olarak, bu tek \(m\) için
$$E(m,n)= \begin{cases} m\,v_2\!\left(\frac{n+1}{2}\right), & n \text{ odd},\\ 0, & n\equiv 2 \pmod 4,\\ v_2(n)-1, & 4\mid n. \end{cases}$$
Şimdi \(E(m,n)\) değerlerini \(1\) ile \(N\) arasında topluyoruz. \(n\equiv 2 \pmod 4\) sınıfı hiç katkı yapmaz; geriye yalnızca tek sayılar ve \(4\)'ün katları kalır.
Tek \(n\) için \(n=2k-1\) yazıp
$$K=\left\lfloor\frac{N+1}{2}\right\rfloor$$
tanımlarız. O halde
$$\sum_{\substack{1\le n\le N\\ n\text{ odd}}}E(m,n)=m\sum_{k=1}^{K}v_2(k)=m\,v_2(K!).$$
\(4\)'ün katları için \(n=4t\) yazıp
$$T=\left\lfloor\frac{N}{4}\right\rfloor$$
alırız. Bu durumda
$$\sum_{\substack{1\le n\le N\\ 4\mid n}}E(m,n)=\sum_{t=1}^{T}\bigl(1+v_2(t)\bigr)=T+v_2(T!).$$
Dolayısıyla toplam ifade
$$Q(m,N)=m\,v_2(K!)+T+v_2(T!)$$
olur.
\(2\) asalı için Legendre formülü
$$v_2(x!)=\sum_{j\ge 1}\left\lfloor\frac{x}{2^j}\right\rfloor=x-\operatorname{popcount}(x)$$
şeklindedir. Böylece son toplam doğrudan
$$Q(m,N)=m\left(K-\operatorname{popcount}(K)\right)+T+\left(T-\operatorname{popcount}(T)\right)$$
olarak hesaplanır. Artık \(N\)'ye kadar giden hiçbir döngü kalmaz.
Bu kontrol örneği elle doğrulanabilecek kadar küçüktür ama tüm mekanizmayı gösterir. Burada
$$K=\left\lfloor\frac{8+1}{2}\right\rfloor=4,\qquad T=\left\lfloor\frac{8}{4}\right\rfloor=2.$$
Legendre ile
$$v_2(4!)=4-\operatorname{popcount}(4)=4-1=3,\qquad v_2(2!)=2-\operatorname{popcount}(2)=2-1=1$$
elde edilir. Dolayısıyla
$$Q(m,8)=3m+3.$$
Gerçek problem parametresi \(m=904961\) için bu
$$Q(904961,8)=3\cdot 904961+3=2714886$$
değerini verir; bu da implementasyonların kullandığı kontrol sonucudur.
C++, Python ve Java implementasyonları \(1\)'den \(N\)'ye kadar ilerlemez. Bunun yerine yukarıdaki kapalı formu doğrudan tek problem girdisi \(m=904961\) için uygular.
Önce
$$K=\left\lfloor\frac{N+1}{2}\right\rfloor,\qquad T=\left\lfloor\frac{N}{4}\right\rfloor$$
hesaplanır, sonra \(v_2(K!)\) ve \(v_2(T!)\) değerleri \(x-\operatorname{popcount}(x)\) özdeşliğiyle bulunur ve en son
$$m\,v_2(K!)+T+v_2(T!)$$
oluşturulur. C++ implementasyonu ayrıca iki küçük doğrulama içerir: biri \(S(6)=5\) sonucunu, diğeri ise \(Q(904961,8)=2714886\) kontrolünü sınar. Son adımda \(N=10^{12}\) için tam ondalık sonuç yazdırılır.
Buradaki sabit boyutlu tamsayı girdileri için algoritma \(O(1)\) zamanda ve \(O(1)\) bellekte çalışır. Türetilen kapalı form sayesinde \(n\) üzerinde büyüyen hiçbir döngü yoktur; sadece birkaç bölme, bit sayma ve toplama işlemi yapılır.
Sea \(p_m\#=\prod_{i=1}^{m} p_i\) el primorial de los primeros \(m\) primos, sea \(\tau(n)\) la función que cuenta divisores, y definamos
$$S(N)=\sum_{d \mid N}\tau(d)-\tau(N),\qquad E(m,n)=v_2\!\left(S\!\left((p_m\#)^n\right)\right).$$
La cantidad pedida es la suma acumulada
$$Q(m,N)=\sum_{n=1}^{N}E(m,n).$$
En la instancia real del problema, \(m=904961\) y \(N=10^{12}\). Como ese \(m\) es impar y \(N\) es gigantesco, no se puede recorrer término a término; hay que obtener una expresión cerrada.
Una potencia de primorial tiene exactamente \(m\) factores primos distintos y todos aparecen con el mismo exponente \(n\). Esa regularidad permite reducir tanto la suma de divisores como la valoración \(2\)-ádica a unas pocas identidades elementales.
Si \(N=(p_m\#)^n\), cada uno de los \(m\) primos tiene exponente \(n\), de modo que
$$\tau\!\left((p_m\#)^n\right)=(n+1)^m.$$
Cada divisor se obtiene eligiendo de forma independiente un exponente entre \(0\) y \(n\) para cada primo. Por tanto,
$$\sum_{d \mid (p_m\#)^n}\tau(d)=\left(\sum_{k=0}^{n}(k+1)\right)^m=\left(\frac{(n+1)(n+2)}{2}\right)^m.$$
Al sustituir en la definición de \(S\), resulta
$$S\!\left((p_m\#)^n\right)=\left(\frac{(n+1)(n+2)}{2}\right)^m-(n+1)^m.$$
Escribamos \(n=2k-1\). Entonces \(n+1=2k\) y \(n+2=2k+1\), así que
$$S\!\left((p_m\#)^{2k-1}\right)=\bigl(k(2k+1)\bigr)^m-(2k)^m=k^m\left((2k+1)^m-2^m\right).$$
El factor entre paréntesis es impar, porque un número impar menos uno par sigue siendo impar. En consecuencia, toda la valoración \(2\)-ádica procede de \(k^m\):
$$E(m,2k-1)=m\,v_2(k)=m\,v_2\!\left(\frac{n+1}{2}\right).$$
Ahora escribamos \(n=2r\). Entonces \(n+1=2r+1\) es impar, y la misma identidad se reescribe como
$$S\!\left((p_m\#)^{2r}\right)=\bigl((2r+1)(r+1)\bigr)^m-(2r+1)^m=(2r+1)^m\left((r+1)^m-1\right).$$
Aquí importa la clase residual de \(n\) módulo \(4\).
Si \(r\) es impar, entonces \(n\equiv 2 \pmod 4\), luego \(r+1\) es par y \((r+1)^m-1\) es impar. Por tanto,
$$E(m,n)=0 \qquad \text{if } n\equiv 2 \pmod 4.$$
Si \(r=2t\), entonces \(n=4t\) y \(r+1=2t+1\) es impar. Como \(m=904961\) es impar, se tiene
$$\begin{aligned} (2t+1)^m-1&=(2t)\left((2t+1)^{m-1}+(2t+1)^{m-2}+\cdots+1\right). \end{aligned}$$
La suma entre paréntesis es impar porque contiene un número impar de términos impares. Así,
$$E(m,4t)=v_2(2t)=1+v_2(t)=v_2(n)-1.$$
Para este \(m\) impar queda la regla por casos
$$E(m,n)= \begin{cases} m\,v_2\!\left(\frac{n+1}{2}\right), & n \text{ odd},\\ 0, & n\equiv 2 \pmod 4,\\ v_2(n)-1, & 4\mid n. \end{cases}$$
Ahora sumamos \(E(m,n)\) desde \(1\) hasta \(N\). La clase \(n\equiv 2 \pmod 4\) no aporta nada, de modo que solo quedan los impares y los múltiplos de \(4\).
Para los impares, escribimos \(n=2k-1\) con
$$K=\left\lfloor\frac{N+1}{2}\right\rfloor.$$
Entonces
$$\sum_{\substack{1\le n\le N\\ n\text{ odd}}}E(m,n)=m\sum_{k=1}^{K}v_2(k)=m\,v_2(K!).$$
Para los múltiplos de \(4\), escribimos \(n=4t\) con
$$T=\left\lfloor\frac{N}{4}\right\rfloor.$$
Luego
$$\sum_{\substack{1\le n\le N\\ 4\mid n}}E(m,n)=\sum_{t=1}^{T}\bigl(1+v_2(t)\bigr)=T+v_2(T!).$$
Por tanto, toda la cantidad acumulada se reduce a
$$Q(m,N)=m\,v_2(K!)+T+v_2(T!).$$
Para el primo \(2\), la fórmula de Legendre dice
$$v_2(x!)=\sum_{j\ge 1}\left\lfloor\frac{x}{2^j}\right\rfloor=x-\operatorname{popcount}(x).$$
Eso convierte el resultado final en una cuenta directa:
$$Q(m,N)=m\left(K-\operatorname{popcount}(K)\right)+T+\left(T-\operatorname{popcount}(T)\right).$$
Después de esta reducción ya no queda ningún recorrido hasta \(N\).
Este punto de control es lo bastante pequeño para comprobarlo a mano y, al mismo tiempo, ya contiene toda la idea. Aquí
$$K=\left\lfloor\frac{8+1}{2}\right\rfloor=4,\qquad T=\left\lfloor\frac{8}{4}\right\rfloor=2.$$
Con Legendre obtenemos
$$v_2(4!)=4-\operatorname{popcount}(4)=4-1=3,\qquad v_2(2!)=2-\operatorname{popcount}(2)=2-1=1.$$
Así,
$$Q(m,8)=3m+3.$$
Para el valor real \(m=904961\), esto da
$$Q(904961,8)=3\cdot 904961+3=2714886,$$
que coincide exactamente con el punto de control de las implementaciones.
Las implementaciones en C++, Python y Java no iteran desde \(1\) hasta \(N\). Aplican directamente la fórmula cerrada anterior al valor impar \(m=904961\).
Cada implementación calcula
$$K=\left\lfloor\frac{N+1}{2}\right\rfloor,\qquad T=\left\lfloor\frac{N}{4}\right\rfloor,$$
evalúa \(v_2(K!)\) y \(v_2(T!)\) mediante la identidad \(x-\operatorname{popcount}(x)\), y finalmente forma
$$m\,v_2(K!)+T+v_2(T!).$$
La implementación en C++ añade además dos comprobaciones pequeñas: una verifica que \(S(6)=5\) y otra verifica el control \(Q(904961,8)=2714886\). Después se imprime la respuesta decimal exacta para \(N=10^{12}\).
Para las entradas de tamaño fijo usadas aquí, el algoritmo trabaja en tiempo \(O(1)\) y memoria \(O(1)\). La derivación elimina cualquier bucle proporcional a \(N\); solo quedan unas pocas divisiones enteras, recuentos de bits y sumas.
设 \(p_m\#=\prod_{i=1}^{m} p_i\) 表示前 \(m\) 个素数的 primorial，\(\tau(n)\) 表示约数个数函数，并定义
$$S(N)=\sum_{d \mid N}\tau(d)-\tau(N),\qquad E(m,n)=v_2\!\left(S\!\left((p_m\#)^n\right)\right).$$
题目要求计算累计量
$$Q(m,N)=\sum_{n=1}^{N}E(m,n).$$
实际参数是 \(m=904961\) 与 \(N=10^{12}\)。由于这个 \(m\) 是奇数，而 \(N\) 又大到不可能逐项枚举，解法必须先把表达式化成闭式，再一次性求值。
对于 \((p_m\#)^n\) 这种数，它的素因子结构极其整齐：恰好有 \(m\) 个不同素数，而且每个素数的指数都同样是 \(n\)。正是这个对称性，使得约数和与 \(2\)-进赋值都可以被压缩成很短的公式。
对 \(N=(p_m\#)^n\) 来说，每个素数的指数都是 \(n\)，因此
$$\tau\!\left((p_m\#)^n\right)=(n+1)^m.$$
任意一个约数都对应于：对这 \(m\) 个素数分别独立地选一个从 \(0\) 到 \(n\) 的指数。所以
$$\sum_{d \mid (p_m\#)^n}\tau(d)=\left(\sum_{k=0}^{n}(k+1)\right)^m=\left(\frac{(n+1)(n+2)}{2}\right)^m.$$
代回定义之后，就得到一个精确闭式：
$$S\!\left((p_m\#)^n\right)=\left(\frac{(n+1)(n+2)}{2}\right)^m-(n+1)^m.$$
后面的全部推导，都从这条式子出发。
令 \(n=2k-1\)。这时 \(n+1=2k\)，\(n+2=2k+1\)，于是
$$S\!\left((p_m\#)^{2k-1}\right)=\bigl(k(2k+1)\bigr)^m-(2k)^m=k^m\left((2k+1)^m-2^m\right).$$
括号中的 \((2k+1)^m-2^m\) 一定是奇数，因为奇数减偶数仍是奇数。因此 \(2\)-进赋值完全来自前面的 \(k^m\)：
$$E(m,2k-1)=m\,v_2(k)=m\,v_2\!\left(\frac{n+1}{2}\right).$$
也就是说，只要 \(n\) 为奇数，问题就退化成“\((n+1)/2\) 中含有多少个因子 \(2\)”这一件事。
再令 \(n=2r\)。此时 \(n+1=2r+1\) 是奇数，同样的闭式可以改写为
$$S\!\left((p_m\#)^{2r}\right)=\bigl((2r+1)(r+1)\bigr)^m-(2r+1)^m=(2r+1)^m\left((r+1)^m-1\right).$$
这里真正需要分析的是 \((r+1)^m-1\) 的 \(2\)-进赋值，而结论取决于 \(n\) 对 \(4\) 的余数。
如果 \(r\) 是奇数，那么 \(n\equiv 2 \pmod 4\)。这时 \(r+1\) 是偶数，于是 \((r+1)^m\) 为偶数，\((r+1)^m-1\) 就是奇数，所以
$$E(m,n)=0 \qquad \text{if } n\equiv 2 \pmod 4.$$
如果 \(r=2t\)，那么 \(n=4t\)，并且 \(r+1=2t+1\) 是奇数。由于实际问题中的 \(m=904961\) 本身也是奇数，可以写出
$$\begin{aligned} (2t+1)^m-1&=(2t)\left((2t+1)^{m-1}+(2t+1)^{m-2}+\cdots+1\right). \end{aligned}$$
括号里是 \(m\) 个奇数的和，而 \(m\) 又是奇数，因此整个括号仍然是奇数。于是所有的 \(2\)-进因子只来自最前面的 \(2t\)，从而
$$E(m,4t)=v_2(2t)=1+v_2(t)=v_2(n)-1.$$
把三种情况合并起来，对于这个奇数 \(m\) 就得到
$$E(m,n)= \begin{cases} m\,v_2\!\left(\frac{n+1}{2}\right), & n \text{ odd},\\ 0, & n\equiv 2 \pmod 4,\\ v_2(n)-1, & 4\mid n. \end{cases}$$
接下来要求的是
$$Q(m,N)=\sum_{n=1}^{N}E(m,n).$$
其中第二类 \(n\equiv 2 \pmod 4\) 的项全部为零，所以实际上只需处理奇数项与 \(4\) 的倍数项。
对奇数项，写 \(n=2k-1\)，其中
$$K=\left\lfloor\frac{N+1}{2}\right\rfloor.$$
于是
$$\sum_{\substack{1\le n\le N\\ n\text{ odd}}}E(m,n)=m\sum_{k=1}^{K}v_2(k)=m\,v_2(K!).$$
这里用到的事实是：从 \(1\) 到 \(K\) 所有整数的 \(2\)-进赋值之和，恰好就是 \(K!\) 的 \(2\)-进赋值。
对 \(4\) 的倍数项，写 \(n=4t\)，其中
$$T=\left\lfloor\frac{N}{4}\right\rfloor.$$
这部分的和变成
$$\sum_{\substack{1\le n\le N\\ 4\mid n}}E(m,n)=\sum_{t=1}^{T}\bigl(1+v_2(t)\bigr)=T+v_2(T!).$$
因此整个题目最终压缩成
$$Q(m,N)=m\,v_2(K!)+T+v_2(T!).$$
对素数 \(2\)，Legendre 公式给出
$$v_2(x!)=\sum_{j\ge 1}\left\lfloor\frac{x}{2^j}\right\rfloor=x-\operatorname{popcount}(x).$$
这里的 \(\operatorname{popcount}(x)\) 表示 \(x\) 的二进制表示中 \(1\) 的个数。代入之后，最后公式直接变成
$$Q(m,N)=m\left(K-\operatorname{popcount}(K)\right)+T+\left(T-\operatorname{popcount}(T)\right).$$
也就是说，整个答案只依赖于两次整除、两次 bit count，再做若干次整数加减乘。原本看似要累计到 \(10^{12}\) 的问题，已经完全不需要遍历。
这个检查点既足够小，可以手算验证；又足够完整，能把公式的工作方式展示清楚。此时
$$K=\left\lfloor\frac{8+1}{2}\right\rfloor=4,\qquad T=\left\lfloor\frac{8}{4}\right\rfloor=2.$$
根据 Legendre 公式，
$$v_2(4!)=4-\operatorname{popcount}(4)=4-1=3,\qquad v_2(2!)=2-\operatorname{popcount}(2)=2-1=1.$$
于是
$$Q(m,8)=3m+3.$$
对题目里的实际参数 \(m=904961\)，马上得到
$$Q(904961,8)=3\cdot 904961+3=2714886,$$
这与实现中使用的校验值完全一致。
C++、Python 和 Java 实现都不会从 \(1\) 一直循环到 \(N\)。它们直接使用上面推导出的闭式，并代入题目的奇数参数 \(m=904961\)。
实现首先计算
$$K=\left\lfloor\frac{N+1}{2}\right\rfloor,\qquad T=\left\lfloor\frac{N}{4}\right\rfloor,$$
然后利用 \(x-\operatorname{popcount}(x)\) 这一恒等式求出 \(v_2(K!)\) 与 \(v_2(T!)\)，最后组合成
$$m\,v_2(K!)+T+v_2(T!).$$
C++ 实现还额外放了两个很小的自检：一个确认 \(S(6)=5\)，另一个确认检查点 \(Q(904961,8)=2714886\)。通过这些检查后，程序直接输出 \(N=10^{12}\) 时的十进制精确结果。
对这里使用的固定大小整数输入而言，算法的时间复杂度是 \(O(1)\)，空间复杂度也是 \(O(1)\)。推导已经把所有随 \(N\) 增长的循环都消掉了，剩下的只有少量整数运算和 bit count。
Пусть \(p_m\#=\prod_{i=1}^{m} p_i\) обозначает примориал первых \(m\) простых чисел, \(\tau(n)\) обозначает функцию числа делителей, а
$$S(N)=\sum_{d \mid N}\tau(d)-\tau(N),\qquad E(m,n)=v_2\!\left(S\!\left((p_m\#)^n\right)\right).$$
Требуется вычислить накопленную сумму
$$Q(m,N)=\sum_{n=1}^{N}E(m,n).$$
В реальном экземпляре задачи \(m=904961\) и \(N=10^{12}\). Поскольку это \(m\) нечётно, а \(N\) слишком велико для прямого перебора, решение обязано свести всё к закрытой формуле.
У степени примориала очень регулярная структура: в разложении участвуют ровно \(m\) различных простых, и каждый входит с одинаковой степенью \(n\). Именно эта симметрия позволяет превратить исходную сумму по делителям и \(2\)-адическую оценку в короткое вычисление.
Для \(N=(p_m\#)^n\) каждая из \(m\) простых имеет показатель \(n\), поэтому
$$\tau\!\left((p_m\#)^n\right)=(n+1)^m.$$
Любой делитель получается независимым выбором показателя от \(0\) до \(n\) для каждого простого. Следовательно,
$$\sum_{d \mid (p_m\#)^n}\tau(d)=\left(\sum_{k=0}^{n}(k+1)\right)^m=\left(\frac{(n+1)(n+2)}{2}\right)^m.$$
Подстановка в определение \(S\) даёт точную формулу
$$S\!\left((p_m\#)^n\right)=\left(\frac{(n+1)(n+2)}{2}\right)^m-(n+1)^m.$$
Положим \(n=2k-1\). Тогда \(n+1=2k\), \(n+2=2k+1\), и потому
$$S\!\left((p_m\#)^{2k-1}\right)=\bigl(k(2k+1)\bigr)^m-(2k)^m=k^m\left((2k+1)^m-2^m\right).$$
Выражение в скобках нечётно, потому что нечётное число минус чётное остаётся нечётным. Значит, вся \(2\)-адическая оценка определяется только множителем \(k^m\):
$$E(m,2k-1)=m\,v_2(k)=m\,v_2\!\left(\frac{n+1}{2}\right).$$
Положим теперь \(n=2r\). Тогда \(n+1=2r+1\) нечётно, и та же формула переписывается так:
$$S\!\left((p_m\#)^{2r}\right)=\bigl((2r+1)(r+1)\bigr)^m-(2r+1)^m=(2r+1)^m\left((r+1)^m-1\right).$$
Дальше всё зависит от остатка \(n\) по модулю \(4\).
Если \(r\) нечётно, то \(n\equiv 2 \pmod 4\), а \(r+1\) чётно. Тогда \((r+1)^m-1\) нечётно, и потому
$$E(m,n)=0 \qquad \text{if } n\equiv 2 \pmod 4.$$
Если же \(r=2t\), то \(n=4t\), а \(r+1=2t+1\) нечётно. Поскольку \(m=904961\) нечётно, имеем
$$\begin{aligned} (2t+1)^m-1&=(2t)\left((2t+1)^{m-1}+(2t+1)^{m-2}+\cdots+1\right). \end{aligned}$$
Сумма в скобках нечётна: это сумма нечётного числа нечётных слагаемых. Следовательно,
$$E(m,4t)=v_2(2t)=1+v_2(t)=v_2(n)-1.$$
Итак, для данного нечётного \(m\) получаем правило
$$E(m,n)= \begin{cases} m\,v_2\!\left(\frac{n+1}{2}\right), & n \text{ odd},\\ 0, & n\equiv 2 \pmod 4,\\ v_2(n)-1, & 4\mid n. \end{cases}$$
Теперь осталось вычислить
$$Q(m,N)=\sum_{n=1}^{N}E(m,n).$$
Класс \(n\equiv 2 \pmod 4\) даёт нулевой вклад, поэтому нужно суммировать только по нечётным \(n\) и по кратным \(4\).
Для нечётных \(n\) пишем \(n=2k-1\) и вводим
$$K=\left\lfloor\frac{N+1}{2}\right\rfloor.$$
Тогда
$$\sum_{\substack{1\le n\le N\\ n\text{ odd}}}E(m,n)=m\sum_{k=1}^{K}v_2(k)=m\,v_2(K!).$$
Для кратных \(4\) пишем \(n=4t\) и вводим
$$T=\left\lfloor\frac{N}{4}\right\rfloor.$$
После этого получаем
$$\sum_{\substack{1\le n\le N\\ 4\mid n}}E(m,n)=\sum_{t=1}^{T}\bigl(1+v_2(t)\bigr)=T+v_2(T!).$$
Значит, всё выражение сводится к формуле
$$Q(m,N)=m\,v_2(K!)+T+v_2(T!).$$
Для простого \(2\) формула Лежандра имеет вид
$$v_2(x!)=\sum_{j\ge 1}\left\lfloor\frac{x}{2^j}\right\rfloor=x-\operatorname{popcount}(x).$$
Здесь \(\operatorname{popcount}(x)\) означает число единиц в двоичной записи \(x\). После подстановки финальная формула становится совсем короткой:
$$Q(m,N)=m\left(K-\operatorname{popcount}(K)\right)+T+\left(T-\operatorname{popcount}(T)\right).$$
Таким образом, в решении не остаётся ни одного цикла длины \(N\).
Этот контрольный пример достаточно мал для ручной проверки и одновременно полностью отражает общий метод. Здесь
$$K=\left\lfloor\frac{8+1}{2}\right\rfloor=4,\qquad T=\left\lfloor\frac{8}{4}\right\rfloor=2.$$
По формуле Лежандра
$$v_2(4!)=4-\operatorname{popcount}(4)=4-1=3,\qquad v_2(2!)=2-\operatorname{popcount}(2)=2-1=1.$$
Следовательно,
$$Q(m,8)=3m+3.$$
Для реального параметра \(m=904961\) отсюда сразу получается
$$Q(904961,8)=3\cdot 904961+3=2714886,$$
что в точности совпадает с контрольным значением в реализациях.
Реализации на C++, Python и Java не перебирают все \(n\) от \(1\) до \(N\). Вместо этого они напрямую применяют выведенную выше закрытую формулу к нечётному параметру \(m=904961\).
Сначала вычисляются
$$K=\left\lfloor\frac{N+1}{2}\right\rfloor,\qquad T=\left\lfloor\frac{N}{4}\right\rfloor,$$
затем по тождеству \(x-\operatorname{popcount}(x)\) находятся \(v_2(K!)\) и \(v_2(T!)\), после чего собирается выражение
$$m\,v_2(K!)+T+v_2(T!).$$
В варианте на C++ дополнительно есть две маленькие проверки: одна подтверждает, что \(S(6)=5\), а другая подтверждает контрольную сумму \(Q(904961,8)=2714886\). Затем программа печатает точный десятичный ответ для \(N=10^{12}\).
Для входов фиксированного машинного размера алгоритм работает за \(O(1)\) времени и использует \(O(1)\) памяти. Все зависимости от величины \(N\) устранены на уровне формул; остаётся лишь несколько целочисленных делений, подсчётов битов и сложений.
ليكن \(p_m\#=\prod_{i=1}^{m} p_i\) هو primorial الخاص بأول \(m\) من الأعداد الأولية، ولتكن \(\tau(n)\) دالة عدد القواسم، ولنعرّف
$$S(N)=\sum_{d \mid N}\tau(d)-\tau(N),\qquad E(m,n)=v_2\!\left(S\!\left((p_m\#)^n\right)\right).$$
والكمية المطلوبة هي المجموع التراكمي
$$Q(m,N)=\sum_{n=1}^{N}E(m,n).$$
في مسألة Project Euler نفسها نأخذ \(m=904961\) و\(N=10^{12}\). وبما أنّ هذا \(m\) فردي وأن \(N\) ضخم جدًا، فلا يمكن الحساب حدًا حدًا، بل يجب اشتقاق صيغة مغلقة مباشرة.
قوة الـ primorial تمتلك بنية منتظمة جدًا: يوجد بالضبط \(m\) عوامل أولية مختلفة، وكل واحد منها يظهر بالأس نفسه \(n\). هذه المنتظمة هي التي تجعل مجموع القواسم والتقييم \(2\)-الأدّي ينهاران إلى حسابات بسيطة.
عندما يكون \(N=(p_m\#)^n\)، فإن كل واحد من العوامل الأولية \(m\) له الأس \(n\)، ولذلك
$$\tau\!\left((p_m\#)^n\right)=(n+1)^m.$$
وكل قاسم ينتج من اختيار أس بين \(0\) و\(n\) لكل عامل أولي بشكل مستقل. إذًا
$$\sum_{d \mid (p_m\#)^n}\tau(d)=\left(\sum_{k=0}^{n}(k+1)\right)^m=\left(\frac{(n+1)(n+2)}{2}\right)^m.$$
وبالتعويض في تعريف \(S\) نحصل على
$$S\!\left((p_m\#)^n\right)=\left(\frac{(n+1)(n+2)}{2}\right)^m-(n+1)^m.$$
اكتب \(n=2k-1\). عندها \(n+1=2k\) و\(n+2=2k+1\)، ومن ثم
$$S\!\left((p_m\#)^{2k-1}\right)=\bigl(k(2k+1)\bigr)^m-(2k)^m=k^m\left((2k+1)^m-2^m\right).$$
العامل بين القوسين فردي، لأن عددًا فرديًا ناقص عدد زوجي يبقى فرديًا. لذلك فإن كل التقييم \(2\)-الأدّي يأتي فقط من \(k^m\):
$$E(m,2k-1)=m\,v_2(k)=m\,v_2\!\left(\frac{n+1}{2}\right).$$
اكتب \(n=2r\). عندها يكون \(n+1=2r+1\) عددًا فرديًا، وتصبح الصيغة نفسها
$$S\!\left((p_m\#)^{2r}\right)=\bigl((2r+1)(r+1)\bigr)^m-(2r+1)^m=(2r+1)^m\left((r+1)^m-1\right).$$
وهنا تتحدد النتيجة بحسب باقي \(n\) modulo \(4\).
إذا كان \(r\) فرديًا، فلدينا \(n\equiv 2 \pmod 4\)، وعندها يكون \(r+1\) زوجيًا، وبالتالي \((r+1)^m-1\) عددًا فرديًا. لذلك
$$E(m,n)=0 \qquad \text{if } n\equiv 2 \pmod 4.$$
أما إذا كان \(r=2t\)، فحينئذ \(n=4t\) و\(r+1=2t+1\) فردي. وبما أن \(m=904961\) فردي أيضًا، يمكن كتابة
$$\begin{aligned} (2t+1)^m-1&=(2t)\left((2t+1)^{m-1}+(2t+1)^{m-2}+\cdots+1\right). \end{aligned}$$
المجموع داخل القوس فردي لأنه مجموع عدد فردي من الحدود الفردية. ومن ثم
$$E(m,4t)=v_2(2t)=1+v_2(t)=v_2(n)-1.$$
وبجمع الحالات الثلاث نحصل، لهذا \(m\) الفردي، على القاعدة
$$E(m,n)= \begin{cases} m\,v_2\!\left(\frac{n+1}{2}\right), & n \text{ odd},\\ 0, & n\equiv 2 \pmod 4,\\ v_2(n)-1, & 4\mid n. \end{cases}$$
الآن نريد حساب
$$Q(m,N)=\sum_{n=1}^{N}E(m,n).$$
الفئة \(n\equiv 2 \pmod 4\) لا تضيف شيئًا، لذا لا يبقى إلا الأعداد الفردية ومضاعفات \(4\).
للأعداد الفردية نكتب \(n=2k-1\)، ونأخذ
$$K=\left\lfloor\frac{N+1}{2}\right\rfloor.$$
وعندها
$$\sum_{\substack{1\le n\le N\\ n\text{ odd}}}E(m,n)=m\sum_{k=1}^{K}v_2(k)=m\,v_2(K!).$$
ولمضاعفات \(4\) نكتب \(n=4t\)، ونأخذ
$$T=\left\lfloor\frac{N}{4}\right\rfloor.$$
فنحصل على
$$\sum_{\substack{1\le n\le N\\ 4\mid n}}E(m,n)=\sum_{t=1}^{T}\bigl(1+v_2(t)\bigr)=T+v_2(T!).$$
إذًا تختزل المسألة كلها إلى
$$Q(m,N)=m\,v_2(K!)+T+v_2(T!).$$
صيغة Legendre للعدد الأولي \(2\) تقول
$$v_2(x!)=\sum_{j\ge 1}\left\lfloor\frac{x}{2^j}\right\rfloor=x-\operatorname{popcount}(x).$$
وهنا \(\operatorname{popcount}(x)\) هو عدد الواحدات في التمثيل الثنائي لـ \(x\). بالتعويض نحصل على الصيغة النهائية المباشرة
$$Q(m,N)=m\left(K-\operatorname{popcount}(K)\right)+T+\left(T-\operatorname{popcount}(T)\right).$$
وبذلك تختفي تمامًا أي دورة تمتد حتى \(N\).
هذا المثال صغير بما يكفي للتحقق اليدوي، وفي الوقت نفسه يوضح الآلية كاملة. لدينا
$$K=\left\lfloor\frac{8+1}{2}\right\rfloor=4,\qquad T=\left\lfloor\frac{8}{4}\right\rfloor=2.$$
وباستخدام Legendre،
$$v_2(4!)=4-\operatorname{popcount}(4)=4-1=3,\qquad v_2(2!)=2-\operatorname{popcount}(2)=2-1=1.$$
إذن
$$Q(m,8)=3m+3.$$
وبالنسبة إلى معامل المسألة الفعلي \(m=904961\)، نحصل على
$$Q(904961,8)=3\cdot 904961+3=2714886,$$
وهو بالضبط نفس مقدار التحقق الموجود في التنفيذات.
تنفيذات C++ وPython وJava لا تسير على كل \(n\) من \(1\) إلى \(N\). بدلًا من ذلك، تطبّق مباشرة الصيغة المغلقة السابقة على القيمة الفردية \(m=904961\).
تحسب كل نسخة أولًا
$$K=\left\lfloor\frac{N+1}{2}\right\rfloor,\qquad T=\left\lfloor\frac{N}{4}\right\rfloor,$$
ثم تحسب \(v_2(K!)\) و\(v_2(T!)\) عبر الهوية \(x-\operatorname{popcount}(x)\)، وبعد ذلك تكوّن
$$m\,v_2(K!)+T+v_2(T!).$$
كما أن نسخة C++ تتضمن تحققين صغيرين: أحدهما يثبت أن \(S(6)=5\)، والآخر يثبت نقطة الفحص \(Q(904961,8)=2714886\). وبعد ذلك تُطبع الإجابة العشرية الدقيقة عند \(N=10^{12}\).
بالنسبة إلى المدخلات ذات الحجم الثابت المستخدمة هنا، تعمل الخوارزمية بزمن \(O(1)\) وذاكرة \(O(1)\). الاشتقاق أزال كل حلقة تعتمد على \(N\)، ولم يبق إلا عدد قليل من عمليات القسمة الصحيحة، وعدّ البتات، والجمع.