Problem 129: Repunit Divisibility

Project Euler Problem 129 Solution

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

Problem Summary For the repunit $R(k)=\underbrace{11\ldots1}_{k}$, let $A(n)$ be the smallest positive integer $k$ such that $R(k)$ is divisible by $n$. Problem 129 asks for the least $n>10^6$ for which $A(n)$ exceeds $10^6$. The implementations therefore solve the threshold form of the problem: given $L$, find the smallest $n>L$ with $A(n)>L$. The important restriction is $\gcd(n,10)=1$. If $n$ is divisible by 2 or 5, no repunit can be a multiple of $n$, because every repunit ends in the digit 1. That observation removes many candidates before any serious work starts. Mathematical Approach The key idea is to avoid ever constructing the enormous integer $R(k)$. Instead, the implementations follow only its remainder modulo $n$, which turns the problem into a simple recurrence on a finite set of states. Repunits as a remainder process The repunits satisfy $$R(1)=1,\qquad R(k+1)=10R(k)+1.$$ For a fixed candidate $n$, define $$r_k \equiv R(k)\pmod n,\qquad 0\le r_k<n.$$ Reducing the repunit recurrence modulo $n$ gives $$r_1\equiv 1\pmod n,\qquad r_{k+1}\equiv 10r_k+1\pmod n.$$ By induction, $r_k$ is always exactly the remainder of $R(k)$ modulo $n$....

Detailed mathematical approach

Problem Summary

A repunit is a number written with the digit $1$ only, and $R(k)$ is the repunit with $k$ digits; for example $R(6)=111111$. For every positive integer $n$ with $\gcd(n,10)=1$ some repunit is divisible by $n$, and $A(n)$ is the least such length $k$. The statement gives $A(7)=6$ and $A(41)=5$ and says that the least $n$ for which $A(n)$ exceeds ten is $17$. We must find the least $n$ for which $A(n)$ exceeds one million, that is, the least $n$ with $\gcd(n,10)=1$ and $A(n)\gt10^6$. ^[1]

The whole solution in one sentence: since $A(n)$ is never larger than $n$, the wanted number is larger than one million, so we test $n=10^6+1,10^6+2,\dots$ one after another, skip the multiples of $2$ and $5$, and for each candidate follow only the remainder of $R(k)$ on division by $n$, which after at most one million cheap steps shows whether $A(n)\gt10^6$.

Mathematical Approach

We write $L$ for the threshold: $L=10$ in the example of the statement and $L=10^6$ in the task. Sections 1 to 4 contain everything the programs use. Sections 5 to 8 prove that the search always ends and show which numbers can win, and Section 9 gives a heuristic reason why it ends soon.

1. Small repunits

The first repunits factor as $R(2)=11$, $R(3)=3\cdot37$, $R(4)=11\cdot101$, $R(5)=41\cdot271$ and $R(6)=3\cdot7\cdot11\cdot13\cdot37$. ^[2] For a prime $p$, $A(p)$ is the length of the first repunit with the factor $p$: $A(11)=2$, $A(3)=A(37)=3$, $A(101)=4$, $A(41)=5$ and $A(7)=A(13)=6$, in agreement with the statement. Every repunit ends in the digit $1$, so it is odd and not a multiple of $5$. A multiple of $2$ or $5$ therefore divides no repunit, which is why $A(n)$ is defined only when $\gcd(n,10)=1$.

2. Following the remainder

$R(10^6)$ has a million digits, but we never need such numbers. Appending a digit $1$ gives $R(k+1)=10\,R(k)+1$, and the remainder of a sum or a product depends only on the remainders of its parts, ^[3] so the remainders $r_k$ of $R(k)$ on division by $n$ obey

$$\begin{aligned}r_1&=1\bmod n,\\r_{k+1}&=(10\,r_k+1)\bmod n,\end{aligned}$$

where $x\bmod n$ is the remainder of $x$ on division by $n$. Every $r_k$ lies between $0$ and $n-1$, and $A(n)$ is the first $k$ with $r_k=0$. For $n=7$ the remainders are $1,4,6,5,2,0$; for instance $10\cdot4+1=41=5\cdot7+6$ gives $r_3=6$. Hence $A(7)=6$, and indeed $111111=7\cdot15873$. For $n=41$ the remainders are $1,11,29,4,0$, so $A(41)=5$.

3. A divisible repunit exists, and $A(n)\le n$

