Project Euler problem 26
February 25th, 2009 at 8:41 pmProblem 26 is another problem from Project Euler with a very cool solution. I suppose it can be solved by sheer brute-force, but it will take long and won’t be elegant.
After some manual experimentation with long division on paper and then with a calculator it becomes clear that some things are very systematic here.
There are 3 kinds of rational numbers:
- Expansion is finite (for instance 1/4 = 0.25): those are numbers of the form
- Expansion is repetitive, from the start (like 1/7 = 0.(142857)). This is for numbers co-prime to 10.
- Expansion is repetitive, after some initial non-repetitive section. This is for numbers that have both factors co-prime to 10 and are divisible by 2 or 5. (for example 1/14 = 0.07(142857))
To find the longest cycle it’s sufficient to look just at the primes – because other numbers will just have the same cycles after some initial non-repetitive section.
But how do you find the length of the cycle efficiently? This is where number theory comes in! This page contains a lot of very interesting information about this problem.
Eventually, it all boils down to the multiplicative order of the denominator.
We have to solve the discrete logarithm:
k is the cycle length for n, for numbers co-prime to 10. The discrete logarithm is a difficult problem, but fortunately the numbers we’re dealing here are small.
It took my Python script about one-tenth of a second to find the answer using this method.
Related posts:
February 26th, 2009 at 01:07
That’s way over my head
I used a regexp.
February 26th, 2009 at 03:04
Interesting post. Knowing some mathematics can help generate a fast algorithm, but it’s not really needed for this question.
“I suppose it can be solved by sheer brute-force, but it will take long and won’t be elegant.” I disagree, my Python program solved it in just 2.5 secs and was quite elegant (I thought).
For Euler problems I nearly always use brute force first, and look at the mathematics only when brute force proves to be much too inefficient. Doing it the other way round is “premature optimization” in my opinion.
February 26th, 2009 at 08:20
@Steve,
Can you send me the code you’ve used for brute-forcing or post it in some pastebin? I’m curious to see how you do it.
I agree about premature optimization, but having solved dozens of problems already, I know for sure that mathematical methods are much more gratifying and fun than brute-force
February 26th, 2009 at 12:34
Totally brute force, yet took no time at all to run.
http://pastebin.com/f1efaf62d
February 26th, 2009 at 19:42
@Ron,
I liked your clever detection of a cycle in the decimal expansion by remembering the next term in long division. This is not totally brute-force, then. That would be going over the decimal expansion digits, looking for cycles, not in “real-time” while dividing.
February 27th, 2009 at 22:56
I’ve been working through Project Euler in Oz (see CTM wiki). I made a function for problem 26 (spoiler alert) that does something similar – though if you’re not familiar with Oz it may be hard to read.
July 3rd, 2009 at 18:15
I loved your solution to this problem. It’s extremely elegant compared to simple bruteforce recurring pattern matching in the decimal expension of the rational number. The article at mathworld.wolfram.com was extremely helpful to understand the concepts at work.
Combining math and programming to solve these issues are a huge thrill.
August 15th, 2009 at 15:17
I solved this problem using Brent’s algorithm, a modification of the tortoise and the hare algorithm for cycle detection. It ran in about 8 ms in c#.
http://en.wikipedia.org/wiki/Cycle_detection
Here’s the code:
http://pastebin.com/f4ef59a5e