Problem 130: Composites with Prime Repunit Property

Project Euler Problem 130 Solution

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

Problem Summary For a positive integer $k$, let $R(k)$ be the base-10 repunit with $k$ ones: $$R(k)=\underbrace{11\ldots1}_{k}=\frac{10^k-1}{9}.$$ For every $n$ with $\gcd(n,10)=1$, define $A(n)$ as the least $k\ge 1$ such that $R(k)\equiv 0 \pmod{n}$. The problem asks for the sum of the first 25 composite integers $n$ for which $A(n)\mid(n-1)$. The reason this is interesting is that primes already behave this way: every prime $p>5$ satisfies $A(p)\mid(p-1)$. Problem 130 asks for composite numbers that imitate that prime-style repunit divisibility property. Mathematical Approach The implementations do not factor numbers, build giant repunits, or use heavy algebraic machinery. They rely on the definition of $A(n)$, a simple remainder recurrence, and a direct search over composite candidates. Repunits and the meaning of $A(n)$ The quantity $A(n)$ is the first length for which a repunit becomes divisible by $n$. The condition $\gcd(n,10)=1$ is essential: if $n$ shared a factor with 2 or 5, no number ending in digit 1 could be divisible by $n$. Existence of $A(n)$ follows from a pigeonhole argument. Consider the residues of $R(1),R(2),\ldots,R(n)$ modulo $n$. If one of them is already 0, we are done. Otherwise two of them are equal, say $R(i)\equiv R(j)\pmod n$ with $i>j$....

Detailed mathematical approach

Problem Summary

A repunit is a number written only with the digit $1$: $R(k)$ has $k$ ones, so $R(6)=111111$. For a 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$. For every prime $p\gt5$ the length $A(p)$ divides $p-1$, for example $A(41)=5$ divides $40$, and a few composite numbers share this property, the first five being $91$, $259$, $451$, $481$ and $703$. We must find the sum of the first twenty-five composite $n$ with $\gcd(n,10)=1$ for which $A(n)$ divides $n-1$. ^[1]

The whole solution in one sentence: we go through the odd composite numbers that are not multiples of $5$ in increasing order, find $A(n)$ for each by appending ones to a remainder modulo $n$ until the remainder becomes $0$, and add up the first twenty-five $n$ for which this length divides $n-1$.

Mathematical Approach

We first compute $A(n)$ with small remainders instead of huge repunits. Then we prove the fact that gives the test its meaning, $n\mid R(k)$ exactly when $A(n)\mid k$, and use it to see why primes pass, which composite numbers can pass and why multiples of $3$ never do.

1. Repunits modulo n

Appending a one to $R(k)$ gives $R(k+1)=10R(k)+1$; for example $R(3)=10\cdot11+1=111$. The remainder of a sum or a product after division by $n$ depends only on the remainders of its parts, ^[3] so the remainder $r_k$ of $R(k)$ can be updated without ever writing the repunit down:

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

For $n=7$ this gives $1,4,6,5,2,0$, so $A(7)=6$ and $7$ divides $111111$. For $n=41$ it gives $1,11,29,4,0$, so $A(41)=5$; indeed $11111=41\cdot271$. For $n=91$ it gives $1,11,20,19,9,0$, so $A(91)=6$, and since $6$ divides $90$, the number $91$ is the first composite example of the statement.

2. Why A(n) exists

Every repunit ends in the digit $1$, so it is odd and not a multiple of $5$. A number that shares the factor $2$ or $5$ with $10$ therefore divides no repunit, which is why the problem requires $\gcd(n,10)=1$. Conversely, let $\gcd(n,10)=1$ and suppose that none of $r_1,\dots,r_n$ is $0$. These $n$ remainders then take at most $n-1$ values, so by the pigeonhole principle ^[4] two of them are equal, say $r_i=r_j$ with $i\gt j$. Their repunits differ by

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

as in $11111-11=100\cdot111$. So $n$ divides $10^jR(i-j)$, and because $10$ has an inverse modulo $n$, ^[3] it divides $R(i-j)$ with $1\le i-j\le n-1$, a contradiction. Hence $A(n)$ exists and $A(n)\le n$. The bound is attained, for example $A(3)=3$, $A(9)=9$ and $A(27)=27$.

3. The remainders repeat

Cutting the digits of $R(a+b)$ after the first $a$ ones gives

$$R(a+b)=10^{b}\,R(a)+R(b),$$

