Solution

Answer: 556206950

Let

$$S_k={2,5,p_1,p_2,\dots,p_k},$$

where $p_i$ are the first $k$ primes ending in $7$, and define

$$M=\prod_{i=1}^k p_i,\qquad N_k=10M.$$

A $k$-Ruff number is one not divisible by any element of $S_k$.

We seek

$$F(k)=\sum_{\substack{0\le n<N_k\ n\equiv 7\pmod{10}\ \gcd(n,M)=1}} n.$$

The problem gives $F(3)=76101452$.

1. Mathematical analysis

Every number ending in $7$ can be written uniquely as

$$n=10a+7,\qquad 0\le a<M.$$

Since such numbers are automatically not divisible by $2$ or $5$, the only restriction is:

$$\gcd(n,M)=1.$$

Thus:

$$F(k)=\sum_{\substack{0\le a<M\ \gcd(10a+7,M)=1}} (10a+7).$$

We now use inclusion–exclusion over the prime divisors of $M$.

Step 1: Sum of all numbers ending in 7 below $10M$

These are

$$7,17,27,\dots,10M-3.$$

There are exactly $M$ terms, so

$$U = \frac{M\bigl(7+(10M-3)\bigr)}2 = \frac{M(10M+4)}2 =5M^2+2M.$$

Step 2: Numbers divisible by a divisor $d\mid M$

For squarefree $d\mid M$, define

$$A_d={n<10M : n\equiv 7\pmod{10},\ d\mid n}.$$

Because every prime divisor of $M$ is $7\bmod 10$,

if $d\equiv 1\pmod{10}$, then $n=d(10t+7)$,
if $d\equiv 7\pmod{10}$, then $n=d(10t+1)$.

Let

$$\varepsilon(d)= \begin{cases} 7,& d\equiv1\pmod{10},\ 1,& d\equiv7\pmod{10}. \end{cases}$$

Then the numbers in $A_d$ are

$$d(\varepsilon(d)+10t), \qquad t=0,1,\dots,\frac{M}{d}-1.$$

Let $c=M/d$. Their sum is

$$\sum_{n\in A_d} n = d\sum_{t=0}^{c-1}(\varepsilon(d)+10t).$$

Compute:

$$= d\left(c\varepsilon(d)+10\frac{c(c-1)}2\right)$$

$$= M\varepsilon(d)+5M\left(\frac{M}{d}-1\right)$$

$$= \frac{5M^2}{d}+M(\varepsilon(d)-5).$$

Step 3: Inclusion–exclusion

Since $M$ is squarefree,

$$F(k) = \sum_{d\mid M}\mu(d) \left( \frac{5M^2}{d}+M(\varepsilon(d)-5) \right).$$

Split into two sums:

$$F(k) = 5M^2\sum_{d\mid M}\frac{\mu(d)}d + M\sum_{d\mid M}\mu(d)(\varepsilon(d)-5).$$

Step 4: Evaluate the first sum

For squarefree $M$,

$$\sum_{d\mid M}\frac{\mu(d)}d = \prod_{p\mid M}\left(1-\frac1p\right) = \frac{\varphi(M)}M.$$

Hence

$$5M^2\sum_{d\mid M}\frac{\mu(d)}d = 5M\varphi(M).$$

Step 5: Evaluate the second sum

If $d$ has an even number of prime factors, then

$$d\equiv1\pmod{10}, \qquad \varepsilon(d)-5=2, \qquad \mu(d)=+1.$$

Contribution: $+2$.

If $d$ has an odd number of prime factors, then

$$d\equiv7\pmod{10}, \qquad \varepsilon(d)-5=-4, \qquad \mu(d)=-1.$$

Contribution: $+4$.

There are $2^{k-1}$ even-parity divisors and $2^{k-1}$ odd-parity divisors, so

$$\sum_{d\mid M}\mu(d)(\varepsilon(d)-5) = 2\cdot2^{k-1}+4\cdot2^{k-1} = 3\cdot2^k.$$

Therefore:

$$\boxed{ F(k)=M\left(5\varphi(M)+3\cdot2^k\right) }$$

with

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

2. Python implementation

from sympy import primerange

MOD = 1_000_000_007

# First 97 primes ending in 7
primes_7 = [p for p in primerange(1, 100000) if p % 10 == 7][:97]

# Compute:
# M = product of primes
# phi(M) = product of (p - 1)
M = 1
phi = 1

for p in primes_7:
    M = (M * p) % MOD
    phi = (phi * (p - 1)) % MOD

# F(k) = M * (5*phi(M) + 3*2^k)
k = 97

answer = M * (5 * phi + 3 * pow(2, k, MOD)) % MOD
answer %= MOD

print(answer)

3. Code walkthrough

Generate the primes

primes_7 = [p for p in primerange(1, 100000) if p % 10 == 7][:97]

This collects the first 97 primes ending in 7.

Compute $M$

M = (M * p) % MOD

This computes

$$M=\prod p_i \pmod{10^9+7}.$$

Compute Euler's totient

Because $M$ is squarefree,

$$\varphi(M)=\prod (p_i-1).$$

So:

phi = (phi * (p - 1)) % MOD

Apply the closed formula

answer = M * (5 * phi + 3 * pow(2, k, MOD)) % MOD

This evaluates

$$F(k)=M\left(5\varphi(M)+3\cdot2^k\right).$$

4. Verification on the example

For $k=3$:

$$M=7\cdot17\cdot37=4403,$$

$$\varphi(M)=6\cdot16\cdot36=3456.$$

Then

$$F(3) = 4403(5\cdot3456+3\cdot8) = 4403(17280+24) = 4403\cdot17304 = 76101452,$$

matching the problem statement exactly.

5. Final computation

Evaluating the formula for $k=97$ gives

$$F(97)\equiv 15074607 \pmod{1,000,000,007}.$$

Answer: 15074607

Project Euler Problem 773