For each pair \((n,k)\), let \(f(n,k)\) be the number of \(k\)-element subsets of \(\{1,2,\dots,n\}\) whose element sum is odd. An odd triplet is a triplet \((n,k,f(n,k))\) in which all three entries are odd.
The quantity to evaluate is
$$A(N)=\#\{(n,k):1\le k\le n\le N,\ n,\ k,\ f(n,k)\text{ are all odd}\},$$
and the implementations compute \(A(10^{12})\). The search space is far too large for direct enumeration, so the key is to understand only the parity of \(f(n,k)\), not its exact size.
The derivation starts from a straightforward combinatorial count, turns that count into a parity statement over modulo 2 arithmetic, and then collapses the whole problem to a short prefix sum involving binary popcounts.
Let
$$o=\left\lceil\frac n2\right\rceil,\qquad e=\left\lfloor\frac n2\right\rfloor.$$
Any \(k\)-subset of \(\{1,\dots,n\}\) has odd total exactly when it contains an odd number of odd elements. Therefore
$$f(n,k)=\sum_{\substack{j=0\\ j\text{ odd}}}^{k}\binom{o}{j}\binom{e}{k-j}.$$
Because an odd triplet must have odd first and second coordinates, we only need \(n=2m+1\) and \(k=2r+1\). Then \(o=m+1\) and \(e=m\), so
$$f(2m+1,2r+1)=\sum_{\substack{j=0\\ j\text{ odd}}}^{2r+1}\binom{m+1}{j}\binom{m}{2r+1-j}.$$
To study only parity, encode subset size by \(x\) and the parity of the subset sum by \(y\). Modulo 2, the relevant polynomial is
$$P_n(x,y)=\prod_{i=1}^{n}\left(1+x\,y^{i\bmod 2}\right)=(1+x)^e(1+xy)^o,$$
with the rule \(y^2=1\). The coefficient of \(x^k y\) is exactly \(f(n,k)\bmod 2\), because each chosen odd number contributes one factor of \(y\), and only the parity of the number of chosen odd elements matters.
For \(n=2m+1\), this becomes
$$P_{2m+1}(x,y)=(1+x)^m(1+xy)^{m+1}.$$
Now split into the parity of \(m\).
If \(m=2t+1\) is odd, then modulo 2 we can square factors:
$$ (1+x)^{2t+1}=(1+x)(1+x^2)^t,\qquad (1+xy)^{2t+2}=(1+x^2)^{t+1}. $$
Hence
$$P_{4t+3}(x,y)=(1+x)(1+x^2)^{2t+1},$$
which contains no \(y\)-term at all. Therefore every \(f(4t+3,2r+1)\) is even, so these values of \(n\) never produce odd triplets.
If instead \(m=2t\) is even, then
$$ (1+x)^{2t}=(1+x^2)^t,\qquad (1+xy)^{2t+1}=(1+x^2)^t(1+xy), $$
and therefore
$$P_{4t+1}(x,y)=(1+x^2)^{2t}(1+xy).$$
The coefficient of \(x^{2r+1}y\) is now the coefficient of \(x^{2r}\) in \((1+x^2)^{2t}\), namely
$$f(4t+1,2r+1)\equiv \binom{2t}{r}\pmod 2.$$
Equivalently, with \(m=(n-1)/2\),
$$f(2m+1,2r+1)\text{ is odd}\iff m\text{ is even and }\binom{m}{r}\text{ is odd}.$$
Modulo 2, Lucas' theorem says
$$\binom{u}{v}\equiv 1\pmod 2\iff (v\ \&\ \sim u)=0.$$
In words: every 1-bit of \(v\) must sit under a 1-bit of \(u\). So if \(m=2t\), the admissible values of \(r\) are exactly the binary submasks of \(m\).
The number of such \(r\) is the number of odd entries in row \(m\) of Pascal's triangle:
$$\#\{r:\binom{m}{r}\text{ odd}\}=2^{\operatorname{popcount}(m)}.$$
Since \(m=2t\) only appends a trailing zero in binary, \(\operatorname{popcount}(m)=\operatorname{popcount}(t)\). Therefore each \(t\) contributes
$$2^{\operatorname{popcount}(t)}$$
odd triplets.
The contributing values of \(n\) are exactly \(n=4t+1\). For a bound \(N\), the largest possible \(t\) is
$$t_{\max}=\left\lfloor\frac{N-1}{4}\right\rfloor.$$
So the entire Project Euler question reduces to
$$A(N)=\sum_{t=0}^{t_{\max}}2^{\operatorname{popcount}(t)}.$$
This is already a complete characterization of all odd triplets: every contributing \(n\) has the form \(4t+1\), and for that \(n\), the valid odd \(k\) are precisely those with \(k=2r+1\) where \(r\) is a binary submask of \(2t\).
Here
$$t_{\max}=\left\lfloor\frac{10-1}{4}\right\rfloor=2.$$
So we only inspect \(t=0,1,2\):
$$ 2^{\operatorname{popcount}(0)}=1,\qquad 2^{\operatorname{popcount}(1)}=2,\qquad 2^{\operatorname{popcount}(2)}=2. $$
The total is \(1+2+2=5\). Concretely, the contributing values are:
\(t=0 \Rightarrow n=1\), giving \(k=1\).
\(t=1 \Rightarrow n=5\), where row 2 of Pascal's triangle has odd entries at \(r=0,2\), giving \(k=1,5\).
\(t=2 \Rightarrow n=9\), where row 4 has odd entries at \(r=0,4\), giving \(k=1,9\).
That matches the small checkpoint used by the reference implementation: there are exactly 5 odd triplets with \(n\le 10\).
Define
$$S(T)=\sum_{t=0}^{T}2^{\operatorname{popcount}(t)}.$$
The implementation scans the bits of \(T\) from most significant to least significant. Suppose the current bit is \(b\), this bit of \(T\) is 1, and there are already \(s\) ones in the higher prefix. If we set bit \(b\) to 0 and allow the lower \(b\) bits to vary freely, every lower pattern \(x\) contributes
$$2^{s+\operatorname{popcount}(x)}.$$
Summing over all \(x\in[0,2^b)\) gives
$$2^s\sum_{x=0}^{2^b-1}2^{\operatorname{popcount}(x)}=2^s\cdot 3^b,$$
because each lower bit independently contributes either a factor \(1\) or a factor \(2\), so the total product is \((1+2)^b=3^b\). After processing every set bit, one final term \(2^s\) accounts for \(T\) itself.
This transforms the whole problem into a constant-memory bit walk over at most 64 positions.
The C++, Python, and Java implementations first replace the original upper bound \(N\) by
$$T=\left\lfloor\frac{N-1}{4}\right\rfloor,$$
because only \(n=4t+1\) can contribute. From that point on, the task is just to compute \(S(T)=\sum_{t=0}^{T}2^{\operatorname{popcount}(t)}\).
All three implementations precompute \(3^b\) for bit positions \(0\) through \(63\). They then scan the bits of \(T\) from high to low, keep track of how many 1-bits have already appeared in the prefix, and whenever a set bit is encountered they add the contribution \(2^s3^b\) for the branch in which that bit is turned off and the remaining suffix is arbitrary.
After the scan finishes, the remaining prefix itself contributes \(2^s\). That exactly reproduces the mathematical prefix-sum formula above, and it is why the final solver is extremely short in every language.
The C++ implementation also contains explicit correctness checks on small inputs. It verifies a direct sample value \(f(5,3)=4\), checks that the total number of odd triplets up to \(n=10\) is 5, compares the closed parity rule against direct combinatorial evaluation for all odd \(n\le 1001\), and tests the prefix-sum routine against a brute-force accumulation on a large range of small \(t\).
The Python and Java implementations keep only the compact production calculation, but they implement exactly the same mathematics.
The actual solver performs one scan over the bit representation of \(T=\lfloor(N-1)/4\rfloor\). For a 64-bit bound this means at most 64 iterations, so the time complexity is \(O(\log N)\) and the memory usage is \(O(1)\).
The optional brute-force and parity-validation routines in the C++ version are only small safety checks; they are not part of the main Project Euler computation.
Für jedes Paar \((n,k)\) sei \(f(n,k)\) die Anzahl der \(k\)-elementigen Teilmengen von \(\{1,2,\dots,n\}\), deren Summe ungerade ist. Ein ungerades Tripel ist also ein Tripel \((n,k,f(n,k))\), bei dem alle drei Einträge ungerade sind.
Gesucht ist
$$A(N)=\#\{(n,k):1\le k\le n\le N,\ n,\ k,\ f(n,k)\text{ alle ungerade}\},$$
und die Implementierungen berechnen \(A(10^{12})\). Eine direkte Suche ist völlig unpraktisch; entscheidend ist nur die Parität von \(f(n,k)\), nicht ihr exakter Wert.
Die Herleitung besteht aus zwei Schritten: Zuerst wird die Parität von \(f(n,k)\) auf die Parität eines Binomialkoeffizienten reduziert, danach wird das entstehende Muster mit einer kurzen Bit-DP-Präfixsumme ausgewertet.
Setze
$$o=\left\lceil\frac n2\right\rceil,\qquad e=\left\lfloor\frac n2\right\rfloor.$$
Eine Teilmenge hat genau dann ungerade Summe, wenn sie eine ungerade Anzahl ungerader Elemente enthält. Daher gilt
$$f(n,k)=\sum_{\substack{j=0\\ j\text{ ungerade}}}^{k}\binom{o}{j}\binom{e}{k-j}.$$
Da in einem ungeraden Tripel sowohl \(n\) als auch \(k\) ungerade sein müssen, betrachten wir nur \(n=2m+1\) und \(k=2r+1\). Dann ist \(o=m+1\) und \(e=m\), also
$$f(2m+1,2r+1)=\sum_{\substack{j=0\\ j\text{ ungerade}}}^{2r+1}\binom{m+1}{j}\binom{m}{2r+1-j}.$$
Für die reine Paritätsfrage kodieren wir Teilmengengröße mit \(x\) und die Summenparität mit \(y\). Modulo 2 ist das relevante Polynom
$$P_n(x,y)=\prod_{i=1}^{n}\left(1+x\,y^{i\bmod 2}\right)=(1+x)^e(1+xy)^o,$$
wobei \(y^2=1\) gilt. Der Koeffizient von \(x^k y\) ist genau \(f(n,k)\bmod 2\), denn jedes gewählte ungerade Element liefert einen Faktor \(y\), und nur die Parität ihrer Anzahl zählt.
Für \(n=2m+1\) wird daraus
$$P_{2m+1}(x,y)=(1+x)^m(1+xy)^{m+1}.$$
Nun entscheidet die Parität von \(m\).
Ist \(m=2t+1\) ungerade, dann darf man modulo 2 Faktoren quadrieren:
$$ (1+x)^{2t+1}=(1+x)(1+x^2)^t,\qquad (1+xy)^{2t+2}=(1+x^2)^{t+1}. $$
Also
$$P_{4t+3}(x,y)=(1+x)(1+x^2)^{2t+1},$$
und dieses Polynom enthält gar keinen \(y\)-Term. Folglich ist jedes \(f(4t+3,2r+1)\) gerade; solche \(n\) liefern nie ein ungerades Tripel.
Ist dagegen \(m=2t\) gerade, so gilt
$$ (1+x)^{2t}=(1+x^2)^t,\qquad (1+xy)^{2t+1}=(1+x^2)^t(1+xy), $$
und damit
$$P_{4t+1}(x,y)=(1+x^2)^{2t}(1+xy).$$
Der Koeffizient von \(x^{2r+1}y\) ist also der Koeffizient von \(x^{2r}\) in \((1+x^2)^{2t}\), also
$$f(4t+1,2r+1)\equiv \binom{2t}{r}\pmod 2.$$
Äquivalent dazu gilt mit \(m=(n-1)/2\):
$$f(2m+1,2r+1)\text{ ist ungerade}\iff m\text{ ist gerade und }\binom{m}{r}\text{ ist ungerade}.$$
Modulo 2 besagt der Satz von Lucas
$$\binom{u}{v}\equiv 1\pmod 2\iff (v\ \&\ \sim u)=0.$$
Das bedeutet: Jedes 1-Bit von \(v\) muss unter einem 1-Bit von \(u\) liegen. Für \(m=2t\) sind die zulässigen \(r\) also genau die Binär-Submasken von \(m\).
Die Anzahl solcher \(r\) ist zugleich die Anzahl ungerader Einträge in Zeile \(m\) des Pascalschen Dreiecks:
$$\#\{r:\binom{m}{r}\text{ ungerade}\}=2^{\operatorname{popcount}(m)}.$$
Da \(m=2t\) im Binärsystem nur eine nachgestellte Null anhängt, ist \(\operatorname{popcount}(m)=\operatorname{popcount}(t)\). Jeder Wert \(t\) liefert also
$$2^{\operatorname{popcount}(t)}$$
ungerade Tripel.
Beitragende Werte von \(n\) sind genau \(n=4t+1\). Für eine Grenze \(N\) ist der größte mögliche Wert
$$t_{\max}=\left\lfloor\frac{N-1}{4}\right\rfloor.$$
Damit reduziert sich die ganze Aufgabe auf
$$A(N)=\sum_{t=0}^{t_{\max}}2^{\operatorname{popcount}(t)}.$$
Das charakterisiert alle ungeraden Tripel vollständig: Jedes beitragende \(n\) hat die Form \(4t+1\), und die zugehörigen ungeraden \(k\) sind genau diejenigen mit \(k=2r+1\), wobei \(r\) eine Binär-Submaske von \(2t\) ist.
Hier ist
$$t_{\max}=\left\lfloor\frac{10-1}{4}\right\rfloor=2.$$
Also genügen \(t=0,1,2\):
$$ 2^{\operatorname{popcount}(0)}=1,\qquad 2^{\operatorname{popcount}(1)}=2,\qquad 2^{\operatorname{popcount}(2)}=2. $$
Die Summe ist \(1+2+2=5\). Konkret:
\(t=0 \Rightarrow n=1\), also \(k=1\).
\(t=1 \Rightarrow n=5\), und in Zeile 2 des Pascalschen Dreiecks sind die ungeraden Einträge bei \(r=0,2\), also \(k=1,5\).
\(t=2 \Rightarrow n=9\), und in Zeile 4 sind sie bei \(r=0,4\), also \(k=1,9\).
Genau diese 5 Fälle erscheinen auch im kleinen Prüfwert der Referenzimplementierung.
Definiere
$$S(T)=\sum_{t=0}^{T}2^{\operatorname{popcount}(t)}.$$
Die Implementierung läuft die Bits von \(T\) von oben nach unten ab. Sei das aktuelle Bit \(b\), dieses Bit von \(T\) sei 1, und im bereits festen Präfix seien \(s\) Einsen enthalten. Setzt man Bit \(b\) auf 0 und lässt die unteren \(b\) Bits frei variieren, dann trägt jedes Muster \(x\)
$$2^{s+\operatorname{popcount}(x)}$$
bei. Summiert über alle \(x\in[0,2^b)\) ergibt das
$$2^s\sum_{x=0}^{2^b-1}2^{\operatorname{popcount}(x)}=2^s\cdot 3^b,$$
denn jedes untere Bit liefert unabhängig entweder einen Faktor \(1\) oder einen Faktor \(2\); insgesamt also \((1+2)^b=3^b\). Nach der Verarbeitung aller gesetzten Bits kommt noch ein letzter Term \(2^s\) für \(T\) selbst hinzu.
Damit wird das gesamte Problem zu einem Bitlauf mit konstantem Speicher über höchstens 64 Positionen.
Die Implementierungen in C++, Python und Java ersetzen die ursprüngliche Grenze \(N\) zunächst durch
$$T=\left\lfloor\frac{N-1}{4}\right\rfloor,$$
weil nur Werte \(n=4t+1\) beitragen können. Danach bleibt nur noch die Berechnung von \(S(T)=\sum_{t=0}^{T}2^{\operatorname{popcount}(t)}\).
Alle drei Versionen berechnen die Werte \(3^b\) für Bitpositionen \(0\) bis \(63\) vor. Dann scannen sie die Bits von \(T\) von oben nach unten, führen die Anzahl der bisher gesehenen 1-Bits im Präfix mit und addieren bei jedem gesetzten Bit den Zweigbeitrag \(2^s3^b\), der entsteht, wenn dieses Bit ausgeschaltet und der Rest frei gelassen wird.
Nach dem Bitlauf trägt das verbleibende Präfix selbst noch \(2^s\) bei. Genau dadurch entsteht die mathematische Präfixformel, und deshalb ist der eigentliche Löser in allen drei Sprachen sehr kurz.
Die C++-Version enthält zusätzlich explizite Korrektheitsprüfungen für kleine Eingaben. Sie kontrolliert den Beispielwert \(f(5,3)=4\), verifiziert, dass es bis \(n=10\) genau 5 ungerade Tripel gibt, vergleicht die geschlossene Paritätsregel für alle ungeraden \(n\le 1001\) mit einer direkten kombinatorischen Auswertung und prüft die Präfixsumme zusätzlich gegen eine brute-force Akkumulation auf einem größeren kleinen Bereich.
Die Python- und Java-Versionen enthalten nur die kompakte Produktionsrechnung, verwenden aber exakt dieselbe Mathematik.
Der eigentliche Solver läuft nur einmal über die Bitdarstellung von \(T=\lfloor(N-1)/4\rfloor\). Für eine 64-Bit-Grenze sind das höchstens 64 Schritte; die Laufzeit ist also \(O(\log N)\), der Speicherbedarf \(O(1)\).
Die optionalen brute-force- und Paritätsprüfungen der C++-Version dienen nur der Absicherung und gehören nicht zur eigentlichen Project-Euler-Berechnung.
Her \((n,k)\) çifti için \(f(n,k)\), \(\{1,2,\dots,n\}\) kümesinin toplamı tek olan \(k\) elemanlı alt kümelerinin sayısı olsun. Tek üçlü, \((n,k,f(n,k))\) üçlüsünün her üç bileşeninin de tek olduğu durumdur.
Hesaplanmak istenen büyüklük
$$A(N)=\#\{(n,k):1\le k\le n\le N,\ n,\ k,\ f(n,k)\text{ hepsi tek}\},$$
ve uygulamalar \(A(10^{12})\) değerini üretir. Doğrudan sayım mümkün değildir; asıl önemli olan \(f(n,k)\)'nin tam değeri değil, yalnızca tek mi çift mi olduğudur.
Çözüm iki katmandan oluşur. Önce \(f(n,k)\)'nin paritesi Pascal üçgenindeki bir binom katsayısının paritesine indirgenir. Ardından ortaya çıkan desen, ikili gösterimde çalışan kısa bir prefix hesabına dönüştürülür.
Tanımlayalım:
$$o=\left\lceil\frac n2\right\rceil,\qquad e=\left\lfloor\frac n2\right\rfloor.$$
Bir alt kümenin toplamı ancak ve ancak seçtiği tek sayı adedi tek ise tektir. Dolayısıyla
$$f(n,k)=\sum_{\substack{j=0\\ j\text{ tek}}}^{k}\binom{o}{j}\binom{e}{k-j}.$$
Tek bir üçlüde hem \(n\) hem de \(k\) tek olmak zorunda olduğundan sadece \(n=2m+1\) ve \(k=2r+1\) durumlarını incelemek yeterlidir. Bu halde \(o=m+1\) ve \(e=m\) olur; yani
$$f(2m+1,2r+1)=\sum_{\substack{j=0\\ j\text{ tek}}}^{2r+1}\binom{m+1}{j}\binom{m}{2r+1-j}.$$
Sadece pariteyle ilgilendiğimiz için alt küme boyutunu \(x\), toplamın tek-çift bilgisini ise \(y\) ile kodlayalım. Mod 2 altında ilgili polinom
$$P_n(x,y)=\prod_{i=1}^{n}\left(1+x\,y^{i\bmod 2}\right)=(1+x)^e(1+xy)^o,$$
şeklindedir ve \(y^2=1\) kuralı kullanılır. \(x^k y\) katsayısı tam olarak \(f(n,k)\bmod 2\)'dir; çünkü seçilen her tek sayı bir \(y\) çarpanı getirir ve yalnızca seçilen tek sayıların sayısının paritesi önemlidir.
\(n=2m+1\) için bu polinom
$$P_{2m+1}(x,y)=(1+x)^m(1+xy)^{m+1}$$
haline gelir. Şimdi belirleyici nokta \(m\)'nin tek mi çift mi olduğudur.
Eğer \(m=2t+1\) tek ise, mod 2 altında kare alma özelliğini kullanabiliriz:
$$ (1+x)^{2t+1}=(1+x)(1+x^2)^t,\qquad (1+xy)^{2t+2}=(1+x^2)^{t+1}. $$
Böylece
$$P_{4t+3}(x,y)=(1+x)(1+x^2)^{2t+1}$$
elde edilir ve bu ifadede hiç \(y\) terimi kalmaz. O halde bütün \(f(4t+3,2r+1)\) değerleri çifttir; bu tür \(n\)'ler tek üçlü üretmez.
Eğer \(m=2t\) çift ise
$$ (1+x)^{2t}=(1+x^2)^t,\qquad (1+xy)^{2t+1}=(1+x^2)^t(1+xy), $$
olur ve dolayısıyla
$$P_{4t+1}(x,y)=(1+x^2)^{2t}(1+xy).$$
Artık \(x^{2r+1}y\) katsayısı, \((1+x^2)^{2t}\) içindeki \(x^{2r}\) katsayısına eşittir; yani
$$f(4t+1,2r+1)\equiv \binom{2t}{r}\pmod 2.$$
Bunu \(m=(n-1)/2\) cinsinden yazarsak
$$f(2m+1,2r+1)\text{ tektir}\iff m\text{ çift ve }\binom{m}{r}\text{ tektir}.$$
Mod 2 için Lucas teoremi şunu söyler:
$$\binom{u}{v}\equiv 1\pmod 2\iff (v\ \&\ \sim u)=0.$$
Yani \(v\)'nin her 1 biti, \(u\)'nun bir 1 bitinin altında durmalıdır. Bu nedenle \(m=2t\) iken uygun \(r\) değerleri, \(m\)'nin ikili alt maskelerinin tam karşılığıdır.
Bu \(r\) sayısı, Pascal üçgeninin \(m\). satırındaki tek katsayı sayısına eşittir:
$$\#\{r:\binom{m}{r}\text{ tek}\}=2^{\operatorname{popcount}(m)}.$$
\(m=2t\) yalnızca ikili yazımın sonuna bir sıfır eklediği için \(\operatorname{popcount}(m)=\operatorname{popcount}(t)\). Dolayısıyla her \(t\) değeri
$$2^{\operatorname{popcount}(t)}$$
adet tek üçlü verir.
Katkı veren \(n\) değerleri tam olarak \(n=4t+1\) biçimindedir. Sınır \(N\) için en büyük \(t\)
$$t_{\max}=\left\lfloor\frac{N-1}{4}\right\rfloor$$
olur. Böylece tüm soru
$$A(N)=\sum_{t=0}^{t_{\max}}2^{\operatorname{popcount}(t)}$$
formülüne iner. Yani her katkı veren \(n\), \(4t+1\) biçimindedir ve o \(n\) için geçerli tek \(k\) değerleri, \(k=2r+1\) olup \(r\)'nin \(2t\)'nin bir ikili alt maskesi olduğu durumlardır.
Bu durumda
$$t_{\max}=\left\lfloor\frac{10-1}{4}\right\rfloor=2.$$
Dolayısıyla yalnızca \(t=0,1,2\) incelenir:
$$ 2^{\operatorname{popcount}(0)}=1,\qquad 2^{\operatorname{popcount}(1)}=2,\qquad 2^{\operatorname{popcount}(2)}=2. $$
Toplam \(1+2+2=5\) eder. Açıkça yazarsak:
\(t=0 \Rightarrow n=1\), dolayısıyla \(k=1\).
\(t=1 \Rightarrow n=5\); Pascal üçgeninin 2. satırında tek katsayılar \(r=0,2\) konumlarındadır, yani \(k=1,5\).
\(t=2 \Rightarrow n=9\); 4. satırda tek katsayılar \(r=0,4\) konumlarındadır, yani \(k=1,9\).
Referans uygulamadaki küçük kontrol de tam olarak bu 5 sonucu doğrular.
Şunu tanımlayalım:
$$S(T)=\sum_{t=0}^{T}2^{\operatorname{popcount}(t)}.$$
Uygulama, \(T\)'nin bitlerini en anlamlı bitten en aza doğru gezer. Diyelim ki sıradaki bit \(b\), bu bit \(T\)'de 1 ve daha üstte sabitlenmiş önekte \(s\) tane 1 biti var. Eğer bu biti 0 yapıp alt \(b\) biti serbest bırakırsak, her alt desen \(x\)
$$2^{s+\operatorname{popcount}(x)}$$
katkı verir. Tüm \(x\in[0,2^b)\) üzerinde toplayınca
$$2^s\sum_{x=0}^{2^b-1}2^{\operatorname{popcount}(x)}=2^s\cdot 3^b$$
elde edilir; çünkü her alt bit bağımsız olarak ya \(1\) ya da \(2\) faktörü getirir ve çarpım \((1+2)^b=3^b\) olur. Tüm 1 bitleri işlendiğinde, \(T\)'nin kendisi için bir son \(2^s\) terimi eklenir.
Böylece problem, en fazla 64 bit üzerinde yürüyen sabit bellekli bir hesaplamaya dönüşür.
C++, Python ve Java uygulamaları önce başlangıç sınırı \(N\)'yi
$$T=\left\lfloor\frac{N-1}{4}\right\rfloor$$
şeklinde dönüştürür; çünkü yalnızca \(n=4t+1\) biçimindeki değerler katkı verebilir. Bundan sonra yapılacak iş sadece \(S(T)=\sum_{t=0}^{T}2^{\operatorname{popcount}(t)}\) hesabıdır.
Üç uygulama da önce \(0\) ile \(63\) arasındaki bit konumları için \(3^b\) değerlerini hazırlar. Sonra \(T\)'nin bitlerini yukarıdan aşağıya tarar, önekte görülen 1 bitlerinin sayısını tutar ve her 1 bitte, o biti kapatıp alt kısmı serbest bırakan dalın katkısı olan \(2^s3^b\) terimini toplama ekler.
Tarama bittiğinde kalan öneğin kendisi \(2^s\) katkı yapar. Matematiksel prefix formülünün doğrudan kod karşılığı budur; bu yüzden her dildeki asıl çözücü çok kısa kalır.
C++ sürümü ek olarak küçük girdiler üzerinde açık doğrulamalar içerir. \(f(5,3)=4\) örneğini kontrol eder, \(n\le 10\) için tek üçlü sayısının 5 olduğunu doğrular, kapalı parite kuralını bütün tek \(n\le 1001\) değerleri için doğrudan kombinatoryal hesapla karşılaştırır ve prefix toplam yordamını da daha küçük değerlerde brute-force toplamla test eder.
Python ve Java sürümleri yalnızca sıkılaştırılmış nihai hesabı tutar, fakat kullandıkları matematik tamamen aynıdır.
Asıl çözücü yalnızca \(T=\lfloor(N-1)/4\rfloor\) sayısının bitlerini bir kez dolaşır. 64 bitlik bir sınır için bu en fazla 64 iterasyon demektir; dolayısıyla zaman karmaşıklığı \(O(\log N)\), bellek kullanımı \(O(1)\)'dir.
C++ sürümündeki opsiyonel brute-force ve parite doğrulamaları yalnızca güvenlik amaçlıdır; ana Project Euler hesabının parçası değildir.
Para cada par \((n,k)\), sea \(f(n,k)\) el número de subconjuntos de tamaño \(k\) de \(\{1,2,\dots,n\}\) cuya suma es impar. Un triplete impar es entonces un triplete \((n,k,f(n,k))\) en el que las tres entradas son impares.
La cantidad que se debe calcular es
$$A(N)=\#\{(n,k):1\le k\le n\le N,\ n,\ k,\ f(n,k)\text{ son impares}\},$$
y las implementaciones evalúan \(A(10^{12})\). Una enumeración directa es inviable; la idea central es determinar solo la paridad de \(f(n,k)\), no su valor exacto.
La solución tiene dos capas. Primero se reduce la paridad de \(f(n,k)\) a la paridad de un coeficiente binomial. Después, el patrón resultante se suma mediante un prefijo calculado con bits.
Definamos
$$o=\left\lceil\frac n2\right\rceil,\qquad e=\left\lfloor\frac n2\right\rfloor.$$
Un subconjunto tiene suma impar exactamente cuando contiene un número impar de elementos impares. Por tanto,
$$f(n,k)=\sum_{\substack{j=0\\ j\text{ impar}}}^{k}\binom{o}{j}\binom{e}{k-j}.$$
Como un triplete impar exige que \(n\) y \(k\) también sean impares, solo hace falta estudiar \(n=2m+1\) y \(k=2r+1\). Entonces \(o=m+1\) y \(e=m\), así que
$$f(2m+1,2r+1)=\sum_{\substack{j=0\\ j\text{ impar}}}^{2r+1}\binom{m+1}{j}\binom{m}{2r+1-j}.$$
Para estudiar solo la paridad, codificamos el tamaño del subconjunto con \(x\) y la paridad de la suma con \(y\). Módulo 2, el polinomio relevante es
$$P_n(x,y)=\prod_{i=1}^{n}\left(1+x\,y^{i\bmod 2}\right)=(1+x)^e(1+xy)^o,$$
con la regla \(y^2=1\). El coeficiente de \(x^k y\) es exactamente \(f(n,k)\bmod 2\), porque cada número impar elegido aporta un factor \(y\) y solo importa la paridad de cuántos se eligen.
Para \(n=2m+1\), esto se convierte en
$$P_{2m+1}(x,y)=(1+x)^m(1+xy)^{m+1}.$$
Ahora hay que distinguir según la paridad de \(m\).
Si \(m=2t+1\) es impar, entonces en módulo 2 podemos reagrupar cuadrados:
$$ (1+x)^{2t+1}=(1+x)(1+x^2)^t,\qquad (1+xy)^{2t+2}=(1+x^2)^{t+1}. $$
De aquí resulta
$$P_{4t+3}(x,y)=(1+x)(1+x^2)^{2t+1},$$
que no contiene ningún término con \(y\). Por lo tanto, todo \(f(4t+3,2r+1)\) es par y esos valores de \(n\) no generan tripletes impares.
Si en cambio \(m=2t\) es par, entonces
$$ (1+x)^{2t}=(1+x^2)^t,\qquad (1+xy)^{2t+1}=(1+x^2)^t(1+xy), $$
y por ello
$$P_{4t+1}(x,y)=(1+x^2)^{2t}(1+xy).$$
El coeficiente de \(x^{2r+1}y\) pasa a ser el coeficiente de \(x^{2r}\) en \((1+x^2)^{2t}\), es decir,
$$f(4t+1,2r+1)\equiv \binom{2t}{r}\pmod 2.$$
Equivalente, usando \(m=(n-1)/2\):
$$f(2m+1,2r+1)\text{ es impar}\iff m\text{ es par y }\binom{m}{r}\text{ es impar}.$$
Módulo 2, el teorema de Lucas dice que
$$\binom{u}{v}\equiv 1\pmod 2\iff (v\ \&\ \sim u)=0.$$
Es decir, cada bit 1 de \(v\) debe estar contenido en un bit 1 de \(u\). Así, cuando \(m=2t\), los valores válidos de \(r\) son exactamente las submáscaras binarias de \(m\).
La cantidad de esos \(r\) coincide con el número de entradas impares en la fila \(m\) del triángulo de Pascal:
$$\#\{r:\binom{m}{r}\text{ impar}\}=2^{\operatorname{popcount}(m)}.$$
Como \(m=2t\) solo añade un cero final en binario, \(\operatorname{popcount}(m)=\operatorname{popcount}(t)\). Cada \(t\) aporta entonces
$$2^{\operatorname{popcount}(t)}$$
tripletes impares.
Los valores de \(n\) que contribuyen son exactamente \(n=4t+1\). Para una cota \(N\), el mayor \(t\) posible es
$$t_{\max}=\left\lfloor\frac{N-1}{4}\right\rfloor.$$
Así, toda la pregunta se reduce a
$$A(N)=\sum_{t=0}^{t_{\max}}2^{\operatorname{popcount}(t)}.$$
Esto describe por completo los tripletes impares: cada \(n\) útil tiene la forma \(4t+1\), y para ese \(n\), los \(k\) impares válidos son exactamente los de la forma \(k=2r+1\) donde \(r\) es una submáscara binaria de \(2t\).
Aquí
$$t_{\max}=\left\lfloor\frac{10-1}{4}\right\rfloor=2.$$
Solo hay que mirar \(t=0,1,2\):
$$ 2^{\operatorname{popcount}(0)}=1,\qquad 2^{\operatorname{popcount}(1)}=2,\qquad 2^{\operatorname{popcount}(2)}=2. $$
La suma es \(1+2+2=5\). En términos concretos:
\(t=0 \Rightarrow n=1\), con \(k=1\).
\(t=1 \Rightarrow n=5\); la fila 2 del triángulo de Pascal tiene entradas impares en \(r=0,2\), así que \(k=1,5\).
\(t=2 \Rightarrow n=9\); la fila 4 tiene entradas impares en \(r=0,4\), así que \(k=1,9\).
Ese total 5 coincide con la comprobación pequeña incluida en la implementación de referencia.
Definamos
$$S(T)=\sum_{t=0}^{T}2^{\operatorname{popcount}(t)}.$$
La implementación recorre los bits de \(T\) desde el más significativo hacia abajo. Supongamos que el bit actual es \(b\), que en \(T\) vale 1 y que el prefijo superior ya contiene \(s\) bits encendidos. Si ponemos ese bit en 0 y dejamos libres los \(b\) bits inferiores, cada patrón inferior \(x\) aporta
$$2^{s+\operatorname{popcount}(x)}.$$
Al sumar todos los \(x\in[0,2^b)\) obtenemos
$$2^s\sum_{x=0}^{2^b-1}2^{\operatorname{popcount}(x)}=2^s\cdot 3^b,$$
porque cada bit inferior contribuye independientemente con un factor \(1\) o \(2\), y el producto total es \((1+2)^b=3^b\). Después de procesar todos los bits 1, un término final \(2^s\) contabiliza el propio \(T\).
Así, el problema completo queda reducido a un recorrido de como mucho 64 posiciones binarias y memoria constante.
Las implementaciones en C++, Python y Java sustituyen primero la cota \(N\) por
$$T=\left\lfloor\frac{N-1}{4}\right\rfloor,$$
porque solo pueden contribuir valores de la forma \(n=4t+1\). A partir de ahí, la tarea consiste únicamente en calcular \(S(T)=\sum_{t=0}^{T}2^{\operatorname{popcount}(t)}\).
Las tres versiones precomputan \(3^b\) para posiciones de bit entre \(0\) y \(63\). Luego recorren los bits de \(T\) de arriba abajo, mantienen el número de unos ya fijados en el prefijo y, cada vez que encuentran un bit activo, añaden el aporte \(2^s3^b\) correspondiente a la rama donde ese bit se apaga y el sufijo restante queda libre.
Al terminar el recorrido, el propio prefijo restante añade \(2^s\). Esa es la traducción directa de la fórmula matemática del prefijo, y por eso el solucionador final es muy compacto en los tres lenguajes.
La versión en C++ incorpora además comprobaciones explícitas sobre entradas pequeñas. Verifica el valor de muestra \(f(5,3)=4\), comprueba que hay exactamente 5 tripletes impares hasta \(n=10\), contrasta la regla cerrada de paridad con una evaluación combinatoria directa para todos los \(n\) impares hasta 1001 y prueba también la rutina del prefijo frente a una suma bruta en un rango grande pero manejable.
Las versiones en Python y Java conservan solo el cálculo compacto final, aunque implementan exactamente la misma matemática.
El solucionador real hace un único recorrido por la representación binaria de \(T=\lfloor(N-1)/4\rfloor\). Para una cota de 64 bits eso significa como mucho 64 iteraciones, así que el tiempo es \(O(\log N)\) y la memoria es \(O(1)\).
Las rutinas opcionales de fuerza bruta y validación de paridad de la versión en C++ son solo comprobaciones de seguridad y no forman parte del cálculo principal del problema.
对每一对 \((n,k)\)，记 \(f(n,k)\) 为从 \(\{1,2,\dots,n\}\) 中选出 \(k\) 个数且元素和为奇数的子集个数。所谓 奇三元组，就是 \((n,k,f(n,k))\) 这三个量本身都为奇数。
题目要求计算
$$A(N)=\#\{(n,k):1\le k\le n\le N,\ n,\ k,\ f(n,k)\text{ 全都为奇数}\},$$
而三个实现最终求的是 \(A(10^{12})\)。显然不可能直接枚举所有 \((n,k)\) 并逐个计算 \(f(n,k)\)。真正有效的做法是只追踪 \(f(n,k)\) 的奇偶性，并把它压缩成一个二项式系数的按位条件。
整个推导分成两层。第一层把“奇和子集个数的奇偶性”化成 Pascal 三角形中某个二项式系数的奇偶性；第二层把全局计数化成一个只依赖二进制中 1 的个数的前缀和。
设
$$o=\left\lceil\frac n2\right\rceil,\qquad e=\left\lfloor\frac n2\right\rfloor.$$
在 \(\{1,\dots,n\}\) 中，奇数共有 \(o\) 个，偶数共有 \(e\) 个。一个 \(k\) 元子集的总和为奇数，当且仅当它选中的奇数个数是奇数。因此有
$$f(n,k)=\sum_{\substack{j=0\\ j\text{ 为奇}}}^{k}\binom{o}{j}\binom{e}{k-j}.$$
由于奇三元组要求 \(n\) 和 \(k\) 本身也必须是奇数，所以只需要考虑
$$n=2m+1,\qquad k=2r+1.$$
这时 \(o=m+1\)、\(e=m\)，于是
$$f(2m+1,2r+1)=\sum_{\substack{j=0\\ j\text{ 为奇}}}^{2r+1}\binom{m+1}{j}\binom{m}{2r+1-j}.$$
为了只研究奇偶性，把子集大小用 \(x\) 记录，把子集和的奇偶性用 \(y\) 记录。在模 2 的世界里，可以写出
$$P_n(x,y)=\prod_{i=1}^{n}\left(1+x\,y^{i\bmod 2}\right)=(1+x)^e(1+xy)^o,$$
并规定 \(y^2=1\)。这样做的含义是：每选一个偶数，只贡献一个 \(x\)；每选一个奇数，贡献一个 \(x\) 和一个 \(y\)。因为只关心奇偶，所以两个 \(y\) 抵消成 1。于是 \(x^k y\) 的系数恰好就是 \(f(n,k)\bmod 2\)。
对于奇数 \(n=2m+1\)，上述多项式化为
$$P_{2m+1}(x,y)=(1+x)^m(1+xy)^{m+1}.$$
接下来只要区分 \(m\) 的奇偶性即可。
若 \(m=2t+1\) 是奇数，那么在模 2 下可以利用平方结构：
$$ (1+x)^{2t+1}=(1+x)(1+x^2)^t,\qquad (1+xy)^{2t+2}=(1+x^2)^{t+1}. $$
所以
$$P_{4t+3}(x,y)=(1+x)(1+x^2)^{2t+1}.$$
这个表达式里已经没有任何 \(y\) 项，因此所有 \(f(4t+3,2r+1)\) 都是偶数。也就是说，凡是 \(n\equiv 3\pmod 4\) 的情况全部淘汰。
若 \(m=2t\) 是偶数，则
$$ (1+x)^{2t}=(1+x^2)^t,\qquad (1+xy)^{2t+1}=(1+x^2)^t(1+xy), $$
于是
$$P_{4t+1}(x,y)=(1+x^2)^{2t}(1+xy).$$
现在 \(x^{2r+1}y\) 的系数等于 \((1+x^2)^{2t}\) 中 \(x^{2r}\) 的系数，也就是
$$f(4t+1,2r+1)\equiv \binom{2t}{r}\pmod 2.$$
用 \(m=(n-1)/2\) 重新表述，就是
$$f(2m+1,2r+1)\text{ 为奇数}\iff m\text{ 为偶数且 }\binom{m}{r}\text{ 为奇数}.$$
对模 2 而言，Lucas 定理给出
$$\binom{u}{v}\equiv 1\pmod 2\iff (v\ \&\ \sim u)=0.$$
也就是说，\(v\) 的每一个 1 位都必须出现在 \(u\) 的某个 1 位之下。所以当 \(m=2t\) 时，所有可行的 \(r\) 正好就是 \(m\) 的二进制子掩码。
这样的 \(r\) 有多少个？这正是 Pascal 三角形第 \(m\) 行中奇数项的个数：
$$\#\{r:\binom{m}{r}\text{ 为奇数}\}=2^{\operatorname{popcount}(m)}.$$
而 \(m=2t\) 只是把 \(t\) 的二进制整体左移一位，因此 \(\operatorname{popcount}(m)=\operatorname{popcount}(t)\)。所以每个 \(t\) 的贡献就是
$$2^{\operatorname{popcount}(t)}.$$
能够产生奇三元组的 \(n\) 恰好是
$$n=4t+1.$$
如果上界是 \(N\)，那么最大的 \(t\) 为
$$t_{\max}=\left\lfloor\frac{N-1}{4}\right\rfloor.$$
因此题目最终完全等价于
$$A(N)=\sum_{t=0}^{t_{\max}}2^{\operatorname{popcount}(t)}.$$
这已经把所有奇三元组描述得非常清楚了：每个有效的 \(n\) 都是 \(4t+1\) 的形式，而对这个 \(n\)，有效的奇数 \(k\) 恰好是 \(k=2r+1\)，其中 \(r\) 是 \(2t\) 的一个二进制子掩码。
当 \(N=10\) 时，
$$t_{\max}=\left\lfloor\frac{10-1}{4}\right\rfloor=2.$$
只需要考察 \(t=0,1,2\)：
$$ 2^{\operatorname{popcount}(0)}=1,\qquad 2^{\operatorname{popcount}(1)}=2,\qquad 2^{\operatorname{popcount}(2)}=2. $$
总数就是 \(1+2+2=5\)。逐项展开为：
\(t=0 \Rightarrow n=1\)，因此只有 \(k=1\)。
\(t=1 \Rightarrow n=5\)，Pascal 三角形第 2 行的奇数项位于 \(r=0,2\)，所以 \(k=1,5\)。
\(t=2 \Rightarrow n=9\)，第 4 行的奇数项位于 \(r=0,4\)，所以 \(k=1,9\)。
这与参考实现中的小规模校验完全一致：当 \(n\le 10\) 时，奇三元组总数确实是 5。
定义
$$S(T)=\sum_{t=0}^{T}2^{\operatorname{popcount}(t)}.$$
实现并不是逐个枚举 \(t\)，而是从高位到低位扫描 \(T\) 的二进制表示。设当前看到的位是 \(b\)，这一位在 \(T\) 中等于 1，并且更高位前缀里已经有 \(s\) 个 1。如果把当前位改成 0，而让下面的 \(b\) 位任意变化，那么每一个低位模式 \(x\) 的贡献都是
$$2^{s+\operatorname{popcount}(x)}.$$
对所有 \(x\in[0,2^b)\) 求和可得
$$2^s\sum_{x=0}^{2^b-1}2^{\operatorname{popcount}(x)}=2^s\cdot 3^b,$$
因为每一个低位都独立地贡献因子 \(1\) 或 \(2\)，全部乘起来就是 \((1+2)^b=3^b\)。所有 1 位处理完后，再额外加上 \(2^s\)，它对应的正是 \(T\) 自身。
这就把原题压缩成了一个长度不超过 64 的按位扫描过程，时间和空间都极小。
C++、Python 和 Java 实现都会先把原始上界 \(N\) 转成
$$T=\left\lfloor\frac{N-1}{4}\right\rfloor,$$
因为只有 \(n=4t+1\) 才会有贡献。从这一刻开始，任务已经不再是子集计数，而只是计算 \(S(T)=\sum_{t=0}^{T}2^{\operatorname{popcount}(t)}\)。
三个实现都会预先计算 \(3^0,3^1,\dots,3^{63}\)。然后从高位到低位扫描 \(T\) 的位模式，维护“当前前缀里有多少个 1 位”这个状态。每当遇到一个 1 位，就把“把这一位关掉、其余低位任取”对应的整块贡献 \(2^s3^b\) 加进答案。
扫描结束后，剩下的当前前缀本身再贡献一个 \(2^s\)。这正好对应数学推导中的前缀和拆分，所以 Python 和 Java 的最终代码都非常紧凑。
C++ 实现额外保留了一组小规模验证。它会检查样例值 \(f(5,3)=4\)，验证 \(n\le 10\) 时奇三元组总数为 5，把闭式奇偶规则与直接组合计数在所有奇数 \(n\le 1001\) 上逐项比对，并且用暴力前缀和去校验按位前缀算法在较大但可控范围内的正确性。
Python 和 Java 版本只保留了精简后的正式求解流程，但数学内容与 C++ 完全一致。
真正的求解器只扫描一次 \(T=\lfloor(N-1)/4\rfloor\) 的二进制表示。对 64 位整数来说，这意味着至多 64 次循环，因此时间复杂度是 \(O(\log N)\)，空间复杂度是 \(O(1)\)。
C++ 版本中的暴力与奇偶性校验只是额外的安全检查，不属于主求解过程。
Для каждой пары \((n,k)\) обозначим через \(f(n,k)\) количество \(k\)-элементных подмножеств множества \(\{1,2,\dots,n\}\), сумма элементов которых нечётна. Нечётный триплет означает, что все три числа в \((n,k,f(n,k))\) нечётны.
Нужно вычислить
$$A(N)=\#\{(n,k):1\le k\le n\le N,\ n,\ k,\ f(n,k)\text{ нечётны}\},$$
и реализации находят \(A(10^{12})\). Полный перебор невозможен, поэтому вся задача строится вокруг вычисления только чётности \(f(n,k)\), а не его точного значения.
Решение состоит из двух идей. Сначала чётность \(f(n,k)\) сводится к чётности одного биномиального коэффициента. Затем итоговый глобальный счёт сворачивается в короткую префиксную сумму, зависящую от количества единичных битов.
Положим
$$o=\left\lceil\frac n2\right\rceil,\qquad e=\left\lfloor\frac n2\right\rfloor.$$
Сумма элементов подмножества нечётна тогда и только тогда, когда в нём выбрано нечётное число нечётных элементов. Поэтому
$$f(n,k)=\sum_{\substack{j=0\\ j\text{ нечётно}}}^{k}\binom{o}{j}\binom{e}{k-j}.$$
Поскольку в нечётном триплете и \(n\), и \(k\) должны быть нечётными, достаточно рассматривать только
$$n=2m+1,\qquad k=2r+1.$$
Тогда \(o=m+1\) и \(e=m\), откуда
$$f(2m+1,2r+1)=\sum_{\substack{j=0\\ j\text{ нечётно}}}^{2r+1}\binom{m+1}{j}\binom{m}{2r+1-j}.$$
Чтобы следить только за чётностью, отметим размер подмножества переменной \(x\), а чётность суммы переменной \(y\). По модулю 2 получаем многочлен
$$P_n(x,y)=\prod_{i=1}^{n}\left(1+x\,y^{i\bmod 2}\right)=(1+x)^e(1+xy)^o,$$
где используется правило \(y^2=1\). Коэффициент при \(x^k y\) равен \(f(n,k)\bmod 2\): каждый выбранный нечётный элемент вносит множитель \(y\), и важна только чётность числа таких множителей.
Для нечётного \(n=2m+1\) имеем
$$P_{2m+1}(x,y)=(1+x)^m(1+xy)^{m+1}.$$
Дальше всё зависит от того, чётно ли \(m\).
Если \(m=2t+1\) нечётно, то по модулю 2 можно использовать квадратную структуру:
$$ (1+x)^{2t+1}=(1+x)(1+x^2)^t,\qquad (1+xy)^{2t+2}=(1+x^2)^{t+1}. $$
Следовательно,
$$P_{4t+3}(x,y)=(1+x)(1+x^2)^{2t+1},$$
и здесь вообще нет члена с \(y\). Значит, все значения \(f(4t+3,2r+1)\) чётны, и числа \(n\equiv 3\pmod 4\) в искомый ответ не входят.
Если же \(m=2t\) чётно, то
$$ (1+x)^{2t}=(1+x^2)^t,\qquad (1+xy)^{2t+1}=(1+x^2)^t(1+xy), $$
поэтому
$$P_{4t+1}(x,y)=(1+x^2)^{2t}(1+xy).$$
Коэффициент при \(x^{2r+1}y\) теперь равен коэффициенту при \(x^{2r}\) в \((1+x^2)^{2t}\), то есть
$$f(4t+1,2r+1)\equiv \binom{2t}{r}\pmod 2.$$
То же самое можно записать через \(m=(n-1)/2\):
$$f(2m+1,2r+1)\text{ нечётно}\iff m\text{ чётно и }\binom{m}{r}\text{ нечётно}.$$
По модулю 2 теорема Лукаса даёт критерий
$$\binom{u}{v}\equiv 1\pmod 2\iff (v\ \&\ \sim u)=0.$$
То есть каждый единичный бит числа \(v\) должен находиться под единичным битом числа \(u\). Поэтому при \(m=2t\) все допустимые \(r\) — это в точности двоичные подмаски числа \(m\).
Их количество совпадает с числом нечётных элементов в строке \(m\) треугольника Паскаля:
$$\#\{r:\binom{m}{r}\text{ нечётно}\}=2^{\operatorname{popcount}(m)}.$$
Но \(m=2t\) лишь добавляет справа один нулевой бит, поэтому \(\operatorname{popcount}(m)=\operatorname{popcount}(t)\). Значит, каждый \(t\) даёт
$$2^{\operatorname{popcount}(t)}$$
нечётных триплетов.
Все подходящие значения \(n\) имеют вид
$$n=4t+1.$$
При ограничении \(N\) максимальное \(t\) равно
$$t_{\max}=\left\lfloor\frac{N-1}{4}\right\rfloor.$$
Следовательно, вся задача сводится к формуле
$$A(N)=\sum_{t=0}^{t_{\max}}2^{\operatorname{popcount}(t)}.$$
Это уже полное описание всех нечётных триплетов: каждое работающее \(n\) имеет форму \(4t+1\), а для такого \(n\) допустимые нечётные \(k\) задаются формулой \(k=2r+1\), где \(r\) является двоичной подмаской числа \(2t\).
Здесь
$$t_{\max}=\left\lfloor\frac{10-1}{4}\right\rfloor=2.$$
Значит, нужно рассмотреть только \(t=0,1,2\):
$$ 2^{\operatorname{popcount}(0)}=1,\qquad 2^{\operatorname{popcount}(1)}=2,\qquad 2^{\operatorname{popcount}(2)}=2. $$
Сумма равна \(1+2+2=5\). Если расписать это явно:
\(t=0 \Rightarrow n=1\), поэтому \(k=1\).
\(t=1 \Rightarrow n=5\); в строке 2 треугольника Паскаля нечётные коэффициенты стоят при \(r=0,2\), значит \(k=1,5\).
\(t=2 \Rightarrow n=9\); в строке 4 нечётные коэффициенты стоят при \(r=0,4\), значит \(k=1,9\).
Это в точности совпадает с малой контрольной проверкой в эталонной реализации: для \(n\le 10\) существует ровно 5 нечётных триплетов.
Обозначим
$$S(T)=\sum_{t=0}^{T}2^{\operatorname{popcount}(t)}.$$
Реализация не перечисляет все \(t\), а проходит по битам числа \(T\) сверху вниз. Пусть текущий бит имеет номер \(b\), этот бит в \(T\) равен 1, а в уже зафиксированном старшем префиксе содержится \(s\) единичных битов. Если занулить текущий бит и разрешить всем младшим \(b\) битам свободно меняться, то каждый нижний шаблон \(x\) внесёт вклад
$$2^{s+\operatorname{popcount}(x)}.$$
Суммирование по всем \(x\in[0,2^b)\) даёт
$$2^s\sum_{x=0}^{2^b-1}2^{\operatorname{popcount}(x)}=2^s\cdot 3^b,$$
потому что каждый младший бит независимо даёт множитель либо \(1\), либо \(2\), а общий результат равен \((1+2)^b=3^b\). После обработки всех единичных битов остаётся добавить ещё \(2^s\) — это вклад самого числа \(T\).
Тем самым исходная задача сводится к битовому проходу длиной не более 64 шагов и постоянной памяти.
Реализации на C++, Python и Java сначала заменяют исходную границу \(N\) на
$$T=\left\lfloor\frac{N-1}{4}\right\rfloor,$$
потому что вклад возможен только от \(n=4t+1\). После этого задача уже выглядит как вычисление \(S(T)=\sum_{t=0}^{T}2^{\operatorname{popcount}(t)}\).
Все три версии заранее вычисляют значения \(3^b\) для битовых позиций от \(0\) до \(63\). Затем они просматривают биты числа \(T\) от старших к младшим, хранят количество единиц в уже просмотренном префиксе и при встрече с очередным установленным битом прибавляют вклад \(2^s3^b\), соответствующий ветви, где этот бит обнуляется, а оставшийся суффикс произволен.
После завершения прохода сам оставшийся префикс даёт последний вклад \(2^s\). Это точная программная реализация математической формулы для префикса, поэтому основной решатель во всех трёх языках получается очень компактным.
Версия на C++ дополнительно содержит набор проверок корректности на малых данных. Она проверяет образец \(f(5,3)=4\), убеждается, что число нечётных триплетов при \(n\le 10\) равно 5, сравнивает замкнутое правило для чётности с прямым комбинаторным вычислением для всех нечётных \(n\le 1001\), а также сверяет битовый алгоритм префиксной суммы с прямым накоплением на достаточно большом, но ещё небольшом диапазоне.
Реализации на Python и Java оставляют только компактное окончательное вычисление, но используют в точности ту же математику.
Основной решатель делает один проход по битовому представлению числа \(T=\lfloor(N-1)/4\rfloor\). Для 64-битной границы это не более 64 итераций, поэтому время работы равно \(O(\log N)\), а память — \(O(1)\).
Необязательные brute-force и проверки паритета в версии на C++ служат только для верификации и не входят в основное вычисление задачи.
لكل زوج \((n,k)\)، نرمز بـ \(f(n,k)\) إلى عدد المجموعات الجزئية ذات الحجم \(k\) من \(\{1,2,\dots,n\}\) التي يكون مجموع عناصرها فرديًا. ويُسمّى الثلاثي الفردي ثلاثيًا من الشكل \((n,k,f(n,k))\) تكون فيه القيم الثلاث كلها فردية.
المطلوب هو حساب
$$A(N)=\#\{(n,k):1\le k\le n\le N,\ n,\ k,\ f(n,k)\text{ odd}\},$$
وتقوم التطبيقات بحساب \(A(10^{12})\). لا يمكن التعامل مع المسألة بعدٍّ مباشر، لذا الفكرة الحاسمة هي الاكتفاء بتحديد فردية \(f(n,k)\) أو زوجيتها بدلًا من حسابها حسابًا كاملًا.
الحل يتكون من مرحلتين. أولًا نختزل فردية \(f(n,k)\) إلى فردية معامل ثنائي واحد. ثم نحوّل العد الكلي إلى مجموع بادئ قصير يعتمد فقط على عدد البتات المساوية لـ 1 في الكتابة الثنائية.
لنكتب
$$o=\left\lceil\frac n2\right\rceil,\qquad e=\left\lfloor\frac n2\right\rfloor.$$
يكون مجموع عناصر مجموعة جزئية فرديًا إذا وفقط إذا احتوت على عدد فردي من العناصر الفردية. لذلك
$$f(n,k)=\sum_{\substack{j=0\\ j\text{ odd}}}^{k}\binom{o}{j}\binom{e}{k-j}.$$
وبما أن الثلاثي الفردي يشترط أن يكون كل من \(n\) و\(k\) فرديًا أيضًا، فتكفي دراسة الحالة
$$n=2m+1,\qquad k=2r+1.$$
عندئذٍ يكون \(o=m+1\) و\(e=m\)، ومن ثم
$$f(2m+1,2r+1)=\sum_{\substack{j=0\\ j\text{ odd}}}^{2r+1}\binom{m+1}{j}\binom{m}{2r+1-j}.$$
لأننا نهتم بالفردية فقط، نستخدم \(x\) لتتبع حجم المجموعة و\(y\) لتتبع فردية مجموع عناصرها. بترديد 2 نحصل على
$$P_n(x,y)=\prod_{i=1}^{n}\left(1+x\,y^{i\bmod 2}\right)=(1+x)^e(1+xy)^o,$$
مع القاعدة \(y^2=1\). معامل \(x^k y\) يساوي تمامًا \(f(n,k)\bmod 2\)، لأن كل عنصر فردي مختار يضيف عامل \(y\)، ولا يهم إلا فردية عدد هذه العوامل.
ولما كان \(n=2m+1\)، يصبح هذا
$$P_{2m+1}(x,y)=(1+x)^m(1+xy)^{m+1}.$$
ومن هنا تصبح فردية \(m\) هي النقطة الفاصلة.
إذا كان \(m=2t+1\) فرديًا، فيمكن استغلال بنية التربيع بترديد 2:
$$ (1+x)^{2t+1}=(1+x)(1+x^2)^t,\qquad (1+xy)^{2t+2}=(1+x^2)^{t+1}. $$
إذن
$$P_{4t+3}(x,y)=(1+x)(1+x^2)^{2t+1},$$
ولا يظهر في هذا التعبير أي حد يحتوي على \(y\). لذلك تكون جميع القيم \(f(4t+3,2r+1)\) زوجية، أي إن الحالات التي فيها \(n\equiv 3\pmod 4\) لا تنتج أي ثلاثي فردي.
أما إذا كان \(m=2t\) زوجيًا، فلدينا
$$ (1+x)^{2t}=(1+x^2)^t,\qquad (1+xy)^{2t+1}=(1+x^2)^t(1+xy), $$
ومن ثم
$$P_{4t+1}(x,y)=(1+x^2)^{2t}(1+xy).$$
وعندئذ يصبح معامل \(x^{2r+1}y\) هو معامل \(x^{2r}\) في \((1+x^2)^{2t}\)، أي
$$f(4t+1,2r+1)\equiv \binom{2t}{r}\pmod 2.$$
وبصياغة مكافئة باستخدام \(m=(n-1)/2\):
$$f(2m+1,2r+1)\text{ odd}\iff m\text{ is even and }\binom{m}{r}\text{ is odd}.$$
بترديد 2 تعطينا مبرهنة لوكاس الشرط التالي:
$$\binom{u}{v}\equiv 1\pmod 2\iff (v\ \&\ \sim u)=0.$$
أي إن كل بت يساوي 1 في \(v\) يجب أن يقع تحت بت يساوي 1 في \(u\). ولهذا، عندما يكون \(m=2t\)، فإن قيم \(r\) المسموح بها هي بالضبط الأقنعة الثنائية الجزئية للعدد \(m\).
وعدد هذه القيم يساوي عدد المعاملات الفردية في الصف \(m\) من مثلث باسكال:
$$\#\{r:\binom{m}{r}\text{ odd}\}=2^{\operatorname{popcount}(m)}.$$
ولأن \(m=2t\) يضيف صفرًا واحدًا في نهاية الكتابة الثنائية، فإن \(\operatorname{popcount}(m)=\operatorname{popcount}(t)\). إذن يساهم كل \(t\) بعدد
$$2^{\operatorname{popcount}(t)}$$
من الثلاثيات الفردية.
القيم الوحيدة لـ \(n\) التي تعطي مساهمة هي
$$n=4t+1.$$
ومع حد أعلى \(N\)، يكون أكبر \(t\) ممكن هو
$$t_{\max}=\left\lfloor\frac{N-1}{4}\right\rfloor.$$
وبذلك تختزل المسألة كلها إلى الصيغة
$$A(N)=\sum_{t=0}^{t_{\max}}2^{\operatorname{popcount}(t)}.$$
وهذا يصف جميع الثلاثيات الفردية وصفًا كاملًا: كل \(n\) صالح له الصورة \(4t+1\)، ولكل \(n\) من هذا النوع تكون قيم \(k\) الفردية الصالحة هي بالضبط \(k=2r+1\) حيث يكون \(r\) قناعًا ثنائيًا جزئيًا للعدد \(2t\).
في هذه الحالة
$$t_{\max}=\left\lfloor\frac{10-1}{4}\right\rfloor=2.$$
إذًا نحتاج فقط إلى \(t=0,1,2\):
$$ 2^{\operatorname{popcount}(0)}=1,\qquad 2^{\operatorname{popcount}(1)}=2,\qquad 2^{\operatorname{popcount}(2)}=2. $$
المجموع هو \(1+2+2=5\). وبالتفصيل:
\(t=0 \Rightarrow n=1\)، ومن ثم \(k=1\).
\(t=1 \Rightarrow n=5\)، وفي الصف 2 من مثلث باسكال تقع المعاملات الفردية عند \(r=0,2\)، ولذلك \(k=1,5\).
\(t=2 \Rightarrow n=9\)، وفي الصف 4 تقع المعاملات الفردية عند \(r=0,4\)، ولذلك \(k=1,9\).
وهذا يطابق تمامًا فحص العينة الصغيرة الموجود في التنفيذ المرجعي: يوجد 5 ثلاثيات فردية بالضبط عندما \(n\le 10\).
لنعرّف
$$S(T)=\sum_{t=0}^{T}2^{\operatorname{popcount}(t)}.$$
لا تقوم الخوارزمية بعدّ جميع قيم \(t\) واحدةً واحدة، بل تمر على بتات \(T\) من الأعلى إلى الأسفل. إذا كان البت الحالي هو \(b\)، وكانت قيمته في \(T\) تساوي 1، وكان في البادئة العليا \(s\) بتات تساوي 1، فإن جعل هذا البت يساوي 0 وترك البتات الأدنى حرة يعني أن كل نمط سفلي \(x\) يضيف
$$2^{s+\operatorname{popcount}(x)}.$$
وبالجمع على كل \(x\in[0,2^b)\) نحصل على
$$2^s\sum_{x=0}^{2^b-1}2^{\operatorname{popcount}(x)}=2^s\cdot 3^b,$$
لأن كل بت سفلي يساهم مستقلًا بعامل \(1\) أو \(2\)، فيكون الناتج الكلي \((1+2)^b=3^b\). وبعد معالجة جميع البتات التي تساوي 1، نضيف حدًا أخيرًا \(2^s\) يمثل \(T\) نفسه.
وهكذا تتحول المسألة كلها إلى مرور ثنائي قصير لا يتجاوز 64 خطوة مع ذاكرة ثابتة.
تبدأ تطبيقات C++ وPython وJava بتحويل الحد \(N\) إلى
$$T=\left\lfloor\frac{N-1}{4}\right\rfloor,$$
لأن القيم الوحيدة الممكنة لـ \(n\) هي \(4t+1\). وبعد ذلك تصبح المهمة مجرد حساب \(S(T)=\sum_{t=0}^{T}2^{\operatorname{popcount}(t)}\).
تقوم التطبيقات الثلاثة بتهيئة القيم \(3^b\) مسبقًا للمواضع الثنائية من \(0\) إلى \(63\). ثم تمسح بتات \(T\) من الأعلى إلى الأسفل، وتحافظ على عدد البتات المساوية لـ 1 في البادئة الحالية، وكلما صادفت بتًا مفعّلًا أضافت المساهمة \(2^s3^b\) الخاصة بالفرع الذي نطفئ فيه ذلك البت ونترك بقية اللاحقة حرة.
بعد انتهاء المسح، تضاف مساهمة أخيرة مقدارها \(2^s\) تخص البادئة نفسها. هذا هو التطبيق البرمجي المباشر لصيغة المجموع البادئ، ولهذا تبقى النواة الحسابية قصيرة جدًا في كل اللغات.
يحتوي تنفيذ C++ أيضًا على مجموعة من فحوص السلامة على المدخلات الصغيرة. فهو يتحقق من القيمة \(f(5,3)=4\)، ويفحص أن عدد الثلاثيات الفردية حتى \(n=10\) يساوي 5، ويقارن القاعدة المغلقة الخاصة بالفردية مع حساب تجميعي مباشر لكل \(n\) فردي حتى 1001، كما يختبر خوارزمية المجموع البادئ بمقارنتها مع تجميع مباشر على مجال كبير لكنه ما يزال صغيرًا بما يكفي للتحقق.
أما تطبيقا Python وJava فيحتفظان بالحساب المختصر النهائي فقط، لكنهما يطبّقان الرياضيات نفسها تمامًا.
الجزء الأساسي من الحل لا يفعل أكثر من المرور مرة واحدة على التمثيل الثنائي للعدد \(T=\lfloor(N-1)/4\rfloor\). ومع حدود من 64 بتًا، فهذا يعني ما لا يزيد على 64 دورة، ولذلك يكون التعقيد الزمني \(O(\log N)\) والتعقيد المكاني \(O(1)\).
أما الفحوص الاختيارية المباشرة وفحوص التحقق من الفردية في نسخة C++ فليست جزءًا من الحساب الأساسي للمسألة، وإنما وسائل تحقق إضافية فقط.