Open Source · 7 Languages · 900+ Problems

Project Euler Solutions

Complete solutions in C++, Python & Java — with step-by-step mathematical explanations

All Problems

Problem 274: Divisibility Multipliers

Project Euler Problem 274 Solution

EulerSolve provides an optimized solution for Project Euler Problem 274, Divisibility Multipliers, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary For every prime $p\neq2,5$, define the decimal divisibility multiplier $m(p)$ as the number that lets us replace a divisibility test on $n=10q+r$ by a test on the shorter number $q+m(p)r$. The problem asks for the sum of these multipliers over all primes below a large limit. The final numeric answer is omitted here; what matters is the mathematical reason this multiplier exists and why the code computes it so quickly. Mathematical Approach 1) Why primes $2$ and $5$ are excluded Any decimal integer can be split into quotient and last digit as $n=10q+r,\qquad 0\le r\le 9.$ If $p=2$ or $p=5$, then $10\equiv0\pmod p$, so $10$ has no multiplicative inverse modulo $p$. That means the whole “remove the last digit and adjust” trick cannot be expressed by multiplying with $10^{-1}$. For every other prime $p$, we have $\gcd(10,p)=1$, so a unique inverse of $10$ exists modulo $p$. 2) Deriving the multiplier formula Start from the divisibility condition $p\mid n \iff p\mid (10q+r).$ Let $t$ be the modular inverse of $10$, so $10t\equiv1\pmod p.$ Multiply the congruence $10q+r\equiv0\pmod p$ by $t$: $q+tr\equiv0\pmod p.$ Therefore $p\mid n \iff p\mid (q+tr).$ So the divisibility multiplier is exactly $\boxed{m(p)\equiv10^{-1}\pmod p.}$ The code returns the least nonnegative representative of this inverse....

Detailed mathematical approach

Problem Summary

For every prime $p\neq2,5$, define the decimal divisibility multiplier $m(p)$ as the number that lets us replace a divisibility test on

$n=10q+r$

by a test on the shorter number $q+m(p)r$. The problem asks for the sum of these multipliers over all primes below a large limit. The final numeric answer is omitted here; what matters is the mathematical reason this multiplier exists and why the code computes it so quickly.

Mathematical Approach

1) Why primes $2$ and $5$ are excluded

Any decimal integer can be split into quotient and last digit as

$n=10q+r,\qquad 0\le r\le 9.$

If $p=2$ or $p=5$, then $10\equiv0\pmod p$, so $10$ has no multiplicative inverse modulo $p$. That means the whole “remove the last digit and adjust” trick cannot be expressed by multiplying with $10^{-1}$.

For every other prime $p$, we have $\gcd(10,p)=1$, so a unique inverse of $10$ exists modulo $p$.

2) Deriving the multiplier formula

Start from the divisibility condition

$p\mid n \iff p\mid (10q+r).$

Let $t$ be the modular inverse of $10$, so

$10t\equiv1\pmod p.$

Multiply the congruence $10q+r\equiv0\pmod p$ by $t$:

$q+tr\equiv0\pmod p.$

Therefore

$p\mid n \iff p\mid (q+tr).$

So the divisibility multiplier is exactly

$\boxed{m(p)\equiv10^{-1}\pmod p.}$

The code returns the least nonnegative representative of this inverse.

3) Relation to the familiar “subtract the last digit” tests

Sometimes schoolbook divisibility rules are written with subtraction instead of addition. That is the same thing, because if $m(p)$ is the inverse of $10$, then $m(p)-p$ is an equivalent multiplier modulo $p$.

For example, for $p=7$ we have

$10^{-1}\equiv5\pmod7,$

so one valid rule is

$7\mid(10q+r)\iff 7\mid(q+5r).$

But since $5\equiv-2\pmod7$, this is the usual rule

$7\mid(10q+r)\iff 7\mid(q-2r).$

The Project Euler problem chooses the positive modular inverse.

4) Worked example: $p=13$

Because $10\cdot4=40\equiv1\pmod{13}$, we have

$m(13)=4.$

So

$13\mid(10q+r)\iff 13\mid(q+4r).$

Apply that repeatedly to the divisible number $3484$:

$3484 \longrightarrow 348+4\cdot4=364,$

$364 \longrightarrow 36+4\cdot4=52,$

$52 \longrightarrow 5+4\cdot2=13.$

Since $13$ is divisible by $13$, the original number is also divisible by $13$. This shows why the multiplier rule is a genuine digit-stripping test, not just a single-step congruence trick.

5) Worked example: $p=113$ and extended Euclid

The code contains the checkpoint $m(113)=34$. Here is why. Run the Euclidean algorithm:

$113=11\cdot10+3,\qquad 10=3\cdot3+1.$

Now back-substitute:

$1=10-3\cdot3=10-(113-11\cdot10)\cdot3=34\cdot10-3\cdot113.$

Hence

$10\cdot34\equiv1\pmod{113},$

so

$m(113)=34.$

A quick check with $791=7\cdot113$:

$79+34\cdot1=113,$

which is obviously divisible by $113$, so the test works exactly as predicted.

6) Why the whole problem reduces to summing inverses

Once the derivation is done, nothing deeper remains: for each prime $p\neq2,5$, the desired multiplier is simply $10^{-1}\pmod p$. So the problem becomes

$\sum_{\substack{p<L\\ p\ \text{prime}\\ p\neq2,5}} 10^{-1}\!\!\!\pmod p,$

with the inverse interpreted as its least nonnegative representative.

How the Code Works

Prime generation. primes_up_to() uses a linear sieve to list all primes below prime_limit.

Inverse computation. inverse_mod_10(p) runs an iterative extended Euclidean algorithm on $10$ and $p$. The returned coefficient of $10$ is reduced into the range $[0,p-1]$.

Accumulation. solve() skips $2$ and $5$, sums the inverses for all other primes, and returns a 64-bit total.

Checkpoints. The source verifies

$m(113)=34,\qquad \text{solve}(1000)=39517.$

It also exposes --prime-limit=... and --skip-checkpoints for controlled runs.

Complexity Analysis

With a linear sieve, generating primes up to $L$ costs $O(L)$ time and $O(L)$ memory. For each prime, the extended Euclidean algorithm costs $O(\log p)$, so the total post-sieve work is

$O\!\left(\sum_{p<L}\log p\right)=O(\pi(L)\log L).$

For the given limit this is easily fast enough, because the arithmetic per prime is tiny.