Problem 26 - Part 2

Hello again.


For the first part of my attempt at solving problem 26 see Problem 26 Part 1.


I could see where my current method was failing me, some of the repeating cycles had a non-repeated chunk of numbers at the start. 1/6 is a good example:


1/6 = 0.166666666.....


So I should treat this as a number with a cycle of 1 but instead no repetition is found and my cycleSize() method overflows some of its numbers and returns 0 when it flows into a number divisible by 6.


I can ignore leading numbers in a similar way to above but I have no way of telling how many numbers I should ignore before giving up. As an example:

1/6 = 0.166666...

10*1/6 = 1.66666...

(10*1/6)*(10-1) = 15

The (10-1) part tells me that there is a cycle of one number and the (10*1/6) tells me that I've ignored one number from the beginning. Here are some more complicated examples to compare:

1/24 = 0.04166666...

1000*1/24 = 41.666666...

(1000*1/24)*(10-1) = 375 (ie. ignore 3 numbers, cycle of 1)

1/420 = 0.00(238095)

100*1/420 = 0.(238095)

(100*1/420)*(1000000-1) = 238095 (ie. ignore 2 numbers, cycle of 6)

So implementable for sure but I have two different numbers to increment now and I don't know before hand which number to increment first. A depth first search of the possible solutions is not going to work (they go on to infinity) so breadth first it is!

A new and improved version of the solution is here:

https://bitbucket.org/WilliamMayor/projecteuler/src/7757ade6a9cf/src/uk/co/williammayor/projecteuler/Problem26.java

And tests can be found here:

https://bitbucket.org/WilliamMayor/projecteuler/src/7757ade6a9cf/test/uk/co/williammayor/projecteuler/Problem26Tests.java

All but one of the tests pass. The failing test reports that 1/49 should have a cycle of 42 but my method says that it's 14. Some digging reveals that the answer 14 was gained when testing 1/49 with 3 ignored numbers and 14 in the cycle. Wolfram Alpha tells me that my method is simply reporting the wrong value. I think that the problem I'm having here is one of overflow again. ((10^3)*(10^14-1)) is a rather large number. To combat this I'm going to have to use BigInteger. This will slow down the arithmetic but should give all correct answers:

https://bitbucket.org/WilliamMayor/projecteuler/src/14cfe7f8a827/src/uk/co/williammayor/projecteuler/Problem26.java

This passes all the tests (good news) and gives the correct answer (good news) but takes 69 seconds (bad news). I know that more efficient methods to solve this problem are out there (I've found some of them) but for tonight I think I'll leave it at that.

If there are other people reading this then let me know if you have ideas or if my explanations are lacking.

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