Detailed mathematical approach

Problem Summary

For Problem 773, the implementations begin with the first \(k\) primes whose last digit is \(7\). The target quantity is then reduced to an inclusion-exclusion calculation in which a large multiplicative term is corrected by a small decimal-residue term. After that reduction, the whole answer depends only on the product of those primes, the totient of that product, and a short alternating binomial sum with period \(4\).

Mathematical Approach

Let

$p_1,p_2,\dots,p_k$

be the first \(k\) primes satisfying

$p_i \equiv 7 \pmod{10}.$

Define the two central products

$P_k=\prod_{i=1}^k p_i,\qquad \Phi_k=\prod_{i=1}^k (p_i-1).$

Because the primes are distinct, \(\Phi_k\) is exactly Euler's totient of \(P_k\):

$\Phi_k=\varphi(P_k).$

Step 1: Separate the Main Multiplicative Part

The derived counting formula used by the implementations splits each inclusion-exclusion contribution into a large uniform part and a small decimal correction. The uniform part depends on which primes are excluded from a chosen subset, so the natural sum runs over all subsets \(S\subseteq \{1,\dots,k\}\):

$\sum_{S}(-1)^{|S|}\prod_{i\notin S} p_i.$

This is a standard product expansion. Each prime \(p_i\) contributes either \(p_i\) or \(-1\), so the whole sum factors as

$\sum_{S}(-1)^{|S|}\prod_{i\notin S} p_i=\prod_{i=1}^k (p_i-1)=\Phi_k.$

In the final formula this term appears multiplied by \(5\), which is why the dominant contribution is \(5\Phi_k\).

Step 2: Track the Decimal Residue Class

The problem-specific correction depends on the last digit of the product of the selected primes. If a subset has size \(t\), then every chosen prime contributes a factor congruent to \(7 \pmod{10}\), so the subset product has last digit

$7^t \pmod{10}.$

The powers of \(7\) modulo \(10\) are periodic with period \(4\):

$7^0\equiv 1,\quad 7^1\equiv 7,\quad 7^2\equiv 9,\quad 7^3\equiv 3 \pmod{10}.$

To force the relevant multiple back into the decimal class ending in \(7\), the multiplier must satisfy

$m \equiv 7\cdot (7^t)^{-1} \pmod{10}.$

Since the invertible residues modulo \(10\) are \(1,3,7,9\), their inverses are

$1^{-1}\equiv 1,\qquad 7^{-1}\equiv 3,\qquad 9^{-1}\equiv 9,\qquad 3^{-1}\equiv 7 \pmod{10}.$

Therefore the correction sequence is

$w_0=7,\qquad w_1=1,\qquad w_2=3,\qquad w_3=9,$

and then it repeats every four steps.

Step 3: Compress the Correction with Binomial Coefficients

The key simplification is that the correction depends only on the subset size \(t\), not on which particular primes were selected. There are exactly \(\binom{k}{t}\) subsets of size \(t\), so the full correction becomes

$S_k=\sum_{t=0}^{k}(-1)^t\binom{k}{t}w_t,$

where \(w_t\) is understood periodically:

$w_t=w_{t\bmod 4}\in \{7,1,3,9\}.$

This is why the code only needs one short period-4 table instead of handling subsets individually.

Step 4: Assemble the Closed Formula

Combining the multiplicative part and the residue correction yields the exact quantity computed by the implementations:

$R_k \equiv P_k\left(5\Phi_k + S_k\right)\pmod{10^9+7}.$

Substituting the explicit definitions gives

$\boxed{R_k \equiv \left(\prod_{i=1}^k p_i\right)\left(5\prod_{i=1}^k (p_i-1)+\sum_{t=0}^{k}(-1)^t\binom{k}{t}w_t\right)\pmod{10^9+7}.}$

So once the relevant primes are known, the remaining work is purely modular arithmetic.

Step 5: Worked Example for \(k=3\)

The first three primes ending in \(7\) are

$7,\ 17,\ 37.$

Hence

$P_3=7\cdot 17\cdot 37=4403,$

and

$\Phi_3=(7-1)(17-1)(37-1)=6\cdot 16\cdot 36=3456.$

The correction sum uses the pattern \(7,1,3,9\):

$\begin{aligned} S_3&=\binom{3}{0}7-\binom{3}{1}1+\binom{3}{2}3-\binom{3}{3}9\\ &=7-3+9-9\\ &=4. \end{aligned}$

Therefore

$R_3=4403\left(5\cdot 3456+4\right)=4403\cdot 17284=76101452,$

which matches the checkpoint built into the implementations.

How the Code Works

The C++, Python, and Java implementations all follow the same sequence. First they scan the arithmetic progression \(7,17,27,\dots\) and retain exactly those terms that are prime. The primality test is straightforward trial division up to \(\sqrt{n}\), which is sufficient because the required \(k\) is small.

After the prime list is built, the implementation multiplies those primes modulo \(10^9+7\) to obtain \(P_k\), and simultaneously multiplies the factors \(p_i-1\) modulo \(10^9+7\) to obtain \(\Phi_k\).

Next it evaluates the correction sum \(S_k\). Instead of recomputing each binomial coefficient from factorials, it updates them iteratively via

$\binom{k}{t+1}=\binom{k}{t}\frac{k-t}{t+1}.$

Division modulo the prime modulus is performed with a modular inverse:

$a^{-1}\equiv a^{M-2}\pmod{M},\qquad M=10^9+7.$

The alternating sign is handled term by term, the period-4 residue table supplies \(w_t\), and finally the program multiplies \(P_k\) by \(5\Phi_k+S_k\) modulo \(10^9+7\). One implementation also includes the \(k=3\) checkpoint shown above before evaluating the final \(k=97\) case.

Complexity Analysis

Let \(B\) be the largest candidate examined while collecting the first \(k\) primes ending in \(7\). With trial division, primality testing costs \(O(\sqrt{n})\) per candidate, so the prime-generation phase is the dominant part and is bounded by \(O(B^{3/2})\) in the simplest worst-case estimate. The modular accumulation of \(P_k\) and \(\Phi_k\) is \(O(k)\), and the binomial correction loop is \(O(k\log M)\) because each modular inverse is computed by fast exponentiation. Memory usage is \(O(k)\) for the stored prime list.

Footnotes and References

1. Problem page: Project Euler 773
2. Euler's totient function: Wikipedia - Euler's totient function
3. Inclusion-exclusion principle: Wikipedia - Inclusion-exclusion principle
4. Binomial coefficient: Wikipedia - Binomial coefficient
5. Modular multiplicative inverse: Wikipedia - Modular multiplicative inverse