Detailed mathematical approach

Problem Summary

Define

$$N=10^{18},\qquad K=10^9,\qquad B=\binom{N}{K}.$$

For every prime \(p\) with \(1000 \lt p \lt 5000\), we need the residue \(B \bmod p\). Then, for every triple of distinct primes \(p \lt q \lt r\) in that interval, we reconstruct the unique number \(x_{pqr}\) with

$$0 \le x_{pqr} \lt pqr,\qquad x_{pqr}\equiv B \pmod{p},\qquad x_{pqr}\equiv B \pmod{q},\qquad x_{pqr}\equiv B \pmod{r}.$$

The required answer is the sum of all these reconstructed values. The sieve used in the code finds exactly \(501\) primes in the interval, so the outer summation runs over

$$\binom{501}{3}=20833250$$

prime triples.

Mathematical Approach

Step 1: Lucas's Theorem Reduces the Huge Binomial

For a fixed prime \(p\), write \(N\) and \(K\) in base \(p\):

$$N=\sum_{t=0}^{s} N_t p^t,\qquad K=\sum_{t=0}^{s} K_t p^t,\qquad 0 \le N_t,K_t \lt p.$$

Lucas's theorem gives the congruence

$$\binom{N}{K}\equiv \prod_{t=0}^{s}\binom{N_t}{K_t}\pmod{p}.$$

If some digit satisfies \(K_t \gt N_t\), then \(\binom{N_t}{K_t}=0\), so the whole product is \(0\pmod p\). This is exactly why the implementation stops immediately and returns zero in that case.

The interval \(1000 \lt p \lt 5000\) makes the digit loop very short. Because \(p \gt 1000\), the number \(10^{18}\) has at most six base-\(p\) digits, and \(10^9\) has at most three. So each residue \(B \bmod p\) is computed from only a handful of digit-level binomials.

Step 2: Each Digit-Level Binomial Is Small

For \(0 \le b \le a \lt p\), we evaluate

$$\binom{a}{b}=\frac{a!}{b!(a-b)!}\pmod{p}.$$

Because \(p\) is prime and \(a,b \lt p\), the denominator is invertible modulo \(p\). The code therefore precomputes

$$\text{fact}[i]=i!\pmod p,\qquad \text{invFact}[i]=(i!)^{-1}\pmod p,$$

and then uses

$$\binom{a}{b}\equiv \text{fact}[a]\cdot \text{invFact}[b]\cdot \text{invFact}[a-b]\pmod p.$$

The modular inverses come from Fermat's little theorem:

$$x^{p-1}\equiv 1\pmod p\quad\Longrightarrow\quad x^{-1}\equiv x^{p-2}\pmod p,$$

which is why all three implementations contain a fast modular exponentiation routine.

Worked Lucas Checkpoint

The C++ code verifies Lucas's theorem on the smaller example \(\binom{30}{12}\). Take \(p=11\). In base \(11\),

$$30=2\cdot 11+8,\qquad 12=1\cdot 11+1.$$

Lucas gives

$$\binom{30}{12}\equiv \binom{8}{1}\binom{2}{1}=8\cdot 2=16\equiv 5\pmod{11}.$$

The exact value is \(\binom{30}{12}=86493225\), and indeed \(86493225 \equiv 5 \pmod{11}\). The checkpoint in the local source repeats this comparison for several primes.

Step 3: Reconstruct One Triple by the Chinese Remainder Theorem

Suppose we already know

$$a\equiv B\pmod p,\qquad b\equiv B\pmod q,\qquad c\equiv B\pmod r,$$

with \(p,q,r\) distinct primes. Since these moduli are pairwise coprime, the Chinese Remainder Theorem guarantees a unique residue modulo \(pqr\).

The code uses a Garner-style two-stage reconstruction. First write

$$x_{pq}=a+p\,t.$$

To make this also congruent to \(b\pmod q\), we need

$$a+p\,t\equiv b\pmod q,$$

so

$$t\equiv (b-a)\,p^{-1}\pmod q.$$

Hence

