Project Euler Problem 26 Solution

Question

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

12=0.513=0.314=0.2515=0.216=0.1617=0.14285718=0.12519=0.1110=0.1\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.160.1\overline{6} means 0.1666...0.1666..., and has a 1-digit recurring cycle. It can be seen that 17\frac{1}{7} has a 6-digit recurring cycle.

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

Haskell

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