Problem 133: Repunit Nonfactors

Mathematical Development

Theorem 1 (5-Smooth Order Criterion). For a prime $p$ with $p \nmid 10$ and $p \neq 3$, there exists a positive integer $n$ such that $p \mid R(10^n)$ if and only if $\operatorname{ord}_p(10)$ is 5-smooth (i.e., all prime factors of $\operatorname{ord}_p(10)$ lie in $\{2, 5\}$).

Proof. By the divisibility theory for repunits (Theorem 1 of Problem 132), $p \mid R(k)$ iff $\operatorname{ord}_p(10) \mid k$. Therefore:

($\Rightarrow$) If $\operatorname{ord}_p(10) \mid 10^n = 2^n \cdot 5^n$ for some $n$, then every prime factor of $\operatorname{ord}_p(10)$ divides $2^n \cdot 5^n$, so $\operatorname{ord}_p(10)$ is 5-smooth.

($\Leftarrow$) If $\operatorname{ord}_p(10) = 2^a \cdot 5^b$, take $n = \max(a, b)$. Then $10^n = 2^n \cdot 5^n$ is divisible by $2^a \cdot 5^b = \operatorname{ord}_p(10)$, so $p \mid R(10^n)$. $\square$

Lemma 1 (Permanent Nonfactors). The primes $p = 2$, $p = 3$, and $p = 5$ never divide $R(10^n)$ for any $n \geq 1$.

Proof. The repunit $R(k) = \underbrace{11\ldots1}_k$ is odd (so $2 \nmid R(k)$) and ends in digit 1 (so $5 \nmid R(k)$), for all $k \geq 1$.

For $p = 3$: since $\operatorname{ord}_{27}(10) = 3$ (verifiable: $10^3 = 1000 \equiv 1 \pmod{27}$), we have $3 \mid R(k) \iff 3 \mid k$. Since $\gcd(3, 10) = 1$ implies $3 \nmid 10^n$ for all $n$, the prime 3 never divides $R(10^n)$. $\square$

Lemma 2 (Efficient Testing). For $p < 10^5$, the condition ”$\operatorname{ord}_p(10)$ is 5-smooth” is equivalent to $10^{10^{20}} \equiv 1 \pmod{p}$, where $10^{20} = 2^{20} \cdot 5^{20}$.

Proof. Since $\operatorname{ord}_p(10) \mid p - 1 < 10^5$, any 5-smooth divisor of $p - 1$ is of the form $2^a \cdot 5^b$ with $a \leq \lfloor \log_2(10^5) \rfloor = 16$ and $b \leq \lfloor \log_5(10^5) \rfloor = 7$. Hence $\operatorname{ord}_p(10) \mid 2^{20} \cdot 5^{20} = 10^{20}$, and the claim follows from the definition of multiplicative order.

Conversely, if $10^{10^{20}} \equiv 1 \pmod{p}$, then $\operatorname{ord}_p(10) \mid 10^{20}$, so $\operatorname{ord}_p(10)$ is 5-smooth. $\square$

Remark. An equivalent approach computes $\operatorname{ord}_p(10)$ explicitly by factoring $p - 1$ and refining, then checks 5-smoothness by dividing out all factors of 2 and 5.

Editorial

A prime p (not 2, 3, 5) can divide some R(10^n) iff ord_p(10) is 5-smooth. We iterate over p in primes.

Pseudocode

    N = 100000
    primes = sieve_primes(N)
    total = 0
    for p in primes:
        If p in {2, 3, 5} then
            total += p // permanent nonfactors
            continue
        d = multiplicative_order(10, p)
        If not is_5_smooth(d) then
            total += p // nonfactor
    Return total

Complexity Analysis

• Time: $O(N \log\log N)$ for the sieve. For each prime $p$, computing $\operatorname{ord}_p(10)$ requires factoring $p - 1$ in $O(\sqrt{p})$ time and $O(\log p)$ modular exponentiations. Over all $\pi(N)$ primes, the total is $O(N^{3/2} / \log N)$ in the worst case, though typically much faster.
• Space: $O(N)$ for the sieve.

Answer

/*
 * Project Euler Problem 133: Repunit Nonfactors
 *
 * Sum of all primes below 100000 that never divide R(10^n).
 * A prime p can divide some R(10^n) iff ord_p(10) is 5-smooth.
 */
#include <bits/stdc++.h>
using namespace std;

long long power_mod(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = (__int128)result * base % mod;
        base = (__int128)base * base % mod;
        exp >>= 1;
    }
    return result;
}

int main() {
    const int LIMIT = 100000;
    vector<bool> is_prime(LIMIT, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i < LIMIT; i++)
        if (is_prime[i])
            for (int j = i * i; j < LIMIT; j += i)
                is_prime[j] = false;

    long long total = 0;

    for (int p = 2; p < LIMIT; p++) {
        if (!is_prime[p]) continue;
        if (p == 2 || p == 3 || p == 5) {
            total += p;
            continue;
        }

        // Compute ord_p(10) by factoring p-1 and refining
        int pm1 = p - 1;
        vector<int> factors;
        int temp = pm1;
        for (int f = 2; (long long)f * f <= temp; f++) {
            if (temp % f == 0) {
                factors.push_back(f);
                while (temp % f == 0) temp /= f;
            }
        }
        if (temp > 1) factors.push_back(temp);

        int d = pm1;
        for (int f : factors)
            while (d % f == 0 && power_mod(10, d / f, p) == 1)
                d /= f;

        // Check if d is 5-smooth
        int dd = d;
        while (dd % 2 == 0) dd /= 2;
        while (dd % 5 == 0) dd /= 5;

        if (dd != 1)
            total += p;
    }

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

"""
Project Euler Problem 133: Repunit Nonfactors

Find the sum of all primes below 100000 that never divide R(10^n).
A prime p (not 2, 3, 5) can divide some R(10^n) iff ord_p(10) is 5-smooth.
"""

def sieve(limit):
    is_prime = [True] * limit
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, limit, i):
                is_prime[j] = False
    return [i for i in range(2, limit) if is_prime[i]]

def multiplicative_order(a, n):
    """Compute ord_n(a) by factoring n-1 and refining."""
    if n <= 1:
        return 1
    pm1 = n - 1
    factors = []
    temp = pm1
    f = 2
    while f * f <= temp:
        if temp % f == 0:
            factors.append(f)
            while temp % f == 0:
                temp //= f
        f += 1
    if temp > 1:
        factors.append(temp)
    d = pm1
    for f in factors:
        while d % f == 0 and pow(a, d // f, n) == 1:
            d //= f
    return d

def is_5_smooth(n):
    while n % 2 == 0:
        n //= 2
    while n % 5 == 0:
        n //= 5
    return n == 1

LIMIT = 100000
primes = sieve(LIMIT)
total = 0

for p in primes:
    if p in (2, 3, 5):
        total += p
        continue
    d = multiplicative_order(10, p)
    if not is_5_smooth(d):
        total += p

print(total)