Project Euler, Problem 26: Reciprocal Cycles

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

\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

Where

0.1 \overline{6}

means

0.166666 \dots

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

For this problem I taught the computer how to do long division.

As I converted the fraction into decimal form with long division, I saved the pairs of quotients and remainders in an array. Then, after each operation I checked the pairs to see if there was a match. If so, I knew the sequence had repeated and based on the index of the pairs I could determine the repetend length. I also only checked 900 - 1000 since, based on research, I had a good idea the final answer would be a large prime.

74,423