for example $11111=100\cdot111+11$. If $n$ divides $R(a)$, the first term is a multiple of $n$ and $r_{a+b}=r_b$. So as soon as the remainder reaches $0$ at $k=A(n)$, the sequence starts again from the beginning; for $n=7$ it continues $1,4,6,5,2,0,1,4,6,5,2,0,\dots$ This gives the key fact of the problem:

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

To prove it, write $k=qA(n)+s$ with $0\le s\lt A(n)$. Applying the rule $q$ times with $a=A(n)$ gives $r_k=r_s$, where $r_0=0$ is the remainder of the empty repunit $R(0)=0$. By the minimality of $A(n)$, $r_s=0$ happens only for $s=0$, so $r_k=0$ exactly when $A(n)$ divides $k$. For $a\ge1$ and $n=R(a)$ we have $A(n)=a$, because every shorter repunit is positive but smaller than $R(a)$, so the fact contains the rule that $R(a)$ divides $R(k)$ exactly when $a$ divides $k$. ^[2]

4. Why primes pass

By Section 3 with $k=n-1$, the condition $A(n)\mid n-1$ says exactly that $n$ divides $R(n-1)$, the repunit with $n-1$ ones. For a prime $p\gt5$, Fermat's little theorem gives $10^{p-1}\equiv1\pmod p$, because $p$ does not divide $10$. ^[5] Since

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

the prime $p$ divides $9R(p-1)$, and as $p\ne3$, it divides $R(p-1)$. Therefore $A(p)\mid p-1$, the fact given in the statement; for $p=41$, $40=8\cdot5$. The prime $3$ fails, since $A(3)=3$ does not divide $2$.

5. The same test with powers of ten

The identity $9R(k)=10^k-1$ also shows that $n\mid R(k)$ exactly when $9n\mid10^k-1$. Since $10$ is coprime to $9n$, the length $A(n)$ is the multiplicative order of $10$ modulo $9n$, the least $k\ge1$ with $10^k\equiv1\pmod{9n}$. ^[6] Every power of $10$ leaves the remainder $1$ after division by $9$, so if $3\nmid n$, then $9n$ divides $10^k-1$ exactly when $n$ does, and $A(n)$ is the order of $10$ modulo $n$. For a prime $p\gt5$ this is also the length of the period of the decimal fraction $1/p$, ^[2] as in $1/7=0.142857\,142857\ldots$ with period $6=A(7)$. For $3\nmid n$ the test $A(n)\mid n-1$ therefore reads

$$10^{\,n-1}\equiv1\pmod n.$$

Every prime that does not divide $10$ passes this test by Fermat's little theorem, and a composite number that passes it is called a Fermat pseudoprime to base $10$. ^[7] The numbers of this problem pass this test for primes without being prime, which is why the OEIS calls them deceptive nonprimes. ^[8]

6. Multiples of 3 never pass

Since $10$ leaves the remainder $1$ after division by $3$, the repunit $R(k)=1+10+\dots+10^{k-1}$ leaves the same remainder as $1+1+\dots+1=k$. Thus $3\mid R(k)$ exactly when $3\mid k$. If $3\mid n$, then $3$ divides $R(A(n))$, hence $3\mid A(n)$; but $n-1$ leaves the remainder $2$ after division by $3$, so $A(n)$ cannot divide $n-1$. Every number we are looking for is therefore coprime to $30$, and by Section 5 the problem asks exactly for the Fermat pseudoprimes to base $10$ that are not multiples of $3$. ^[7] Below $1000$ the pseudoprimes to base $10$ are $9$, $33$, $91$, $99$, $259$, $451$, $481$, $561$, $657$, $703$ and $909$; removing the six multiples of $3$ leaves exactly the five numbers of the statement. For example $A(33)=6$ does not divide $32$.

7. Products of primes

Let $m$ and $n$ be coprime to each other and to $10$. Then $mn$ divides $R(k)$ exactly when both $m$ and $n$ do, so by Section 3 the lengths $k$ that work for $mn$ are the common multiples of $A(m)$ and $A(n)$. The least of them is their least common multiple:

$$A(mn)=\mathrm{lcm}\bigl(A(m),A(n)\bigr).$$

