Detailed mathematical approach

Problem Summary

We seek the unique prime \(p\) such that the decimal expansion of \(1/p\) begins with the digits \(00000000137\) and the full repetend defines a cyclic number whose last five digits are \(56789\). Once that prime is identified, the required Project Euler quantity is the sum of the digits of the cyclic number.

Mathematical Approach

Step 1: Write the repetend as an integer

For a prime \(p \neq 2,5\), the decimal expansion of \(1/p\) is purely repeating. If the period is maximal, then its length is \(p-1\), and the repeating block can be written as

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

The number \(N\) is the integer formed by the repeating digits of \(1/p\). When \(p\) is a full reptend prime in base \(10\), the multiples \(N,2N,\dots,(p-1)N\) are cyclic rotations of the same digit string, which is exactly why the problem is about cyclic numbers.

Step 2: Convert the decimal prefix into an interval for \(p\)

The first eleven digits after the decimal point are \(00000000137\). Multiplying \(1/p\) by \(10^{11}\) therefore gives a number whose integer part is \(137\):

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

Rearranging yields the narrow interval

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

This is implemented directly as

$\texttt{low}=\left\lfloor\frac{10^{11}}{138}\right\rfloor+1,\qquad \texttt{high}=\left\lfloor\frac{10^{11}}{137}\right\rfloor.$

Numerically, this is \(724637682 \lt p \le 729927007\), so the prefix already limits the search to a window of about \(5.29\times 10^6\).

Step 3: Convert the suffix into a congruence

The problem also tells us that the cyclic number ends in \(56789\). Therefore

$N \equiv 56789 \pmod{10^5}.$

Since \(pN=10^{p-1}-1\), reducing modulo \(10^5\) gives

$pN \equiv -1 \pmod{10^5}.$

Substituting the known suffix of \(N\),

$p \cdot 56789 \equiv -1 \pmod{10^5}.$

Solving this congruence yields

$p \equiv 9891 \pmod{10^5}.$

So every valid prime must lie in one arithmetic progression inside the interval. In the actual search window, that leaves exactly \(53\) candidates.

Step 4: Enforce the full-reptend condition

Not every prime in that progression has a repetend of length \(p-1\). For primes \(p \neq 2,5\), the period of \(1/p\) in base \(10\) is the multiplicative order

$\operatorname{ord}_p(10).$

By Fermat's little theorem, this order divides \(p-1\). Therefore the period is maximal exactly when

$\operatorname{ord}_p(10)=p-1.$

The standard test used by all three local solutions is: factor \(p-1\) into distinct prime divisors \(q\), and verify that

$10^{(p-1)/q} \not\equiv 1 \pmod p$

for every such \(q\). If any one of these congruences equals \(1\), then the order is a proper divisor of \(p-1\), so the candidate is rejected. In this repository's search, the arithmetic progression gives \(53\) values, only \(3\) of them are prime, and only one survives the order test:

$p=729809891.$

Step 5: Derive the digit-sum formula

Let \(s\) be the sum of the digits of the cyclic number \(N\). Because \(N,2N,\dots,(p-1)N\) are cyclic rotations, each of these numbers has the same digit sum \(s\). Summing them as multiples gives

$\sum_{k=1}^{p-1} kN = N \cdot \frac{p(p-1)}{2}.$

Summing the same set column by column gives a repunit times the digit sum:

$\sum_{k=1}^{p-1} kN = s \cdot R_{p-1},\qquad R_{p-1}=\frac{10^{p-1}-1}{9}.$

Since \(pN=10^{p-1}-1\), we also have \(R_{p-1}=pN/9\). Cancelling \(N\) yields

$s=\frac{9(p-1)}{2}.$

Substituting the unique prime found above gives

$s=\frac{9(729809891-1)}{2}=3284144505.$

This is the value returned by the local implementations.

How the Code Works

The C++, Python, and Java solutions follow the same structure. First, mod_pow performs binary modular exponentiation, which is needed for the order test. The C++ code uses __int128 during multiplication to avoid overflow, Java uses BigInteger for the same reason, and Python relies on native arbitrary-precision integers.

Second, is_prime performs trial division up to \(\sqrt{p}\). That would be too slow for a wide brute-force scan, but after the interval and congruence filters the candidate set is tiny, so the simple implementation is entirely sufficient here. Third, prime_factors_distinct strips repeated factors from \(p-1\), because the order test only needs the distinct prime divisors.

Finally, find_prime_p computes the interval bounds, aligns the first candidate to the residue class \(9891 \bmod 100000\), and scans by steps of \(100000\). The extra guard

$\left\lfloor\frac{10^{11}}{p}\right\rfloor=137$

keeps the prefix condition exact. The C++ version also runs checkpoints: \(p=7\) must be full reptend in base \(10\), the unique candidate must be \(729809891\), and the digit-sum formula must produce \(3284144505\).

Complexity Analysis

Let \(C\) be the number of candidates after the interval and congruence filters. In this instance \(C=53\). Each primality check uses naive trial division, so the worst-case cost per candidate is \(O(\sqrt{p})\). Factoring \(p-1\) by trial division has the same asymptotic bound, and the order test then uses one modular exponentiation for each distinct prime factor of \(p-1\), costing \(O(\log p)\) modular multiplications per factor.

So the repository implementation is asymptotically a small number of \(O(\sqrt{p})\) checks plus a few \(O(\log p)\) exponentiations. Practically, the search is tiny: \(53\) arithmetic-progression candidates, \(3\) primes, and \(1\) full-reptend prime.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=358
2. Multiplicative order: Wikipedia - Multiplicative order
3. Full reptend prime: Wikipedia - Full reptend prime
4. Cyclic number: Wikipedia - Cyclic number
5. Repeating decimal: Wikipedia - Repeating decimal