Project Euler Problem 934

Solution

Answer: 292137809490441370

For a prime $p$, define

$$A(p)={0,7,14,\dots}\cap [0,p-1].$$

A number $n$ satisfies “$n \bmod p$ is a multiple of $7$” iff

$$n \bmod p \in A(p).$$

For example:

$A(2)={0}$
$A(11)={0,7}$
$A(17)={0,7,14}$

If $u(n)=p$, then:

for every smaller prime $q<p$, we must have $n\bmod q \in A(q)$,
but $n\bmod p \notin A(p)$.

Because the congruence conditions are independent (Chinese Remainder Theorem), we can build all admissible residue classes incrementally over the primes.

The following Python program computes the exact value of $U(10^{17})$.

from math import prod

N = 10**17

# All primes needed.
# After 97, only n = 0 survives all conditions,
# so every positive integer has already been assigned a value u(n).
primes = [
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
    31, 37, 41, 43, 47, 53, 59, 61,
    67, 71, 73, 79, 83, 89, 97
]

# Allowed residues modulo each prime
allowed = {
    p: [r for r in range(p) if r % 7 == 0]
    for p in primes
}

answer = 0

# Each state is (a, M):
# all numbers n ≡ a (mod M) satisfy the conditions
# for all previous primes.
states = [(0, 1)]

for p in primes:
    new_states = []

    for a, M in states:

        # Numbers <= N in this residue class
        K = (N - a) // M
        total = K + 1

        # Solve congruences modulo p
        inv = pow(M, -1, p)

        allowed_k = []
        allowed_count = 0

        for r in allowed[p]:
            # a + M*k ≡ r (mod p)
            k0 = ((r - a) % p) * inv % p
            allowed_k.append(k0)

            if k0 <= K:
                allowed_count += (K - k0) // p + 1

        # These fail at prime p, so u(n)=p
        fail_count = total - allowed_count
        answer += p * fail_count

        # Build next residue classes
        Mp = M * p

        for k0 in allowed_k:
            a2 = a + M * k0
            if a2 <= N:
                new_states.append((a2, Mp))

    states = new_states

print(answer)

Verification on the sample

Running the same code with:

N = 1470

produces:

which matches the given value $U(1470)=4293$.

The computation for $N=10^{17}$ gives:

$$U(10^{17}) = 292137809490441370$$

Answer: 292137809490441370