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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s