Problem

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.

Answer

983

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])

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]

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]

Mathematica

CycleLength[x_] := Length[Last[First[RealDigits[x]]]]
d = 1;
For[i = 1, i < 1000, i++,
  If[CycleLength[1 / i] > CycleLength[1 / d], d = i]]
d

Java

import java.util.HashMap;
import java.util.Map;


public final class p026 implements EulerSolution {
	
	public static void main(String[] args) {
		System.out.println(new p026().run());
	}
	
	
	public String run() {
		int bestNumber = 0;
		int bestLength = 0;
		for (int i = 1; i <= 1000; i++) {
			int len = getCycleLength(i);
			if (len > bestLength) {
				bestNumber = i;
				bestLength = len;
			}
		}
		return Integer.toString(bestNumber);
	}
	
	
	private static int getCycleLength(int n) {
		Map<Integer,Integer> stateToIter = new HashMap<>();
		int state = 1;
		for (int iter = 0; ; iter++) {
			if (stateToIter.containsKey(state))
				return iter - stateToIter.get(state);
			else {
				stateToIter.put(state, iter);
				state = state * 10 % n;
			}
		}
	}
	
}