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.21/6

=0.1(6)1/7

=0.(142857)1/8

=0.1251/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 ofd< 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?

if (sequenceLength > i) {}

should be

if (sequenceLength >= i) {}

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

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

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

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

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.

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

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.

Hello Jean-Marie.

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

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

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)

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

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.

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

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

Hi Ronnie

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

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

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.

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

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

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

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

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.

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?

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.

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

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.

#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()

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)

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.

Thanks,

Jon

Very nice idea. Thanks for sharing.

Should not the solution be 983 (not 982)? I’ve checked the solution also in http://projecteuler.net/problem=26

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;

i--;

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

}

}

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

end

remainders.length

end

`def find_longest_cycle(limit)`

max = 0

limit.downto(1) do |n|

break if n < max

max = [max, cycle_length(n)].max

end

max

end