Project Euler 26: Find the value of d < 1000 for which 1/d contains the longest recurring cycle

Written by on 5 February 2011

Topics: Project Euler

Problem 26 of Project Euler reads

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.

How can be possibly approach this problem. Just doing a division and then analysing the double we get out of it is not likely to give us enough digits to find the solution. Usually when the number representation lacks we can use the BigInteger class, but for once that wont help us. However, I found one possible approach. Instead of actually calculating the fraction, we analyse the remainder on each position. It has the advantage that we work with integers rather than fractions.

Solution Approach

Let me illustrate with 1/7.  First calculation of the remainder of 1/7 gives us 1.

Second calculation to analyse the remainder on the first decimal place we multiply by 10,  and divide by 7. The remainder of 10/7 is 3.

In the third calculation we get 30/7 which gives us a remainder of 2.

In the fourth calculation we get 20/7 which gives us a remainder of 6.

In the fifth calculation we get 60/7 which gives us a remainder of 4.

In the sixth calculation we get 40/7 which gives us a remainder of 5.

In the seventh calculation we get 50/7 which gives us a remainder of 1.

We already have had a remainder of 1 on the first calculation which means that we continue the calculations we will see the same pattern emerge again, since 10/7 gives us 3 and so on.  Thus we have found the longest recurring cycle in 1/7. Or rather we have found the length of the recurring cycle in 1/7 which is 7-1 = 6 digits long.

This is a pretty simple solution approach, where all we need to do is to keep calculating the remainder and keep track of the already found remainders.

One more thing to note is that the maximum recurring cycle length of 1/d is d-1, as it is pretty obvious from the example. We can get d-1 different possible remainders from the number, since if the result is equal to or greater than d, then it is not a remainder.

What that means is that we are more likely to find a large recurring cycle when d is large, and we can stop the search once d becomes lower than the longest recurring cycle we have found.

The algorithm

So with the solution approach explained I will present the algorithm. I have chosen to store the already found remainders in an integer array by filling in the position of the remainder in the array index corresponding to the remainder.

The algorithm looks like

int sequenceLength = 0;

for (int i = 1000; i > 1; i--) {
    if (sequenceLength >= i) {
        break;
    }

    int[] foundRemainders = new int[i];
    int value = 1;
    int position = 0;

    while (foundRemainders[value] == 0 && value != 0) {
        foundRemainders[value] = position;
        value *= 10;
        value %= i;
        position++;
    }

    if (position - foundRemainders[value] > sequenceLength) {
        sequenceLength = position - foundRemainders[value];
    }
}

With the explanation above I think it is pretty self explanatory. It is really fast and runs in under 1ms on my computer. The result is

The number with the longest recurring cycle is 983, and the cycle is length is 982
Solution took 0 ms

Source Code

As usual the source code is available for download. Any questions or comments to the post is most appreciated. Did you solve the problem in another way?

