Problem 152: Writing 1/2 as a Sum of Inverse Squares

Mathematical Development

Definition 1. Let $L = \operatorname{lcm}(k^2 : 2 \le k \le 80)$. For any subset $S \subseteq \{2, \ldots, 80\}$, define $\Sigma(S) = \sum_{k \in S} L / k^2$, so the target equation becomes $\Sigma(S) = L/2$.

Theorem 1 (Large Prime Elimination). Let $p$ be a prime with $40 < p \le 80$. Then $p \notin S$ for any valid subset $S$.

Proof. Since $p > 40$, the only multiple of $p$ in $\{2, \ldots, 80\}$ is $p$ itself (as $2p > 80$). Consider the $p$-adic valuation of the cleared equation $\Sigma(S) = L/2$. We have $v_p(L) = 2$ (from $p^2 \mid L$ and $p^3 \nmid L$, since $p^2 \le 6400 \le L$ but $p^2$ appears only once in the range). For $k \neq p$ with $p \nmid k$, $v_p(L/k^2) = v_p(L) = 2$. For $k = p$, $v_p(L/p^2) = v_p(L) - 2 = 0$.

Suppose $p \in S$. Then $v_p(\Sigma(S)) = \min(v_p(L/p^2), \min_{k \in S \setminus \{p\}} v_p(L/k^2)) = \min(0, 2) = 0$. But $v_p(L/2) = v_p(L) - v_p(2) = 2$ (since $p \ge 41 > 2$). This gives $0 = v_p(\Sigma(S)) \neq v_p(L/2) = 2$, a contradiction (more precisely, the term with $v_p = 0$ cannot cancel since it is the unique term with minimal $p$-adic valuation). Hence $p \notin S$.

This eliminates $\{41, 43, 47, 53, 59, 61, 67, 71, 73, 79\}$. $\square$

Theorem 2 (Paired Prime Elimination). Let $p$ be a prime with $26 < p \le 40$, and let $M_p = \{k \in \{2, \ldots, 80\} : p \mid k\}$. The subset $S \cap M_p$ must satisfy a modular constraint: the partial sum $\sum_{k \in S \cap M_p} L/k^2$ must be congruent to a specific residue modulo $p^{v_p(L)}$. For each such $p$, exhaustive enumeration of the (at most $2^{|M_p|}$) subsets of $M_p$ determines which elements can appear.

Proof. Write the cleared equation as $\Sigma(S) = L/2$. Partition $S = (S \cap M_p) \sqcup (S \setminus M_p)$. For every $k \in S \setminus M_p$, we have $p \nmid k$, so $v_p(L/k^2) \ge v_p(L)$. Hence $\sum_{k \in S \setminus M_p} L/k^2 \equiv 0 \pmod{p^{v_p(L)}}$. Also $v_p(L/2) \ge v_p(L)$ since $p \ge 29 > 2$, so $L/2 \equiv 0 \pmod{p^{v_p(L)}}$.

Therefore $\sum_{k \in S \cap M_p} L/k^2 \equiv 0 \pmod{p^{v_p(L)}}$. Since $|M_p| \le 3$ for $p \ge 29$ (at most $p, 2p$ and possibly $3p$ lie in $\{2, \ldots, 80\}$), the constraint is verified by exhaustive check over at most $2^3 = 8$ subsets. If no non-empty subset of $M_p$ satisfies the congruence, all elements of $M_p$ are excluded from $S$. $\square$

Lemma 1 (Reduced Candidate Set). Applying Theorems 1 and 2 systematically for all primes $p$ from 79 down to 2, the candidate set reduces from 79 elements to approximately 36 elements, with certain elements forced to appear in specific groups.

Proof. Direct computation of modular constraints for each prime. The eliminated elements include all multiples of primes $\ge 29$ that fail the congruence test, as well as various multiples of smaller primes constrained by similar $p$-adic arguments. $\square$

Theorem 3 (Correctness of DFS Enumeration). The valid subsets are enumerated by depth-first search over the reduced candidate set with integer arithmetic and the following pruning rules:

1. If the partial sum exceeds $L/2$, prune (remaining terms are positive).
2. If the partial sum plus the sum of all remaining candidates is less than $L/2$, prune (insufficient capacity).

