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