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:

\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.

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.262s
user   0m0.262s
sys    0m0.000s

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.398s
user   0m1.390s
sys    0m0.008s

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.778s
user   0m0.762s
sys    0m0.016s

Rust

fn cycle_length(n: usize) -> usize {
    let mut remainder = 10;
    let mut seen = vec![0; 10 * n + 1];
    for i in 0.. {
        if remainder == 0 {
            return 0;
        } else if seen[remainder] != 0 {
            return i - seen[remainder];
        }
        seen[remainder] = i;
        remainder = 10 * (remainder % n);
    }
    0
}

fn main() {
    let max: usize = (1..1000).max_by_key(|&n| cycle_length(n)).unwrap();
    println!("{}", max);
}

$ rustc -C target-cpu=native -C opt-level=3 -o cycle cycle.rs
$ time ./cycle
real   0m0.003s
user   0m0.000s
sys    0m0.003s