Project Euler Problem 358

Project Euler Problem 358

Solution

Answer: 3284144505

Let $N$ be the cyclic number. A classical fact about cyclic numbers is:

• Every cyclic number comes from the repeating decimal of $1/p$, where $p$ is a prime for which $10$ is a primitive root modulo $p$ (a full reptend prime).
• The cyclic number is the repetend of $1/p$:

$$N=\frac{10^{p-1}-1}{p}$$

with exactly $p-1$ digits.

For example:

$$\frac{1}{7}=0.\overline{142857}$$

gives the cyclic number $142857$.

---

Step 1: Use the leftmost digits

We are told the decimal expansion begins:

$$0.00000000137\cdots$$

Thus

$$\frac{1}{p} \in \left[ 1.37\times 10^{-9}, 1.38\times 10^{-9} \right)$$

so

$$\frac{10^{11}}{138} < p \le \frac{10^{11}}{137}.$$

This gives:

$$724,637,681 < p < 729,927,007.$$

---

Step 2: Use the last five digits

The cyclic number ends in $56789$.

Since

$$pN = 10^{p-1}-1,$$

we have modulo $100000$:

$$p\cdot 56789 \equiv -1 \pmod{100000}.$$

The modular inverse of $56789$ modulo $100000$ gives:

$$p \equiv 9891 \pmod{100000}.$$

Searching the interval above gives only three candidates:

$$725509891,\quad 726509891,\quad 729809891.$$

Now impose the full reptend condition (that $10$ has order $p-1$ mod $p$):

• $725509891$: not cyclic
• $726509891$: not cyclic
• $729809891$: cyclic ✓

Hence

$$p = 729809891.$$

---

Step 3: Sum of digits

For a full reptend prime $p$, the repetend has length $p-1$, and by Midy’s theorem the second half is the 9’s complement of the first half. Therefore each paired digit sums to $9$.

So the digit sum is

$$9\cdot \frac{p-1}{2}.$$

Substitute $p=729809891$:

$$9\cdot \frac{729809890}{2} = 9\cdot 364904945 = 3284144505.$$

Python implementation

from sympy import primerange, factorint

# Interval forced by leading digits 00000000137
lo = int(10**11 / 138) + 1
hi = int(10**11 / 137)

def is_full_reptend_prime(p):
    """Check whether 10 is a primitive root mod p."""
    factors = factorint(p - 1)
    return all(pow(10, (p - 1) // q, p) != 1 for q in factors)

def last_five_digits_match(p):
    """Check that repetend ends in 56789."""
    # N = (10^(p-1) - 1) / p
    mod = p * 100000
    n_mod = (pow(10, p - 1, mod) - 1) // p
    return n_mod % 100000 == 56789

candidate = None

for p in primerange(lo, hi + 1):
    # congruence from last five digits
    if p % 100000 != 9891:
        continue

    # first 11 digits must be 00000000137
    if 10**11 // p != 137:
        continue

    if last_five_digits_match(p) and is_full_reptend_prime(p):
        candidate = p
        break

# digit sum of cyclic number
answer = 9 * (candidate - 1) // 2
print(answer)

Code walkthrough

• Range narrowing: computes the interval for $p$ using the prefix 00000000137.
• Congruence filter: keeps only primes satisfying

$$p\cdot 56789\equiv -1 \pmod{100000}.$$

• Prefix test: verifies the first 11 digits are exactly 00000000137.
• Cyclic test: checks that $10$ is a primitive root mod $p$, ensuring the decimal expansion is cyclic.
• Digit sum: uses the complement property of cyclic numbers to compute

$$9\cdot\frac{p-1}{2}.$$

Final sanity check:

• $p$ lies in the required interval ✓
• repetend ends with 56789 ✓
• full cyclic property holds ✓
• digit sum formula matches known examples ($1/7\to27$, $1/17\to72$) ✓

Answer: 3284144505