Project Euler Problem 274

Solution

Answer: 1601912348822

Let $n = 10a+b$, where $b$ is the last digit and $a$ is the number formed by all preceding digits.

The transformation is

$$f(n)=a+bm$$

We want a multiplier $m$ such that

$$p \mid n \iff p \mid f(n)$$

for primes $p$ coprime to $10$ (so $p\neq 2,5$).

Step 1: Deriving the divisibility multiplier

Since

$$n=10a+b,$$

we want divisibility by $p$ to be preserved:

$$10a+b \equiv 0 \pmod p \iff a+bm \equiv 0 \pmod p.$$

Multiply the second congruence by $10$:

$$10a+10bm \equiv 0 \pmod p.$$

To match the original expression $10a+b$, we require

$$10m \equiv 1 \pmod p.$$

Thus:

$$m \equiv 10^{-1} \pmod p.$$

Since $p$ is prime and coprime to $10$, the modular inverse of $10$ always exists, and the required multiplier is the unique integer

$$1 \le m < p$$

satisfying

$$10m \equiv 1 \pmod p.$$

Example for $p=113$:

$$10^{-1}\equiv 34 \pmod{113}$$

because

$$10\cdot 34=340\equiv 1 \pmod{113}.$$

This matches the problem statement.

So the task reduces to:

$$\sum_{p<10^7,\ p\neq 2,5} 10^{-1}\pmod p.$$

Python implementation

from math import isqrt

LIMIT = 10_000_000

# Sieve of Eratosthenes
is_prime = bytearray(b'\x01') * LIMIT
is_prime[0] = is_prime[1] = 0

for i in range(2, isqrt(LIMIT - 1) + 1):
    if is_prime[i]:
        is_prime[i * i:LIMIT:i] = b'\x00' * (
            ((LIMIT - 1 - i * i) // i) + 1
        )

total = 0

# Skip 2 and 5 since they are not coprime to 10
for p in range(3, LIMIT):
    if is_prime[p] and p != 5:
        # modular inverse of 10 mod p
        m = pow(10, -1, p)
        total += m

print(total)

Code walkthrough

1. Build the prime sieve

We use the Sieve of Eratosthenes up to $10^7$:

is_prime = bytearray(b'\x01') * LIMIT

Each entry starts as “prime”.

We eliminate multiples:

for i in range(2, isqrt(LIMIT - 1) + 1):
    if is_prime[i]:
        is_prime[i * i:LIMIT:i] = ...

This marks composites efficiently.

2. Iterate through primes

We skip $2$ and $5$, because they are not coprime to $10$:

if is_prime[p] and p != 5:

3. Compute the multiplier

Python’s modular inverse:

pow(10, -1, p)

returns the unique number $m$ such that

$$10m \equiv 1 \pmod p.$$

For example:

$p=113$
pow(10, -1, 113) → 34

exactly matching the statement.

4. Validate with the small test

For primes less than $1000$, the program returns:

$$39517$$

which matches the problem statement.

Final verification

Every valid prime $p\neq 2,5$ contributes exactly one multiplier.
The multiplier is always between $1$ and $p-1$.
The sample case (<1000) matches exactly.
Computation for $10^7$ gives a plausible large positive integer.

Answer: 1601912348822