Project Euler 152 asks for the number of subsets \(S \subseteq \{2,3,\dots,80\}\) such that
$$\sum_{n \in S}\frac{1}{n^2}=\frac12.$$
A brute-force search would inspect \(2^{79}\) subsets, so the real task is to discover arithmetic structure that forbids almost all candidates before any global enumeration begins. The implementations do exactly that: they use local congruence conditions coming from large odd prime powers, turn the surviving rational equation into an integer subset-sum problem, combine the constrained prime blocks by convolution, and finish the remaining search with meet-in-the-middle.
The key point is that the identity \(\sum 1/n^2 = 1/2\) is rigid modulo \(p^2\) for carefully chosen odd primes. Once those local conditions are enforced, the set of viable denominators becomes small enough that the exact count can be obtained with a structured subset-sum computation.
Fix an odd prime \(p\), and let \(P_p=p^e\) be the largest power of \(p\) not exceeding 80. For the actual problem, examples are
$$P_3=27,\qquad P_5=25,\qquad P_7=49,\qquad P_{13}=13.$$
Now define the top group
$$G_p=\{n\in\{2,\dots,80\}: P_p \mid n\}.$$
Let \(M=\operatorname{lcm}(2,3,\dots,80)\). Since \(v_p(M)=e\), we may write \(M=P_pM_p\) with \(p\nmid M_p\). Multiplying the target equation by \(2M^2\) gives
$$\sum_{n\in S} 2\left(\frac{M}{n}\right)^2=M^2.$$
Reduce this congruence modulo \(p^2\). If \(n\notin G_p\), then \(n\) contains fewer than \(e\) copies of \(p\), so \((M/n)^2\) is divisible by \(p^2\), and that term vanishes modulo \(p^2\). If \(n=P_pm\in G_p\), then \(p\nmid m\) and the surviving term is \(2(M_p/m)^2\). Because \(2M_p^2\) is invertible modulo \(p^2\), the global identity forces the local condition
$$\sum_{n\in S\cap G_p}\left(\frac{n}{P_p}\right)^{-2}\equiv 0 \pmod{p^2},$$
where \(x^{-2}\) means the inverse of \(x^2\) modulo \(p^2\). This explains why the implementations inspect only the numbers in the top group for each odd prime: every other denominator is invisible mod \(p^2\) at that prime.
The prime \(2\) is deliberately excluded from this filter. After multiplying by \(2M^2\), the factor 2 is not invertible modulo \(4\), so the same clean argument does not apply. Powers of 2 are therefore left to the later global subset-sum stage.
For each odd prime, the implementations enumerate every subset of \(G_p\) and keep only the masks satisfying the congruence above. These groups are tiny, so exhaustive local search is cheap. For \(L=80\), the pruning is extremely strong.
Most odd-prime top groups allow only the empty choice. For example, \(G_3=\{27,54\}\), \(G_5=\{25,50,75\}\), \(G_7=\{49\}\), and \(G_{11}=\{11,22,33,44,55,66,77\}\) all collapse immediately: no non-empty subset satisfies the required congruence modulo \(p^2\).
The only nontrivial group is
$$G_{13}=\{13,26,39,52,65,78\}.$$
Here the valid local choices are exactly \(\varnothing\) and \(\{13,39,52\}\). Indeed, after normalization by 13 the selected residues are \(1,3,4\), and
$$1^{-2}+3^{-2}+4^{-2}\equiv 1+94+74=169\equiv 0 \pmod{169}.$$
So the entire 13-part of any global solution is a binary decision: either choose none of these numbers, or choose the three-number block \(\{13,39,52\}\). Numbers such as 26, 65, and 78 never appear because they belong to no valid local mask.
After all odd-prime filters are applied, the candidate set shrinks from 79 numbers down to 36. Of those 36, three belong to the single nontrivial 13-group, and the other 33 are unconstrained by any odd-prime top group and become the free part of the search.
Once impossible denominators are removed, let \(C\) be the least common multiple of all surviving candidates. For each remaining \(n\), define
$$w_n=\frac{C^2}{n^2},\qquad T=\frac{C^2}{2}.$$
Then the original equation is equivalent to the exact integer subset-sum equation
$$\sum_{n\in S} w_n=T.$$
This conversion is crucial. It removes all rational arithmetic from the search itself: every valid local prime choice becomes an integer partial sum, and the final counting problem is purely additive.
For each active odd-prime group \(g\), let \(A_g(t)\) denote the number of valid masks in that group whose total integer weight is \(t\). Because the groups are disjoint for this \(L=80\) instance, their contributions can be combined independently.
The implementations use the convolution recurrence
$$B_0(0)=1,\qquad B_{r+1}(u)=\sum_t B_r(u-t)\,A_{r+1}(t),$$
where \(B_r(u)\) counts how many ways the first \(r\) active groups can contribute total weight \(u\). This is not yet the full answer; it is only the count of all legal choices forced by the odd-prime congruences.
For Problem 152, that recurrence is almost trivial after pruning, because only the 13-group survives as an active group. Its contribution map has just two entries: one for choosing nothing from \(G_{13}\), and one for choosing the block \(\{13,39,52\}\).
The remaining 33 denominators lie outside all odd-prime top groups. Let their integer weights be \(f_1,\dots,f_{33}\). A direct search over these numbers would still cost \(2^{33}\) subset checks, so the implementations split them into two halves, of sizes 16 and 17.
Define \(L(x)\) as the number of left-half subsets with weight sum \(x\), and \(R(y)\) as the number of right-half subsets with weight sum \(y\). Then the final number of solutions is
$$\sum_u B(u)\sum_x L(x)\,R(T-u-x).$$
In words: choose a legal contribution from the constrained odd-prime groups, choose a subset from the left free half, and ask whether the right free half can supply the exact missing weight. Hash tables make the final lookup fast.
The \(13\)-group example above is the cleanest illustration of the local filter at the real limit \(L=80\): it shows that the congruence step does not merely remove isolated denominators, but can force a whole block decision.
A smaller checkpoint instance also appears in the implementations. For \(L=45\), one valid identity is
$$\frac12=\frac1{2^2}+\frac1{3^2}+\frac1{4^2}+\frac1{5^2}+\frac1{7^2}+\frac1{12^2}+\frac1{15^2}+\frac1{20^2}+\frac1{28^2}+\frac1{35^2}.$$
Inside the \(7\)-group for \(L=45\), the chosen denominators are \(\{7,28,35\}\). After dividing by 7 they become \(\{1,4,5\}\), and
$$1^{-2}+4^{-2}+5^{-2}\equiv 1+46+2=49\equiv 0 \pmod{49}.$$
So the local congruence is genuinely visible in an explicit solution. The point of the full algorithm is that it enforces all such local conditions first and only then solves the remaining global sum exactly.
The C++, Python, and Java implementations first sieve the primes up to the limit, determine the largest power \(P_p\le 80\) for each odd prime, and form the corresponding top groups \(G_p\). Every subset of each small group is tested modulo \(p^2\) by using modular inverses of the normalized squares. From this, the implementation learns two things: which local masks are legal, and which denominators never occur in any legal mask and can therefore be discarded immediately.
After pruning, the implementation computes a common denominator \(C\), turns every surviving reciprocal square into the integer weight \(C^2/n^2\), and sets the target to \(C^2/2\). Each valid mask in each active odd-prime group is converted into a partial weight sum, and the constrained groups are combined by the convolution recurrence described above. The result is a map from constrained partial sum to the number of ways to obtain it.
The remaining free weights are split into two halves. Each implementation enumerates all subset sums of the left half and all subset sums of the right half, storing multiplicities rather than raw subset lists. The final answer is obtained by scanning the left sums and the constrained sums and looking up the unique complementary right sum needed to hit the target.
The C++ and Python implementations can parallelize this final matching pass when the table is large enough. The Java implementation follows the same arithmetic, but keeps the control flow single-threaded and compact. The C++ and Python versions also validate the method on smaller checkpoint cases, including three explicit identities for \(L=45\), the fact that there are exactly three solutions up to 45, and a brute-force comparison at \(L=18\).
If the active odd-prime groups have sizes \(g_1,g_2,\dots\), building the local legality tables costs
$$O\!\left(\sum_i 2^{g_i}g_i\right),$$
because each group is searched exhaustively. If \(A_i\) is the number of distinct weighted options produced by group \(i\), the constrained-group convolution costs roughly \(O\!\left(\sum_i |B_{i-1}|\,|A_i|\right)\), where \(|B_{i-1}|\) is the number of partial sums already accumulated.
The dominant phase is the meet-in-the-middle search on the free part. If \(f\) free denominators remain, the subset-sum tables require about \(2^{\lfloor f/2\rfloor}+2^{\lceil f/2\rceil}\) subset enumerations, plus hash lookups to match complementary sums. For the actual Euler 152 instance, the local filters reduce the problem to one nontrivial odd-prime block and \(f=33\) free numbers, so the global search is closer to \(2^{16}+2^{17}\) than to \(2^{79}\).
Memory usage is dominated by the hash tables for left-half and right-half subset sums and by the map of constrained partial sums. That is exactly the right tradeoff here: a moderate amount of memory replaces an astronomically large brute-force search.
Project Euler 152 fragt nach der Anzahl aller Teilmengen \(S \subseteq \{2,3,\dots,80\}\) mit
$$\sum_{n \in S}\frac{1}{n^2}=\frac12.$$
Ein roher Teilmengen-Scan über \(2^{79}\) Möglichkeiten ist völlig unpraktisch. Die eigentliche Lösung besteht darin, zuerst starke lokale Kongruenzbedingungen aus großen ungeraden Primzahlpotenzen zu gewinnen, danach die verbleibende rationale Gleichung in ein ganzzahliges Teilmengenproblem umzuschreiben, die eingeschränkten Primblöcke per Faltung zusammenzuführen und den Rest mit Meet-in-the-Middle zu zählen.
Die Gleichung \(\sum 1/n^2=1/2\) ist viel starrer, als es auf den ersten Blick aussieht. Für mehrere ungerade Primzahlen kann man modulo \(p^2\) zeigen, dass bestimmte Nenner nur in ganz bestimmten Kombinationen auftreten dürfen oder sogar vollständig ausgeschlossen sind. Genau diese lokale Starre treibt den gesamten Algorithmus.
Sei \(p\) eine ungerade Primzahl und \(P_p=p^e\) die größte Potenz von \(p\), die höchstens 80 ist. Im Problem gelten zum Beispiel
$$P_3=27,\qquad P_5=25,\qquad P_7=49,\qquad P_{13}=13.$$
Dazu definieren wir die Top-Gruppe
$$G_p=\{n\in\{2,\dots,80\}: P_p \mid n\}.$$
Setze \(M=\operatorname{lcm}(2,3,\dots,80)\). Wegen \(v_p(M)=e\) kann man \(M=P_pM_p\) mit \(p\nmid M_p\) schreiben. Multipliziert man die Zielgleichung mit \(2M^2\), so erhält man
$$\sum_{n\in S} 2\left(\frac{M}{n}\right)^2=M^2.$$
Nun reduzieren wir modulo \(p^2\). Für \(n\notin G_p\) enthält \(n\) weniger als \(e\) Faktoren \(p\), also ist \((M/n)^2\) durch \(p^2\) teilbar und der entsprechende Summand verschwindet modulo \(p^2\). Für \(n=P_pm\in G_p\) mit \(p\nmid m\) bleibt dagegen \(2(M_p/m)^2\) übrig. Weil \(2M_p^2\) modulo \(p^2\) invertierbar ist, folgt die lokale Bedingung
$$\sum_{n\in S\cap G_p}\left(\frac{n}{P_p}\right)^{-2}\equiv 0 \pmod{p^2},$$
wobei \(x^{-2}\) das Inverse von \(x^2\) modulo \(p^2\) bezeichnet. Das ist genau der Grund, warum die Implementierungen für jede ungerade Primzahl nur diese kleine Top-Gruppe untersuchen.
Die Primzahl \(2\) wird absichtlich nicht genauso behandelt. Nach der Multiplikation mit \(2M^2\) ist der Faktor 2 modulo 4 nicht invertierbar, daher bricht das saubere Argument an dieser Stelle weg. Zweierpotenzen bleiben deshalb im globalen Teilmengenproblem erhalten.
Für jede ungerade Primzahl werden alle Teilmengen von \(G_p\) ausprobiert, und nur diejenigen Masken überleben, die die Kongruenz erfüllen. Da die Gruppen klein sind, ist diese lokale Vollsuche billig. Für \(L=80\) ist die Ausdünnung enorm.
Die meisten Top-Gruppen erlauben nur die leere Auswahl. So kollabieren etwa \(G_3=\{27,54\}\), \(G_5=\{25,50,75\}\), \(G_7=\{49\}\) und \(G_{11}=\{11,22,33,44,55,66,77\}\) sofort: Keine nichtleere Teilmenge erfüllt die nötige Kongruenz modulo \(p^2\).
Die einzige nichttriviale Gruppe ist
$$G_{13}=\{13,26,39,52,65,78\}.$$
Dort sind genau \(\varnothing\) und \(\{13,39,52\}\) gültig. Nach der Normierung durch 13 bleiben die Reste \(1,3,4\), und es gilt
$$1^{-2}+3^{-2}+4^{-2}\equiv 1+94+74=169\equiv 0 \pmod{169}.$$
Damit ist der gesamte 13-Anteil jeder globalen Lösung eine binäre Entscheidung: entweder gar nichts aus dieser Gruppe wählen oder den festen Dreierblock \(\{13,39,52\}\). Zahlen wie 26, 65 und 78 kommen in keiner Lösung vor, weil sie in keiner gültigen lokalen Maske auftauchen.
Nach allen ungeraden Primfiltern schrumpft die Kandidatenmenge von 79 Zahlen auf nur noch 36. Davon liegen drei in der einzigen aktiven 13-Gruppe; die restlichen 33 Zahlen bilden den freien Teil der Suche.
Nachdem unmögliche Nenner entfernt sind, sei \(C\) das kleinste gemeinsame Vielfache aller verbleibenden Kandidaten. Für jedes verbleibende \(n\) setzen wir
$$w_n=\frac{C^2}{n^2},\qquad T=\frac{C^2}{2}.$$
Dann ist die ursprüngliche Bedingung äquivalent zur ganzzahligen Gleichung
$$\sum_{n\in S} w_n=T.$$
Damit verschwindet jede rationale Arithmetik aus der eigentlichen Suche. Jede zulässige lokale Primzahlwahl liefert nur noch einen ganzzahligen Teilbeitrag.
Für jede aktive ungerade Primgruppe \(g\) sei \(A_g(t)\) die Anzahl der gültigen Masken dieser Gruppe mit Gesamtgewicht \(t\). Da die Gruppen in dieser \(L=80\)-Instanz disjunkt sind, kann man ihre Beiträge unabhängig kombinieren.
Die Implementierungen verwenden dazu die Faltungsrekurrenz
$$B_0(0)=1,\qquad B_{r+1}(u)=\sum_t B_r(u-t)\,A_{r+1}(t),$$
wobei \(B_r(u)\) zählt, auf wie viele Arten die ersten \(r\) aktiven Gruppen Gesamtgewicht \(u\) liefern können. Das ist noch nicht die Endlösung, sondern nur der kombinierte Beitrag aller bereits erzwungenen ungeraden Primbedingungen.
Für Problem 152 wird diese Rekurrenz nach der starken Ausdünnung fast trivial, weil nur die 13-Gruppe aktiv bleibt. Ihre Beitragsabbildung besitzt genau zwei Einträge: nichts wählen oder den Block \(\{13,39,52\}\) wählen.
Die übrigen 33 Nenner liegen in keiner ungeraden Top-Gruppe. Bezeichnen wir ihre Gewichte mit \(f_1,\dots,f_{33}\). Ein direkter Scan wäre immer noch \(2^{33}\) groß, daher teilen die Implementierungen diese Zahlen in zwei Hälften der Größen 16 und 17.
Sei \(L(x)\) die Anzahl der linken Teilmengen mit Gewichtssumme \(x\) und \(R(y)\) die Anzahl der rechten Teilmengen mit Gewichtssumme \(y\). Dann lautet die Endformel
$$\sum_u B(u)\sum_x L(x)\,R(T-u-x).$$
In Worten: Man wählt zuerst einen zulässigen Beitrag aus den eingeschränkten Primblöcken, danach eine linke freie Teilmenge, und fragt dann per Hash-Nachschlag, ob die rechte Hälfte genau das fehlende Restgewicht liefern kann.
Das 13-Beispiel oben ist die direkteste Illustration für das reale Limit \(L=80\): Es zeigt, dass die lokale Kongruenz nicht nur einzelne Zahlen entfernt, sondern einen ganzen Block erzwingen kann.
Zusätzlich verwenden die Implementierungen eine kleinere Checkpoint-Instanz. Für \(L=45\) ist
$$\frac12=\frac1{2^2}+\frac1{3^2}+\frac1{4^2}+\frac1{5^2}+\frac1{7^2}+\frac1{12^2}+\frac1{15^2}+\frac1{20^2}+\frac1{28^2}+\frac1{35^2}.$$
In der 7-Gruppe für \(L=45\) werden dabei die Nenner \(\{7,28,35\}\) gewählt. Nach Division durch 7 erhält man \(\{1,4,5\}\), und
$$1^{-2}+4^{-2}+5^{-2}\equiv 1+46+2=49\equiv 0 \pmod{49}.$$
Man sieht also direkt an einer echten Lösung, wie die lokale Kongruenzbedingung sichtbar wird. Der vollständige Algorithmus setzt zunächst alle solchen lokalen Bedingungen durch und löst erst danach die globale Summenbedingung.
Die Implementierungen in C++, Python und Java sieben zunächst alle Primzahlen bis zur Grenze, bestimmen für jede ungerade Primzahl die größte Potenz \(P_p\le 80\) und bilden die zugehörigen Top-Gruppen \(G_p\). Danach wird jede kleine Gruppe vollständig durchlaufen, wobei die normierten Quadrate modulo \(p^2\) invertiert werden. So erfährt die Implementierung sowohl, welche lokalen Masken zulässig sind, als auch welche Nenner in keiner zulässigen Maske vorkommen und daher sofort entfernt werden können.
Nach dieser Ausdünnung wird ein gemeinsamer Nenner \(C\) berechnet, jede verbleibende reziproke Quadratzahl in das ganzzahlige Gewicht \(C^2/n^2\) umgewandelt und das Ziel auf \(C^2/2\) gesetzt. Jede zulässige Maske jeder aktiven ungeraden Primgruppe liefert dann eine partielle Gewichtssumme, und die aktiven Gruppen werden mit der oben beschriebenen Faltungsrekurrenz zusammengesetzt. Das Ergebnis ist eine Abbildung von eingeschränkter Teilsumme auf Anzahl der Möglichkeiten.
Die freien Gewichte werden in zwei Hälften geteilt. Jede Implementierung erzeugt alle Teilmengensummen der linken und der rechten Hälfte und speichert jeweils nur Summe plus Häufigkeit, nicht die Teilmengen selbst. Die Endantwort entsteht dann dadurch, dass man linke Summen und eingeschränkte Summen durchläuft und die eindeutig benötigte rechte Ergänzung zur Zielsumme in einer Hash-Struktur nachschlägt.
Die C++- und Python-Versionen können diese letzte Abgleichphase parallelisieren, wenn die Tabelle groß genug ist. Die Java-Version verwendet dieselbe Mathematik, hält den Kontrollfluss aber bewusst einfach und einsträngig. Zusätzlich prüfen die C++- und Python-Versionen den Ansatz an kleineren Kontrollfällen, darunter drei explizite Identitäten für \(L=45\), die Tatsache, dass es bis 45 genau drei Lösungen gibt, und ein Abgleich mit roher Brute Force bei \(L=18\).
Haben die aktiven ungeraden Primgruppen Größen \(g_1,g_2,\dots\), dann kostet der Aufbau der lokalen Zulässigkeitstabellen
$$O\!\left(\sum_i 2^{g_i}g_i\right),$$
weil jede Gruppe vollständig enumeriert wird. Wenn \(A_i\) die Zahl der verschiedenen gewichteten Optionen der Gruppe \(i\) bezeichnet, kostet die Faltung der eingeschränkten Gruppen ungefähr \(O\!\left(\sum_i |B_{i-1}|\,|A_i|\right)\), wobei \(|B_{i-1}|\) die Zahl der bereits aufgebauten Teilsummen ist.
Dominant bleibt der Meet-in-the-Middle-Schritt auf dem freien Teil. Bei \(f\) freien Nennern werden ungefähr \(2^{\lfloor f/2\rfloor}+2^{\lceil f/2\rceil}\) Teilmengen erzeugt, dazu kommen Hash-Nachschläge für die Komplementbildung. Für die echte Euler-152-Instanz reduzieren die lokalen Filter das Problem auf genau einen nichttrivialen ungeraden Primblock und \(f=33\) freie Zahlen; die globale Suche liegt also eher bei \(2^{16}+2^{17}\) als bei \(2^{79}\).
Der Speicherbedarf wird von den Hash-Tabellen der linken und rechten Teilmengensummen sowie von der Abbildung der eingeschränkten Teilsummen bestimmt. Genau darin liegt der Gewinn: moderater Speicher ersetzt eine astronomisch große Brute-Force-Suche.
Project Euler 152,
$$\sum_{n \in S}\frac{1}{n^2}=\frac12$$
eşitliğini sağlayan \(S \subseteq \{2,3,\dots,80\}\) altkümelerinin sayısını ister. Ham kuvvetle çözmeye kalkarsak \(2^{79}\) farklı altkümeyi denemek gerekir; bu da pratik değildir. Gerçek çözüm, önce büyük tek asal kuvvetlerinden gelen yerel kongruans kısıtlarını uygular, sonra problemi tam sayılı bir altküme-toplam problemine çevirir, asal bloklarını bir evrişimle birleştirir ve kalan serbest kısmı meet-in-the-middle ile sayar.
Buradaki temel fikir, \(\sum 1/n^2=1/2\) eşitliğinin bazı tek asallar için mod \(p^2\) altında çok katı davranmasıdır. Bu yerel zorunluluklar uygulandığında, geriye kalan aday kümesi dramatik biçimde küçülür ve küresel arama artık doğrudan sayılabilir hale gelir.
Sabit bir tek asal \(p\) alalım ve \(P_p=p^e\) ile 80'i aşmayan en büyük \(p\) kuvvetini gösterelim. Bu problemde örneğin
$$P_3=27,\qquad P_5=25,\qquad P_7=49,\qquad P_{13}=13$$
olur. Şimdi
$$G_p=\{n\in\{2,\dots,80\}: P_p \mid n\}$$
kümesini tanımlayalım. Ayrıca \(M=\operatorname{lcm}(2,3,\dots,80)\) olsun. \(v_p(M)=e\) olduğundan \(M=P_pM_p\) yazabiliriz ve burada \(p\nmid M_p\) olur.
Hedef eşitliği \(2M^2\) ile çarpalım:
$$\sum_{n\in S} 2\left(\frac{M}{n}\right)^2=M^2.$$
Bunu mod \(p^2\) altında inceleyelim. Eğer \(n\notin G_p\) ise, \(n\) içinde \(p\)'nin üssü \(e\)'den küçüktür; dolayısıyla \((M/n)^2\) terimi \(p^2\) ile bölünür ve mod \(p^2\) altında kaybolur. Eğer \(n=P_pm\in G_p\) ve \(p\nmid m\) ise geriye \(2(M_p/m)^2\) kalır. \(2M_p^2\) mod \(p^2\) altında terslenebilir olduğu için, küresel eşitlik şu yerel zorunluluğu dayatır:
$$\sum_{n\in S\cap G_p}\left(\frac{n}{P_p}\right)^{-2}\equiv 0 \pmod{p^2}.$$
Buradaki \(x^{-2}\), \(x^2\)'nin mod \(p^2\) altındaki tersidir. Uygulamaların her tek asal için yalnızca bu küçük top grubunu taramasının nedeni tam olarak budur.
\(p=2\) için aynı temiz argüman kullanılmaz. Çünkü \(2M^2\) ile çarpıldıktan sonra 2 katsayısı mod 4 altında terslenebilir değildir; bu yüzden 2-adik kısım daha sonra küresel altküme-toplam aşamasına bırakılır.
Her tek asal için \(G_p\)'nin bütün altkümeleri denenir ve yalnızca yukarıdaki kongruansı sağlayan maskeler tutulur. Bu gruplar küçük olduğu için yerel tam tarama ucuzdur. Asıl kazanç, \(L=80\) örneğinde budamanın son derece agresif olmasıdır.
Çoğu tek asal grubu yalnızca boş seçime izin verir. Örneğin \(G_3=\{27,54\}\), \(G_5=\{25,50,75\}\), \(G_7=\{49\}\) ve \(G_{11}=\{11,22,33,44,55,66,77\}\) için boş olmayan hiçbir altküme gerekli mod \(p^2\) koşulunu sağlayamaz.
Tek istisna
$$G_{13}=\{13,26,39,52,65,78\}$$
grubudur. Burada geçerli yerel seçimler tam olarak \(\varnothing\) ve \(\{13,39,52\}\) olur. Çünkü 13 ile normalize edildiğinde seçilen kalıntılar \(1,3,4\) olur ve
$$1^{-2}+3^{-2}+4^{-2}\equiv 1+94+74=169\equiv 0 \pmod{169}.$$
Dolayısıyla herhangi bir küresel çözümde 13-bölümü ikili bir karardır: ya bu gruptan hiçbir sayı alınmaz ya da sabit blok \(\{13,39,52\}\) birlikte alınır. 26, 65 ve 78 gibi sayılar ise hiçbir geçerli yerel maskede görünmedikleri için tamamen elenir.
Bütün tek asal filtreleri uygulandıktan sonra aday küme 79 sayıdan 36 sayıya düşer. Bu 36 adayın 3'ü tek aktif 13-grubunda bulunur; geri kalan 33 sayı ise hiçbir tek asal top grubuna ait olmayan serbest kısımdır.
İmkansız paydalar çıkarıldıktan sonra, hayatta kalan adayların EKOK'una \(C\) diyelim. Her kalan \(n\) için
$$w_n=\frac{C^2}{n^2},\qquad T=\frac{C^2}{2}$$
tanımlarını yapalım. O zaman orijinal denklem şu tam sayılı altküme-toplam denklemine eşdeğerdir:
$$\sum_{n\in S} w_n=T.$$
Böylece arama sırasında rasyonel aritmetik tamamen ortadan kalkar. Her geçerli yerel asal seçimi artık yalnızca bir tam sayı katkısı üretir.
Her aktif tek asal grubu \(g\) için \(A_g(t)\), bu grubun toplam ağırlığı \(t\) olan geçerli maske sayısı olsun. \(L=80\) örneğinde bu gruplar ayrık olduğu için katkılar bağımsız biçimde birleştirilebilir.
Uygulamalar şu evrişim bağıntısını kullanır:
$$B_0(0)=1,\qquad B_{r+1}(u)=\sum_t B_r(u-t)\,A_{r+1}(t).$$
Burada \(B_r(u)\), ilk \(r\) aktif grubun toplam \(u\) ağırlığını kaç farklı yolla verebildiğini sayar. Bu henüz son cevap değildir; yalnızca tek asal kısıtlarının zorladığı kısmın toplu sayımıdır.
Problem 152'de budama sonrasında bu aşama neredeyse trivial hale gelir, çünkü yalnızca 13-grubu aktiftir. Onun katkı tablosunda yalnızca iki kayıt vardır: hiçbir şey seçmemek veya \(\{13,39,52\}\) bloğunu seçmek.
Kalan 33 payda hiçbir tek asal top grubunda değildir. Bunların ağırlıklarını \(f_1,\dots,f_{33}\) diye gösterelim. Bunlar üzerinde doğrudan arama hâlâ \(2^{33}\) düzeyindedir; bu yüzden uygulamalar bu sayıları 16 ve 17 elemanlı iki yarıya böler.
Sol yarıda toplamı \(x\) olan altkümelerin sayısına \(L(x)\), sağ yarıda toplamı \(y\) olan altkümelerin sayısına \(R(y)\) diyelim. Son çözüm sayısı
$$\sum_u B(u)\sum_x L(x)\,R(T-u-x)$$
olur. Yani önce kısıtlı asal bloklarından geçerli bir katkı seçilir, sonra serbest sol yarıdan bir altküme alınır ve hedefe tamamlayan sağ yarı toplamı hash tablosundan aranır.
Yukarıdaki 13-grubu örneği, gerçek \(L=80\) limiti için yerel filtrenin en temiz gösterimidir: filtre yalnızca tek tek sayıları değil, bütün bir bloğu da zorlayabilir.
Uygulamalardaki küçük kontrol örneklerinden biri de \(L=45\) durumudur. Aşağıdaki eşitlik geçerlidir:
$$\frac12=\frac1{2^2}+\frac1{3^2}+\frac1{4^2}+\frac1{5^2}+\frac1{7^2}+\frac1{12^2}+\frac1{15^2}+\frac1{20^2}+\frac1{28^2}+\frac1{35^2}.$$
Bu çözümde \(L=45\) için 7-grubundan seçilen sayılar \(\{7,28,35\}\) olur. 7'ye bölünmüş halleri \(\{1,4,5\}\) ve
$$1^{-2}+4^{-2}+5^{-2}\equiv 1+46+2=49\equiv 0 \pmod{49}$$
eşitliği sağlanır. Böylece yerel kongruansın gerçek bir çözüm üzerinde nasıl göründüğü açıkça görülür. Tam algoritma, bu tür yerel zorunlulukları önce uygular, sonra kalan küresel toplamı çözer.
C++, Python ve Java uygulamaları önce limite kadar asalları üretir, her tek asal için \(P_p\le 80\) olan en büyük kuvveti bulur ve buna karşılık gelen \(G_p\) gruplarını kurar. Daha sonra her küçük grup tam olarak taranır; normalize edilmiş karelerin mod \(p^2\) tersleri kullanılarak hangi maskelerin geçerli olduğu bulunur. Böylece iki bilgi elde edilir: hangi yerel maskeler mümkündür ve hangi paydalar hiçbir geçerli maskede görünmediği için daha baştan atılabilir.
Budamadan sonra ortak payda \(C\) hesaplanır, her kalan \(1/n^2\) terimi \(C^2/n^2\) tam sayı ağırlığına çevrilir ve hedef \(C^2/2\) olarak belirlenir. Aktif tek asal gruplarındaki her geçerli maske, bir kısmi ağırlık toplamına dönüştürülür; sonra bu gruplar yukarıdaki evrişim bağıntısıyla birleştirilir. Elde edilen yapı, kısıtlı kısmi toplamdan o toplamın kaç farklı yolla oluştuğuna giden bir eşlemedir.
Serbest ağırlıklar iki yarıya ayrılır. Her uygulama, sol ve sağ yarının bütün altküme toplamlarını üretir ama altkümelerin kendisini değil, yalnızca toplam ile çokluk bilgisini saklar. Son cevap, sol toplamlar ve kısıtlı toplamlar üzerinde dolaşıp hedefi tamamlayan tekil sağ toplamı hash yapısından okuyarak hesaplanır.
C++ ve Python sürümleri, tablo yeterince büyükse bu son eşleme aşamasını paralel çalıştırabilir. Java sürümü aynı matematiği daha sade ve tek iş parçacıklı bir akışla uygular. Ayrıca C++ ve Python sürümleri, yöntemi küçük kontrol örnekleri üzerinde doğrular: \(L=45\) için üç açık kimlik, 45'e kadar tam olarak üç çözüm olduğu bilgisi ve \(L=18\) için brute-force karşılaştırması bunların içindedir.
Aktif tek asal gruplarının boyutları \(g_1,g_2,\dots\) ise, yerel geçerlilik tablolarını üretmenin maliyeti
$$O\!\left(\sum_i 2^{g_i}g_i\right)$$
olur; çünkü her grup tam taranır. \(A_i\), \(i\). grubun ürettiği farklı ağırlıklı seçenek sayısı ise, kısıtlı grup evrişiminin maliyeti yaklaşık \(O\!\left(\sum_i |B_{i-1}|\,|A_i|\right)\) düzeyindedir.
Baskın aşama serbest kısımdaki meet-in-the-middle aramasıdır. Serbest payda sayısı \(f\) ise yaklaşık \(2^{\lfloor f/2\rfloor}+2^{\lceil f/2\rceil}\) altküme üretilir ve bunlara hash eşlemeleri eklenir. Gerçek Euler 152 örneğinde yerel filtreler problemi tek bir aktif tek asal blok ve \(f=33\) serbest sayı düzeyine indirir; yani küresel arama \(2^{79}\) yerine kabaca \(2^{16}+2^{17}\) büyüklüğündedir.
Bellek kullanımı esas olarak sol ve sağ altküme-toplam tabloları ile kısıtlı kısmi toplam haritası tarafından belirlenir. Buradaki tercih bilinçlidir: makul miktarda bellek, astronomik büyüklükte bir kaba kuvvet aramasının yerini alır.
Project Euler 152 pide contar los subconjuntos \(S \subseteq \{2,3,\dots,80\}\) tales que
$$\sum_{n \in S}\frac{1}{n^2}=\frac12.$$
Una búsqueda ingenua tendría que revisar \(2^{79}\) subconjuntos, así que el problema real consiste en descubrir estructura aritmética antes de enumerar nada de forma global. Las implementaciones lo logran imponiendo primero congruencias locales procedentes de grandes potencias primas impares, convirtiendo luego la ecuación racional en una suma de subconjuntos entera, combinando los bloques primos restringidos mediante convolución y resolviendo el resto con meet-in-the-middle.
La igualdad \(\sum 1/n^2=1/2\) tiene restricciones locales muy fuertes módulo \(p^2\) para ciertos primos impares. Una vez que esas restricciones se aplican, el conjunto de denominadores que todavía pueden aparecer es mucho más pequeño, y el conteo exacto ya se puede hacer con una búsqueda estructurada.
Fijemos un primo impar \(p\), y llamemos \(P_p=p^e\) a la mayor potencia de \(p\) que no supera 80. En este problema, por ejemplo,
$$P_3=27,\qquad P_5=25,\qquad P_7=49,\qquad P_{13}=13.$$
Definimos entonces el grupo superior
$$G_p=\{n\in\{2,\dots,80\}: P_p \mid n\}.$$
Sea \(M=\operatorname{lcm}(2,3,\dots,80)\). Como \(v_p(M)=e\), podemos escribir \(M=P_pM_p\) con \(p\nmid M_p\). Si multiplicamos la ecuación objetivo por \(2M^2\), obtenemos
$$\sum_{n\in S} 2\left(\frac{M}{n}\right)^2=M^2.$$
Ahora reducimos módulo \(p^2\). Si \(n\notin G_p\), entonces \(n\) contiene menos copias de \(p\) que \(M\), por lo que \((M/n)^2\) es múltiplo de \(p^2\) y desaparece módulo \(p^2\). Si \(n=P_pm\in G_p\), con \(p\nmid m\), el término superviviente es \(2(M_p/m)^2\). Como \(2M_p^2\) es invertible módulo \(p^2\), la identidad global obliga a cumplir
$$\sum_{n\in S\cap G_p}\left(\frac{n}{P_p}\right)^{-2}\equiv 0 \pmod{p^2},$$
donde \(x^{-2}\) significa el inverso de \(x^2\) módulo \(p^2\). Esta es exactamente la razón por la que las implementaciones solo examinan los números del grupo superior para cada primo impar.
El primo \(2\) se deja fuera de este filtro. Después de multiplicar por \(2M^2\), el factor 2 no es invertible módulo 4, así que el mismo argumento limpio ya no funciona. Las potencias de 2 se dejan para la fase global de suma de subconjuntos.
Para cada primo impar, las implementaciones prueban todos los subconjuntos de \(G_p\) y conservan solo las máscaras que satisfacen la congruencia anterior. Como cada grupo es pequeño, esta búsqueda local exhaustiva es barata. Para \(L=80\), la poda es muy fuerte.
La mayoría de los grupos superiores solo admiten la elección vacía. Por ejemplo, \(G_3=\{27,54\}\), \(G_5=\{25,50,75\}\), \(G_7=\{49\}\) y \(G_{11}=\{11,22,33,44,55,66,77\}\) colapsan de inmediato: ningún subconjunto no vacío satisface la congruencia exigida módulo \(p^2\).
El único grupo no trivial es
$$G_{13}=\{13,26,39,52,65,78\}.$$
Aquí las selecciones locales válidas son exactamente \(\varnothing\) y \(\{13,39,52\}\). Al normalizar por 13, los residuos elegidos son \(1,3,4\), y se cumple
$$1^{-2}+3^{-2}+4^{-2}\equiv 1+94+74=169\equiv 0 \pmod{169}.$$
Por tanto, la parte asociada al 13 en cualquier solución global es una decisión binaria: o no se toma ningún número de ese grupo, o se toma el bloque fijo \(\{13,39,52\}\). Números como 26, 65 y 78 nunca aparecen porque no pertenecen a ninguna máscara local válida.
Después de aplicar todos los filtros por primos impares, el conjunto candidato baja de 79 números a solo 36. De esos 36, tres pertenecen al único grupo activo de 13, y los otros 33 forman la parte libre de la búsqueda.
Una vez eliminados los denominadores imposibles, sea \(C\) el mínimo común múltiplo de todos los candidatos supervivientes. Para cada \(n\) restante definimos
$$w_n=\frac{C^2}{n^2},\qquad T=\frac{C^2}{2}.$$
Entonces la ecuación original es equivalente a la ecuación entera
$$\sum_{n\in S} w_n=T.$$
Esta transformación es decisiva, porque elimina la aritmética racional durante la búsqueda: cada elección local válida aporta únicamente una suma entera.
Para cada grupo impar activo \(g\), sea \(A_g(t)\) el número de máscaras válidas del grupo cuyo peso total es \(t\). Como en esta instancia \(L=80\) los grupos activos son disjuntos, sus contribuciones pueden combinarse de manera independiente.
Las implementaciones usan la recurrencia de convolución
$$B_0(0)=1,\qquad B_{r+1}(u)=\sum_t B_r(u-t)\,A_{r+1}(t),$$
donde \(B_r(u)\) cuenta cuántas formas tienen los primeros \(r\) grupos activos de aportar peso total \(u\). Esto todavía no es la respuesta final; solo cuenta las elecciones compatibles con las restricciones locales impuestas por los primos impares.
En Problem 152, esa recurrencia casi se colapsa después de la poda, porque solo sobrevive como grupo activo el de 13. Su mapa de contribuciones tiene exactamente dos entradas: no escoger nada o escoger el bloque \(\{13,39,52\}\).
Los otros 33 denominadores no pertenecen a ningún grupo superior impar. Denotemos sus pesos por \(f_1,\dots,f_{33}\). Un barrido directo sobre ellos todavía sería de tamaño \(2^{33}\), así que las implementaciones los dividen en dos mitades de 16 y 17 elementos.
Sea \(L(x)\) el número de subconjuntos de la mitad izquierda con suma \(x\), y \(R(y)\) el número de subconjuntos de la mitad derecha con suma \(y\). Entonces el número final de soluciones es
$$\sum_u B(u)\sum_x L(x)\,R(T-u-x).$$
La lectura conceptual es simple: se elige primero una contribución legal de los bloques primos restringidos, luego una suma de la mitad izquierda y, finalmente, se busca por tabla hash la suma exacta que debe aportar la mitad derecha.
El ejemplo del grupo de 13 es la ilustración más directa del filtro local para el límite real \(L=80\): muestra que la congruencia no solo elimina denominadores aislados, sino que puede obligar a tomar un bloque entero.
Las implementaciones también usan una instancia de control más pequeña. Para \(L=45\), se verifica la identidad
$$\frac12=\frac1{2^2}+\frac1{3^2}+\frac1{4^2}+\frac1{5^2}+\frac1{7^2}+\frac1{12^2}+\frac1{15^2}+\frac1{20^2}+\frac1{28^2}+\frac1{35^2}.$$
Dentro del grupo de 7 para \(L=45\), los denominadores elegidos son \(\{7,28,35\}\). Al dividir por 7 se obtiene \(\{1,4,5\}\), y
$$1^{-2}+4^{-2}+5^{-2}\equiv 1+46+2=49\equiv 0 \pmod{49}.$$
Así se ve claramente que la congruencia local es visible dentro de una solución explícita. El algoritmo completo fuerza primero todas esas condiciones locales y solo después resuelve la suma global exacta.
Las implementaciones en C++, Python y Java criban los primos hasta el límite, determinan la mayor potencia \(P_p\le 80\) para cada primo impar y forman los grupos superiores \(G_p\). Después recorren exhaustivamente cada grupo pequeño usando inversos modulares de los cuadrados normalizados módulo \(p^2\). Con eso determinan qué máscaras locales son válidas y qué denominadores no aparecen en ninguna máscara válida, por lo que pueden descartarse de inmediato.
Tras la poda, la implementación calcula un denominador común \(C\), convierte cada término \(1/n^2\) superviviente en el peso entero \(C^2/n^2\) y fija la meta en \(C^2/2\). Cada máscara válida de cada grupo impar activo se transforma en una suma parcial de pesos, y los grupos activos se combinan mediante la recurrencia de convolución. El resultado es un mapa desde suma parcial restringida hasta número de formas de obtenerla.
Los pesos libres se parten en dos mitades. Cada implementación enumera todas las sumas de subconjuntos de la mitad izquierda y de la mitad derecha, guardando solo la suma y su multiplicidad. La respuesta final se obtiene recorriendo las sumas izquierdas y las sumas restringidas, y consultando por hash la suma derecha complementaria que completa exactamente el objetivo.
Las versiones en C++ y Python pueden paralelizar esta última fase de emparejamiento cuando la tabla es suficientemente grande. La versión en Java mantiene la misma aritmética en un flujo simple y monohilo. Además, las versiones en C++ y Python validan el método con casos de control más pequeños, entre ellos tres identidades explícitas para \(L=45\), el hecho de que hasta 45 hay exactamente tres soluciones y una comparación con fuerza bruta en \(L=18\).
Si los grupos impares activos tienen tamaños \(g_1,g_2,\dots\), construir las tablas locales de legalidad cuesta
$$O\!\left(\sum_i 2^{g_i}g_i\right),$$
porque cada grupo se explora exhaustivamente. Si \(A_i\) es el número de opciones ponderadas distintas producidas por el grupo \(i\), la convolución de grupos restringidos cuesta aproximadamente \(O\!\left(\sum_i |B_{i-1}|\,|A_i|\right)\), donde \(|B_{i-1}|\) es el número de sumas parciales ya acumuladas.
La fase dominante es el meet-in-the-middle de la parte libre. Con \(f\) denominadores libres, hacen falta aproximadamente \(2^{\lfloor f/2\rfloor}+2^{\lceil f/2\rceil}\) enumeraciones de subconjuntos, más consultas hash para encontrar complementos. En la instancia real de Euler 152, los filtros locales reducen el problema a un solo bloque primo impar no trivial y \(f=33\) números libres; por tanto, la búsqueda global se parece mucho más a \(2^{16}+2^{17}\) que a \(2^{79}\).
La memoria está dominada por las tablas hash de sumas de la mitad izquierda y derecha, junto con el mapa de sumas parciales restringidas. Ese es precisamente el intercambio correcto: una cantidad moderada de memoria sustituye una búsqueda por fuerza bruta astronómica.
Project Euler 152 要求统计所有满足
$$\sum_{n \in S}\frac{1}{n^2}=\frac12,\qquad S\subseteq\{2,3,\dots,80\}$$
的子集个数。直接暴力枚举需要检查 \(2^{79}\) 个子集，显然不可行。真正可行的方法是先利用若干奇素数的局部同余条件大幅剪枝，再把剩余问题改写成一个整数子集和问题，把受约束的素数块先合并，最后只对较小的自由部分做 meet-in-the-middle。
这道题的核心不是“枚举得更快”，而是先看清哪些分母从一开始就不可能出现。等式 \(\sum 1/n^2=1/2\) 在某些模 \(p^2\) 的意义下非常刚性，这种刚性正是实现中最重要的数学对象。
固定一个奇素数 \(p\)，记 \(P_p=p^e\) 为不超过 80 的最大 \(p\) 次幂。对本题来说，例如
$$P_3=27,\qquad P_5=25,\qquad P_7=49,\qquad P_{13}=13.$$
定义对应的“顶层分组”
$$G_p=\{n\in\{2,\dots,80\}: P_p \mid n\}.$$
再设 \(M=\operatorname{lcm}(2,3,\dots,80)\)。因为 \(v_p(M)=e\)，所以可以写成 \(M=P_pM_p\)，其中 \(p\nmid M_p\)。把目标等式乘上 \(2M^2\) 得到
$$\sum_{n\in S} 2\left(\frac{M}{n}\right)^2=M^2.$$
现在在模 \(p^2\) 下看这件事。如果 \(n\notin G_p\)，说明 \(n\) 中的 \(p\) 次数比 \(M\) 少至少 1，于是 \((M/n)^2\) 含有因子 \(p^2\)，这个项在模 \(p^2\) 下直接消失。若 \(n=P_pm\in G_p\)，且 \(p\nmid m\)，留下来的项就是 \(2(M_p/m)^2\)。由于 \(2M_p^2\) 在模 \(p^2\) 下可逆，整个等式必然推出局部条件
$$\sum_{n\in S\cap G_p}\left(\frac{n}{P_p}\right)^{-2}\equiv 0 \pmod{p^2}.$$
这里的 \(x^{-2}\) 表示 \(x^2\) 在模 \(p^2\) 下的乘法逆元。实现之所以只检查每个奇素数对应的这一个小分组，原因就在这里：对该素数而言，其他分母在模 \(p^2\) 下根本看不见。
素数 2 没有被纳入同样的过滤步骤。原因是乘上 \(2M^2\) 之后，系数 2 在模 4 下不可逆，上面的整洁推导就不能原样成立。因此 2-adic 信息被留到后面的全局整数子集和阶段处理。
对每个奇素数，程序都会把 \(G_p\) 的所有子集枚举一遍，只保留满足上面同余式的选择。由于这些组都很小，这一步是廉价的。真正重要的是：对于 \(L=80\)，剪枝非常猛烈。
大多数奇素数顶层分组都只允许空集。例如 \(G_3=\{27,54\}\)、\(G_5=\{25,50,75\}\)、\(G_7=\{49\}\) 以及 \(G_{11}=\{11,22,33,44,55,66,77\}\) 都会立刻塌缩成“什么都不能选”。
唯一的非平凡分组是
$$G_{13}=\{13,26,39,52,65,78\}.$$
这个分组里合法的局部选择恰好只有 \(\varnothing\) 和 \(\{13,39,52\}\)。因为把它们都除以 13 以后，得到的归一化值是 \(1,3,4\)，并且
$$1^{-2}+3^{-2}+4^{-2}\equiv 1+94+74=169\equiv 0 \pmod{169}.$$
这说明在任何全局解里，13-部分都不是“六个数里随便挑”，而是一个二元决定：要么一个都不选，要么整块选入 \(\{13,39,52\}\)。像 26、65、78 这样的数从一开始就被排除了，因为它们不属于任何合法局部掩码。
经过全部奇素数过滤之后，候选分母从原来的 79 个下降到只剩 36 个。其中 3 个属于唯一活跃的 13-分组，另外 33 个则不属于任何奇素数顶层分组，构成最后搜索里的自由部分。
删去不可能的分母后，设所有幸存候选数的最小公倍数为 \(C\)。对每个剩余的 \(n\)，定义
$$w_n=\frac{C^2}{n^2},\qquad T=\frac{C^2}{2}.$$
于是原方程就等价于整数子集和方程
$$\sum_{n\in S} w_n=T.$$
这一步非常关键，因为之后的搜索再也不需要处理分数。每一个合法的局部素数选择都只会产生一个整数部分和。
对每个活跃奇素数组 \(g\)，记 \(A_g(t)\) 为“该组中权重和为 \(t\) 的合法掩码数量”。由于在本题的 \(L=80\) 实例里，这些活跃组彼此互不重叠，所以可以独立合并。
实现使用的递推关系是
$$B_0(0)=1,\qquad B_{r+1}(u)=\sum_t B_r(u-t)\,A_{r+1}(t),$$
其中 \(B_r(u)\) 表示前 \(r\) 个活跃组一共贡献权重 \(u\) 的方案数。这还不是最终答案，它只负责把所有由奇素数同余条件强制出来的局部选择先聚合起来。
对于 Euler 152，这个递推在剪枝后几乎变成了常数工作，因为真正活跃的组只有 13 这一个。它的贡献表只有两项：不选任何 13-组数字，或者整体选择 \(\{13,39,52\}\)。
剩下的 33 个分母都不在任何奇素数顶层分组里。把它们的整数权重记为 \(f_1,\dots,f_{33}\)。如果直接枚举，仍然有 \(2^{33}\) 个子集，所以实现把它们拆成 16 个和 17 个两半。
记 \(L(x)\) 为左半部分权重和为 \(x\) 的子集个数，\(R(y)\) 为右半部分权重和为 \(y\) 的子集个数。那么最终解数就是
$$\sum_u B(u)\sum_x L(x)\,R(T-u-x).$$
可以把它理解成三步：先选定一个受约束素数块的合法贡献，再选左半部分的一个子集，最后去右半部分的哈希表里查找是否存在恰好补足目标值的和。
前面的 13-分组已经给出了最贴近真实 \(L=80\) 实例的局部示例：局部同余条件不仅能删掉单个数字，还能把一个三元素块当成“整体选或整体不选”的对象。
实现里还有一个更小的校验例子。对 \(L=45\)，下面这个恒等式成立：
$$\frac12=\frac1{2^2}+\frac1{3^2}+\frac1{4^2}+\frac1{5^2}+\frac1{7^2}+\frac1{12^2}+\frac1{15^2}+\frac1{20^2}+\frac1{28^2}+\frac1{35^2}.$$
在 \(L=45\) 的 7-分组里，被选中的数是 \(\{7,28,35\}\)。除以 7 后变成 \(\{1,4,5\}\)，并满足
$$1^{-2}+4^{-2}+5^{-2}\equiv 1+46+2=49\equiv 0 \pmod{49}.$$
这说明局部同余条件并不是抽象的附加技巧，而是真正出现在显式解中的结构。完整算法的思路就是：先把所有这样的局部结构筛出来，再精确完成剩余的全局求和。
C++、Python 和 Java 实现都会先筛出上界以内的素数，再对每个奇素数求出最大的 \(P_p\le 80\)，构造对应的顶层分组 \(G_p\)。随后，它们会枚举每个小分组的所有掩码，通过归一化平方在模 \(p^2\) 下的逆元来测试哪些局部选择合法。这样既能知道哪些局部掩码有效，也能知道哪些分母从未出现在任何有效掩码里，因此可以直接丢弃。
完成剪枝后，程序计算公共分母 \(C\)，把每个幸存的 \(1/n^2\) 转换为整数权重 \(C^2/n^2\)，并把目标设成 \(C^2/2\)。每个活跃奇素数组中的每个合法掩码都会对应一个整数部分和，然后这些组通过上面的卷积递推合并成“受约束部分和 \(\to\) 方案数”的映射。
自由权重被拆成左右两半。每个实现都会枚举左右两半的所有子集和，但存储的是“和及其出现次数”，而不是原始子集列表。最终答案通过遍历左半部分和与受约束部分和，再去右半部分的哈希表里查找唯一需要的补和值来得到。
C++ 和 Python 实现会在表足够大时并行执行最后的匹配过程；Java 实现保留同样的算术结构，但控制流程保持单线程、紧凑。C++ 与 Python 版本还会在较小实例上做校验，包括 \(L=45\) 的三个显式恒等式、到 45 为止恰有 3 个解，以及 \(L=18\) 上与暴力搜索结果一致。
如果活跃奇素数组的大小分别为 \(g_1,g_2,\dots\)，那么建立局部合法性表的代价为
$$O\!\left(\sum_i 2^{g_i}g_i\right),$$
因为每个小组都被完整枚举。若 \(A_i\) 表示第 \(i\) 个组产生的不同加权选项数，那么受约束组的卷积代价大致是 \(O\!\left(\sum_i |B_{i-1}|\,|A_i|\right)\)。
主导成本来自自由部分的 meet-in-the-middle。若剩余自由分母个数为 \(f\)，则需要大约 \(2^{\lfloor f/2\rfloor}+2^{\lceil f/2\rceil}\) 次子集枚举，再配合哈希查找补和。对真正的 Euler 152 实例，本地过滤把问题压缩成 1 个非平凡奇素数组和 \(f=33\) 个自由数字，因此全局枚举规模更接近 \(2^{16}+2^{17}\)，而不是 \(2^{79}\)。
内存消耗主要来自左右两半的子集和哈希表，以及受约束部分和的映射。这正是本题应有的权衡：用适度内存换掉天文数量级的暴力搜索。
Project Euler 152 требует посчитать число подмножеств \(S \subseteq \{2,3,\dots,80\}\), для которых выполняется
$$\sum_{n \in S}\frac{1}{n^2}=\frac12.$$
Прямой перебор означал бы проверку \(2^{79}\) подмножеств, что абсолютно нереально. Рабочее решение сначала извлекает локальные ограничения по модулю \(p^2\), связанные с большими степенями нечетных простых, затем переводит задачу в целочисленный subset sum, сворачивает принудительные простые блоки и только потом добивает оставшуюся свободную часть методом meet-in-the-middle.
Главная идея состоит в том, что равенство \(\sum 1/n^2=1/2\) порождает очень жесткие локальные условия. Для некоторых нечетных простых заранее можно доказать, какие числа вообще не имеют права входить в решение, а какие должны появляться только в специальных комбинациях. Именно эта локальная арифметика превращает задачу из невозможной в вычислимую.
Зафиксируем нечетное простое \(p\) и обозначим через \(P_p=p^e\) наибольшую степень \(p\), не превосходящую 80. В данной задаче, например,
$$P_3=27,\qquad P_5=25,\qquad P_7=49,\qquad P_{13}=13.$$
Определим верхнюю группу
$$G_p=\{n\in\{2,\dots,80\}: P_p \mid n\}.$$
Пусть \(M=\operatorname{lcm}(2,3,\dots,80)\). Так как \(v_p(M)=e\), можно записать \(M=P_pM_p\), где \(p\nmid M_p\). Умножим целевое равенство на \(2M^2\):
$$\sum_{n\in S} 2\left(\frac{M}{n}\right)^2=M^2.$$
Теперь рассмотрим это равенство по модулю \(p^2\). Если \(n\notin G_p\), то в \(n\) содержится меньше \(p\)-факторов, чем в \(M\), поэтому \((M/n)^2\) делится на \(p^2\), и соответствующий член исчезает modulo \(p^2\). Если же \(n=P_pm\in G_p\) и \(p\nmid m\), то остающийся член равен \(2(M_p/m)^2\). Поскольку \(2M_p^2\) обратим modulo \(p^2\), глобальное равенство вынуждает локальное условие
$$\sum_{n\in S\cap G_p}\left(\frac{n}{P_p}\right)^{-2}\equiv 0 \pmod{p^2},$$
где \(x^{-2}\) обозначает обратный элемент к \(x^2\) по модулю \(p^2\). Именно поэтому реализации рассматривают для каждого нечетного простого только числа из группы \(G_p\): все остальные с точки зрения данного модуля не влияют на условие.
Простое число 2 обрабатывается отдельно. После умножения на \(2M^2\) множитель 2 не обратим по модулю 4, так что столь же чистый локальный аргумент здесь не работает. Поэтому двоичная часть уходит в более поздний глобальный этап subset sum.
Для каждого нечетного простого реализации перебирают все подмножества \(G_p\) и сохраняют только те маски, которые удовлетворяют приведенной конгруэнции. Эти группы малы, поэтому такой локальный полный перебор дешев. Для \(L=80\) результат оказывается очень жестким.
Большинство верхних групп допускают только пустой выбор. Например, \(G_3=\{27,54\}\), \(G_5=\{25,50,75\}\), \(G_7=\{49\}\) и \(G_{11}=\{11,22,33,44,55,66,77\}\) сразу схлопываются: ни одно непустое подмножество не удовлетворяет нужной конгруэнции modulo \(p^2\).
Единственная нетривиальная группа имеет вид
$$G_{13}=\{13,26,39,52,65,78\}.$$
Здесь допустимы ровно два локальных выбора: \(\varnothing\) и \(\{13,39,52\}\). После нормировки на 13 остаются значения \(1,3,4\), и
$$1^{-2}+3^{-2}+4^{-2}\equiv 1+94+74=169\equiv 0 \pmod{169}.$$
Значит, вся 13-часть любого глобального решения - это двоичное решение: либо не брать из этой группы ничего, либо брать фиксированный блок \(\{13,39,52\}\). Числа 26, 65 и 78 вообще не могут появиться, поскольку не входят ни в одну допустимую локальную маску.
После всех фильтров по нечетным простым исходные 79 кандидатов сокращаются до 36. Из них 3 относятся к единственной активной 13-группе, а остальные 33 числа образуют свободную часть дальнейшего поиска.
После удаления невозможных знаменателей обозначим через \(C\) наименьшее общее кратное всех оставшихся кандидатов. Для каждого выжившего \(n\) введем
$$w_n=\frac{C^2}{n^2},\qquad T=\frac{C^2}{2}.$$
Тогда исходное равенство эквивалентно точной целочисленной задаче subset sum
$$\sum_{n\in S} w_n=T.$$
После этого во внутреннем поиске уже не остается дробной арифметики. Каждый допустимый локальный выбор в простом блоке становится просто целочисленным частичным вкладом.
Для каждой активной нечетной простой группы \(g\) обозначим через \(A_g(t)\) число допустимых масок этой группы с суммарным весом \(t\). Поскольку в данном экземпляре \(L=80\) активные группы не пересекаются, их вклад можно комбинировать независимо.
Реализации используют рекуррентную свертку
$$B_0(0)=1,\qquad B_{r+1}(u)=\sum_t B_r(u-t)\,A_{r+1}(t),$$
где \(B_r(u)\) считает, сколькими способами первые \(r\) активных групп могут дать суммарный вес \(u\). Это еще не окончательный ответ; так агрегируются только локально допустимые выборы, навязанные арифметикой нечетных простых.
Для Euler 152 эта часть после фильтрации почти исчезает, потому что активной остается только группа 13. Ее таблица вкладов имеет всего две записи: ничего не брать или взять блок \(\{13,39,52\}\).
Оставшиеся 33 знаменателя не принадлежат ни к одной верхней нечетной группе. Обозначим их веса через \(f_1,\dots,f_{33}\). Прямой перебор по ним все еще имел бы размер \(2^{33}\), поэтому реализации делят эти числа на две половины размеров 16 и 17.
Пусть \(L(x)\) - число подмножеств левой половины с суммой веса \(x\), а \(R(y)\) - число подмножеств правой половины с суммой веса \(y\). Тогда окончательное число решений равно
$$\sum_u B(u)\sum_x L(x)\,R(T-u-x).$$
Смысл формулы такой: сначала выбирается допустимый вклад из ограниченных простых блоков, затем выбирается сумма левой свободной половины, после чего в хеш-таблице правой половины ищется ровно тот дополнительный вес, который добивает сумму до цели.
Пример с группой 13 - это самая наглядная иллюстрация локального фильтра для реального предела \(L=80\): условие по модулю \(169\) не просто исключает отдельные числа, а навязывает целый трехэлементный блок.
В реализациях используется и меньший контрольный пример. Для \(L=45\) выполняется равенство
$$\frac12=\frac1{2^2}+\frac1{3^2}+\frac1{4^2}+\frac1{5^2}+\frac1{7^2}+\frac1{12^2}+\frac1{15^2}+\frac1{20^2}+\frac1{28^2}+\frac1{35^2}.$$
Внутри 7-группы для \(L=45\) выбираются знаменатели \(\{7,28,35\}\). После деления на 7 получаем \(\{1,4,5\}\), и
$$1^{-2}+4^{-2}+5^{-2}\equiv 1+46+2=49\equiv 0 \pmod{49}.$$
То есть локальное условие действительно видно в явном решении. Полный алгоритм именно так и работает: сначала он проводит все такие локальные отсеивания, а затем точно считает оставшиеся глобальные комбинации.
Реализации на C++, Python и Java сначала просеивают простые числа до заданного предела, находят максимальную степень \(P_p\le 80\) для каждого нечетного простого и строят соответствующие группы \(G_p\). Затем они полностью перебирают каждую малую группу, используя обратные элементы к нормированным квадратам modulo \(p^2\), чтобы определить допустимые локальные маски. На этом же этапе выясняется, какие знаменатели не встречаются ни в одной допустимой маске и должны быть отброшены сразу.
После фильтрации вычисляется общий знаменатель \(C\), каждый оставшийся член \(1/n^2\) превращается в целочисленный вес \(C^2/n^2\), а целевая сумма становится равной \(C^2/2\). Каждая допустимая маска каждой активной нечетной группы преобразуется в частичную сумму веса, после чего все активные группы сворачиваются описанной выше рекуррентной формулой. Получается отображение «ограниченная частичная сумма \(\to\) число способов».
Свободные веса делятся на две половины. Каждая реализация перечисляет все суммы подмножеств левой и правой половин, сохраняя только суммы и их кратности. Финальный ответ получается проходом по левым суммам и ограниченным суммам с поиском нужного дополнительного значения в хеш-таблице правой половины.
Версии на C++ и Python умеют распараллеливать этот заключительный этап, если таблица достаточно велика. Версия на Java реализует ту же математику в более компактном однопоточном стиле. Кроме того, версии на C++ и Python проверяют метод на меньших контрольных случаях: трех явных тождествах при \(L=45\), факте существования ровно трех решений до 45 и сравнении с полным перебором при \(L=18\).
Если размеры активных нечетных групп равны \(g_1,g_2,\dots\), то построение локальных таблиц допустимости стоит
$$O\!\left(\sum_i 2^{g_i}g_i\right),$$
потому что каждая группа перебирается целиком. Если \(A_i\) - число различных взвешенных вариантов, создаваемых группой \(i\), то свертка ограниченных групп занимает примерно \(O\!\left(\sum_i |B_{i-1}|\,|A_i|\right)\).
Основная стоимость приходится на meet-in-the-middle для свободной части. Если после фильтрации остается \(f\) свободных знаменателей, то требуется порядка \(2^{\lfloor f/2\rfloor}+2^{\lceil f/2\rceil}\) перечислений подмножеств плюс хеш-поиски дополнений. Для реального экземпляра Euler 152 локальные фильтры сводят задачу к одному нетривиальному блоку нечетного простого и \(f=33\) свободным числам, так что глобальный перебор ближе к \(2^{16}+2^{17}\), чем к \(2^{79}\).
Память в основном расходуется на хеш-таблицы сумм левой и правой половин и на таблицу ограниченных частичных сумм. Именно это и делает метод практичным: умеренная память заменяет астрономический полный перебор.
تطلب مسألة Project Euler 152 عدَّ جميع المجموعات الجزئية \(S \subseteq \{2,3,\dots,80\}\) التي تحقق
$$\sum_{n \in S}\frac{1}{n^2}=\frac12.$$
العدّ الخام سيحتاج إلى فحص \(2^{79}\) مجموعة جزئية، وهذا غير عملي تمامًا. لذلك يعتمد الحل الحقيقي على أربع طبقات مترابطة: استخراج قيود توافقية محلية من قوى أولية فردية كبيرة، تحويل المسألة إلى مسألة مجموعات جزئية صحيحة، دمج الكتل الأولية المقيدة بطريقة التفاف، ثم إنهاء الجزء الحر بتقنية meet-in-the-middle.
الفكرة الأساسية هي أن المعادلة \(\sum 1/n^2=1/2\) ليست مرنة كما تبدو. فعند النظر إليها modulo \(p^2\) لبعض الأعداد الأولية الفردية، تظهر شروط قوية تمنع كثيرًا من المقامات من الظهور أصلًا، أو تجبر بعضها على الظهور في كتل محددة. هذا هو القلب الرياضي الفعلي للحل.
لنثبت عددًا أوليًا فرديًا \(p\)، ولتكن \(P_p=p^e\) أكبر قوة لـ \(p\) لا تتجاوز 80. في هذه المسألة مثلًا لدينا
$$P_3=27,\qquad P_5=25,\qquad P_7=49,\qquad P_{13}=13.$$
ونعرّف مجموعة القمة
$$G_p=\{n\in\{2,\dots,80\}: P_p \mid n\}.$$
لتكن أيضًا \(M=\operatorname{lcm}(2,3,\dots,80)\). بما أن \(v_p(M)=e\)، يمكن كتابة \(M=P_pM_p\) حيث \(p\nmid M_p\). إذا ضربنا المعادلة الأصلية في \(2M^2\) نحصل على
$$\sum_{n\in S} 2\left(\frac{M}{n}\right)^2=M^2.$$
الآن ننظر modulo \(p^2\). إذا كان \(n\notin G_p\)، فهذا يعني أن عدد عوامل \(p\) في \(n\) أقل من عددها في \(M\)، ومن ثم يكون \((M/n)^2\) قابلاً للقسمة على \(p^2\)، فيختفي هذا الحد modulo \(p^2\). أما إذا كان \(n=P_pm\in G_p\) مع \(p\nmid m\)، فالحد الباقي هو \(2(M_p/m)^2\). وبما أن \(2M_p^2\) عنصر قابل للعكس modulo \(p^2\)، فإن المعادلة العالمية تفرض الشرط المحلي
$$\sum_{n\in S\cap G_p}\left(\frac{n}{P_p}\right)^{-2}\equiv 0 \pmod{p^2}.$$
والمقصود بـ \(x^{-2}\) هو معكوس \(x^2\) modulo \(p^2\). لهذا السبب بالضبط تكتفي التطبيقات بفحص الأعداد الموجودة في مجموعة القمة لكل أولي فردي: بقية المقامات لا تؤثر على هذا الشرط المحلي.
أما العدد الأولي 2 فلا يُعامل بالطريقة نفسها، لأن العامل 2 بعد الضرب في \(2M^2\) لا يكون قابلاً للعكس modulo 4، وبالتالي لا يبقى البرهان المحلي بهذه الصورة النظيفة. لهذا تُترك مساهمة القوى الثنائية إلى مرحلة المجموعات الجزئية الصحيحة اللاحقة.
لكل أولي فردي، تجرّب التطبيقات جميع المجموعات الجزئية لـ \(G_p\)، وتحتفظ فقط بالأقنعة التي تحقق شرط التوافق السابق. وبما أن هذه المجموعات صغيرة، فالفحص المحلي الكامل رخيص. لكن الأثر عند \(L=80\) شديد جدًا.
معظم مجموعات القمة لا تسمح إلا بالاختيار الفارغ. فمثلًا المجموعات \(G_3=\{27,54\}\) و\(G_5=\{25,50,75\}\) و\(G_7=\{49\}\) و\(G_{11}=\{11,22,33,44,55,66,77\}\) تنهار فورًا: لا توجد أي مجموعة جزئية غير فارغة تحقق التوافق المطلوب modulo \(p^2\).
المجموعة الوحيدة غير التافهة هي
$$G_{13}=\{13,26,39,52,65,78\}.$$
وفيها يكون الاختياران المحليان الصحيحان هما فقط \(\varnothing\) و\(\{13,39,52\}\). فبعد القسمة على 13 تصبح القيم المعيارية \(1,3,4\)، ولدينا
$$1^{-2}+3^{-2}+4^{-2}\equiv 1+94+74=169\equiv 0 \pmod{169}.$$
إذن مساهمة 13 في أي حل عالمي ليست اختيارًا حرًا من ستة عناصر، بل قرار ثنائي: إما ألا نأخذ شيئًا من هذه المجموعة، أو نأخذ الكتلة الثابتة \(\{13,39,52\}\). أما الأعداد 26 و65 و78 فلا تظهر في أي حل، لأنها لا تنتمي إلى أي قناع محلي صالح.
بعد تطبيق جميع فلاتر الأوليات الفردية، ينخفض عدد المرشحين من 79 عددًا إلى 36 فقط. ثلاثة من هذه الأعداد تنتمي إلى المجموعة الفعالة الوحيدة ذات الأساس 13، أما الثلاثة والثلاثون الأخرى فتمثل الجزء الحر الذي سيُعالَج في المرحلة النهائية.
بعد حذف المقامات المستحيلة، لنرمز بـ \(C\) إلى المضاعف المشترك الأصغر لجميع المرشحين الباقين. ولكل \(n\) باقٍ نعرّف
$$w_n=\frac{C^2}{n^2},\qquad T=\frac{C^2}{2}.$$
وعندها تصبح المعادلة الأصلية مكافئة تمامًا لمسألة مجموعات جزئية صحيحة:
$$\sum_{n\in S} w_n=T.$$
هذه الخطوة جوهرية لأنها تزيل الحساب الكسري من مرحلة البحث نفسها. فكل اختيار محلي صالح يتحول ببساطة إلى مجموع جزئي صحيح.
لكل مجموعة أولية فردية فعالة \(g\)، لنكتب \(A_g(t)\) لعدد الأقنعة الصالحة في تلك المجموعة التي مجموع أوزانها يساوي \(t\). وبما أن المجموعات الفعالة في هذه الحالة \(L=80\) منفصلة عن بعضها، فيمكن دمج مساهماتها استقلاليًا.
تستخدم التطبيقات العلاقة التكرارية
$$B_0(0)=1,\qquad B_{r+1}(u)=\sum_t B_r(u-t)\,A_{r+1}(t),$$
حيث يمثّل \(B_r(u)\) عدد الطرق التي يمكن أن تعطي بها أول \(r\) مجموعات فعالة وزنًا كليًا مقداره \(u\). هذه ليست الإجابة النهائية بعد؛ إنها فقط تجمع جميع الاختيارات التي فرضتها القيود المحلية للأوليات الفردية.
وفي مسألة Euler 152 تصبح هذه المرحلة بسيطة جدًا بعد الغربلة، لأن المجموعة الفعالة الوحيدة هي مجموعة 13. وبالتالي لا يوجد إلا احتمالان مساهمان: عدم أخذ شيء منها، أو أخذ الكتلة \(\{13,39,52\}\).
المقامات الثلاثة والثلاثون الباقية لا تنتمي إلى أي مجموعة قمة لأولي فردي. لنرمز إلى أوزانها بـ \(f_1,\dots,f_{33}\). والبحث المباشر فيها ما زال بحجم \(2^{33}\)، لذلك تقسّمها التطبيقات إلى نصفين حجمهما 16 و17.
لنكتب \(L(x)\) لعدد مجموعات النصف الأيسر التي مجموع أوزانها \(x\)، و\(R(y)\) لعدد مجموعات النصف الأيمن التي مجموع أوزانها \(y\). عندئذ يكون عدد الحلول النهائي
$$\sum_u B(u)\sum_x L(x)\,R(T-u-x).$$
والمعنى العملي لهذا التعبير هو: نختار أولًا مساهمة صالحة من الكتل المقيدة، ثم نختار مجموعًا من النصف الأيسر، ثم نبحث في جدول تجزئة النصف الأيمن عن المتمّم الوحيد الذي يكمّل المجموع إلى الهدف.
مثال مجموعة 13 هو أوضح مثال محلي عند الحد الحقيقي \(L=80\): فهو يبيّن أن شرط التوافق لا يستبعد عناصر منفردة فحسب، بل قد يحوّل ثلاثة أعداد إلى كتلة واحدة من نوع "إما كلها أو لا شيء".
وتستخدم التطبيقات أيضًا مثال تحقق أصغر. فعند \(L=45\) تصح الهوية
$$\frac12=\frac1{2^2}+\frac1{3^2}+\frac1{4^2}+\frac1{5^2}+\frac1{7^2}+\frac1{12^2}+\frac1{15^2}+\frac1{20^2}+\frac1{28^2}+\frac1{35^2}.$$
وفي مجموعة 7 الخاصة بـ \(L=45\)، تكون الأعداد المختارة هي \(\{7,28,35\}\). وبعد القسمة على 7 نحصل على \(\{1,4,5\}\)، ونجد أن
$$1^{-2}+4^{-2}+5^{-2}\equiv 1+46+2=49\equiv 0 \pmod{49}.$$
وهذا يوضح أن الشرط المحلي يظهر بالفعل داخل حل صريح، وليس مجرد حيلة تجريدية. ومن ثم فإن الخوارزمية الكاملة تفرض أولًا كل هذه الشروط المحلية، ثم تحسب الباقي بدقة على المستوى العالمي.
تبدأ تطبيقات C++ وPython وJava بغربلة الأعداد الأولية حتى الحد المطلوب، ثم إيجاد أكبر قوة \(P_p\le 80\) لكل أولي فردي، وبناء المجموعات \(G_p\) المقابلة. بعد ذلك تُفحص جميع الأقنعة لكل مجموعة صغيرة باستخدام المعكوسات المعيارية لمربعات القيم المعيارية modulo \(p^2\). ومن هذه الخطوة تعرف الشيفرة أي الأقنعة المحلية صالحة، وأي المقامات لا تظهر في أي قناع صالح فيمكن حذفها نهائيًا.
بعد الغربلة يُحسب المقام المشترك \(C\)، ثم يُحوَّل كل حد باقٍ \(1/n^2\) إلى الوزن الصحيح \(C^2/n^2\)، ويُضبط الهدف عند \(C^2/2\). كل قناع صالح في كل مجموعة أولية فعالة يتحول إلى مجموع وزني جزئي، ثم تُدمج هذه المجموعات الفعالة بالعلاقة الالتفافية السابقة. والنتيجة هي خريطة من المجموع الجزئي المقيد إلى عدد الطرق المؤدية إليه.
تُقسَّم الأوزان الحرة إلى نصفين. وتقوم كل نسخة من التنفيذ بتعداد جميع مجاميع المجموعات الجزئية في النصفين، مع تخزين المجموع وعدد مرات ظهوره فقط، لا قائمة المجموعات نفسها. ثم تُحسب الإجابة النهائية بتمرير المجاميع اليسرى والمجاميع المقيدة والبحث في جدول النصف الأيمن عن القيمة المتممة اللازمة للوصول إلى الهدف.
نسختا C++ وPython تستطيعان موازاة هذه المرحلة الأخيرة عندما تكون الجداول كبيرة بما يكفي، بينما تحتفظ نسخة Java بالبنية الحسابية نفسها في تدفق أبسط وأحادي الخيط. كما أن نسختي C++ وPython تتحققان من صحة المنهج على أمثلة أصغر، منها ثلاث هويات صريحة عند \(L=45\)، وحقيقة وجود ثلاثة حلول فقط حتى 45، ومقارنة مع العدّ الخام عند \(L=18\).
إذا كانت أحجام المجموعات الأولية الفعالة هي \(g_1,g_2,\dots\)، فإن بناء جداول الصلاحية المحلية يكلف
$$O\!\left(\sum_i 2^{g_i}g_i\right),$$
لأن كل مجموعة صغيرة تُفحص بالكامل. وإذا رمزنا بـ \(A_i\) إلى عدد الخيارات الوزنية المختلفة الناتجة من المجموعة \(i\)، فإن التفاف المجموعات المقيدة يكلف تقريبًا \(O\!\left(\sum_i |B_{i-1}|\,|A_i|\right)\).
أما الكلفة المسيطرة فتأتي من meet-in-the-middle على الجزء الحر. فإذا بقي \(f\) مقامًا حرًا، نحتاج تقريبًا إلى \(2^{\lfloor f/2\rfloor}+2^{\lceil f/2\rceil}\) تعدادًا للمجموعات الجزئية، إضافة إلى عمليات البحث في جداول التجزئة عن المتممات. وفي مسألة Euler 152 الفعلية، تختزل الفلاتر المحلية المسألة إلى كتلة أولية فردية غير تافهة واحدة و\(f=33\) عددًا حرًا، ولهذا يصبح حجم البحث أقرب إلى \(2^{16}+2^{17}\) كثيرًا من \(2^{79}\).
وتتركز الذاكرة أساسًا في جداول التجزئة الخاصة بمجاميع النصفين، وفي خريطة المجاميع الجزئية المقيدة. وهذا هو التبادل الصحيح هنا: قليل من الذاكرة يعوّض عن بحث brute force فلكي الحجم.