The search is exhaustive over the non-pruned branches and therefore returns the exact count.

Proof. Let $c_1 < c_2 < \cdots < c_m$ be the sorted candidates with corresponding values $v_i = L / c_i^2$. The DFS considers, for each index $i$, whether to include $c_i$ in $S$. Let $R_i = \sum_{j \ge i} v_j$. At any node with partial sum $\sigma$ at index $i$:

• If $\sigma > L/2$: since $v_j > 0$ for all $j$, adding further elements only increases the sum, so no completion exists.
• If $\sigma + R_i < L/2$: even including all remaining elements cannot reach $L/2$, so no completion exists.

Both pruning conditions eliminate only infeasible branches. The base case ($i = m$ or $\sigma = L/2$) is exact. By structural induction on the DFS tree, all valid subsets are found. $\square$

Editorial

We prime elimination (reduce candidate set). Finally, integer DFS with pruning. We perform a recursive search over the admissible choices, prune branches that violate the derived constraints, and keep only the candidates that satisfy the final condition.

Pseudocode

Prime elimination (reduce candidate set)
Integer DFS with pruning

Complexity Analysis

• Time: $O(2^m)$ in the worst case where $m \approx 36$ is the candidate count. The branch-and-bound pruning dramatically reduces the effective search space; empirically the search completes in under one second.
• Space: $O(m)$ for the recursion stack and $O(m)$ for the precomputed suffix sums.

Answer

#include <bits/stdc++.h>
using namespace std;
typedef long double ld;

int main() {
    set<int> excluded = {
        79,73,71,67,61,59,53,47,43,41,37,74,31,62,29,58,23,46,69,
        19,38,57,76,34,51,26,65,78,11,22,33,44,55,66,77,49,25,50,
        75,27,54,17,68
    };

    vector<int> candidates;
    for (int k = 2; k <= 80; k++)
        if (excluded.find(k) == excluded.end())
            candidates.push_back(k);

    int n = candidates.size();
    ld target = 0.5L;

    vector<ld> vals(n);
    for (int i = 0; i < n; i++)
        vals[i] = 1.0L / ((ld)candidates[i] * candidates[i]);

    vector<ld> suffix(n + 1, 0);
    for (int i = n - 1; i >= 0; i--)
        suffix[i] = suffix[i + 1] + vals[i];

    int count = 0;
    ld eps = 1e-18L;

    function<void(int, ld)> dfs = [&](int idx, ld current) {
        if (fabsl(current - target) < eps) { count++; return; }
        if (idx >= n) return;
        ld need = target - current;
        if (need < -eps) return;
        if (suffix[idx] < need - eps) return;
        for (int i = idx; i < n; i++) {
            if (vals[i] > need + eps) continue;
            if (suffix[i] < need - eps) return;
            dfs(i + 1, current + vals[i]);
        }
    };

    dfs(0, 0.0L);
    printf("%d\n", count);
    return 0;
}

from fractions import Fraction
from math import gcd
from functools import reduce

def solve():
    excluded = {
        79, 73, 71, 67, 61, 59, 53, 47, 43, 41, 37, 74, 31, 62, 29, 58,
        23, 46, 69, 19, 38, 57, 76, 34, 51, 26, 65, 78, 11, 22, 33, 44,
        55, 66, 77, 49, 25, 50, 75, 27, 54, 17, 68
    }
    candidates = sorted(k for k in range(2, 81) if k not in excluded)

    def lcm(a, b):
        return a * b // gcd(a, b)

    L = reduce(lcm, (k * k for k in candidates))
    target = L // 2
    vals = [L // (k * k) for k in candidates]
    n = len(candidates)

    suffix = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        suffix[i] = suffix[i + 1] + vals[i]

    count = 0

    def dfs(idx, current):
        nonlocal count
        if current == target:
            count += 1
            return
        if idx >= n:
            return
        need = target - current
        if need <= 0 or suffix[idx] < need:
            return
        for i in range(idx, n):
            if vals[i] > need:
                continue
            if suffix[i] < need:
                return
            dfs(i + 1, current + vals[i])

    dfs(0, 0)
    print(count)

solve()