Project Euler Problem #26:

Problem #26 is the first Project Euler problem to feature repeating decimals. The question reads:

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:

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.

It should be clear that having prior mathematical knowledge about repeating decimals in base 10 is crucial to solving this problem. Here is my solution:

Solution #1: Mathematical Approach

First of all, it is worth determining for what d will 1/d end in a recurring cycle of digits. If we write d = p_1 * p_2 * p_3 * . . . * p_x (where p_1, p_2, . . . p_x are the not necessarily distinct prime factors of d), then we can also write 1/d = 1/(p_1) * 1/(p_2) * . . . * 1/(p_x). It is easy to see that if none of 1/(p_1), 1/(p_2), . . . 1/(p_x) end in a recurring cycle of digits, then 1/d will not end in a recurring cycle of digits either. Therefore, it makes sense to check when 1/p will end in a recurring cycle of digits for prime numbers p.

We can instantly notice that 1/2 = 0.5 and 1/5 = 0.2 do not end in a recurring cycle of digits. However, it appears that for all other prime numbers p, 1/p ends in a recurring cycle of digits. This makes sense, as if the decimal portion of a number terminates, then we should be able to write it as a/(10^x) for some integers a, x. 2 and 5 are the only prime numbers that could possibly divide 10^x, so all other primes cannot be in the denominator of a fraction that terminates. With this observation, we can determine that the length of the recurring cycle depends solely on the largest factor of d which is not divisibly by 2 or 5.

Next we can notice that the fraction a/(10^x – 1) = a/(10^x) + a/(10^(2x)) + a/(10^(3x)) + . . . using the formula for an infinite geometric series. It is clear that this fraction will have a recurring cycle of digits of length x as there are x digits between each fraction on the RHS of this equation. The only problem is if each repeating cycle of digits is composed of multiple cycles of a shorter repeating cycle of digits. Thus, it suffices to find the minimum value of x such that 1/d = a/(10^x – 1) for some integer (or terminating decimal) a.

With all of these observations, the method can be summarized as follows: First divide out all factors of 2 and 5 from d. Then find the smallest power of 10 which leaves a remainder of 1 when divided by d. (This is known as the order of 10 under the modulus d). After doing this for all possible values of d, we should be able to find the maximum repeating cycle. Here is an implementation of this method in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Order of 10 Approach to Project Euler Problem #26
 '''

 import time

 def projectEulerProblemTwentySix(n):
     maxIndex = 1
     maxCycle = 0
     for i in range(2,n):
         temp = i
         while(temp%2==0):
             temp/=2
         while(temp%5==0):
             temp/=5
         if(temp!=1):
             e = 1
             p = 10
             while(p%temp!=1):
                 p*=10
                 p%=temp
                 e+=1
             if(e>maxCycle):
                 maxIndex = i
                 maxCycle = e
     return maxIndex

 start = time.time()
 print projectEulerProblemTwentySix(1000)
 print ("--- %s seconds ---" % (time.time()-start))

 '''
 Prints

 983
 --- 0.0106329917908 seconds ---

 for input of n=1000
 '''

And just like that, we’re done. As we get to the more complex problems on Project Euler, a background in math will become more and more important.

Thanks for reading! See you tomorrow.