Detailed mathematical approach

Problem Summary

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.

Mathematical Approach

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.

Congruence Conditions from Maximal Odd Prime Powers

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.

What the Local Filters Do at \(L=80\)

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.

Turning the Rational Equation into Integer Weights

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.

Convolving the Constrained Prime Blocks

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\}\).

Meet-in-the-Middle on the Free Part

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.

Worked Examples

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.

How the Code Works

Build the Odd-Prime Feasibility Data

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.

Convert Legal Local Choices into Weighted Partial Sums

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.

Enumerate the Free Halves and Match Complements

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\).

Complexity Analysis

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.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=152
2. Subset-sum problem: Wikipedia - Subset sum problem
3. \(p\)-adic valuation: Wikipedia - p-adic valuation
4. Least common multiple: Wikipedia - Least common multiple
5. Modular multiplicative inverse: Wikipedia - Modular multiplicative inverse