Problem 26

It's been a long time since my last proper post, my summer became rather busy and the problem I'd picked next became reasonably frustrating. I've got a Sunday afternoon free now so I'm going to explain what I've managed so far and then hopefully finish up and provide a working solution. *fingers crossed*


So problem 26 is: find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.


The examples given on the site are: 

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

So for d <= 10 you can see that d=7 has the longest recurring cycle (6 digits long).


The most immediate problem is the obvious one: 'how on Earth can you find out the length of a recurring cycle?!?!?!?'. The first thing that struck me was that not all fractions have recurring cycles, the non-repeating fractions seemed easy to discover as you could multiply them by 10^n and they would give an integer for some n.


My first draft of the solution used this fact to test for non-recurring cycles. You can see it here:


https://bitbucket.org/WilliamMayor/projecteuler/src/9e6c77530133/Project%20Euler/src/uk/co/williammayor/projecteuler/Problem26.java


DO NOT TRY TO RUN THIS CODE! You'll notice that there's a nasty while(true) statement in there, this draft doesn't solve anything. The while loop's conditional statement needs to be changed to ask 'have we discovered a cycle?'.


In order to answer this problem I broke out some GCSE maths and remembered that you can get the cycle out of the decimal expansion by multiplying by (a^n - 1). The reasoning for 1/3 is easy to understand:


1/3 = 0.333333333333...
10 * 1/3 = 3.333333333333...
(10 * 1/3) - 1/3 = 3.333333333333... - 0.333333333333...
                 = 3
9 * 1/3 = 3


So the next attempt at this solution can be found here:


https://bitbucket.org/WilliamMayor/projecteuler/src/9982c86a3649/src/uk/co/williammayor/projecteuler/Problem26.java


This doesn't give the correct solution but I think it's not a bad first try. I'm going to stop here for some lunch. I'll add another post later (hopefully with correct results!)