For example, $A(11)=2$ and $A(41)=5$ give $A(451)=10$. Now let $n=p_1p_2\cdots p_r$ be a product of distinct primes $p_i\ge7$. Then $A(n)\mid n-1$ holds exactly when $A(p_i)\mid n-1$ for every $i$. Since $A(p_i)\mid p_i-1$ by Section 4, the identity

$$n-1=\frac{n}{p_i}\,(p_i-1)+\Bigl(\frac{n}{p_i}-1\Bigr)$$

turns this into the condition $A(p_i)\mid n/p_i-1$ for every $i$. For two primes $p$ and $q$ it reads $A(p)\mid q-1$ and $A(q)\mid p-1$, and all five examples of the statement are of this kind:

$91=7\cdot13$: $A(7)=6$ divides $12$, and $A(13)=6$ divides $6$;
$259=7\cdot37$: $6$ divides $36$, and $A(37)=3$ divides $6$;
$451=11\cdot41$: $A(11)=2$ divides $40$, and $A(41)=5$ divides $10$;
$481=13\cdot37$: $6$ divides $36$, and $3$ divides $12$;
$703=19\cdot37$: $A(19)=18$ divides $36$, and $3$ divides $18$.

The prime $37$ occurs in three of the five examples: $111=3\cdot37$ gives the unusually small $A(37)=3$, and $37-1=36$ is divisible by $A(7)=6$, $A(13)=6$ and $A(19)=18$. In contrast, $77=7\cdot11$ fails: $A(77)=\mathrm{lcm}(6,2)=6$ does not divide $76$, because $A(7)=6$ does not divide $11-1=10$.

8. Small cases and Carmichael numbers

Below $100$ there are sixteen composite numbers coprime to $10$, with these values of $A(n)$:

$A(9)=9$, $A(21)=6$, $A(27)=27$, $A(33)=6$, $A(39)=6$, $A(49)=42$, $A(51)=48$, $A(57)=18$, $A(63)=18$, $A(69)=66$, $A(77)=6$, $A(81)=81$, $A(87)=84$, $A(91)=6$, $A(93)=15$, $A(99)=18$.

All thirteen multiples of $3$ among them have $3\mid A(n)$, as Section 6 predicts, and only $91$ passes. The property is rare: below $10^6$ exactly $219$ composite numbers have it. Some of them are forced, however. A Carmichael number is a composite $n$ with $b^{n-1}\equiv1\pmod n$ for every $b$ coprime to $n$. By Korselt's criterion these are exactly the composite $n$ that are squarefree, with no prime factor repeated, and for which $p-1$ divides $n-1$ for every prime $p$ dividing $n$. ^[9] If such an $n$ is coprime to $30$, then $A(p)\mid p-1\mid n-1$ for each of its prime factors, so $A(n)\mid n-1$ by the lcm rule. For example $1729=7\cdot13\cdot19$ has $A(1729)=\mathrm{lcm}(6,6,18)=18$, and $1728=18\cdot96$. The smallest Carmichael number, $561=3\cdot11\cdot17$, is a multiple of $3$ and fails: $A(561)=48$ does not divide $560$.

9. The search

The programs find these numbers by a direct search. They test $n=3,5,7,\dots$, skip multiples of $5$ and primes, compute $A(n)$ with the recurrence of Section 1, which stops after at most $n$ steps by Section 2, and accept $n$ when $A(n)$ divides $n-1$. Every remainder is below $n$, whereas the repunits $R(A(n))$ met in the search have up to $14562$ digits. The twenty-fifth accepted number lies below $15000$.

How the Code Works

The C++ program ^[10] keeps its settings in Options: count is $25$ and run_checkpoints is true. parse_arguments accepts --skip-checkpoints and --count=N, whose digits parse_int_after_prefix reads; any other argument, or a count below $1$, makes main return $1$. The digits are accumulated in an int without an overflow check, so a value above the largest int, such as --count=2147483648, causes undefined behaviour. is_prime is trial division: it rejects $n\lt2$ and the even numbers other than $2$, then tries the odd divisors $p$ with $p^2\le n$, forming $p\cdot p$ as a 64-bit i64 so that the product cannot overflow. A_of_n is the recurrence of Section 1: rem starts at 1 % n and k at $1$, and while rem is not $0$ the function sets rem = (rem * 10 + 1) % n and increases k.

