Detailed mathematical approach

Problem Summary

For every prime \(p \ge 5\), define

$S(p)=\sum_{k=1}^{5}(p-k)!\pmod{p}=(p-1)!+(p-2)!+(p-3)!+(p-4)!+(p-5)!\pmod{p}.$

The problem asks for the prime sum

$\sum_{5 \le p \lt 10^8} S(p).$

A naive implementation would recompute factorial residues for every prime, but the local C++, Python, and Java solutions all exploit the same fact: after Wilson's theorem, the five factorial terms collapse to one constant-size modular expression.

Mathematical Approach

Step 1: Start from Wilson's theorem

For every prime \(p\), Wilson's theorem gives

$(p-1)! \equiv -1 \pmod{p}.$

Because the problem only uses primes \(p \ge 5\), the numbers \(2\), \(3\), \(4\), \(8\), and \(24\) are all invertible modulo \(p\). That lets us divide congruences safely.

Step 2: Rewrite the descending factorials one by one

Using \(p-1 \equiv -1\), \(p-2 \equiv -2\), \(p-3 \equiv -3\), and \(p-4 \equiv -4 \pmod{p}\), we obtain

$(p-2)! \equiv \frac{(p-1)!}{p-1} \equiv \frac{-1}{-1} \equiv 1 \pmod{p},$

$(p-3)! \equiv \frac{(p-2)!}{p-2} \equiv \frac{1}{-2} \equiv -\frac{1}{2} \pmod{p},$

$(p-4)! \equiv \frac{(p-3)!}{p-3} \equiv \frac{-1/2}{-3} \equiv \frac{1}{6} \pmod{p},$

$(p-5)! \equiv \frac{(p-4)!}{p-4} \equiv \frac{1/6}{-4} \equiv -\frac{1}{24} \pmod{p}.$

So the five required terms are known without ever computing a factorial explicitly.

Step 3: Collapse the five-term sum

Substituting the four derived congruences back into \(S(p)\) gives

$S(p)\equiv -1+1-\frac{1}{2}+\frac{1}{6}-\frac{1}{24}\pmod{p}.$

The integer parts cancel, and the remaining rational combination is

$-\frac{1}{2}+\frac{1}{6}-\frac{1}{24}=-\frac{12}{24}+\frac{4}{24}-\frac{1}{24}=-\frac{9}{24}=-\frac{3}{8}.$

Therefore

$\boxed{S(p)\equiv -\frac{3}{8}\equiv -3\cdot 8^{-1}\pmod{p}.}$

This is the entire mathematical core of the implementation: one modular inverse of \(8\), then one multiplication by \(-3\).

Step 4: Match the exact inverse construction used in code

The source files do not call an extended Euclidean algorithm. Instead, they build an integer representative of \(8^{-1}\pmod{p}\) directly. Let

$r=p\bmod 8,\qquad k=8-r,\qquad \mathrm{inv8}=\frac{kp+1}{8}.$

For an odd prime \(p\), we have \(r\in\{1,3,5,7\}\). Then \(r^2\equiv 1\pmod{8}\), so

$kp+1\equiv (8-r)r+1=1-r^2\equiv 0\pmod{8},$

which proves that \(\mathrm{inv8}\) is an integer. Also, since \(kp\equiv 0\pmod{p}\),

$8\cdot \mathrm{inv8}=kp+1\equiv 1\pmod{p},$

so \(\mathrm{inv8}\equiv 8^{-1}\pmod{p}\). The per-prime contribution is therefore computed as

$S(p)\equiv -3\cdot \mathrm{inv8}\pmod{p}.$

The C++ and Java versions write this as

$\left(2p-\left((3\cdot \mathrm{inv8})\bmod p\right)\right)\bmod p,$

which is just a non-negative way to represent the same residue.

Step 5: Small checkpoints from the local implementation

The C++ solution contains explicit tests. For \(p=7\), \(8^{-1}\equiv 1\pmod{7}\), so

$S(7)\equiv -3\equiv 4\pmod{7},$

matching the checkpoint S_of_prime(7) == 4. It also verifies the closed form against a brute-force factorial computation for \(p\in\{5,7,11,13,17,19\}\), and checks

$\sum_{5 \le p \lt 100} S(p)=480.$

Those checkpoints confirm both the derivation and the implementation details.

How the Code Works

The C++ file exposes the structure most clearly. primes_below(limit) runs a standard sieve of Eratosthenes and returns all primes below the bound. inv8_mod_prime(p) computes \((kp+1)/8\) using the low three bits of \(p\), namely p & 7. S_of_prime(p) then evaluates the closed form in \(O(1)\) time. The main loop skips \(2\) and \(3\), sums the value for every prime \(p \ge 5\), and returns the total.

The Python solution mirrors the same mathematics with a bytearray sieve. The Java solution uses a boolean composite table and computes the inverse inline inside the prime loop. None of the three implementations ever forms \((p-k)!\) directly for large \(p\); only the optional C++ checkpoint routine does that for tiny primes.

Complexity Analysis

Let \(L=10^8\). The dominant cost is generating all primes below \(L\) with the sieve, which takes \(O(L\log\log L)\) time. After that, each prime contributes only a constant number of arithmetic operations, so the post-processing cost is \(O(\pi(L))\), which is asymptotically smaller than the sieve. Memory usage is \(O(L)\) for the sieve array.

This is dramatically better than evaluating factorial residues separately for every prime, which would introduce much larger per-prime work.

References

1. Problem page: https://projecteuler.net/problem=381
2. Wilson's theorem: Wikipedia — Wilson's theorem
3. Modular inverse: cp-algorithms — Modular Multiplicative Inverse
4. Sieve of Eratosthenes: Wikipedia — Sieve of Eratosthenes