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:


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) {

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

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

    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?

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


  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)


  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.


  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.


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


  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:
    1/7 = 0.142857142857…
    1/7 = 0.(142857)
    (The period starts right after the decimal point).

    “Mixed” periodic decimal fraction:
    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,


  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


    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,

  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 😀
    sorry if the comment is misleading 😀 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):

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

    if t>=maximum_r:
    #print t

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


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


  29. Jean-Marie Hachey says:

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

    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.

    1) Code of Project Euler – Problem 26
    2) Microsoft Visual C# 2010 Express
    3) Microsoft Office Excel (2007)

  30. Jon Carifio says:

    Hi Kristian,

    I came across your solution and like it a lot. I think I can add a bit more insight into where your method with multiplying by 10 and taking remainders comes from.

    As an example, take the decimal 0.abcdefabcdef… This can be written as abcdef/999999. This is true for a simple repeating decimal of any length, so 0.123123… = 123/999, 0.121212… = 12/99, etc (the number of digits in the denominator matches the number in the numerator). Also note that 999…999 = 10^n – 1, where n is the number of nines.

    So, for a simple repeating decimal, you want to find the smallest n > 0 such that the decimal can be written as a fraction with denominator 10^n – 1. We’re looking at fractions 1/d, so this becomes finding the smallest n > 0 such that there exists x with 1/d = x/(10^n – 1), or with xd = 10^n – 1. Reducing modulo d, this becomes 0 == 10^n – 1 (mod d), or 10^n == 1 (mod d). This is exactly what you had above where you found the cycle length n by counting how many times you had to multiply by 10 to get a remainder of 1 (aka equal to 1 modulo the denominator).

    Any mixed repeating decimal can be obtained by dividing a simple one by some power of ten then adding a terminating decimal with the right number of decimal places, so the same idea essentially applies. Multiply the mixed decimal by the correct power of ten to get a simple one, then apply the same concept. This new number is just some power of 10 times the original one, so it will have the same recurring cycle of digits.


  31. Mag says:

    Very nice idea. Thanks for sharing.
    Should not the solution be 983 (not 982)? I’ve checked the solution also in

  32. JB says:

    According to Wikipedia A fraction in lowest terms with a prime denominator other than 2 or 5 (i.e. coprime to 10) always produces a repeating decimal. The length of the repetend (period of the repeating decimal) of 1/p is equal to the order of 10 modulo p. If 10 is a primitive root modulo p, the repetend length is equal to p − 1; if not, the repetend length is a factor of p − 1.

    Armed with this information, the solution that I implemented is to get a list of primes below 1000. Starting with the largest prime, iterate through searching for a prime p such that 10 is a primitive root of p.

    Below is the C# class I wrote with the necessary methods.
    public class NumberTheory {
    // return true if s is a primitve root mod n, false otherwise
    public static bool PrimitiveRoot(long a, long n) {
    if (GCD((int)a, (int)n) != 1) return false;
    int s = Totient((int)n);
    List pf = FactorTools.PrimeFactor(s);
    foreach (long f in pf) {
    BigInteger ba = new BigInteger(a);
    ba = BigInteger.Pow(ba, (int)(s/f));
    if (ba % n == 1) return false;
    return true;

    // returns Euler's Totient of n
    public static int Totient(int n) {
    Listprimes = Primes.PrimesList(n + 1);
    int numPrimes = primes.Count;

    int totient = n;
    int currentNum = n, temp, p, prevP = 0;
    for (int i = 0; i currentNum) break;
    temp = currentNum / p;
    if (temp * p == currentNum)
    currentNum = temp;
    if (prevP != p) { prevP = p; totient -= (totient / p); }
    return totient;

    // returns Greatest Common Divisor of a and b
    public static int GCD(int a, int b) {
    return b == 0 ? a : GCD(b, a % b);

  33. Sunny says:

    I haven’t been able to determine if the longest cycle will always occur with a prime less than ‘d,’ but I do find it interesting that an overwhelming number of primes have cycles of either n – 1 or (n – 1)/2. Just an observation, and I apologize if someone above already beat me to it. And to Mag above, if you read this, the number that produces the longest cycle is 983. The length of that cycle is 982. Also, here’s my code in Ruby if anyone’s interested:

    def cycle_length(n)
    remainders, remainder = [], 1
    loop do
    remainder %= n
    break if remainders.include? remainder
    remainders << remainder
    remainder *= 10

    def find_longest_cycle(limit)
    max = 0
    limit.downto(1) do |n|
    break if n < max
    max = [max, cycle_length(n)].max

  34. bharath says:

    U stop when you find the first number repeated again. ‘that means 1/23 is 0.04347826086956521739130434782608

    instead of having sequence as 0434782608695652173913 your algorithm would stop at 04347826 as you would get zero repeated.

    Correct me if i have reported wrong

  35. aa1992 says:

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

    it should be if (position – foundRemainders[value] > sequenceLength&&value>0) {
    sequenceLength = position – foundRemainders[value];
    so that we can ignore numbers who donot have any recurrence.

  36. SzechuanSage says:

    First of all, my solution only focused on primes.

    The reptend for the reciprocal 1/d has a length that is either Euler’s totient quotient for d (which is d-1) or is a factor of (d-1).

    Second, I like the algorithm of multiplying by 10 and dividing by d. It is, after all, how I was taught long division at school. If you are only looking at primes then you don’t have to store each remainder since you will always get back to 1 eventually.

    Third, finding the reptend length for non-primes can also be done by multiplying together the reptend lengths for the prime factors of the non-prime.

  37. Pippo says:

    I can see observe that the length L of the cycle if 1/d is always such that L <= d-1 . Do you have a proof for this property?

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=""> <s> <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.

This site uses cookies.