For each integer \(n\ge 1\), define
$$F(n)=\max_{0\le m\le n} v_2\binom{n}{m},$$
where \(v_2(x)\) is the exponent of 2 in the factorization of \(x\). The required quantity is
$$S(N)=\sum_{n=1}^{N}F(n).$$
A direct search over all binomial coefficients is far too slow when \(N\) is huge, so the solution replaces the optimization over \(m\) by a binary carry argument and then sums entire dyadic blocks at once.
Let \(s_2(x)\) be the number of 1-bits in the binary expansion of \(x\). For the prime \(2\), Kummer's theorem gives
$$v_2\binom{n}{m}=s_2(m)+s_2(n-m)-s_2(n),$$
which is also the number of carries produced when \(m\) and \(n-m\) are added in base 2. Therefore \(F(n)\) is the largest carry count obtainable by writing \(n\) as a sum of two nonnegative integers.
Fix \(n\ge 1\) and write
$$k=\lfloor\log_2 n\rfloor,$$
so \(2^k\le n<2^{k+1}\). Also define
$$r=v_2(n+1).$$
The number \(r\) is exactly the number of trailing 1s in the binary expansion of \(n\). When we add \(m\) and \(n-m\), no carry can start in those lowest \(r\) positions. At bit 0 there is no incoming carry, and at any bit whose output digit is 1, a carry-out is only possible if a carry-in already existed. By induction, the entire trailing block of 1s is carry-free.
That leaves only the positions \(r,r+1,\dots,k-1\), so
$$F(n)\le k-\min(r,k).$$
If \(n=2^{k+1}-1\), then \(r=k+1\) and this upper bound already says \(F(n)\le 0\), hence \(F(n)=0\).
Assume now that \(n\neq 2^{k+1}-1\), so \(r\le k\). Choose
$$m=2^k-1.$$
This number has its lower \(k\) bits equal to 1, and
$$n-m=n+1-2^k.$$
In binary subtraction, subtracting \(2^k-1\) from \(n\) forces a borrow to start exactly at the first 0 above the trailing block of \(r\) ones, and that borrow propagates through every higher position up to bit \(k-1\). So the number of borrows, and equivalently the number of carries in the matching addition, is exactly \(k-r\).
The same conclusion follows from the digit-sum identity:
$$\begin{aligned} v_2\binom{n}{2^k-1} &=s_2(2^k-1)+s_2(n+1-2^k)-s_2(n)\\ &=k+\bigl(s_2(n)-r\bigr)-s_2(n)=k-r. \end{aligned}$$
Combining this construction with the upper bound gives the exact closed form
$$\boxed{F(n)=k-\min\bigl(v_2(n+1),k\bigr).}$$
Now consider one full block
$$n\in[2^k,2^{k+1}-1].$$
Set \(x=n+1\), so \(x\in[2^k+1,2^{k+1}]\). Then
$$F(n)=k-\min(v_2(x),k).$$
Therefore
$$\sum_{n=2^k}^{2^{k+1}-1}F(n)=k2^k-\sum_{x=2^k+1}^{2^{k+1}}\min(v_2(x),k).$$
Use the standard valuation-counting identity
$$\sum_{x=A}^{B}\min(v_2(x),k)=\sum_{t=1}^{k}\#\{x\in[A,B]:2^t\mid x\}.$$
Inside \([2^k+1,2^{k+1}]\), the number of multiples of \(2^t\) is exactly \(2^{k-t}\). Hence
$$\sum_{x=2^k+1}^{2^{k+1}}\min(v_2(x),k)=\sum_{t=1}^{k}2^{k-t}=2^k-1,$$
and the block total becomes
$$\boxed{\sum_{n=2^k}^{2^{k+1}-1}F(n)=(k-1)2^k+1.}$$
Let
$$K=\lfloor\log_2 N\rfloor.$$
All blocks with indices \(1,2,\dots,K-1\) are complete. The last block is
$$n\in[2^K,N],$$
whose length is
$$M=N-2^K+1.$$
Again put \(x=n+1\), so \(x\in[2^K+1,N+1]\). Then
$$\sum_{n=2^K}^{N}F(n)=KM-\sum_{x=2^K+1}^{N+1}\min(v_2(x),K).$$
Counting multiples of \(2^t\) gives
$$\sum_{x=2^K+1}^{N+1}\min(v_2(x),K)=\sum_{t=1}^{K}\left(\left\lfloor\frac{N+1}{2^t}\right\rfloor-\left\lfloor\frac{2^K}{2^t}\right\rfloor\right).$$
Since \(\left\lfloor 2^K/2^t\right\rfloor=2^{K-t}\) for \(1\le t\le K\), we obtain the exact formula
$$\boxed{S(N)=\sum_{k=1}^{K-1}\bigl((k-1)2^k+1\bigr)+K(N-2^K+1)-\sum_{t=1}^{K}\left(\left\lfloor\frac{N+1}{2^t}\right\rfloor-2^{K-t}\right).}$$
No approximation is involved; every term comes from exact carry counting.
Here \(K=6\) because \(64\le 100<128\). The complete blocks are \(k=1\) through \(5\), so their contributions are
$$\begin{aligned} k=1&:&&(1-1)2^1+1=1,\\ k=2&:&&(2-1)2^2+1=5,\\ k=3&:&&(3-1)2^3+1=17,\\ k=4&:&&(4-1)2^4+1=49,\\ k=5&:&&(5-1)2^5+1=129. \end{aligned}$$
These add up to \(201\).
The final partial block is \(n\in[64,100]\), so \(M=37\) and \(x\in[65,101]\). In that interval, the counts of multiples of powers of 2 are
$$\begin{aligned} 2^1&:&&18,\\ 2^2&:&&9,\\ 2^3&:&&4,\\ 2^4&:&&2,\\ 2^5&:&&1,\\ 2^6&:&&0. \end{aligned}$$
So
$$\sum_{x=65}^{101}\min(v_2(x),6)=18+9+4+2+1=34,$$
and the tail contributes
$$6\cdot 37-34=188.$$
Therefore
$$S(100)=201+188=389,$$
which matches the check used by the implementation.
The C++, Python, and Java implementations all follow the same structure. First they determine the index \(K\) of the highest set bit of \(N\). Then they sum every complete dyadic block with the closed formula \((k-1)2^k+1\).
After that, they process the last partial block \([2^K,N]\). Instead of evaluating \(F(n)\) one by one, the implementation counts how many numbers in \(x\in[2^K+1,N+1]\) are divisible by \(2,4,8,\dots,2^K\). The sum of those counts is exactly \(\sum \min(v_2(x),K)\), so subtracting it from \(K(N-2^K+1)\) yields the remaining contribution.
The arithmetic is exact in all three languages. Python uses arbitrary-precision integers automatically, Java uses arbitrary-precision arithmetic for the final accumulation, and the C++ version uses a wide integer accumulator for the same purpose.
Let \(K=\lfloor\log_2 N\rfloor\). The complete-block summation takes \(K-1\) iterations, and the valuation-counting loop for the tail takes \(K\) more. So the total running time is
$$O(\log N),$$
and the extra memory usage is
$$O(1).$$
Für jedes \(n\ge 1\) definieren wir
$$F(n)=\max_{0\le m\le n} v_2\binom{n}{m},$$
wobei \(v_2(x)\) den Exponenten von 2 in der Primfaktorzerlegung von \(x\) bezeichnet. Gesucht ist
$$S(N)=\sum_{n=1}^{N}F(n).$$
Ein direktes Durchprobieren aller Binomialkoeffizienten ist für große Werte von \(N\) unbrauchbar. Deshalb übersetzt die Lösung das Optimierungsproblem in eine Aussage über binäre Überträge und summiert anschließend ganze Zweierpotenz-Blöcke in geschlossener Form.
Sei \(s_2(x)\) die Anzahl der Einsen in der Binärdarstellung von \(x\). Für die Primzahl \(2\) liefert der Satz von Kummer
$$v_2\binom{n}{m}=s_2(m)+s_2(n-m)-s_2(n),$$
also genau die Anzahl der Überträge beim Addieren von \(m\) und \(n-m\) im Binärsystem. Damit ist \(F(n)\) die größtmögliche Übertragszahl unter allen Zerlegungen \(n=m+(n-m)\).
Fixiere \(n\ge 1\) und setze
$$k=\lfloor\log_2 n\rfloor,$$
also \(2^k\le n<2^{k+1}\). Weiter definieren wir
$$r=v_2(n+1).$$
Die Zahl \(r\) ist genau die Anzahl der abschließenden Einsen in der Binärdarstellung von \(n\). In diesen untersten \(r\) Positionen kann kein Übertrag neu entstehen. Am Bit 0 gibt es keinen eingehenden Übertrag, und an einer Stelle mit Ausgabebit 1 kann ein ausgehender Übertrag nur auftreten, wenn bereits ein eingehender Übertrag vorhanden ist. Induktiv bleibt also der gesamte Endblock aus Einsen übertragsfrei.
Damit bleiben nur die Positionen \(r,r+1,\dots,k-1\). Also gilt
$$F(n)\le k-\min(r,k).$$
Im Sonderfall \(n=2^{k+1}-1\) ist \(r=k+1\), und daraus folgt sofort \(F(n)=0\).
Nehmen wir nun \(n\neq 2^{k+1}-1\) an, also \(r\le k\). Wähle
$$m=2^k-1.$$
Dann sind die unteren \(k\) Bits von \(m\) alle gleich 1 und
$$n-m=n+1-2^k.$$
Bei der binären Subtraktion von \(2^k-1\) von \(n\) beginnt ein Borrow genau am ersten 0-Bit oberhalb des Endblocks aus \(r\) Einsen und propagiert dann durch jede höhere Position bis Bit \(k-1\). Die Anzahl der Borrows, und damit äquivalent die Anzahl der Überträge in der zugehörigen Addition, ist also genau \(k-r\).
Dasselbe sieht man auch direkt über die Ziffernsummenformel:
$$\begin{aligned} v_2\binom{n}{2^k-1} &=s_2(2^k-1)+s_2(n+1-2^k)-s_2(n)\\ &=k+\bigl(s_2(n)-r\bigr)-s_2(n)=k-r. \end{aligned}$$
Zusammen mit der oberen Schranke ergibt das die exakte geschlossene Form
$$\boxed{F(n)=k-\min\bigl(v_2(n+1),k\bigr).}$$
Betrachte nun den vollständigen Block
$$n\in[2^k,2^{k+1}-1].$$
Setze \(x=n+1\), also \(x\in[2^k+1,2^{k+1}]\). Dann gilt
$$F(n)=k-\min(v_2(x),k).$$
Daher ist
$$\sum_{n=2^k}^{2^{k+1}-1}F(n)=k2^k-\sum_{x=2^k+1}^{2^{k+1}}\min(v_2(x),k).$$
Verwende nun die Standardidentität
$$\sum_{x=A}^{B}\min(v_2(x),k)=\sum_{t=1}^{k}\#\{x\in[A,B]:2^t\mid x\}.$$
Im Intervall \([2^k+1,2^{k+1}]\) gibt es genau \(2^{k-t}\) Vielfache von \(2^t\). Also
$$\sum_{x=2^k+1}^{2^{k+1}}\min(v_2(x),k)=\sum_{t=1}^{k}2^{k-t}=2^k-1,$$
und damit folgt für den Block
$$\boxed{\sum_{n=2^k}^{2^{k+1}-1}F(n)=(k-1)2^k+1.}$$
Sei
$$K=\lfloor\log_2 N\rfloor.$$
Die Blöcke mit Indizes \(1,2,\dots,K-1\) sind vollständig, der letzte Block ist
$$n\in[2^K,N]$$
mit Länge
$$M=N-2^K+1.$$
Wieder setzen wir \(x=n+1\), also \(x\in[2^K+1,N+1]\). Dann
$$\sum_{n=2^K}^{N}F(n)=KM-\sum_{x=2^K+1}^{N+1}\min(v_2(x),K).$$
Das Zählen der Vielfachen von \(2^t\) liefert
$$\sum_{x=2^K+1}^{N+1}\min(v_2(x),K)=\sum_{t=1}^{K}\left(\left\lfloor\frac{N+1}{2^t}\right\rfloor-\left\lfloor\frac{2^K}{2^t}\right\rfloor\right).$$
Wegen \(\left\lfloor 2^K/2^t\right\rfloor=2^{K-t}\) für \(1\le t\le K\) erhalten wir die exakte Summenformel
$$\boxed{S(N)=\sum_{k=1}^{K-1}\bigl((k-1)2^k+1\bigr)+K(N-2^K+1)-\sum_{t=1}^{K}\left(\left\lfloor\frac{N+1}{2^t}\right\rfloor-2^{K-t}\right).}$$
Die Methode ist also vollständig exakt und verwendet nur elementare binäre Zählargumente.
Hier ist \(K=6\), denn \(64\le 100<128\). Die vollständigen Blöcke sind \(k=1\) bis \(5\), also
$$\begin{aligned} k=1&:&&(1-1)2^1+1=1,\\ k=2&:&&(2-1)2^2+1=5,\\ k=3&:&&(3-1)2^3+1=17,\\ k=4&:&&(4-1)2^4+1=49,\\ k=5&:&&(5-1)2^5+1=129. \end{aligned}$$
Das ergibt zusammen \(201\).
Der letzte Teilblock ist \(n\in[64,100]\), also \(M=37\) und \(x\in[65,101]\). In diesem Intervall gibt es so viele Vielfache von Zweierpotenzen:
$$\begin{aligned} 2^1&:&&18,\\ 2^2&:&&9,\\ 2^3&:&&4,\\ 2^4&:&&2,\\ 2^5&:&&1,\\ 2^6&:&&0. \end{aligned}$$
Somit
$$\sum_{x=65}^{101}\min(v_2(x),6)=18+9+4+2+1=34,$$
und der Restblock trägt
$$6\cdot 37-34=188$$
bei. Also insgesamt
$$S(100)=201+188=389,$$
genau der Kontrollwert der Implementierung.
Die C++-, Python- und Java-Implementierungen setzen diese Formel direkt um. Zuerst bestimmen sie das höchstwertige gesetzte Bit von \(N\) und damit den Index \(K\) des letzten Zweierblocks. Danach werden alle vollständigen Blöcke mit der geschlossenen Formel \((k-1)2^k+1\) aufsummiert.
Anschließend verarbeitet die Implementierung den letzten Teilblock \([2^K,N]\). Statt \(F(n)\) einzeln zu berechnen, zählt sie, wie viele Zahlen im Bereich \(x\in[2^K+1,N+1]\) durch \(2,4,8,\dots,2^K\) teilbar sind. Die Summe dieser Häufigkeiten ist genau \(\sum \min(v_2(x),K)\), und damit erhält man den Restbeitrag durch eine einzige weitere Schleife.
Die Rechenschritte sind in allen drei Sprachen identisch. Python verwendet automatisch beliebig große Ganzzahlen, Java nutzt Präzisionsarithmetik für die Akkumulation, und die C++-Variante verwendet dafür einen breiten Integer-Typ.
Mit \(K=\lfloor\log_2 N\rfloor\) benötigt die Summe über die vollständigen Blöcke \(K-1\) Iterationen, und die Auswertung des letzten Blocks benötigt weitere \(K\) Iterationen. Insgesamt ist die Laufzeit daher
$$O(\log N),$$
bei einem zusätzlichen Speicherverbrauch von
$$O(1).$$
Her \(n\ge 1\) için
$$F(n)=\max_{0\le m\le n} v_2\binom{n}{m}$$
tanımlansın. Burada \(v_2(x)\), \(x\)'in asal çarpanlara ayrılışındaki 2 üssüdür. İstenen toplam
$$S(N)=\sum_{n=1}^{N}F(n)$$
şeklindedir. Büyük \(N\) için bütün binom katsayılarını taramak pratik değildir; bu yüzden çözüm, problemi ikili tabandaki elde sayımına çevirir ve ardından tüm iki kuvveti bloklarını birden toplar.
\(s_2(x)\), \(x\)'in ikili yazımındaki 1 bitlerinin sayısı olsun. 2 asalı için Kummer teoremi şunu verir:
$$v_2\binom{n}{m}=s_2(m)+s_2(n-m)-s_2(n).$$
Bu ifade aynı zamanda \(m\) ile \(n-m\) ikili tabanda toplanırken oluşan elde sayısına eşittir. Dolayısıyla \(F(n)\), \(n\)'i iki negatif olmayan parçaya ayırırken elde edilebilecek en büyük elde sayısıdır.
Sabit bir \(n\ge 1\) için
$$k=\lfloor\log_2 n\rfloor$$
yazalım; yani \(2^k\le n<2^{k+1}\). Ayrıca
$$r=v_2(n+1)$$
tanımını yapalım. Bu \(r\), \(n\)'in ikili yazımındaki sondaki ardışık 1 sayısıdır. En düşük \(r\) bit konumunda yeni bir elde başlayamaz. Çünkü bit 0'da gelen elde yoktur; ayrıca sonuç biti 1 olan bir konumda çıkan elde ancak zaten bir gelen elde varsa oluşabilir. Bu nedenle sondaki 1 bloğu boyunca hiç elde oluşmaz.
Geriye yalnızca \(r,r+1,\dots,k-1\) konumları kalır. O halde
$$F(n)\le k-\min(r,k).$$
Eğer \(n=2^{k+1}-1\) ise \(r=k+1\) olur ve buradan doğrudan \(F(n)=0\) çıkar.
Şimdi \(n\neq 2^{k+1}-1\) olduğunu, yani \(r\le k\) olduğunu varsayalım. Şu seçimi yapalım:
$$m=2^k-1.$$
Bu sayının alt \(k\) biti tamamen 1'dir ve
$$n-m=n+1-2^k$$
olur. İkili çıkarma sırasında \(2^k-1\)'i \(n\)'den çıkarmak, sondaki \(r\) adet 1 bloğunun hemen üstündeki ilk 0 bitinde ödünç alma zincirini başlatır; bu zincir de bit \(k-1\)'e kadar bütün daha yüksek konumlardan geçer. Böylece ödünç alma sayısı, dolayısıyla eşdeğer olarak elde sayısı, tam olarak \(k-r\) olur.
Aynı sonuç rakam toplamı özdeşliğiyle de görülebilir:
$$\begin{aligned} v_2\binom{n}{2^k-1} &=s_2(2^k-1)+s_2(n+1-2^k)-s_2(n)\\ &=k+\bigl(s_2(n)-r\bigr)-s_2(n)=k-r. \end{aligned}$$
Üst sınırla birlikte bu bize tam kapalı formu verir:
$$\boxed{F(n)=k-\min\bigl(v_2(n+1),k\bigr).}$$
Şimdi şu tam bloğu ele alalım:
$$n\in[2^k,2^{k+1}-1].$$
\(x=n+1\) dersek \(x\in[2^k+1,2^{k+1}]\) olur ve
$$F(n)=k-\min(v_2(x),k)$$
yazılır. Buna göre
$$\sum_{n=2^k}^{2^{k+1}-1}F(n)=k2^k-\sum_{x=2^k+1}^{2^{k+1}}\min(v_2(x),k).$$
Şimdi standart değerlik sayma özdeşliğini kullanalım:
$$\sum_{x=A}^{B}\min(v_2(x),k)=\sum_{t=1}^{k}\#\{x\in[A,B]:2^t\mid x\}.$$
\([2^k+1,2^{k+1}]\) aralığında \(2^t\)'nin katı olan sayı adedi tam olarak \(2^{k-t}\)'dir. Böylece
$$\sum_{x=2^k+1}^{2^{k+1}}\min(v_2(x),k)=\sum_{t=1}^{k}2^{k-t}=2^k-1$$
ve blok toplamı
$$\boxed{\sum_{n=2^k}^{2^{k+1}-1}F(n)=(k-1)2^k+1}$$
olur.
Şimdi
$$K=\lfloor\log_2 N\rfloor$$
olsun. \(1,2,\dots,K-1\) indeksli bloklar tamdır. Son blok ise
$$n\in[2^K,N]$$
aralığıdır ve uzunluğu
$$M=N-2^K+1$$
olur. Yine \(x=n+1\) yazarsak \(x\in[2^K+1,N+1]\) ve
$$\sum_{n=2^K}^{N}F(n)=KM-\sum_{x=2^K+1}^{N+1}\min(v_2(x),K)$$
elde edilir. İki kuvveti katlarını sayarsak
$$\sum_{x=2^K+1}^{N+1}\min(v_2(x),K)=\sum_{t=1}^{K}\left(\left\lfloor\frac{N+1}{2^t}\right\rfloor-\left\lfloor\frac{2^K}{2^t}\right\rfloor\right).$$
\(1\le t\le K\) için \(\left\lfloor 2^K/2^t\right\rfloor=2^{K-t}\) olduğundan tam formül
$$\boxed{S(N)=\sum_{k=1}^{K-1}\bigl((k-1)2^k+1\bigr)+K(N-2^K+1)-\sum_{t=1}^{K}\left(\left\lfloor\frac{N+1}{2^t}\right\rfloor-2^{K-t}\right)}$$
şeklini alır. Burada hiçbir yaklaşım yoktur; tüm terimler tam sayma ile gelir.
Burada \(K=6\)'dır; çünkü \(64\le 100<128\). Tam bloklar \(k=1\) ile \(5\) arasındadır ve katkıları
$$\begin{aligned} k=1&:&&(1-1)2^1+1=1,\\ k=2&:&&(2-1)2^2+1=5,\\ k=3&:&&(3-1)2^3+1=17,\\ k=4&:&&(4-1)2^4+1=49,\\ k=5&:&&(5-1)2^5+1=129. \end{aligned}$$
Bunların toplamı \(201\)'dir.
Son kısmi blok \(n\in[64,100]\) olduğundan \(M=37\) ve \(x\in[65,101]\) olur. Bu aralıkta iki kuvveti katı sayıları şöyledir:
$$\begin{aligned} 2^1&:&&18,\\ 2^2&:&&9,\\ 2^3&:&&4,\\ 2^4&:&&2,\\ 2^5&:&&1,\\ 2^6&:&&0. \end{aligned}$$
Dolayısıyla
$$\sum_{x=65}^{101}\min(v_2(x),6)=18+9+4+2+1=34,$$
ve kuyruk blok katkısı
$$6\cdot 37-34=188$$
olur. Sonuçta
$$S(100)=201+188=389,$$
ki bu, implementasyondaki kontrol değeriyle aynıdır.
C++, Python ve Java implementasyonları aynı matematiksel akışı izler. Önce \(N\)'in en yüksek 1 bitinin konumu bulunur; bu da son iki kuvveti bloğunun indeksi olan \(K\)'yi verir. Ardından tüm tam bloklar \((k-1)2^k+1\) kapalı formülüyle toplanır.
Sonrasında \([2^K,N]\) aralığındaki kısmi blok işlenir. Uygulama \(F(n)\)'yi tek tek hesaplamak yerine, \(x\in[2^K+1,N+1]\) aralığında 2, 4, 8, \(\dots\), \(2^K\)'ye bölünebilen sayıların kaç tane olduğunu sayar. Bu sayıların toplamı tam olarak \(\sum \min(v_2(x),K)\) olduğundan, bunu \(K(N-2^K+1)\)'den çıkarmak kuyruk katkısını verir.
Üç dilde de yöntem aynıdır. Python doğal olarak büyük tamsayı kullanır, Java toplam için çok büyük tamsayı aritmetiğine başvurur, C++ sürümü de yeterince geniş bir tamsayı toplayıcısı kullanır.
\(K=\lfloor\log_2 N\rfloor\) olmak üzere, tam blok döngüsü \(K-1\) adım sürer ve kısmi blok için yapılan değerlik sayımı döngüsü de \(K\) adım sürer. Böylece toplam süre
$$O(\log N)$$
ve ek bellek kullanımı
$$O(1)$$
olur.
Para cada entero \(n\ge 1\), definimos
$$F(n)=\max_{0\le m\le n} v_2\binom{n}{m},$$
donde \(v_2(x)\) es el exponente de 2 en la factorización prima de \(x\). La cantidad pedida es
$$S(N)=\sum_{n=1}^{N}F(n).$$
Probar todos los coeficientes binomiales es inviable cuando \(N\) es grande. La solución sustituye esa búsqueda por un problema de acarreos en base 2 y luego suma bloques completos delimitados por potencias de 2.
Sea \(s_2(x)\) el número de bits iguales a 1 en la expansión binaria de \(x\). Para el primo \(2\), el teorema de Kummer afirma que
$$v_2\binom{n}{m}=s_2(m)+s_2(n-m)-s_2(n),$$
que coincide con el número de acarreos al sumar \(m\) y \(n-m\) en base 2. Por tanto, \(F(n)\) es el mayor número de acarreos que se puede obtener al descomponer \(n\) en dos sumandos no negativos.
Fijemos \(n\ge 1\) y escribamos
$$k=\lfloor\log_2 n\rfloor,$$
de modo que \(2^k\le n<2^{k+1}\). Además definimos
$$r=v_2(n+1).$$
Ese valor \(r\) es exactamente el número de unos finales en la representación binaria de \(n\). En esas \(r\) posiciones más bajas no puede iniciarse ningún acarreo. En el bit 0 no existe acarreo entrante, y en cualquier posición cuyo bit de salida sea 1, un acarreo saliente solo puede aparecer si ya había un acarreo entrante. Por inducción, todo el bloque final de unos queda libre de acarreos.
Así solo quedan disponibles las posiciones \(r,r+1,\dots,k-1\), y por tanto
$$F(n)\le k-\min(r,k).$$
Si \(n=2^{k+1}-1\), entonces \(r=k+1\) y esta cota ya implica \(F(n)=0\).
Supongamos ahora que \(n\neq 2^{k+1}-1\), es decir, \(r\le k\). Tomamos
$$m=2^k-1.$$
Este número tiene sus \(k\) bits inferiores iguales a 1 y satisface
$$n-m=n+1-2^k.$$
Al restar \(2^k-1\) de \(n\) en binario, el préstamo comienza exactamente en el primer 0 situado por encima del bloque final de \(r\) unos, y luego se propaga por todas las posiciones superiores hasta el bit \(k-1\). Por eso el número de préstamos, y equivalentemente el número de acarreos en la suma correspondiente, es exactamente \(k-r\).
La misma conclusión se obtiene con la identidad de sumas de dígitos:
$$\begin{aligned} v_2\binom{n}{2^k-1} &=s_2(2^k-1)+s_2(n+1-2^k)-s_2(n)\\ &=k+\bigl(s_2(n)-r\bigr)-s_2(n)=k-r. \end{aligned}$$
Juntando la construcción con la cota superior, llegamos a la fórmula exacta
$$\boxed{F(n)=k-\min\bigl(v_2(n+1),k\bigr).}$$
Consideremos ahora un bloque completo
$$n\in[2^k,2^{k+1}-1].$$
Si ponemos \(x=n+1\), entonces \(x\in[2^k+1,2^{k+1}]\) y
$$F(n)=k-\min(v_2(x),k).$$
Por consiguiente,
$$\sum_{n=2^k}^{2^{k+1}-1}F(n)=k2^k-\sum_{x=2^k+1}^{2^{k+1}}\min(v_2(x),k).$$
Usamos la identidad estándar
$$\sum_{x=A}^{B}\min(v_2(x),k)=\sum_{t=1}^{k}\#\{x\in[A,B]:2^t\mid x\}.$$
Dentro de \([2^k+1,2^{k+1}]\), el número de múltiplos de \(2^t\) es exactamente \(2^{k-t}\). De ahí se obtiene
$$\sum_{x=2^k+1}^{2^{k+1}}\min(v_2(x),k)=\sum_{t=1}^{k}2^{k-t}=2^k-1,$$
y por tanto
$$\boxed{\sum_{n=2^k}^{2^{k+1}-1}F(n)=(k-1)2^k+1.}$$
Sea
$$K=\lfloor\log_2 N\rfloor.$$
Los bloques con índices \(1,2,\dots,K-1\) son completos. El último bloque es
$$n\in[2^K,N],$$
de longitud
$$M=N-2^K+1.$$
De nuevo ponemos \(x=n+1\), así que \(x\in[2^K+1,N+1]\). Entonces
$$\sum_{n=2^K}^{N}F(n)=KM-\sum_{x=2^K+1}^{N+1}\min(v_2(x),K).$$
Contar los múltiplos de \(2^t\) produce
$$\sum_{x=2^K+1}^{N+1}\min(v_2(x),K)=\sum_{t=1}^{K}\left(\left\lfloor\frac{N+1}{2^t}\right\rfloor-\left\lfloor\frac{2^K}{2^t}\right\rfloor\right).$$
Como \(\left\lfloor 2^K/2^t\right\rfloor=2^{K-t}\) para \(1\le t\le K\), obtenemos la fórmula exacta
$$\boxed{S(N)=\sum_{k=1}^{K-1}\bigl((k-1)2^k+1\bigr)+K(N-2^K+1)-\sum_{t=1}^{K}\left(\left\lfloor\frac{N+1}{2^t}\right\rfloor-2^{K-t}\right).}$$
Todo el cálculo es exacto; no aparece ninguna aproximación.
Aquí \(K=6\), porque \(64\le 100<128\). Los bloques completos son \(k=1\) hasta \(5\), con contribuciones
$$\begin{aligned} k=1&:&&(1-1)2^1+1=1,\\ k=2&:&&(2-1)2^2+1=5,\\ k=3&:&&(3-1)2^3+1=17,\\ k=4&:&&(4-1)2^4+1=49,\\ k=5&:&&(5-1)2^5+1=129. \end{aligned}$$
Su suma es \(201\).
El bloque parcial final es \(n\in[64,100]\), así que \(M=37\) y \(x\in[65,101]\). En ese intervalo, los múltiplos de potencias de 2 son
$$\begin{aligned} 2^1&:&&18,\\ 2^2&:&&9,\\ 2^3&:&&4,\\ 2^4&:&&2,\\ 2^5&:&&1,\\ 2^6&:&&0. \end{aligned}$$
Por tanto,
$$\sum_{x=65}^{101}\min(v_2(x),6)=18+9+4+2+1=34,$$
y la cola aporta
$$6\cdot 37-34=188.$$
En consecuencia,
$$S(100)=201+188=389,$$
que coincide con la comprobación usada por la implementación.
Las implementaciones en C++, Python y Java siguen exactamente esta derivación. Primero determinan la posición del bit más alto de \(N\), lo que fija el índice \(K\) del último bloque diádico. Después acumulan todos los bloques completos con la fórmula cerrada \((k-1)2^k+1\).
Luego procesan el bloque parcial \([2^K,N]\). En vez de calcular \(F(n)\) para cada \(n\), la implementación cuenta cuántos valores de \(x\in[2^K+1,N+1]\) son divisibles por \(2,4,8,\dots,2^K\). La suma de esos conteos es exactamente \(\sum \min(v_2(x),K)\), y restarla de \(K(N-2^K+1)\) da la contribución final.
Los tres lenguajes usan la misma lógica matemática. Python maneja enteros grandes de forma nativa, Java usa enteros de precisión arbitraria para la acumulación y la versión en C++ utiliza un acumulador entero amplio para conservar el resultado exacto.
Si \(K=\lfloor\log_2 N\rfloor\), el bucle sobre bloques completos hace \(K-1\) iteraciones y el conteo de valoraciones para la cola hace \(K\) más. Por ello, el tiempo total es
$$O(\log N),$$
con memoria adicional
$$O(1).$$
对每个整数 \(n\ge 1\)，定义
$$F(n)=\max_{0\le m\le n} v_2\binom{n}{m},$$
其中 \(v_2(x)\) 表示 \(x\) 的质因数分解里 2 的指数。题目要求计算
$$S(N)=\sum_{n=1}^{N}F(n).$$
如果真的去枚举每个 \(n\) 的所有二项式系数，规模一大就完全不可行。真正有效的做法是先把“最大的 2 因子个数”改写成“二进制加法中的最大进位数”，再把连续区间按 \(2\) 的幂分块整体求和。
记 \(s_2(x)\) 为 \(x\) 的二进制表示中 1 的个数。对素数 \(2\)，Kummer 定理给出
$$v_2\binom{n}{m}=s_2(m)+s_2(n-m)-s_2(n).$$
这个量也正好等于把 \(m\) 与 \(n-m\) 按二进制相加时产生的进位次数。因此，\(F(n)\) 就变成了这样一个问题：把 \(n\) 拆成两个非负整数之和时，最多能产生多少次二进制进位。
固定一个 \(n\ge 1\)，设
$$k=\lfloor\log_2 n\rfloor,$$
于是 \(2^k\le n<2^{k+1}\)。再定义
$$r=v_2(n+1).$$
\(r\) 的含义很重要：它正好等于 \(n\) 的二进制表示末尾连续 1 的个数。为什么这能限制进位数？因为在最低位 bit 0 根本没有“输入进位”；而在某一位上，如果结果位是 1，那么想要出现“输出进位”，必须先已经有一个“输入进位”。于是从最低位开始递推，可以看出末尾那一整段连续 1 的位置都不可能成为新进位的起点。
所以真正可能出现进位的，只剩下位置 \(r,r+1,\dots,k-1\)。这立刻给出上界
$$F(n)\le k-\min(r,k).$$
特别地，如果 \(n=2^{k+1}-1\)，那么它的二进制就是全 1，此时 \(r=k+1\)，上式直接说明 \(F(n)=0\)。
现在假设 \(n\neq 2^{k+1}-1\)，也就是 \(r\le k\)。取
$$m=2^k-1.$$
这个 \(m\) 的低 \(k\) 位全是 1，并且
$$n-m=n+1-2^k.$$
从二进制减法的角度看，把 \(2^k-1\) 从 \(n\) 中减掉时，借位会在“末尾那串 \(r\) 个 1 之上的第一个 0 位”开始出现，然后一路向上传播，直到 bit \(k-1\)。因此借位总数恰好是 \(k-r\)。而 Kummer 定理告诉我们，借位数与相应加法中的进位数本质上是同一个计数，所以这就构造出了 \(k-r\) 次进位。
也可以直接用数字和恒等式验证：
$$\begin{aligned} v_2\binom{n}{2^k-1} &=s_2(2^k-1)+s_2(n+1-2^k)-s_2(n)\\ &=k+\bigl(s_2(n)-r\bigr)-s_2(n)=k-r. \end{aligned}$$
这说明上界是可以达到的，于是得到精确闭式
$$\boxed{F(n)=k-\min\bigl(v_2(n+1),k\bigr).}$$
考虑完整区间
$$n\in[2^k,2^{k+1}-1].$$
令 \(x=n+1\)，则 \(x\in[2^k+1,2^{k+1}]\)，而
$$F(n)=k-\min(v_2(x),k).$$
于是
$$\sum_{n=2^k}^{2^{k+1}-1}F(n)=k2^k-\sum_{x=2^k+1}^{2^{k+1}}\min(v_2(x),k).$$
接下来用一个标准技巧：对任意区间 \([A,B]\)，有
$$\sum_{x=A}^{B}\min(v_2(x),k)=\sum_{t=1}^{k}\#\{x\in[A,B]:2^t\mid x\}.$$
也就是说，不去逐个看每个数的 2 进赋值，而是改成统计“有多少个数能被 \(2^t\) 整除”。在 \([2^k+1,2^{k+1}]\) 里，\(2^t\) 的倍数恰好有 \(2^{k-t}\) 个，因此
$$\sum_{x=2^k+1}^{2^{k+1}}\min(v_2(x),k)=\sum_{t=1}^{k}2^{k-t}=2^k-1.$$
于是完整块的贡献就是
$$\boxed{\sum_{n=2^k}^{2^{k+1}-1}F(n)=(k-1)2^k+1.}$$
设
$$K=\lfloor\log_2 N\rfloor.$$
那么编号 \(1,2,\dots,K-1\) 的块都是完整的，最后一个块是
$$n\in[2^K,N],$$
长度为
$$M=N-2^K+1.$$
同样令 \(x=n+1\)，于是 \(x\in[2^K+1,N+1]\)。由闭式可得
$$\sum_{n=2^K}^{N}F(n)=KM-\sum_{x=2^K+1}^{N+1}\min(v_2(x),K).$$
再用“统计 \(2^t\) 倍数”的方法，得到
$$\sum_{x=2^K+1}^{N+1}\min(v_2(x),K)=\sum_{t=1}^{K}\left(\left\lfloor\frac{N+1}{2^t}\right\rfloor-\left\lfloor\frac{2^K}{2^t}\right\rfloor\right).$$
由于对 \(1\le t\le K\) 有 \(\left\lfloor 2^K/2^t\right\rfloor=2^{K-t}\)，最终得到完整公式
$$\boxed{S(N)=\sum_{k=1}^{K-1}\bigl((k-1)2^k+1\bigr)+K(N-2^K+1)-\sum_{t=1}^{K}\left(\left\lfloor\frac{N+1}{2^t}\right\rfloor-2^{K-t}\right).}$$
这就是程序使用的数学核心，而且它是严格精确的，不包含任何估算。
这里 \(K=6\)，因为 \(64\le 100<128\)。完整块对应 \(k=1\) 到 \(5\)，它们的贡献分别是
$$\begin{aligned} k=1&:&&(1-1)2^1+1=1,\\ k=2&:&&(2-1)2^2+1=5,\\ k=3&:&&(3-1)2^3+1=17,\\ k=4&:&&(4-1)2^4+1=49,\\ k=5&:&&(5-1)2^5+1=129. \end{aligned}$$
这些加起来是 \(201\)。
尾块是 \(n\in[64,100]\)，所以 \(M=37\)，而 \(x\in[65,101]\)。在这个区间里，各个 \(2\) 的幂的倍数个数为
$$\begin{aligned} 2^1&:&&18,\\ 2^2&:&&9,\\ 2^3&:&&4,\\ 2^4&:&&2,\\ 2^5&:&&1,\\ 2^6&:&&0. \end{aligned}$$
因此
$$\sum_{x=65}^{101}\min(v_2(x),6)=18+9+4+2+1=34,$$
尾块贡献为
$$6\cdot 37-34=188.$$
所以最终
$$S(100)=201+188=389,$$
这与实现中的校验结果完全一致。
C++、Python 和 Java 三个实现都严格按照上面的推导执行。第一步是找到 \(N\) 的最高位 1 所在的位置，从而得到最后一个二进制块的编号 \(K\)。然后把所有完整块按闭式 \((k-1)2^k+1\) 直接累加。
接着处理最后的不完整区间 \([2^K,N]\)。实现并不会逐个计算每个 \(n\) 的 \(F(n)\)，而是改为统计区间 \(x\in[2^K+1,N+1]\) 中，有多少个数能被 \(2,4,8,\dots,2^K\) 整除。这些计数的总和正好就是 \(\sum \min(v_2(x),K)\)，把它从 \(K(N-2^K+1)\) 中减掉，就得到了尾块的精确贡献。
三个版本的区别只在整数类型上。Python 的整数天然支持大数，Java 用任意精度整数做最终累加，C++ 则使用足够宽的整数累加器。数学步骤本身完全一致。
设 \(K=\lfloor\log_2 N\rfloor\)。完整块求和需要 \(K-1\) 次迭代，尾块中的赋值计数还需要 \(K\) 次迭代，因此总时间复杂度是
$$O(\log N),$$
额外空间复杂度是
$$O(1).$$
Для каждого целого \(n\ge 1\) определим
$$F(n)=\max_{0\le m\le n} v_2\binom{n}{m},$$
где \(v_2(x)\) означает показатель степени двойки в разложении числа \(x\). Требуется вычислить
$$S(N)=\sum_{n=1}^{N}F(n).$$
Полный перебор всех биномиальных коэффициентов слишком дорог уже для умеренно больших \(N\). Поэтому решение переводит задачу в язык двоичных переносов и затем суммирует целые блоки между соседними степенями двойки.
Обозначим через \(s_2(x)\) число единиц в двоичной записи \(x\). Для простого \(2\) теорема Куммера дает
$$v_2\binom{n}{m}=s_2(m)+s_2(n-m)-s_2(n).$$
Это же число равно количеству переносов при сложении \(m\) и \(n-m\) в двоичной системе. Значит, \(F(n)\) есть максимально возможное число переносов среди всех разбиений \(n=a+b\) на два неотрицательных слагаемых.
Зафиксируем \(n\ge 1\) и положим
$$k=\lfloor\log_2 n\rfloor,$$
так что \(2^k\le n<2^{k+1}\). Далее введем
$$r=v_2(n+1).$$
Число \(r\) точно равно количеству завершающих единиц в двоичной записи \(n\). В этих младших \(r\) разрядах новый перенос появиться не может. В нулевом разряде нет входящего переноса, а в разряде, где результирующий бит равен 1, исходящий перенос возможен только при наличии уже существующего входящего переноса. Поэтому по индукции весь хвост из единиц не содержит переносов.
Следовательно, переносы могут возникать только в позициях \(r,r+1,\dots,k-1\), и мы сразу получаем оценку
$$F(n)\le k-\min(r,k).$$
Если же \(n=2^{k+1}-1\), то \(r=k+1\), и эта оценка сразу дает \(F(n)=0\).
Пусть теперь \(n\neq 2^{k+1}-1\), то есть \(r\le k\). Возьмем
$$m=2^k-1.$$
У этого числа все младшие \(k\) битов равны 1, а также
$$n-m=n+1-2^k.$$
При двоичном вычитании \(2^k-1\) из \(n\) заимствование начинается ровно в первом нуле над конечным блоком из \(r\) единиц и затем распространяется через все более старшие разряды до бита \(k-1\). Поэтому число заимствований, а значит и число переносов в эквивалентном сложении, в точности равно \(k-r\).
То же самое видно и из формулы для суммы цифр:
$$\begin{aligned} v_2\binom{n}{2^k-1} &=s_2(2^k-1)+s_2(n+1-2^k)-s_2(n)\\ &=k+\bigl(s_2(n)-r\bigr)-s_2(n)=k-r. \end{aligned}$$
Совмещая построение с верхней границей, получаем точную формулу
$$\boxed{F(n)=k-\min\bigl(v_2(n+1),k\bigr).}$$
Рассмотрим полный блок
$$n\in[2^k,2^{k+1}-1].$$
Положим \(x=n+1\). Тогда \(x\in[2^k+1,2^{k+1}]\), и
$$F(n)=k-\min(v_2(x),k).$$
Значит,
$$\sum_{n=2^k}^{2^{k+1}-1}F(n)=k2^k-\sum_{x=2^k+1}^{2^{k+1}}\min(v_2(x),k).$$
Теперь используем стандартное тождество
$$\sum_{x=A}^{B}\min(v_2(x),k)=\sum_{t=1}^{k}\#\{x\in[A,B]:2^t\mid x\}.$$
На отрезке \([2^k+1,2^{k+1}]\) кратных \(2^t\) ровно \(2^{k-t}\). Поэтому
$$\sum_{x=2^k+1}^{2^{k+1}}\min(v_2(x),k)=\sum_{t=1}^{k}2^{k-t}=2^k-1,$$
и вклад полного блока равен
$$\boxed{\sum_{n=2^k}^{2^{k+1}-1}F(n)=(k-1)2^k+1.}$$
Пусть
$$K=\lfloor\log_2 N\rfloor.$$
Блоки с индексами \(1,2,\dots,K-1\) полные, а последний блок имеет вид
$$n\in[2^K,N]$$
и длину
$$M=N-2^K+1.$$
Снова положим \(x=n+1\), так что \(x\in[2^K+1,N+1]\). Тогда
$$\sum_{n=2^K}^{N}F(n)=KM-\sum_{x=2^K+1}^{N+1}\min(v_2(x),K).$$
Подсчет кратных степеней двойки дает
$$\sum_{x=2^K+1}^{N+1}\min(v_2(x),K)=\sum_{t=1}^{K}\left(\left\lfloor\frac{N+1}{2^t}\right\rfloor-\left\lfloor\frac{2^K}{2^t}\right\rfloor\right).$$
Так как \(\left\lfloor 2^K/2^t\right\rfloor=2^{K-t}\) для \(1\le t\le K\), получаем точную формулу
$$\boxed{S(N)=\sum_{k=1}^{K-1}\bigl((k-1)2^k+1\bigr)+K(N-2^K+1)-\sum_{t=1}^{K}\left(\left\lfloor\frac{N+1}{2^t}\right\rfloor-2^{K-t}\right).}$$
Здесь нет никаких приближений: все слагаемые получены точным подсчетом переносов.
Здесь \(K=6\), поскольку \(64\le 100<128\). Полные блоки соответствуют \(k=1,\dots,5\), и их вклады равны
$$\begin{aligned} k=1&:&&(1-1)2^1+1=1,\\ k=2&:&&(2-1)2^2+1=5,\\ k=3&:&&(3-1)2^3+1=17,\\ k=4&:&&(4-1)2^4+1=49,\\ k=5&:&&(5-1)2^5+1=129. \end{aligned}$$
В сумме это дает \(201\).
Последний неполный блок: \(n\in[64,100]\), поэтому \(M=37\), а \(x\in[65,101]\). На этом промежутке числа, кратные степеням двойки, распределяются так:
$$\begin{aligned} 2^1&:&&18,\\ 2^2&:&&9,\\ 2^3&:&&4,\\ 2^4&:&&2,\\ 2^5&:&&1,\\ 2^6&:&&0. \end{aligned}$$
Следовательно,
$$\sum_{x=65}^{101}\min(v_2(x),6)=18+9+4+2+1=34,$$
и хвостовой вклад равен
$$6\cdot 37-34=188.$$
Итак,
$$S(100)=201+188=389,$$
что совпадает с проверкой, используемой в реализации.
Реализации на C++, Python и Java повторяют именно эту схему. Сначала они находят позицию старшего установленного бита числа \(N\), то есть индекс \(K\) последнего двоичного блока. Затем все полные блоки суммируются по закрытой формуле \((k-1)2^k+1\).
После этого обрабатывается последний неполный блок \([2^K,N]\). Вместо того чтобы вычислять \(F(n)\) для каждого \(n\) отдельно, реализация считает, сколько чисел в диапазоне \(x\in[2^K+1,N+1]\) делятся на \(2,4,8,\dots,2^K\). Сумма этих количеств и есть \(\sum \min(v_2(x),K)\), поэтому хвостовой вклад получается одной дополнительной суммой.
Разница между версиями заключается только в типах чисел. Python использует длинную арифметику автоматически, Java применяет целые произвольной точности для накопления суммы, а C++ задействует достаточно широкий целочисленный аккумулятор.
Пусть \(K=\lfloor\log_2 N\rfloor\). Цикл по полным блокам выполняется \(K-1\) раз, и еще \(K\) шагов требуется для подсчета 2-адических оценок в хвостовом блоке. Следовательно, суммарная асимптотика равна
$$O(\log N),$$
а дополнительная память составляет
$$O(1).$$
لكل عدد صحيح \(n\ge 1\) نعرّف
$$F(n)=\max_{0\le m\le n} v_2\binom{n}{m},$$
حيث تمثل \(v_2(x)\) أسّ العدد \(2\) في تحليل \(x\) إلى عوامل أولية. والمطلوب هو حساب
$$S(N)=\sum_{n=1}^{N}F(n).$$
فحص جميع معاملات ذي الحدين مباشرة يصبح بطيئًا جدًا عندما يكون \(N\) كبيرًا. لذلك يحوّل الحل المسألة إلى مسألة عدّ النقلات الثنائية، ثم يجمع كتلًا كاملة بين قوى العدد \(2\) دفعة واحدة.
لنرمز بـ \(s_2(x)\) إلى عدد البتات التي تساوي \(1\) في التمثيل الثنائي للعدد \(x\). بالنسبة إلى العدد الأولي \(2\)، تعطي نظرية كومر العلاقة
$$v_2\binom{n}{m}=s_2(m)+s_2(n-m)-s_2(n).$$
وهذه الكمية نفسها تساوي عدد النقلات الناتجة عند جمع \(m\) و\(n-m\) بالنظام الثنائي. لذلك فإن \(F(n)\) هو أكبر عدد ممكن من النقلات عند كتابة \(n\) على صورة مجموع عددين غير سالبين.
ثبّت عددًا \(n\ge 1\)، واكتب
$$k=\lfloor\log_2 n\rfloor,$$
بحيث \(2^k\le n<2^{k+1}\). ثم عرّف
$$r=v_2(n+1).$$
هذا العدد \(r\) يساوي بالضبط عدد الواحدات المتتالية في نهاية الكتابة الثنائية للعدد \(n\). ولا يمكن أن تبدأ نقلة جديدة داخل هذه الخانة النهائية من الواحدات. ففي البت الأدنى لا يوجد أصلًا نقل داخل، وفي أي موضع يكون فيه بت الناتج مساويًا لـ \(1\)، لا يظهر نقل خارج إلا إذا كان هناك نقل داخل مسبق. وبالاستقراء نحصل على أن كل الكتلة النهائية من الواحدات خالية من النقلات.
إذن لا تبقى إلا المواضع \(r,r+1,\dots,k-1\)، ومن ثم
$$F(n)\le k-\min(r,k).$$
وفي الحالة الخاصة \(n=2^{k+1}-1\) يكون \(r=k+1\)، وعندئذ نحصل مباشرة على \(F(n)=0\).
افترض الآن أن \(n\neq 2^{k+1}-1\)، أي إن \(r\le k\). خذ
$$m=2^k-1.$$
هذا العدد يملك \(k\) بتات دنيا كلها تساوي \(1\)، كما أن
$$n-m=n+1-2^k.$$
وعند طرح \(2^k-1\) من \(n\) بالنظام الثنائي يبدأ الاستلاف عند أول صفر يقع فوق الكتلة النهائية المؤلفة من \(r\) واحدات، ثم يستمر عبر كل المواضع الأعلى حتى البت \(k-1\). لذلك يكون عدد عمليات الاستلاف، وبالتالي عدد النقلات في الجمع الموافق، مساويًا تمامًا لـ \(k-r\).
ويمكن التحقق من ذلك أيضًا عبر هوية مجموع البتات:
$$\begin{aligned} v_2\binom{n}{2^k-1} &=s_2(2^k-1)+s_2(n+1-2^k)-s_2(n)\\ &=k+\bigl(s_2(n)-r\bigr)-s_2(n)=k-r. \end{aligned}$$
وبضم هذه البنية إلى الحد الأعلى نحصل على الصيغة الدقيقة
$$\boxed{F(n)=k-\min\bigl(v_2(n+1),k\bigr).}$$
لننظر الآن إلى الكتلة الكاملة
$$n\in[2^k,2^{k+1}-1].$$
ضع \(x=n+1\)، وعندئذ يكون \(x\in[2^k+1,2^{k+1}]\)، ولدينا
$$F(n)=k-\min(v_2(x),k).$$
إذن
$$\sum_{n=2^k}^{2^{k+1}-1}F(n)=k2^k-\sum_{x=2^k+1}^{2^{k+1}}\min(v_2(x),k).$$
ثم نستخدم الهوية القياسية
$$\sum_{x=A}^{B}\min(v_2(x),k)=\sum_{t=1}^{k}\#\{x\in[A,B]:2^t\mid x\}.$$
داخل المجال \([2^k+1,2^{k+1}]\)، يكون عدد المضاعفات لـ \(2^t\) مساويًا تمامًا لـ \(2^{k-t}\). لذلك
$$\sum_{x=2^k+1}^{2^{k+1}}\min(v_2(x),k)=\sum_{t=1}^{k}2^{k-t}=2^k-1,$$
ومن ثم يصبح مجموع الكتلة
$$\boxed{\sum_{n=2^k}^{2^{k+1}-1}F(n)=(k-1)2^k+1.}$$
لتكن
$$K=\lfloor\log_2 N\rfloor.$$
الكتل ذات الفهارس \(1,2,\dots,K-1\) كاملة، أما الكتلة الأخيرة فهي
$$n\in[2^K,N]$$
وطولها
$$M=N-2^K+1.$$
مرة أخرى نضع \(x=n+1\)، فيكون \(x\in[2^K+1,N+1]\). عندها
$$\sum_{n=2^K}^{N}F(n)=KM-\sum_{x=2^K+1}^{N+1}\min(v_2(x),K).$$
وبعد عدّ مضاعفات قوى العدد \(2\) نحصل على
$$\sum_{x=2^K+1}^{N+1}\min(v_2(x),K)=\sum_{t=1}^{K}\left(\left\lfloor\frac{N+1}{2^t}\right\rfloor-\left\lfloor\frac{2^K}{2^t}\right\rfloor\right).$$
وبما أن \(\left\lfloor 2^K/2^t\right\rfloor=2^{K-t}\) لكل \(1\le t\le K\)، نحصل في النهاية على الصيغة الدقيقة
$$\boxed{S(N)=\sum_{k=1}^{K-1}\bigl((k-1)2^k+1\bigr)+K(N-2^K+1)-\sum_{t=1}^{K}\left(\left\lfloor\frac{N+1}{2^t}\right\rfloor-2^{K-t}\right).}$$
وهذه صيغة exact تمامًا، وليست تقريبًا عدديًا.
هنا \(K=6\) لأن \(64\le 100<128\). الكتل الكاملة هي من \(k=1\) إلى \(k=5\)، ومساهماتها تساوي
$$\begin{aligned} k=1&:&&(1-1)2^1+1=1,\\ k=2&:&&(2-1)2^2+1=5,\\ k=3&:&&(3-1)2^3+1=17,\\ k=4&:&&(4-1)2^4+1=49,\\ k=5&:&&(5-1)2^5+1=129. \end{aligned}$$
ومجموعها هو \(201\).
أما الكتلة الجزئية الأخيرة فهي \(n\in[64,100]\)، ولذلك \(M=37\) و\(x\in[65,101]\). في هذا المجال تكون أعداد المضاعفات لقوى 2 كما يلي:
$$\begin{aligned} 2^1&:&&18,\\ 2^2&:&&9,\\ 2^3&:&&4,\\ 2^4&:&&2,\\ 2^5&:&&1,\\ 2^6&:&&0. \end{aligned}$$
إذن
$$\sum_{x=65}^{101}\min(v_2(x),6)=18+9+4+2+1=34,$$
فتكون مساهمة الذيل
$$6\cdot 37-34=188.$$
وبالتالي
$$S(100)=201+188=389,$$
وهو نفس مقدار التحقق الذي تستخدمه التطبيقات.
تتبع تطبيقات C++ وPython وJava البنية نفسها تمامًا. فهي تبدأ بتحديد موضع أعلى بت مساوٍ لـ \(1\) في \(N\)، ومنه يُستخرج الفهرس \(K\) للكتلة الثنائية الأخيرة. بعد ذلك تُجمع جميع الكتل الكاملة باستعمال الصيغة المغلقة \((k-1)2^k+1\).
ثم تعالج التطبيقات الكتلة الجزئية \([2^K,N]\). وبدلًا من حساب \(F(n)\) لكل \(n\) على حدة، تقوم بعدّ الأعداد في المجال \(x\in[2^K+1,N+1]\) القابلة للقسمة على \(2,4,8,\dots,2^K\). مجموع هذه الأعداد يساوي تمامًا \(\sum \min(v_2(x),K)\)، ومن ثم فإن طرحه من \(K(N-2^K+1)\) يعطي مساهمة الذيل بدقة كاملة.
الاختلاف بين اللغات الثلاث يقتصر على نوع الأعداد المستخدمة في التجميع النهائي. Python تتعامل مع الأعداد الكبيرة تلقائيًا، وJava تستخدم أعدادًا ذات دقة غير محدودة للتجميع، أما نسخة C++ فتستخدم مُجمِّعًا عدديًا واسعًا للغرض نفسه.
إذا كان \(K=\lfloor\log_2 N\rfloor\)، فإن حلقة الكتل الكاملة تنفذ \(K-1\) مرة، وحلقة عدّ القيم في الذيل تنفذ \(K\) مرة أخرى. لذلك يكون الزمن الكلي
$$O(\log N),$$
بينما تكون الذاكرة الإضافية
$$O(1).$$