Solution

Answer: 1000023

Let

$$R(k)=\underbrace{111\ldots 1}_{k\text{ digits}}$$

be the repunit of length $k$. Since

$$R(k)=1+10+10^2+\cdots+10^{k-1}$$

we have the closed form

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

We define $A(n)$ to be the smallest $k$ such that $R(k)\equiv 0\pmod n$, assuming $\gcd(n,10)=1$.

The problem asks for the least $n$ such that

$$A(n)>1{,}000{,}000.$$

1. Mathematical analysis

We want the least $n$ for which the minimal repunit multiple length exceeds one million.

Step 1: Reformulating the divisibility condition

We need

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

Using

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

we get

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

If $\gcd(n,9)=1$, this is equivalent to

$$10^k\equiv 1 \pmod n.$$

More generally, $A(n)$ is the multiplicative order of $10$ modulo $9n$ (or modulo $n$ when $9\nmid n$).

However, for computation, we do not need advanced number theory. We can compute $A(n)$ directly using modular recurrence.

Step 2: Computing $A(n)$ efficiently

Instead of constructing enormous repunits, define the recurrence

$$r_k = R(k)\bmod n.$$

Then

$$R(k+1)=10R(k)+1,$$

$$r_{k+1}=(10r_k+1)\bmod n.$$

We start with:

$$r_1=1\bmod n.$$

The first $k$ such that $r_k=0$ is exactly $A(n)$.

This requires only modular arithmetic and runs in $O(A(n))$ time.

Step 3: Important observations

Since $A(n)\le n$ for primes $n$ not dividing 10 (because the order divides $\varphi(n)=n-1$), we immediately know:

if $A(n)>10^6$, then necessarily $n>10^6$.

So we begin searching just above one million.

Also:

numbers divisible by $2$ or $5$ can never divide a repunit,
so we skip such $n$.

Step 4: Strategy

We test integers $n>10^6$ with $\gcd(n,10)=1$:

Compute $A(n)$ by iterative modular recurrence.
Stop at the first $n$ with $A(n)>10^6$.

The first such $n$ is the answer.

2. Python implementation

from math import gcd

LIMIT = 1_000_000

def A(n):
    """
    Compute the least k such that R(k) is divisible by n,
    where R(k) = 111...1 (k ones).
    Assumes gcd(n, 10) = 1.
    """
    remainder = 1 % n
    k = 1

    while remainder != 0:
        remainder = (remainder * 10 + 1) % n
        k += 1

    return k

n = LIMIT + 1

while True:

    # Repunits can only be divisible by numbers coprime to 10
    if gcd(n, 10) == 1:

        if A(n) > LIMIT:
            print(n)
            break

    n += 1

3. Code walkthrough

Imports and constant

from math import gcd
LIMIT = 1_000_000

We use gcd to skip numbers divisible by 2 or 5.

Function `A(n)`

def A(n):

Computes the minimal repunit length divisible by n.

Initialize

remainder = 1 % n
k = 1

This corresponds to $R(1)=1$.

Iterative recurrence

while remainder != 0:
    remainder = (remainder * 10 + 1) % n
    k += 1

This implements:

$$R(k+1)=10R(k)+1.$$

We never construct huge integers — only remainders modulo $n$.

Return

return k

The first $k$ producing remainder 0 is $A(n)$.

Main search loop

n = LIMIT + 1

We start just above one million.

Skip invalid candidates

if gcd(n, 10) == 1:

A repunit is never divisible by 2 or 5.

Test condition

if A(n) > LIMIT:

As soon as we find the first such $n$, we print it and stop.

4. Small-example verification

The problem states:

$$A(7)=6.$$

Indeed:

$$111111 = 7 \times 15873.$$

Running the recurrence:

$1 \bmod 7 = 1$
$11 \bmod 7 = 4$
$111 \bmod 7 = 6$
$1111 \bmod 7 = 5$
$11111 \bmod 7 = 2$
$111111 \bmod 7 = 0$

So $A(7)=6$.

Also:

$$A(17)=16>10,$$

which matches the statement that 17 is the first $n$ with $A(n)>10$.

5. Final verification

The answer should:

be slightly larger than $10^6$,
be coprime to 10,
have a very large multiplicative order of 10.

The computation yields:

$$n = 1{,}000{,}023.$$

This is indeed just above one million and satisfies

$$A(1{,}000{,}023) > 1{,}000{,}000.$$

Answer: 1000023

Project Euler Problem 129