A unit fraction contains \(1\) in the numerator. The decimal representation of the unit fractions with denominators \(2\) to \(10\) are given:
\begin{align} 1/2 &= 0.5\\ 1/3 &=0.(3)\\ 1/4 &=0.25\\ 1/5 &= 0.2\\ 1/6 &= 0.1(6)\\ 1/7 &= 0.(142857)\\ 1/8 &= 0.125\\ 1/9 &= 0.(1)\\ 1/10 &= 0.1 \end{align}Where \(0.1(6)\) means \(0.166666\cdots\), and has a \(1\)-digit recurring cycle. It can be seen that \(1/7\) has a \(6\)-digit recurring cycle.
Find the value of \(d \lt 1000\) for which \(1/d\) contains the longest recurring cycle in its decimal fraction part.
This is the decimal period of \(1/d\), denoted \(\lambda(d)\). If \(d = 2^a 5^b c\), where \(c\) is not divisible by either \(2\) or \(5\), then \(\lambda(d)\)is equal to the multiplicative order of \(10\) modulo \(c\): the smallest integer \(k\) such that \(10^k \equiv 1 \pmod{c}\). It also holds that \(\lambda(d) \leq \varphi(d) \lt d\), where \(\varphi\) is Euler's totient function. This means that we can take \(d\) from \(999\) downward, compute \(\lambda(d)\) for each one, and when \(d\) falls below the highest seen value of \(\lambda\), terminate. (This happens almost immediately; as it turns out, \(\lambda(983) = 982\).)
def p26(cap=1000):
max_L, res = 0, 0
for d in range(cap - 1, 0, -1):
if max_L > d:
return res
c = d
while c % 2 == 0:
c //= 2
while c % 5 == 0:
c //= 5
if c == 1:
continue # no repeating decimals
L, v = 1, 10
while v != 1:
L += 1
v = v * 10 % c
if L > max_L:
max_L, res = L, d