The difference of two repunits is a repunit followed by zeros: for $i\lt j$,

$$R(j)-R(i)=10^{i}\,R(j-i),$$

for example $11111-11=11100=10^2\cdot111$. Now let $\gcd(n,10)=1$ and look at the $n$ remainders $r_1,\dots,r_n$. If none of them were $0$, these $n$ numbers would take at most the $n-1$ values $1,\dots,n-1$, so by the pigeonhole principle ^[4] two of them would be equal, say $r_i=r_j$ with $i\lt j$. Then $n$ divides $R(j)-R(i)=10^i\,R(j-i)$. Since $n$ has no prime factor in common with $10^i$, Euclid's lemma ^[5] gives $n\mid R(j-i)$, that is, $r_{j-i}=0$ with $1\le j-i\le n-1$, a contradiction. So one of $r_1,\dots,r_n$ is $0$: a repunit divisible by $n$ exists, as the statement claims, ^[2] and

$$A(n)\le n.$$

The bound can be reached: modulo $9$ the remainders are $1,2,\dots,8,0$, so $A(9)=9$, and likewise $A(3)=3$.

4. Where the search starts and when a test stops

By Section 3, every $n\le L$ coprime to $10$ has $A(n)\le n\le L$. The least $n$ with $A(n)\gt L$ is therefore larger than $L$, and the search may start at $n=L+1$ without missing anything. Moreover, $A(n)\gt L$ holds exactly when $r_1,\dots,r_L$ are all different from $0$. One test therefore needs at most $L$ steps of the rule, however large $A(n)$ is, and a candidate with $A(n)\le L$ is rejected as soon as $r_{A(n)}=0$ appears.

The statement's example $L=10$ shows both points. Above $10$ the first candidates are $11$, rejected at $r_2=0$, and $13$, rejected at $r_6=0$; $12$, $14$, $15$ and $16$ are skipped. For $n=17$ the ten remainders $1,11,9,6,10,16,8,13,12,2$ are all nonzero, so $A(17)\gt10$ and the answer for $L=10$ is $17$, as stated. The test never computes the actual value $A(17)=16$.

5. The remainders repeat

Once $r_k=0$, the rule gives $r_{k+1}=1\bmod n=r_1$, and from then on the remainders run through the same values again. They repeat with period $A(n)$, and $r_k=0$ exactly when $k$ is a multiple of $A(n)$; modulo $7$ the zeros are at the multiples of $6$. In other words,

$$n\mid R(k)\iff A(n)\mid k.$$

6. $A(n)$ is an order of $10$

Since $9\,R(k)=10^k-1$, $n$ divides $R(k)$ exactly when $9n$ divides $10^k-1$. So $A(n)$ is the least $k$ with $10^k\equiv1\pmod{9n}$, the multiplicative order of $10$ modulo $9n$. ^[6] If also $\gcd(n,3)=1$, then $n\mid10^k-1$ already implies $9n\mid10^k-1$, because $9$ divides $10^k-1$ and hence, by Euclid's lemma, the cofactor $(10^k-1)/n$; so $A(n)$ is the order of $10$ modulo $n$. That order divides Euler's totient $\varphi(n)$, the number of integers among $1,\dots,n$ that are coprime to $n$. ^[6] For a prime $p\ne2,3,5$ this means $A(p)\mid p-1$: $A(7)=6$, while $A(13)=6$ divides $12$ and $A(41)=5$ divides $40$. The primes with $A(p)=p-1$, those for which $10$ is a primitive root, are the full reptend primes, which begin $7,17,19,23,29,47,59,61,97$. For them the decimal fraction $1/p$ repeats only after $p-1$ digits, as $1/7=0.142857\,142857\ldots$ shows. ^[7]

7. Powers of three

Because $10$ leaves remainder $1$ on division by $3$, each digit of $R(k)$ contributes $1$ to its remainder, so $R(k)\equiv k\pmod3$, and $3$ divides $R(k)$ only when $3\mid k$. Cutting the $3k$ digits of $R(3k)$ into three blocks of $k$ ones gives

$$R(3k)=R(k)\,\bigl(10^{2k}+10^{k}+1\bigr),$$

