## Question

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

\displaystyle \begin{aligned} \frac{1}{2}&=0.5 \\\\ \frac{1}{3}&=0.\overline{3} \\\\ \frac{1}{4}&=0.25 \\\\ \frac{1}{5}&=0.2 \\\\ \frac{1}{6}&=0.1\overline{6} \\\\ \frac{1}{7}&=0.\overline{142857} \\\\ \frac{1}{8}&=0.125 \\\\ \frac{1}{9}&=0.\overline{1} \\\\ \frac{1}{10}&=0.1 \end{aligned}

Where $0.1\overline{6}$ means $0.1666...$, and has a 1-digit recurring cycle. It can be seen that $\frac{1}{7}$ has a 6-digit recurring cycle.

Find the value of $d < 1000$ for which $\frac{1}{d}$ contains the longest recurring cycle in its decimal fraction part.

import Data.List (maximumBy)
import Data.Function (on)

cycleLength :: Integer -> Integer
cycleLength n | even n = 0
| n rem 5 == 0 = 0
| otherwise = head [p | p <- [1..], (10^p - 1) rem n == 0]

main :: IO ()
main = print $maximumBy (compare on cycleLength) [1,3..1000] $ ghc -O2 -o decimal-cycle decimal-cycle.hs
$time ./decimal-cycle real 0m0.831s user 0m0.812s sys 0m0.008s ## Python #!/usr/bin/env python def recurring_cycle(n, d): # solve 10^s % d == 10^(s+t) % d # where t is length and s is start for t in range(1, d): if 1 == 10**t % d: return t return 0 longest = max(recurring_cycle(1, i) for i in range(2,1001)) print([i for i in range(2,1001) if recurring_cycle(1, i) == longest][0]) $ time python3 recurring-decimal.py
real   0m1.156s
user   0m1.136s
sys    0m0.000s

## Ruby

#!/usr/bin/env ruby
puts (0..1000).map { |d|
(1..d).detect(lambda{0}) { |t| (10**t % d) == 1 }
}.each_with_index.max[1]
\$ time ruby decimal-cycle.rb
real   0m0.815s
user   0m0.792s
sys    0m0.008s

Questions? Comments? Send me an email: z@chdenton.com