Introduction
Project Euler is one of my favorite ways to occasionally exercise both my puzzle-solving, math, and programming interests. The problems tend to not be sophisticated from a software engineering angle, but the more advanced problems require both mathematical and computer science knowledge. It seems like the more difficult problems tend to be more mathematical.I chose problem 243 because it was in the 200s and many people had solved it. 243 is one of the few problems necessary to get the "Trinary Triumph" badge, along with 1, 3, 9, 27, and 81 (powers of 3).
I'll say this about 243 - I did a lot of work before finiding the quick mathematical solution. I could give a quick write up on the actual solution, but I put in so much work on the solutions that didn't quite work that it would seem like a waste to me to not show the process. The other nice thing? Giving out the actual answer rubs me the wrong way, allowing people who haven't done the work to take credit for doing so. There are other places where you can find the answers, but not here. If you want to cheat, you can easily find the answer elsewhere, and more easily than you'll find here.
The other part of this is my journey into Python. I've only been coding in Python for a few months. I took up Python basically because I hadn't done it before, and I wanted to work in a language that isn't associated with the Microsoft sphere of influence. I worked for Microsoft, so I don't necessarily need more of that.
Part 1 - Brute Force
https://projecteuler.net/problem=243
The first step, usually, is to look at the problem from a brute force angle. For Project Euler, I prefer problems that cannot be solved by the brute force approach within anywhere near a reasonable amount of time. Since the problems are supposed to be solvable within a minute, I consider the problem too easy if brute force can solve it even within an hour. Fortunately, Project Euler rarely makes the problems that easy.
Anyway, brute force is pretty much always worth trying. It gives a way to check the more sophisticated algorithm, and often lets me wrap my head around the problem, so my brain can think of other ways to solve it.
We are looking for irreduceable fractions. On an individual fraction basis, that seems pretty easy to do manually: Just find out if the numerator and denominator have any common factors. If they do, the fraction can be reduced.
Python has a greast common denominator function, gcd, which makes a brute force solution easy.
The basic brute force solution is:
Starting from d=2.
Find the resilience of d.
If it is less than 15499/94744, we have the solution.
What is the resilience R(d) of a number?
Take all the numbers from 1 to d-1.
Determine which of those numbers has a gcd with d == 1, the count of those over d-1 is the resilience.
def R(d):
resilient_numerator = 0
for i in range(1,d):
if gcd(i,d) == 1:
resilient_numerator += 1
return Fraction(resilient_numerator,d-1)
That bit of code correctly returns the value expected for d=12 given in the example, 4/11. So we'll consider that good for now.
Running R(d) through a range of denominators, I didn't get one less than 15499/94744 within a minute. Or two. Or three.
That was the first attempt, and it was no surprise it failed. I didn't even know how close it was.
Part 2 - How close
Next I wanted to see how close I was actually getting.
def brute_lowest_resilience(maxint):
best = Fraction(1,1)
for i in range(2,maxint):
current = R(i)
if current < best:
print "New lowest!", i, current, float(current)
best = current
return best
The goal is 15499/94744, which is around 0.163588.
So I ran my brute_lowest_resilience to 100000.
Even after a few minutes, the best result was far above the goal, creeping more slowly towards it as time went on.
Here's the output after a few minutes:
New lowest! 4 2/3 0.666666666667
New lowest! 6 2/5 0.4
New lowest! 12 4/11 0.363636363636
New lowest! 18 6/17 0.352941176471
New lowest! 24 8/23 0.347826086957
New lowest! 30 8/29 0.275862068966
New lowest! 60 16/59 0.271186440678
New lowest! 90 24/89 0.269662921348
New lowest! 120 32/119 0.268907563025
New lowest! 150 40/149 0.268456375839
New lowest! 180 48/179 0.268156424581
New lowest! 210 48/209 0.22966507177
New lowest! 420 96/419 0.229116945107
New lowest! 630 144/629 0.22893481717
New lowest! 840 192/839 0.22884386174
New lowest! 1050 240/1049 0.228789323165
New lowest! 1260 288/1259 0.228752978554
New lowest! 1470 336/1469 0.228727025187
New lowest! 1680 384/1679 0.228707564026
New lowest! 1890 432/1889 0.228692429857
New lowest! 2100 480/2099 0.228680323964
New lowest! 2310 480/2309 0.207882200087
New lowest! 4620 960/4619 0.207837194198
New lowest! 6930 1440/6929 0.207822196565
New lowest! 9240 1920/9239 0.20781469856
New lowest! 11550 2400/11549 0.207810200017
New lowest! 13860 2880/13859 0.207807201097
New lowest! 16170 3360/16169 0.207805059064
New lowest! 18480 3840/18479 0.207803452568
New lowest! 20790 4320/20789 0.207802203088
New lowest! 23100 4800/23099 0.207801203515
New lowest! 25410 5280/25409 0.20780038569
New lowest! 27720 5760/27719 0.207799704174
New lowest! 30030 5760/30029 0.19181457924
One of the first things I noticed was a sort of pattern. 6, 12, 18, 24, 30 - multiples of 6. Then multiples of 30 - 30, 60, 90, 120, 150, 180, 210. Then multiples of 210. And so on.
If you take a look at where the pattern made its biggest changes: 6, 30, 210, 2310...
You can see:
6 * 5 = 30
30 * 7 = 210
210 * 11 = 2310
The pattern changes when it is a multiple of the next prime.
So, with the information I have now, I can try to find a solution. At least, I can try narrowing down where I'll find the answer.
2*3*5*7*11*13*17*19 = 9699690
R(9699690) = 1658880/9699689
And that's around 17.1024
And that took around 16 seconds.
So, as it stands, this path will not get me to an answer in under a minute. It does get me closer to the answer, and it does give me a better idea of just how large the answer is.
9699690 * 23 = 223092870
R(223092870) = ?
I get a MemoryError when I try to run that.
So I have two problems here.
First, the algorithm is too slow.
Second, it can't handle large enough numbers.
Next time: MemoryErrors, for loops, the Sieve of Eratosthenes!
This is awesome!
ReplyDelete