for example $R(6)=11\cdot10101$. The second factor leaves remainder $3$ on division by $9$, since $10$ leaves remainder $1$, so it contains the prime factor $3$ exactly once. Starting from a $k$ not divisible by $3$ and tripling it again and again shows that $R(k)$ contains the factor $3$ exactly as often as $k$ does; this is also the lifting-the-exponent lemma applied to $10^k-1$. ^[8] Hence $3^j\mid R(k)$ exactly when $3^j\mid k$, so $A(3^j)=3^j$: every power of $3$ reaches the bound of Section 3. As $3^{12}=531441$ lies below $10^6$ and $3^{13}=1594323$ above it, the search for $L=10^6$ stops at $3^{13}$ at the latest. This proves that the search ends, but it still allows $237730$ candidates coprime to $10$ up to that power.

8. Which numbers can win just above $L$

Most candidates lose, and close above $L$ the winners have a special form. Let $L\lt n\le L+\sqrt L$; then $n-\sqrt n\le L$.

If $n$ is composite and $\gcd(n,3)=1$, it has a prime factor $q\le\sqrt n$, and the $n/q\ge\sqrt n$ multiples of $q$ up to $n$ are not coprime to $n$. So $A(n)\le\varphi(n)$${}\le n-\sqrt n\le L$, and $n$ loses; for example $A(49)=42=49-7$.
If $n=p$ is a prime other than $3$, Section 6 gives $A(p)\mid p-1$, and every divisor of $p-1$ other than $p-1$ itself is at most $(p-1)/2$, which is less than $L$. So $p$ wins exactly when it is a full reptend prime with $p\ge L+2$. The prime $3$ is a power of $3$, treated below.
If $n=3^a m$ with $a\ge1$ and $m\gt1$ not divisible by $3$, then $n\mid R(k)$ exactly when $3^a\mid k$ and $A(m)\mid k$, by Sections 7 and 5, so $A(n)=\mathrm{lcm}(3^a,A(m))$, which is at most $3^a\,A(m)\le3^a(m-1)=n-3^a$ by Section 6. For a composite $m$ the first case gives $A(n)\le3^a(m-\sqrt m)$, which is less than $n-\sqrt n$ because $3^a\sqrt m=\sqrt{3^a n}\gt\sqrt n$. For a prime $m=p$ with $A(p)\ne p-1$, the least common multiple is at most $3^aA(p)\le3^a(p-1)/2$; for a full reptend prime $p$ with $3\mid p-1$, it is $\mathrm{lcm}(3^a,p-1)\le3^a(p-1)/3$, because $3^a$ and $p-1$ share the factor $3$. Both bounds are below $n/2$, and $n/2\lt L$ since $n\le L+\sqrt L\lt2L$. In all these cases $n$ loses. Only a full reptend prime $p$ with $3\nmid p-1$ remains; then $A(n)=n-3^a$, and $n$ wins when $n-3^a\gt L$. Examples are $A(51)=\mathrm{lcm}(3,16)=48$ and $A(1017)=\mathrm{lcm}(9,112)=1008$, where $1017=9\cdot113$.

Together with the powers of $3$, the case $m=1$, which always win, these are all the winners in the range; a computation over all $n\le2\cdot10^5$ confirms this description.

9. How soon a winner comes

Artin's conjecture on primitive roots predicts that $10$ is a primitive root for a fixed share of all primes, Artin's constant $0.3739558\dots$; Hooley proved it in 1967 assuming an extended Riemann hypothesis. ^[9] The count agrees: among the $78498$ primes below $10^6$ there are $29500$ full reptend primes, ^[7] about $37.6\%$. By the prime number theorem, on average about one integer in $\ln L$ near $L$ is prime; ^[10] if the full reptend primes are spread evenly with the conjectured share, about one integer in $\ln L/0.374$ near $L$ is one of them. This is a heuristic, not a bound for the gap after a particular $L$, but any full reptend prime above $L+1$ ends the search. The smaller thresholds behave like this: for $L=10^2,10^3,10^4,10^5$ the winners are $109$, $1017$, $10007$ and $100019$, found after $4$, $7$, $3$ and $8$ candidates.

How the Code Works

The C++ program ^[11] starts in main with the defaults of Options: limit $=10^6$ and the checkpoints switched on. parse_arguments accepts --limit= followed by digits, which parse_int_after_prefix reads, and --skip-checkpoints; any other argument, or a limit below $1$, ends the program with exit code $1$. run_checkpoints requires A_of_n(7) to be $6$ and solve(10) to be $17$, the values of the statement, and otherwise the exit code is $2$. Then main prints solve(limit).

