Problem 130: Composites with Prime Repunit Property

Mathematical Foundation

Theorem 1 (Prime repunit property). For any prime $p > 5$, $A(p)$ divides $p - 1$.

Proof. Since $p > 5$ is prime and $\gcd(p, 10) = 1$, Fermat’s Little Theorem gives $10^{p-1} \equiv 1 \pmod{p}$. Also $\gcd(9, p) = 1$ (since $p \neq 3$), so

Therefore $p \mid R(p-1)$, which means $A(p) \mid (p-1)$ (since $A(p)$ is the least such $k$ and $A(p)$ divides any $k$ with $p \mid R(k)$).

To see that $A(p) \mid k$ whenever $p \mid R(k)$: if $p \mid R(k)$ then $10^k \equiv 1 \pmod{p}$. Since $A(p) = \text{ord}_p(10)$ (by Theorem 2 of Problem 129, as $\gcd(9, p) = 1$), the multiplicative order divides $k$. $\square$

Theorem 2 (Fermat pseudoprime connection). If $n$ is composite with $\gcd(n, 10) = 1$, $\gcd(n, 9) = 1$, and $10^{n-1} \equiv 1 \pmod{n}$ (i.e., $n$ is a Fermat pseudoprime to base 10), then $A(n) \mid (n-1)$.

Proof. Since $\gcd(n, 9) = 1$, we have $A(n) = \text{ord}_n(10)$ (as shown in Problem 129). If $10^{n-1} \equiv 1 \pmod{n}$, then $\text{ord}_n(10) \mid (n-1)$, i.e., $A(n) \mid (n-1)$. $\square$

Lemma 1 (Divisibility of $A$). If $n \mid R(k)$, then $A(n) \mid k$.

Proof. Write $k = qA(n) + r$ with $0 \leq r < A(n)$. Then

More directly: using $R(k) = (10^k - 1)/9$ and the fact that $\text{ord}_n(10) = A(n)$ (when $\gcd(n,9) = 1$), we have $10^k \equiv 1 \pmod{n}$ iff $A(n) \mid k$. For $\gcd(n, 9) \neq 1$, the iterative computation of $A(n)$ still yields the correct minimal period, and the divisibility property holds by the periodicity of the sequence $r_k = R(k) \bmod n$. $\square$

Lemma 2 (Iterative computation of $A(n)$). As in Problem 129: $r_1 = 1$, $r_k = (10 r_{k-1} + 1) \bmod n$. The first $k$ with $r_k = 0$ is $A(n)$.

Proof. Follows from $R(k) = 10 R(k-1) + 1$. $\square$

Editorial

We compute A(n). We first generate the primes required by the search, then enumerate the admissible combinations and retain only the values that satisfy the final test.

Pseudocode

    results = []
    n = 1
    While len(results) < target_count:
        n += 1
        If gcd(n, 10) != 1 then
            continue
        If is_prime(n) then
            continue
        Compute A(n)
        r = 1 mod n
        k = 1
        While r != 0:
            r = (10 * r + 1) mod n
            k += 1
        A_n = k
        If (n - 1) mod A_n == 0 then
            results.append(n)
    Return sum(results)

    if n < 2: return false
    for d = 2, 3, ..., floor(sqrt(n)):
        if n mod d == 0: return false
    Return true

Complexity Analysis

• Time: For each candidate $n$, computing $A(n)$ costs $O(A(n)) \leq O(n)$, and primality testing costs $O(\sqrt{n})$. The 25 qualifying composites are found among relatively small values of $n$ (the largest is a few thousand). Total work is manageable, roughly $O(N_{\max}^2)$ in the worst case where $N_{\max}$ is the largest qualifying composite.
• Space: $O(1)$ beyond the result list.

Answer

#include <bits/stdc++.h>
using namespace std;

bool is_prime(int n) {
    if (n < 2) return false;
    if (n < 4) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; (long long)i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

int repunit_order(int n) {
    int r = 1;
    int k = 1;
    while (r != 0) {
        r = (10LL * r + 1) % n;
        k++;
    }
    return k;
}

int main() {
    int count = 0;
    long long total = 0;

    for (int n = 2; count < 25; n++) {
        if (n % 2 == 0 || n % 5 == 0) continue;
        if (is_prime(n)) continue;

        int an = repunit_order(n);
        if ((n - 1) % an == 0) {
            total += n;
            count++;
        }
    }

    cout << total << endl;
    return 0;
}

"""
Problem 130: Composites with Prime Repunit Property

Find the sum of the first 25 composite n with gcd(n,10)=1
where A(n) divides (n-1).
"""

from math import gcd, isqrt

def is_prime(n):
    if n < 2:
        return False
    if n < 4:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

def repunit_order(n):
    """Find smallest k such that R(k) is divisible by n."""
    r = 1
    k = 1
    while r != 0:
        r = (10 * r + 1) % n
        k += 1
    return k

def solve():
    composites = []
    n = 2
    while len(composites) < 25:
        if n % 2 != 0 and n % 5 != 0 and not is_prime(n):
            an = repunit_order(n)
            if (n - 1) % an == 0:
                composites.append(n)
        n += 1

    return sum(composites)

def visualize():
    """Visualize the qualifying composite numbers."""