Project Euler Problem 130

Solution

Answer: 149253

Let $R(k)$ denote the repunit

$$R(k)=\frac{10^k-1}{9}=111\ldots1$$

(with $k$ ones). For any integer $n$ coprime to $10$, there exists some $k$ such that

$$R(k)\equiv 0 \pmod n.$$

Define $A(n)$ to be the smallest such $k$.

We seek the first $25$ composite integers $n$ such that

$$A(n)\mid (n-1),$$

and $\gcd(n,10)=1$. Then we must sum them.

---

1. Mathematical analysis

The key observation is:

$$R(k)\equiv 0 \pmod n \iff \frac{10^k-1}{9}\equiv 0 \pmod n.$$

Since $\gcd(n,10)=1$, this is equivalent to

$$10^k \equiv 1 \pmod{9n}$$

(except for factors of $3$, but using $9n$ uniformly works correctly).

Thus $A(n)$ is the multiplicative order of $10$ modulo $9n$:

$$A(n)=\operatorname{ord}_{9n}(10).$$

We are looking for composite $n$ satisfying

$$n-1 \equiv 0 \pmod{A(n)}.$$

---

Important property for primes

For primes $p>5$,

$$A(p)\mid p-1$$

by Fermat’s little theorem, since the multiplicative order divides the group size.

The problem asks for the rare composite numbers with the same property.

These are related to pseudoprime-like behavior.

---

2. Efficient algorithm

We test integers $n$ in increasing order.

Conditions:

1. $n$ composite
2. $\gcd(n,10)=1$
3. $(n-1)\bmod A(n)=0$

The computational challenge is evaluating $A(n)$.

---

Computing $A(n)$

We can compute the multiplicative order directly:

Start with

$$x = 10 \bmod (9n)$$

and repeatedly multiply by $10$:

$$x \leftarrow (10x)\bmod (9n)$$

until $x=1$.

The number of steps is $A(n)$.

This is efficient enough because the required numbers are relatively small.

---

3. Python implementation

from math import gcd

# Simple primality test
def is_prime(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2

    d = 3
    while d * d <= n:
        if n % d == 0:
            return False
        d += 2

    return True

# Compute A(n):
# the smallest k such that R(k) is divisible by n
def A(n):
    # modulus used for multiplicative order
    mod = 9 * n

    x = 10 % mod
    k = 1

    while x != 1:
        x = (x * 10) % mod
        k += 1

    return k

count = 0
total = 0
n = 1

while count < 25:
    n += 1

    # must be coprime to 10
    if gcd(n, 10) != 1:
        continue

    # only composite numbers
    if is_prime(n):
        continue

    an = A(n)

    if (n - 1) % an == 0:
        count += 1
        total += n
        print(count, n)

print("Answer =", total)

---

4. Code walkthrough

Primality test

def is_prime(n):

A straightforward trial-division primality test.

We skip all primes because the problem asks for composite values only.

---

Computing $A(n)$

mod = 9 * n

We work modulo $9n$ because

$$R(k)=\frac{10^k-1}{9}.$$

---

x = 10 % mod
k = 1

Initially we have $10^1$.

---

while x != 1:
    x = (x * 10) % mod
    k += 1

This searches for the smallest $k$ such that

$$10^k \equiv 1 \pmod{9n}.$$

That $k$ is exactly $A(n)$.

---

Main search loop

if gcd(n, 10) != 1:
    continue

Necessary condition for $A(n)$ to exist.

---

if is_prime(n):
    continue

We only want composite values.

---

if (n - 1) % an == 0:

Checks the defining property.

---

5. Small examples

The problem gives:

• $91$
• $259$
• $451$
• $481$
• $703$

Running the program indeed produces these as the first five matches.

For example:

$$A(91)=6,\qquad 90 \equiv 0 \pmod 6.$$

So the logic is correct.

---

6. Final verification

The resulting numbers are all:

• composite,
• coprime to $10$,
• satisfy $A(n)\mid n-1$.

Summing the first $25$ such values gives:

$$149253$$

---

Answer: 149253