A_of_n applies the rule of Section 2 until the remainder is $0$ and returns the number of remainders seen, $A(n)$; it starts from 1 % n, which is $0$ for $n=1$, so that $A(1)=1$. exceeds_limit(n, limit) is the test of Section 4: in round $k=1,\dots,L$ the variable rem holds $r_k$, and the function returns false as soon as it is $0$ and true after $L$ nonzero remainders. solve starts at limit + 1, as Section 4 allows, skips every $n$ for which std::gcd(n, 10) is not $1$, ^[12] and returns the first $n$ that passes the test. Its loop has no upper bound; Section 7 guarantees that it ends as long as the arithmetic stays inside the range of int, as it does in the default run.

The Python and Java programs fix $L=10^6$ and have no options or checks. Python loops over range(limit + 1, 10000000), whose end is safe because $3^{13}\lt10^7$; Java skips $n$ when n % 2 == 0 || n % 5 == 0, the same condition as $\gcd(n,10)\ne1$. Both apply the rule while rem != 0 and k <= limit, where $k$ is the index of the current remainder, and accept $n$ when the loop ends with k > limit. This happens exactly when $r_1,\dots,r_L$ are all nonzero: a zero at a step $k\le L$ ends the loop with $k=A(n)\le L$, while $A(n)=L+1$ ends it with $k=L+1$, rightly accepted.

Every remainder is below $n$, so each step computes a value below $10n$; in the default run $n\le3^{13}$, so all values stay below $1.6\cdot10^7$, far inside the range of a 32-bit int, and Python's integers are unbounded anyway. Larger C++ limits are not safe: above about $2.1\cdot10^8$, rem * 10 + 1 can overflow, which is undefined behaviour, ^[12] limit + 1 overflows for $2^{31}-1$, the largest limit that fits in an int, and parse_int_after_prefix does not check the range of its number. A detector for undefined behaviour reports these cases for --limit=300000000, --limit=2147483647 and --limit=3000000000, and nothing for the default run.

Complexity and Verification

A rejected candidate costs $A(n)-1$ updates of the remainder and the winner costs $L$, so a search that tests $C$ candidates, the winner included, takes $O(C\,L)$ time, and the memory is $O(1)$: the programs store only $n$, the remainder and a counter. Section 7 bounds $C$ by $237730$ for $L=10^6$, which would still allow about $2.4\cdot10^{11}$ updates; this is only a worst case, and Section 9 explains heuristically why far fewer occur. For $L=10^3$, $10^4$ and $10^5$ the searches make $2539$, $11434$ and $210888$ updates in total, and for $L=10^6$ each of the three programs finishes in well under a second on a desktop computer.

Before the main run the C++ program checks $A(7)=6$ and the result $17$ for $L=10$; $A(41)=5$ is not checked. For this article all three programs were run and print the same number, and the C++ program with --limit= $10$, $10^2$, …, $10^5$ agrees with a separate Python search. An independent computation that finds $A(n)$ as the order of $10$ modulo $9n$ with the routine n_order of SymPy, without the remainder rule, gives the same least $n$ for $L=10^6$. Further checks confirm $A(n)\le n$ for every $n\le10^6$ coprime to $10$, with equality exactly for the powers of $3$; the facts of Sections 6 and 8, including the list of winners, for every $n\le2\cdot10^5$; the factor count of Section 7 for every $k\le10^5$; and the first values of $A(n)$ against OEIS A099679. ^[13] These checks are not part of the published solutions.

Footnotes and References

The references below supply the background facts used above. The early-stop test, the description of the winners in Section 8 and the operation counts are derived in this article.

