# 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:

\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.719s user 0m0.716s 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.001s
user   0m1.000s
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.778s user 0m0.776s sys 0m0.000s ## 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.000s