Detailed mathematical approach

Problem Summary

Let \(p_n\) be the \(n\)-th prime, and define \(r_n\) as the least nonnegative remainder of

$\left((p_n-1)^n+(p_n+1)^n\right)\bmod p_n^2.$

The task is to find the smallest index \(n\) for which \(r_n\gt 10^{10}\). At first sight this looks like a large modular-exponentiation problem, but modulo \(p_n^2\) almost every binomial term disappears. That collapse is the whole reason the problem becomes easy.

Mathematical Approach

The remainder is governed entirely by the first two terms of the binomial expansion. Once that is written out carefully, the problem stops being about huge powers and becomes a search over prime indices.

Binomial expansion modulo \(p_n^2\)

Expand both powers around \(p_n\):

$ (p_n\pm 1)^n=\sum_{k=0}^{n}\binom{n}{k}p_n^k(\pm 1)^{\,n-k}. $

Adding the two expansions gives

$ (p_n-1)^n+(p_n+1)^n = \sum_{k=0}^{n}\binom{n}{k}p_n^k\left((-1)^{n-k}+1\right). $

Any term with \(k\ge 2\) is already divisible by \(p_n^2\), so modulo \(p_n^2\) only the cases \(k=0\) and \(k=1\) can survive. Which of those survives depends only on the parity of \(n\).

Even indices and odd indices behave differently

If \(n\) is even, then the constant terms add and the linear terms cancel, so

$ r_n\equiv 2 \pmod{p_n^2}. $

Because \(0\le 2\lt p_n^2\), the actual remainder is simply \(r_n=2\). Even indices can therefore never exceed \(10^{10}\).

If \(n\) is odd, then the constant terms cancel and the linear terms add, giving

$ r_n\equiv 2np_n \pmod{p_n^2}. $

So for odd indices the remainder is controlled by the single quantity \(2np_n\), but at this stage it is still a congruence rather than an exact equality.

Why the congruence becomes the exact remainder

The implementations compare \(2np_n\) directly against the limit, so we need to know when \(2np_n\) is already smaller than \(p_n^2\). A simple counting argument is enough. For \(n\ge 5\), the odd numbers

$ 1,3,5,\dots,2n-1 $

form a list of exactly \(n\) numbers. Among them, both \(1\) and \(9\) are non-prime, so there are at most \(n-2\) odd primes below \(2n\). Including the prime \(2\), there are at most \(n-1\) primes not exceeding \(2n\). Therefore the \(n\)-th prime must satisfy

$ p_n\gt 2n \qquad (n\ge 5). $

For odd \(n\ge 5\) this implies

$ 0\lt 2np_n\lt p_n^2, $

so the least nonnegative residue of \(2np_n \pmod{p_n^2}\) is exactly \(2np_n\). Hence

$ r_n=2np_n. $

The first solution occurs far beyond \(n=5\), so this is the formula the code can safely search with.

Worked example: \(n=3\) versus \(n=5\)

The distinction between congruence and exact remainder matters for tiny odd indices. For \(n=3\), we have \(p_3=5\), so

$ (5-1)^3+(5+1)^3=4^3+6^3=280. $

Modulo \(25\), this gives \(280\bmod 25=5\). The linear formula gives \(2np_n=2\cdot 3\cdot 5=30\), and indeed \(30\equiv 5\pmod{25}\), but the exact remainder is \(5\), not \(30\).

For \(n=5\), however, \(p_5=11\) and

$ (11-1)^5+(11+1)^5=10^5+12^5=348832. $

Now \(348832\bmod 121=110\), and that equals

$ 2\cdot 5\cdot 11=110. $

Here no wrap-around occurs because \(2n\lt p_n\). The target threshold is so large that the first qualifying index lies in this stable regime.

Estimating the search range

The prime number theorem gives the rough estimate \(p_n\sim n\log n\). Substituting that into the odd-index formula yields

$ 2n^2\log n \gtrsim 10^{10}. $

This places the crossing a little above \(2\times 10^4\). So the program only needs to generate primes up to roughly the corresponding \(p_n\), which is on the order of a few hundred thousand. That makes a straightforward sequential search entirely adequate.

How the Code Works

Generate primes in order

The C++, Python, and Java implementations all walk through the prime sequence in increasing order so that the current prime and its index are known simultaneously. The C++ and Java versions keep a growing list of earlier primes and test each new integer candidate only by those primes up to its square root. The Python version advances from one prime to the next through a prime-generation routine, but conceptually it performs the same ordered scan.

Check only odd indices

Each time a new prime \(p_n\) is reached, the implementation first checks whether \(n\) is odd. Even indices are skipped immediately because their remainder is always \(2\). For odd indices, it evaluates the simple expression \(2np_n\) and stops as soon as this exceeds the limit. None of the implementations ever compute \((p_n-1)^n\) or \((p_n+1)^n\) directly. One implementation also verifies the logic against the smaller threshold \(10^9\) before running the full search.

Complexity Analysis

Let \(P\) be the prime where the search stops. After a prime is known, the mathematical test is constant time: parity check plus one multiplication and one comparison.

In the C++ and Java implementations, the real cost is prime generation by incremental trial division. A candidate \(c\) is tested only by previously found primes up to \(\sqrt c\), so a standard worst-case estimate is

$ O\!\left(\sum_{c=2}^{P}\pi(\sqrt c)\right)=O\!\left(\frac{P^{3/2}}{\log P}\right), $

with memory usage \(O(\pi(P))\) for the stored primes. For this problem \(P\) is only a few \(10^5\), so that cost is small in practice. The Python implementation delegates prime stepping to a library routine, but from the problem's point of view it still performs one constant-time remainder test per prime index.

Footnotes and References

1. Problem page: Project Euler 123 - Prime square remainders
2. Binomial theorem: Wikipedia - Binomial theorem
3. Modular arithmetic: Wikipedia - Modular arithmetic
4. Prime number theorem: Wikipedia - Prime number theorem
5. Prime numbers: Wikipedia - Prime number