Problem 026


Project Euler

Reciprocal cycles

Problem 26

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

1/2 = 0.5
1/3 = 0.(3)
1/4 = 0.25
1/5 = 0.2
1/6 = 0.1(6)
1/7 = 0.(142857)
1/8 = 0.125
1/9 = 0.(1)
1/10 = 0.1

Where 0.1(6) means 0.166666…, and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.

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


This problem is interesting because there is an element of abstract algebra that looks familiar. The first thing to note is when 10 is divisible by the denominator, there will not be a recurring cycle. Secondly, if any n ever produce a r_i in the following recurring fraction calculation such that 10 ~r_i = 10 or r_j, there is a recurring cycle:

r_0 = 10 ~mod ~d, r_1 = 10 r_0 ~mod ~d, \ldots r_i = 10 r_{i-1} ~mod ~d

For example, 10 mod 6 = 4, 40 mod 6 = 4 … so on.

Now, to get a very long chain, the denominator (d) should be a prime and a large prime as well. Therefore, using a list of prime generated from previous problem (3), going from the largest to smallest, looks for any number that will continuously generate n-1 different remainder. The largest n with this condition will be the answer.

Advertisements