Project Euler 129 — Repunit Divisibility. The official statement defines the repunit R(k) of length k, with R(6) = 111111, and, for gcd(n, 10) = 1, the least k = A(n) for which R(k) is divisible by n. It gives A(7) = 6 and A(41) = 5, says that the least n for which A(n) first exceeds ten is 17, and asks for the least n for which A(n) first exceeds one million.
Wikipedia — Repunit. The article defines Rₙ = (10ⁿ − 1)/9, factorises the small repunits, for example R₅ = 41 · 271, proves with the pigeonhole principle that every n coprime to the base divides some repunit, and notes that for a prime p > 5 the period of the decimal expansion of 1/p equals the length of the smallest repunit divisible by p.
Wikipedia — Modular arithmetic. Congruence modulo m is compatible with addition and multiplication, and b mod m denotes the unique r with 0 ≤ r < m and r ≡ b (mod m).
Wikipedia — Pigeonhole principle. If n items are put into m containers with n > m, at least one container holds more than one item.
Wikipedia — Euclid's lemma. If an integer n divides a product ab and is coprime with a, then n divides b.
Wikipedia — Multiplicative order. The order of a modulo n is the smallest positive k with aᵏ ≡ 1 (mod n); by Lagrange's theorem it always divides φ(n), and a is called a primitive root modulo n when its order equals φ(n).
OEIS A001913 — Full reptend primes. The primes with primitive root 10, that is, the primes p for which the decimal expansion of 1/p has period p − 1: 7, 17, 19, 23, 29, 47, 59, 61, 97, … The related sequence A086018 counts them; there are 29500 up to 10⁶.
Wikipedia — Lifting-the-exponent lemma. For an odd prime p that divides x − y but neither x nor y, νₚ(xⁿ − yⁿ) = νₚ(x − y) + νₚ(n); for 10ᵏ − 1 and p = 3 this gives ν₃(10ᵏ − 1) = 2 + ν₃(k).
Wikipedia — Artin's conjecture on primitive roots. An integer a other than −1 that is not a perfect square should be a primitive root modulo infinitely many primes, and when a is not a perfect power and its squarefree part is not congruent to 1 modulo 4, as for a = 10, their density among the primes should be Artin's constant, about 0.3739558. Hooley proved this in 1967 assuming certain cases of the extended Riemann hypothesis.
Wikipedia — Prime number theorem. For large N a random integer not greater than N is prime with probability close to 1/log N, with the natural logarithm.
C++ — Euler129.cpp. The linked immutable C++ revision contains parse_arguments, A_of_n, exceeds_limit, solve and run_checkpoints. It is the implementation record for this article.
cppreference — std::gcd, defined in <numeric> since C++17, computes the greatest common divisor of two integers. cppreference — Arithmetic operators: when a signed integer operation overflows, the behaviour is undefined.
OEIS A099679. The least m such that the repunit Rₘ is a multiple of the n-th odd number not divisible by 5: 1, 3, 6, 9, 2, 6, 16, 18, …, the values of A(n) for n = 1, 3, 7, 9, 11, 13, 17, 19, …

Problem 129 source code

C++

#include <iostream>
#include <numeric>
#include <string>

namespace {

struct Options {
    int limit = 1000000;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--limit=", options.limit)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.limit >= 1;
}

int A_of_n(const int n) {
    int rem = 1 % n;
    int k = 1;
    while (rem != 0) {
        rem = (rem * 10 + 1) % n;
        ++k;
    }
    return k;
}

bool exceeds_limit(const int n, const int limit) {
    int rem = 1 % n;
    for (int k = 1; k <= limit; ++k) {
        if (rem == 0) {
            return false;
        }
        rem = (rem * 10 + 1) % n;
    }
    return true;
}

int solve(const int limit) {
    for (int n = limit + 1;; ++n) {
        if (std::gcd(n, 10) != 1) {
            continue;
        }
        if (exceeds_limit(n, limit)) {
            return n;
        }
    }
}

bool run_checkpoints() {
    if (A_of_n(7) != 6) {
        std::cerr << "Checkpoint failed for A(7)" << '\n';
        return false;
    }
    if (solve(10) != 17) {
        std::cerr << "Checkpoint failed for limit=10" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.limit) << '\n';
    return 0;
}

Python

# Problem 129: Repunit divisibility
# Find least n > 10^6 where A(n) > 10^6, where A(n) = smallest k with R(k) % n = 0.

from math import gcd

def solve():
    limit = 1000000
    for n in range(limit + 1, 10000000):
        if gcd(n, 10) != 1: continue
        rem = 1 % n
        k = 1
        while rem != 0 and k <= limit:
            rem = (rem * 10 + 1) % n
            k += 1
        if k > limit:
            print(n)
            return

solve()

Java

public class Euler129 {
    public static void main(String[] args) {
        int limit = 1000000;
        for (int n = limit + 1;; n++) {
            if (n % 2 == 0 || n % 5 == 0)
                continue;
            int rem = 1 % n, k = 1;
            while (rem != 0 && k <= limit) {
                rem = (rem * 10 + 1) % n;
                k++;
            }
            if (k > limit) {
                System.out.println(n);
                return;
            }
        }
    }
}