Detailed mathematical approach

Problem Summary

For each \(n\), the counting formula used by the implementations is

$C(n)=6\sum_{k=0}^{\pi(n)} \binom{n-1}{k}5^{\,n-1-k},$

where \(\pi(n)\) is the number of primes not exceeding \(n\). The final target is the cumulative sum

$S(L)=\sum_{n=1}^{L} C(n)\pmod{10^9+7},\qquad L=50{,}000{,}000.$

A direct evaluation of every truncated binomial sum would be far too slow, so the solution derives a constant-time transition from \(n\) to \(n+1\).

Mathematical Approach

Step 1: Isolate the Summand

Define

$B_n(k)=\binom{n-1}{k}5^{\,n-1-k},\qquad t_n=\pi(n).$

Then the inner truncated sum is

$P_n=\sum_{k=0}^{t_n} B_n(k),$

so the quantity contributed at level \(n\) is simply

$C(n)=6P_n.$

The whole problem is therefore reduced to updating \(P_n\) efficiently as \(n\) increases.

Step 2: Pascal's Identity Gives the Row Transition

Using

$\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1},$

we obtain

$B_{n+1}(k)=\binom{n}{k}5^{\,n-k}=5B_n(k)+B_n(k-1).$

This recurrence is the key structural fact. It says that every term in the next row depends only on two neighboring terms from the current row, so there is no need to rebuild the full truncated sum from scratch.

Step 3: Only the Boundary Matters

The cutoff \(t_n=\pi(n)\) changes by at most one when \(n\) increases. Therefore it is enough to keep:

$P_n=\sum_{k=0}^{t_n} B_n(k),\qquad U_n=B_n(t_n),\qquad V_n=B_n(t_n+1).$

These are, respectively, the truncated sum, the last included term, and the first excluded term. The initial state is immediate from \(n=1\):

$t_1=\pi(1)=0,\qquad P_1=1,\qquad U_1=1,\qquad V_1=0.$

Step 4: Transition When \(n+1\) Is Composite

If \(n+1\) is composite, then \(t_{n+1}=t_n=t\). Summing the row transition up to \(k=t\) gives

$\begin{aligned} P_{n+1} &=\sum_{k=0}^{t}\left(5B_n(k)+B_n(k-1)\right) \\ &=5\sum_{k=0}^{t}B_n(k)+\sum_{k=0}^{t-1}B_n(k) \\ &=6P_n-U_n. \end{aligned}$

The new boundary terms are

$U_{n+1}=5U_n+B_n(t-1),\qquad V_{n+1}=5V_n+U_n.$

The missing term \(B_n(t-1)\) is recovered from a ratio:

$\frac{B_n(t-1)}{B_n(t)}=\frac{\binom{n-1}{t-1}5^{\,n-t}}{\binom{n-1}{t}5^{\,n-1-t}}=\frac{5t}{n-t},$

hence

$B_n(t-1)=U_n\cdot \frac{5t}{n-t}.$

Step 5: Transition When \(n+1\) Is Prime

If \(n+1\) is prime, then the cutoff moves to the right: \(t_{n+1}=t_n+1=t+1\). The next truncated sum now includes one extra boundary term:

$P_{n+1}=6P_n+5V_n.$

The new last included term is

$U_{n+1}=5V_n+U_n,$

and the new first excluded term satisfies

$V_{n+1}=5B_n(t+2)+V_n.$

Again a ratio gives the unseen term:

$\frac{B_n(t+2)}{B_n(t+1)}=\frac{\binom{n-1}{t+2}5^{\,n-t-3}}{\binom{n-1}{t+1}5^{\,n-t-2}}=\frac{n-t-2}{5(t+2)},$

so

$B_n(t+2)=V_n\cdot \frac{n-t-2}{5(t+2)}.$

If \(t+2>n-1\), that term is simply \(0\), exactly as the implementations handle it.

Step 6: Modular Arithmetic and Final Accumulation

Every step contributes

$C(n)=6P_n,$

therefore

$S(L)\equiv \sum_{n=1}^{L} 6P_n \pmod{10^9+7}.$

The recurrence contains divisions by \(n-t\), \(t+2\), and \(5\). Since the modulus \(10^9+7\) is prime and all these numbers are positive and strictly smaller than the modulus for the target range, each division is replaced by multiplication with a modular inverse.

Sanity Checks

The derived formulas reproduce the exact checkpoint values used by the implementations:

$C(3)=216,\qquad C(4)=1290,\qquad C(11)=361912500,$

$C(24)=4727547363281250000,$

and for the cumulative sum,

$S(50)\equiv 832833871 \pmod{10^9+7}.$

How the Code Works

The C++, Python, and Java implementations all follow the same plan. They first build a primality table up to \(L+1\), because only the question “is \(n+1\) prime?” decides which recurrence branch to use. They also precompute modular inverses up to \(L+2\), which turns the rational boundary ratios into constant-time modular multiplications. A single forward pass then maintains the truncated sum together with the two boundary terms, updates them with the prime or composite formulas above, and adds \(6P_n\) to the running answer at each step.

Complexity Analysis

The sieve costs \(O(L\log\log L)\) time. Precomputing modular inverses costs \(O(L)\) time. The recurrence itself performs only constant-time arithmetic per \(n\), so the main loop is \(O(L)\). Overall the method is \(O(L\log\log L)\) time and \(O(L)\) memory, with only \(O(1)\) recurrence state beyond the primality and inverse tables.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=423
2. Binomial coefficient and Pascal's identity: Wikipedia — Binomial coefficient
3. Prime-counting function \(\pi(n)\): Wikipedia — Prime-counting function
4. Sieve of Eratosthenes: Wikipedia — Sieve of Eratosthenes
5. Modular multiplicative inverse: Wikipedia — Modular multiplicative inverse