solve(wanted_count) runs through $n=3,5,7,\dots$, skips multiples of $5$, primes and, redundantly at that point, any $n$ with std::gcd(n, 10) != 1, and adds $n$ to a 64-bit sum when (n - 1) % a == 0 for a = A_of_n(n), until wanted_count numbers have been found. It does not skip multiples of $3$, although Section 6 shows that they never pass; they only cost time. run_checkpoints requires solve(5) to equal $1985=91+259+451+481+703$, the sum of the five examples of the statement, and main returns $2$ if it does not; otherwise main prints solve(count).

The Python version has the same A_of_n and the same loop, but tests primality with SymPy's isprime, whose answer is definitive below $2^{64}$, ^[11] always looks for $25$ numbers and has no checkpoint. The Java version mirrors is_prime and A_of_n as isPrime and A, without options or checkpoint; its second test of n % 2 and n % 5 can never succeed. C++ and Java keep the sum in 64 bits (i64, long) and n and the remainder in int. Since the remainder is below $n$, $10r+1$ fits in a 32-bit int for every $n\le214748365$, far beyond the twenty-five requested numbers, all below $15000$; nothing checks this bound for a much larger --count. Python's integers have no fixed size.

Complexity and Verification

In C++ and Java the primality test of one candidate $n$ costs at most about $\sqrt n/2$ trial divisions, and A_of_n makes $A(n)-1\le n-1$ constant-time updates on machine integers, with a few variables of memory. Scanning up to $X$ therefore costs $O(X^{3/2})$ for the primality tests and $O(X^2)$ for the updates in the worst case; Python makes the same updates but tests primality with SymPy. For the requested search all three programs make $5880$ primality tests and compute $A(n)$ for $4162$ composite numbers with $6639238$ updates, $3782292$ of them, about $57\%$, for multiples of $3$, which Section 6 excludes in advance. The trial division of C++ and Java tries $92420$ odd divisors in total; the C++ checkpoint adds a much shorter search for five numbers. On our test computer the C++, Java and Python programs took about $0.02$, $0.05$ and $0.4$ seconds. A faster test, not used by the programs, follows from Section 5: a composite $n$ passes exactly when $10^{n-1}\equiv1\pmod{9n}$, and fast modular exponentiation by repeated squaring decides this with $O(\log n)$ multiplications.

The C++ program checks the sum of the five given examples before the main search. For this article we also verified that:

the three programs print the same value;
for every $n$ coprime to $10$, the recurrence gives the same $A(n)$ as a direct search with exact repunits when $n\le3000$, and the same as the order of $10$ modulo $9n$ when $n\le20000$;
$A(p)\mid p-1$ for all $9589$ primes $7\le p\lt10^5$, and the lcm rule of Section 7 holds for all $9279$ pairs $1\lt m\lt n$ coprime to each other and to $10$ with $mn\lt20000$;
for every composite $n\lt10^6$ coprime to $10$, the property holds exactly when $10^{n-1}\equiv1\pmod{9n}$, and exactly when $3\nmid n$ and $10^{n-1}\equiv1\pmod n$;
the first thirty numbers found by the search agree with the b-file of OEIS A000864. ^[8]

Footnotes and References

The references below supply the background facts used above. The repetition of the remainders, the reduction to pseudoprimes not divisible by $3$, the criterion for products of primes and the operation counts are derived explicitly in this article.