$$x_{pq}=a+p\left((b-a)\,p^{-1}\bmod q\right),\qquad 0 \le x_{pq} \lt pq.$$

Now lift once more by writing

$$x=x_{pq}+pq\,u.$$

Imposing \(x\equiv c\pmod r\) yields

$$u\equiv (c-x_{pq})(pq)^{-1}\pmod r,$$

and therefore

$$x=x_{pq}+pq\left((c-x_{pq})(pq)^{-1}\bmod r\right),\qquad 0 \le x \lt pqr.$$

This final \(x\) is the value denoted \(x_{pqr}\) in the statement.

Step 4: Why the Precomputed Inverse Table Is Enough

The implementations store every pairwise inverse

$$\text{inv}[i][j]\equiv p_i^{-1}\pmod{p_j}.$$

Then the inverse of a product is obtained for free:

$$ (pq)^{-1}\equiv p^{-1}q^{-1}\pmod r.$$

So once the table of pairwise inverses has been built, each triple reconstruction uses only a few modular additions and multiplications. There is no extended Euclidean algorithm inside the cubic loop.

Worked CRT Checkpoint

The local C++ checkpoints also test the CRT stage on \(\binom{20}{8}=125970\) and the tiny prime set \(\{7,11,13,17\}\). For the triple \((7,11,13)\), the exact residues are

$$125970\equiv 5\pmod 7,\qquad 125970\equiv 9\pmod{11},\qquad 125970\equiv 0\pmod{13}.$$

First combine \(7\) and \(11\):

$$t\equiv (9-5)\cdot 7^{-1}\equiv 4\cdot 8\equiv 10\pmod{11},$$

so

$$x_{7,11}=5+7\cdot 10=75.$$

Next combine with \(13\): since \(75\equiv 10\pmod{13}\) and \(77\equiv 12\pmod{13}\),

$$u\equiv (0-10)\cdot 12^{-1}\equiv 3\cdot 12\equiv 10\pmod{13},$$

which gives

$$x_{7,11,13}=75+77\cdot 10=845.$$

This matches the direct reduction \(125970\bmod(7\cdot 11\cdot 13)=845\). Summing the four tiny triples \((7,11,13)\), \((7,11,17)\), \((7,13,17)\), and \((11,13,17)\) gives the checkpoint total \(3803\) used by the source.

Step 5: Final Summation

If \(\mathcal P\) denotes the set of primes between \(1000\) and \(5000\), the target quantity is

$$\boxed{S=\sum_{p \lt q \lt r,\; p,q,r\in\mathcal P} x_{pqr}.}$$

Running the supplied implementations yields

$$S=162619462356610313.$$

How the Code Works

The three language versions follow the same structure. They first generate the prime list with a sieve, then compute every Lucas residue \(B \bmod p\), then precompute all pairwise inverses \(p_i^{-1}\bmod p_j\), and finally iterate over all prime triples. The C++ version accumulates the sum in unsigned __int128, the Java version uses BigInteger, and the Python version relies on Python's built-in arbitrary-precision integers.

Complexity Analysis

Let \(m=501\) be the number of primes in the interval. Sieve construction up to \(5000\) is negligible, roughly \(O(5000\log\log 5000)\). The Lucas preprocessing costs

$$\sum_{p\in\mathcal P} O(p+\log_p N),$$

because each prime builds factorial and inverse-factorial tables of size \(p\), while the digit loop is tiny. Precomputing pairwise inverses costs \(O(m^2)\) time and memory. The dominant stage is the triple loop, which performs

$$\binom{m}{3}=\binom{501}{3}=20833250$$

constant-time CRT merges. Therefore the overall running time is \(O(m^3)\), and the memory usage is \(O(m^2)\) because of the inverse matrix.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=365
2. Lucas's theorem: Wikipedia — Lucas's theorem
3. Chinese remainder theorem: Wikipedia — Chinese remainder theorem
4. Fermat's little theorem: Wikipedia — Fermat's little theorem
5. Garner-style reconstruction: cp-algorithms — Chinese remainder theorem