29 Comments For This Post I'd Love to Hear Yours!

  1. if (sequenceLength > i) {}
    should be
    if (sequenceLength >= i) {}

  2. Kristian says:

    Hi Sanchit

    Thank you for noticing. You are absolutely right. It doesn’t mean anything for the code as a such but it tightens the bound just a tad and thus we limit our search.

    I have updated the post and source code to include the change you mentioned.

    Once again, thank you I really appreciate the fix.

    /Kristian

  3. Gideon says:

    hey, thanks for the article. Simple question:

    I’m not clear on your solution/algorithm.

    For 1/7 why and when do you mutiple by 10? And for the fifth calculation, where 6 is the remainder, you don’t divide by 10?

    Also for 1/6 you get into a loop with 40/6 where the remainder is 4, then 4×10 = 40 so 40/6. So do you just stop counting as soon as you see a repeated remainder?

    (I tried not too look\study your code, it kind prevents me from coming up with my own algorithm)

    Thanks
    Gideon

  4. Kristian says:

    Hi Gedion

    For your first question, why I don’t multiply by 10? That was a typo, I should have, and that is fixed now. Thanks for noticing.

    Yes, as soon as I reach a number I have already encountered before I stop. That is the stopping criteria for all the numbers no matter if we reach it after 1 iteration or have to go through a longer cycle.

    /Kristian

  5. Jean-Marie Hachey says:

    Hi Kristian,

    Thanks for your powerful program.

    One problem : the output is not readable as it lasts for a few ms.
    Adding these two lines will enable reading of the results.

    Console.WriteLine(“Problem26″);
    Console.ReadLine();

    By the way, if your program could produce the 982 numbers of the decimal periodic fraction, it would be much appreciated.

    Jean-Marie

  6. Kristian says:

    Hi Jean-Marie

    You are right that it closes right after. Except for the computers I normally use, where the console stays open until I press a key. So I have never bothered to add something like your suggestion to avoid that problem.

    The solution here never actually calculates the fraction, it just calculates the length of it. However if you calculate value/10 where / is integer division you would get the digit I think. So you might be able to make that change your self.

  7. Jean-Marie Hachey says:

    Hi Kristian,

    As a complement to Project Euler, Problem 26

    “Simple” periodic decimal fractions and “mixed” periodic decimal fractions.

    “Simple” periodic decimal fraction:
    Ex.:
    1/7 = 0.142857142857…
    1/7 = 0.(142857)
    (The period starts right after the decimal point).

    “Mixed” periodic decimal fraction:
    Ex.:
    13 / 14 = 0.92857142857142857142 …
    13 / 14 = 0.9(285714)
    (The period does not start right after the decimal point).

    ___

    Inspired by Project Euler, Problem 26 …

    What is the value of d < 1000 for which 1/d contains the longest recurring cycle in its “mixted” decimal fraction part ?

    Thanks for your interest,

    Jean-Marie

  8. Kristian says:

    Thanks for posting a related question like this. I think I will let it remain unanswered by me here for now, but maybe someone else will give it a shot.

  9. Bjarki Ágúst says:

    Hello Jean-Marie.

    As far as I can see, this is exactly the same question. Is there something I’m misunderstanding?

  10. Jean-Marie Hachey says:

    Thank you Kristian and Bjarki Ágúst for your comments.

    I’m just looking at the differences between « simple » and « mixed » periodic decimal fractions.

    ___

    Some comments and questions …

    1) The smallest “simple” periodic decimal fraction: 1/3.
    [1 / 3 = 0.(3)]

    What is the biggest “simple” periodic decimal fraction
    obtained by 1/d (d : natural positive integer), where d <= 100 ?
    Solution to problem 26 shows that it is generated by 1/97.

    With the program written by Kristian (Problem 26),
    the following results were obtained: (For : 1/d, with d <= 100).
    The number with the longest recurring cycle is 97,
    and the cycle length is 96.
    1 / 97 = 0.(01030927835051546391752577
    31958762886597938144329896907216494
    84536082474226804123711340206185567)

    ___

    2) The smallest "mixed" periodic decimal fraction: 1/6.
    [1 / 6 = 0.1(6)]

    The fraction 1/d where d=98 gives the following "mixed" periodic decimal fraction :

    1 / 98 = 0.0(102040816326530612244897959183673469387755)

    (I don’t know if it is the biggest one for the range d<=100).

    Your interest is appreciated,
    Jean-Marie

  11. Jean-Marie Hachey says:

    Note added to the preceding comment :

    For 1/d, where 1 ≤ d ≤ 100

    Longest « mixed » periodic decimal fraction :
    1 / 94 = 0.0(1063829787234042553191489361702127659574468085)

    Number of digits in the period : 46

    ___

    Rem. :
    1 / 98 = 0.0(102040816326530612244897959183673469387755)
    Number of digits in the period : 42

    ___

    Interesting case : (« mixed » periodic decimal fraction) :
    5 digits after the decimal point and before the beginning of the period.
    1 / 96 = 0.01041(6)

  12. Kristian says:

    Out of curiosity. Is 1/96 the fraction with the longest non recurring part? :)

  13. Jean-Marie Hachey says:

    Hi Kristian,

    Re : [Quotient of 1/d where 1 ≤ d ≤ 100].

    Yes, the quotient of 1/d, where d = 96 is the longest string of digits in the non-recurring part of the decimal.

  14. Jean-Marie Hachey says:

    A list of quotients obtained by the division of 1/d, where d = (2^p) x 3
    with 0 ≤ p ≤ 10.

    Simple periodic decimal fraction :
    1 / 3 = 0.(3)

    Mixed periodic decimal fractions :
    1 / 6 = 0.1(6)
    1 / 12 = 0.08(3)
    1 / 24 = 0.041(6)
    1 / 48 = 0.0208(3)
    1 / 96 = 0.01041(6)
    1 / 192 = 0.005208(3)
    1 / 384 = 0.0026041(6)
    1 / 768 = 0.00130208(3)
    1 / 1536 = 0.000651041(6)
    1 / 3072 = 0.0003255208(3)

    (Note the alternance of the period).

  15. Ronnie says:

    Hello, I have noticed that
    except 2 and 5 every prime possess a recurring fraction,

    It can be used on every prime in the reverse direction to get the fastest result,,

    like any number divisible by 7 leaves us with 142857 or one of its permutations

    I’ve done it in the third try number (since I was suspicious, I used a counter…

    997, 991, 983.. here we go

  16. Kristian says:

    Hi Ronnie

    Nice observation. Can you prove that the result must be a prime, or is it “just” an observation?

  17. Ronnie says:

    “just” an observation.. since I am 16.. I could not help further with the mathematical knowledge… but I’m sure one day, I will

  18. Kristian says:

    The reason i put the “just” in quotes, is that I am still pretty impressed by the observation which could be the key to this problem.

  19. nick says:

    In which case may this -> (sequenceLength >= i) happen?

  20. Kristian says:

    In our case it happens at i = 982. Since the cycle length at i=983 is 982.

  21. Aditya says:

    Can anyone tell me the number<10000 which give largest recurring cycle

  22. Kristian says:

    Well, considering how easy it is to change the limit, I will challenge you to figure it out your self :)

  23. Rob says:

    I am curious, how did you know how to solve this one? Is there something easy I am supposed to know here? Thanks for this website! I am definitely learning a lot here.

  24. Michael Aquilina says:

    Thanks for your solution. I was attempting to find patterns in a string to solve this but was never getting anywhere!

    The one thing i would like to ask however is what is the mathematical reasoning behind associating remainders with recurring decimal points? Is there some like you could provide so i could read up on it more?

  25. Kristian says:

    There is no more reasoning than this is the same procedure than I use for long division with pen and paper. And since you are repeating the same operation again and again, using the same input will result the same output. So unfortunately, I am afraid that I don’t have some deep insights into it.

  26. swapnil says:

    i am impressed with the solution …can you plz tell from where u got idea of this ..for many Questions i think why i dint knew that..
    i did some calculation and found that u can also use
    3,5 instead of 10 but not 2,4,8,9,11
    for example
    1%7=1 ; 1%7=1 ;
    5%7=5 ; 3%7=3 ;
    25%7=4 ; 9%7=2 ;
    20%7=6 ; 6%7=6 ;
    30%7=2 ;18%7=4 ;
    10%7=3 ;12%7=5 ;
    15%7=1 ;15%7=1 ;
    and the no are same as for 10(1,5,4,6,2,3) but different order

    i also used 3,5 to calculate for 13 but it doesn’t work :D
    sorry if the comment is misleading :D have fun

  27. Kristian says:

    As I mentioned earlier, I got the idea here from doing long division by hand. How I made that connection I have no clue about. Probably what they call experience :)

    It sounds like you are on to something with primes. And that should tell me something. However, I am uncertain what this should tell me. Maybe I will remember later.

  28. so_what says:

    #where i am wrong please do help i got 998 as d with 996 as recuuring
    #cycle plzz help
    def call(n):
    maximum_r=0
    r=10
    t=1
    f_number=0
    t=1%n

    for i in xrange(1,n):
    #calculate the first number and stor in the varibale maximum_r
    if t>=n:
    break

    if t>=maximum_r:
    maximum_r=t
    t=(t*10)%n
    #print t

    return maximum_r
    def cal():
    d=dict()
    for i in xrange(1,1000):

    d[i]=call(i)
    maxx=0
    index=0

    for i in d:
    if d[i]>=maxx and i>=d[i]:
    maxx=d[i]
    index=i
    print index,maxx

    cal()

  29. Jean-Marie Hachey says:

    Table 1
    Longest recurring decimal fraction and cycle length generated by 1/d; (d<=1000).

    http://img11.hostingpics.net/pics/448499pe26tableone.jpg

    Table 1 shows the divisor(d)generating the longest recurring decimal fraction:
    [1/d, where d<=1000].
    All denominators are primes except 289.
    The period of the quotient is always one unit less than the corresponding divisor with the exception of 289.
    ___

    Sources:
    1) Code of Project Euler – Problem 26
    http://www.mathblog.dk/files/euler/Problem26.cs
    2) Microsoft Visual C# 2010 Express
    3) Microsoft Office Excel (2007)

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.