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

U Can Has Teh Code Nao

I hadn't thought to pass out the URL to the repository that I'm keeping my Project Euler code in. Seems like a good idea if people are interested, so here it is:

https://bitbucket.org/WilliamMayor/projecteuler

It's a Mercurial repo so you'll need to get hg installed if you don't have it already but instructions are given on bitbucket so clone away.

Problem 1

Okay, so to start of I'd thought I'd go from the beginning and try my luck with problem 1:


What is the sum of all the multiples of 3 or 5 below 1000.


This one seems pretty easy and coming up with a solution didn't take me too long at all, my first attempt was simply to do this:

sum = 0
for every number between 1 and 1000
    if the number is a multiple of 5 or 3
        sum += number


This definitely works as the answer it spews out was enough for me to get my first tick on the Project Euler site. Exciting. I went to bed happy.


I began to think over the next day that the point of the challenge was not to simply solve the problem but to really think about it and come up with the 'best' solution. I became convinced on my train ride home that what I had didn't cut the mustard and I had a plan to help me improve. I would time the execution of my solution and then try to best my time.


One small problem was that the solution takes 0.0 milliseconds when timed with System.currentTimeMillis() (I'm a Java guy). Rather than play around with using smaller and smaller units I decided to up the range of the problem until the 'old' solution took a decent chunk of time. So I rephrased the question to be:


What is the sum of all the multiples of 3 or 5 below Integer.MAX_VALUE (2 147 483 647)


Solving this took ~9.5 seconds and gave the answer -787410670 (*giggle*, integer overflow). Now I just had to improve the solution.


The most striking problem is that I run a maximum of 3 comparisons for every integer (one for the for loop and two for the multiplicity checks) and that the comparisons aren't trivial (modulo arithmetic FTW). This problem has a decent solution in that I can generate the required numbers rather than check every number to see if it matches:


fivemultiple = 5
threemultiple = 3
sum = 0
while fivemultiple < MAX
    sum += fivemultiple
    fivemultiple += 5
while threemultiple < MAX
    repeat 4 times
        sum += threemultiple
        threemultiple += 3
    threemultiple += 3


The repeat 4 times hassle at the end is to counter the fact that I now generate numbers that are multiples of both 3 and 5 twice.


Solution two solves the new problem in a modest ~0.95 seconds, a tenth of the original.


I had a facepalm moment when I realised that I could shave off more time by generating the three multiples first then the fives (now I only repeat the fiddly bit twice).


Solution three solves the new problem in ~0.39 seconds that's less than one twentieth of the original solution's time.


I'm going to read the forums soon to see how I could improve on this. For the second evening in a row though, I'm going to bed happy.

Intro

Hello

My name is William Mayor (Billy), I'm a UCL student currently in between courses; I've just finished a BSc in Computer Science, results pending.

In order to sharpen my programming and maths skills (and to have fun), I'm participating in the GDC's "12 Problems in 12 Weeks" Project Euler Challenge.

This blog will chronicle my rise to fame and power via the sucessful completion of the problems. Wish me luck.