Project Euler 130 — Composites with Prime Repunit Property. The official statement defines R(k) and, for gcd(n, 10) = 1, the least length A(n) of a repunit divisible by n, gives A(7) = 6 and A(41) = 5, states that A(p) divides p − 1 for every prime p > 5, lists 91, 259, 451, 481 and 703 as the first five composite numbers with this property, and asks for the sum of the first twenty-five.
Wikipedia — Repunit. The decimal repunits are Rₙ = (10ⁿ − 1)/9; Rₙ is divisible by Rₐ whenever a divides n; every number coprime to 10 divides some repunit; and 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, subtraction and multiplication, so remainders can be updated step by step, and an integer has an inverse modulo m exactly when it is coprime to m.
Wikipedia — Pigeonhole principle. If n items are put into m containers with n > m, at least one container holds more than one item; Section 2 applies it to n remainders that could take only n − 1 values.
Wikipedia — Fermat's little theorem. For a prime p and an integer a not divisible by p, a^(p−1) ≡ 1 (mod p). The converse fails: a composite number can satisfy the same congruence, and it is then called a Fermat pseudoprime to base a.
Wikipedia — Multiplicative order. For a coprime to n, the order of a modulo n is the smallest positive k with aᵏ ≡ 1 (mod n); it divides Euler's φ(n) and the Carmichael function λ(n).
Wikipedia — Fermat pseudoprime. A composite x with a^(x−1) ≡ 1 (mod x) is a Fermat pseudoprime to base a; the table of fixed bases lists the base-10 pseudoprimes 9, 33, 91, 99, 259, 451, 481, 561, 657, …, and the section on deceptive nonprimes states that a composite number divides the repunit with one digit fewer than itself exactly when it is a Fermat pseudoprime to base 10 and not divisible by 3.
OEIS A000864 — Deceptive nonprimes. The composite numbers k that divide the repunit with k − 1 ones, beginning 91, 259, 451, 481, 703, 1729, 2821, 2981; a comment identifies them with the pseudoprimes to base 10 (A005939) that are not divisible by 3.
Wikipedia — Carmichael number. A Carmichael number is a composite n with bⁿ ≡ b (mod n) for all integers b, which can also be written as b^(n−1) ≡ 1 (mod n) for all b coprime to n. By Korselt's criterion a composite n is a Carmichael number exactly when it is squarefree and p − 1 divides n − 1 for every prime p dividing n; 561 = 3·11·17 is the smallest Carmichael number and 1729 = 7·13·19 the third.
C++ — Euler130.cpp. The linked immutable revision contains is_prime, A_of_n, solve and run_checkpoints. It is the implementation record for this article.
SymPy — isprime. The documentation of sympy.ntheory.primetest.isprime describes a quick check for trivial factors, a bisection search in SymPy's sieve when the sieve is large enough and deterministic Miller–Rabin tests for small numbers, and states that the answer is definitive for n < 2⁶⁴.

Problem 130 source code

C++

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

namespace {

using i64 = std::int64_t;

struct Options {
    int count = 25;
    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, "--count=", options.count)) {
            continue;
        }

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

bool is_prime(const int n) {
    if (n < 2) {
        return false;
    }
    if ((n % 2) == 0) {
        return n == 2;
    }
    for (int p = 3; static_cast<i64>(p) * p <= n; p += 2) {
        if ((n % p) == 0) {
            return false;
        }
    }
    return true;
}

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;
}

i64 solve(const int wanted_count) {
    int found = 0;
    i64 sum = 0;

    for (int n = 3; found < wanted_count; n += 2) {
        if ((n % 5) == 0) {
            continue;
        }
        if (is_prime(n)) {
            continue;
        }
        if (std::gcd(n, 10) != 1) {
            continue;
        }

        const int a = A_of_n(n);
        if (((n - 1) % a) == 0) {
            ++found;
            sum += n;
        }
    }

    return sum;
}

bool run_checkpoints() {
    if (solve(5) != 1985) {
        std::cerr << "Checkpoint failed for first five values" << '\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.count) << '\n';
    return 0;
}

Python

# Problem 130: Composites with prime repunit property
# Find sum of first 25 composite n (coprime to 10) where (n-1) % A(n) = 0.

from sympy import isprime
from math import gcd

def A_of_n(n):
    rem = 1 % n
    k = 1
    while rem != 0:
        rem = (rem * 10 + 1) % n
        k += 1
    return k

def solve():
    found = 0
    total = 0
    n = 3
    while found < 25:
        if n % 5 != 0 and not isprime(n) and gcd(n, 10) == 1:
            a = A_of_n(n)
            if (n - 1) % a == 0:
                found += 1
                total += n
        n += 2
    print(total)

solve()

Java

public class Euler130 {
    static boolean isPrime(int n) {
        if (n < 2)
            return false;
        if (n % 2 == 0)
            return n == 2;
        for (int p = 3; (long) p * p <= n; p += 2)
            if (n % p == 0)
                return false;
        return true;
    }

    static int A(int n) {
        int rem = 1 % n, k = 1;
        while (rem != 0) {
            rem = (rem * 10 + 1) % n;
            k++;
        }
        return k;
    }

    public static void main(String[] args) {
        int found = 0;
        long sum = 0;
        for (int n = 3; found < 25; n += 2) {
            if (n % 5 == 0 || isPrime(n))
                continue;
            if (n % 2 == 0 || n % 5 == 0)
                continue;
            int a = A(n);
            if ((n - 1) % a == 0) {
                found++;
                sum += n;
            }
        }
        System.out.println(sum);
    }
}