Detailed mathematical approach

Problem Summary

For an odd prime \(p\), pair the numbers \(1,2,\dots,p-1\) into \(\frac{p-1}{2}\) disjoint pairs. Each pair \(\{a,b\}\) contributes the least positive residue of \(ab \bmod p\), and the goal is to minimize the total sum over all pairs. The implementations solve the large target prime by converting this pairing problem into a modular optimization problem inside \((\mathbb{Z}/p\mathbb{Z})^\times\), then reconstructing the corresponding witness integer.

Mathematical Approach

Let \(n=\frac{p-1}{2}\). If a pairing produces pair residues \(r_1,\dots,r_n\in\{1,\dots,p-1\}\), then the total pairing cost is

$S(p)=\min \sum_{i=1}^{n} r_i.$

Step 1: Every valid pairing gives a product constraint

If the pairs are \(\{a_i,b_i\}\), then \(r_i\equiv a_i b_i \pmod p\). Because the pairing uses each nonzero residue exactly once, we get

$\prod_{i=1}^{n} r_i \equiv \prod_{k=1}^{p-1} k \equiv -1 \pmod p,$

where the last congruence is Wilson's theorem. So every admissible pairing yields a multiset of positive residues whose product is \(-1\) modulo \(p\).

Step 2: Split the total into baseline plus excess

Every pair contributes at least \(1\), so

$\sum_{i=1}^{n} r_i = n + \sum_{i=1}^{n}(r_i-1).$

The constant term \(n\) is unavoidable. The real optimization is the excess \(\sum (r_i-1)\).

If a residue \(c>1\) is composite, say \(c=uv\), then

$c-1=(u-1)+(v-1)+(u-1)(v-1)\ge (u-1)+(v-1).$

This is why prime factors are the natural atomic pieces: splitting a composite residue into smaller factors never increases the excess. The implementations therefore search for a witness of the form

$W=\prod_q q^{e_q}\equiv -1 \pmod p,$

with \(q\) prime and \(e_q\ge 0\), minimizing

$E(p)=\sum_q e_q(q-1).$

For the large target prime, this excess is tiny compared with \(n\), so the factorized search matches the pairing objective cleanly. The small-prime checks in the C++ implementation confirm the relation

$S(p)=\frac{p-1}{2}+E(p).$

Step 3: Compress the search into residue-cost states

Fix a current excess budget \(B\). Any prime with \(q-1>B\) cannot appear, so only primes \(q\le B+1\) matter. An exponent vector determines two values:

$r=\prod_q q^{e_q}\bmod p,\qquad c=\sum_q e_q(q-1).$

For each reachable residue \(r\), only the smallest cost \(c\) matters. Many exponent vectors can therefore be compressed into one best state per residue class.

Step 4: Use meet-in-the-middle

Split the allowed primes into two groups. Enumerate all reachable residue-cost states on the left and on the right, always staying within the same budget \(B\). If the left side produces \(r_A\), then the right side must produce

$r_B\equiv -r_A^{-1}\pmod p$

so that \(r_A r_B\equiv -1\pmod p\). Because \(p\) is prime, every nonzero residue has an inverse. The cheapest compatible left-right combination gives the best excess under budget \(B\).

The implementations further speed up the merge step by computing many inverses in one batch, using prefix products and one Fermat-style inverse instead of inverting every left residue separately.

Step 5: Reconstruct the exact witness

After the smallest feasible excess has been found, a second exact search recovers the exponents \(e_q\) that attain it. Their product

$W=\prod_q q^{e_q}$

is then built as an arbitrary-precision integer. This witness is what the implementations finally print for the large prime from the problem.

Worked Example: \(p=7\)

Here \(n=\frac{7-1}{2}=3\), and the target congruence is \(W\equiv -1\equiv 6 \pmod 7\).

The cheapest prime-factor witness is

$W=2\cdot 3=6,$

with excess

$E(7)=(2-1)+(3-1)=3.$

So the predicted minimum pairing cost is

$S(7)=3+3=6.$

An explicit pairing is

$\{1,3\},\qquad \{2,4\},\qquad \{5,6\},$

whose pair residues are \(3\), \(1\), and \(2\). Their sum is \(3+1+2=6\), and their product is \(3\cdot 1\cdot 2=6\equiv -1\pmod 7\), exactly as the theory predicts. The \(p=5\) checkpoint works the same way: \(W=4=2^2\), the excess is \(2\), and the optimal pairing sum is \(4\).

How the Code Works

The C++, Python, and Java implementations start with a small excess budget and enlarge it gradually until a feasible witness appears. For each budget they generate all primes up to \(B+1\), split them into two groups, and recursively enumerate every exponent pattern whose weighted cost stays within the budget. Each side stores only the cheapest cost for each residue modulo \(p\).

After the two maps are built, the implementation searches for matching residues whose product is \(-1\) modulo \(p\). When the first successful budget is found, a second recursive pass reconstructs the exact exponents and multiplies the corresponding primes to obtain the final big-integer witness \(W\). The C++ implementation also checks small primes by exhaustive pairing search, confirming that the computed excess matches the true minimum pairing total after adding the baseline \(\frac{p-1}{2}\).

Complexity Analysis

Let \(B^*\) be the minimal excess cost. For a given budget \(B\), sieving primes up to \(B+1\) costs \(O(B\log\log B)\). The dominant work is enumerating exponent vectors satisfying

$\sum_q e_q(q-1)\le B.$

If \(N_A(B)\) and \(N_B(B)\) are the numbers of states explored on the two sides, then one round costs

$O\bigl(B\log\log B + N_A(B) + N_B(B)\bigr)$

time. Memory usage is

$O\bigl(M_A(B)+M_B(B)\bigr),$

where \(M_A(B)\) and \(M_B(B)\) are the numbers of stored residues in the two hash maps. In practice the budget stays small, so the running time depends much more on the optimal excess than on the huge size of \(p\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=789
2. Wilson's theorem: Wikipedia — Wilson's theorem
3. Multiplicative group modulo \(n\): Wikipedia — Multiplicative group of integers modulo n
4. Fermat's little theorem: Wikipedia — Fermat's little theorem
5. Meet-in-the-middle: Wikipedia — Meet-in-the-middle
6. Matching in graph theory: Wikipedia — Matching