Sunday, June 15, 2014

Project Euler hacked

Why anyone would want to pick on a non-profit nichey math puzzle site is beyond me...


Tuesday, June 10, 2014

Project Euler

I spent a lot of time being frustrated with Problem 472 . It seems like a problem that should admit to a nice closed form solution but solving it ended up being a (fun) pattern matching exercise.

The main thing to realize is that you are asked to sum the function $f$ over $10^{12}$ terms, but there is really no way to do that in under 1 minute of execution time. (Of course, I did not realize this until I had spent a great deal of time devising efficient algorithms for evaluating $f$ at a single value.)
You have to group the terms and add over the groups. One way yields about $\log N$ terms, which
brings the execution time down to < 0.1s.

It's all about pattern matching -- I guess....hacking + math = project euler

Saturday, May 24, 2014

Paul Otlet, a great man way before his time





Thoughts on Project Euler

Project Euler describes itself as a
I've worked my through about 150 of the approximately 500 problems over the last few months, and it's been a lot of fun!

The obvious difference between these problems and the brainteasers is that you are required to use some math (not advanced math, but math nonetheless). You end up looking up cool stuff on the wikipedia. A problem on prime numbers may have you reacquainting yourself with the Sieve of Eratosthenes  as a fast way of generating prime numbers, and delving into the details of the Miller Rabin Primality Test for the first time. When I say "delving into the details" what I really mean  is that you learn enough to be able to implement it in code. This isn't super deep but deeper than most of us would go if weren't focused on solving a concrete problem.

The problems that I like best follow a specific pattern: the setting involves a game or a process that can be easily simulated in a few lines of code. One is asked to compute some function, which again can be easily coded. But the kicker is that one has to provide the answer to the function for some gargantuan input like \(10^{12}\) and the nifty lines of code one has written so far would have to run for eternity to arrive at the answer. It is the process of rethinking one's approach so that the answer is computable in about a minute's worth of running time is what is most fun and rewarding about Project Euler.

An example of this (and one that I would rate as moderately hard on the "Euler Scale") is Problem 469, which concerns itself with knights sitting around a table. We have a round table with $n$ seats and Knights enter the room sequentially. The first knight picks any chair and blocks the seats to his immediate left and right. Then the next knight enters and picks one of the available seats uniformly at random. This goes on until a Knight cannot be seated. The question concerns the average fraction of seats that remain empty. Now for a small value of $n$ (say $1000$), this is not hard to compute. One simulates the  knight seating process and estimates the average. But the problem asks to compute the answer for $10^{18}$ and it wants the answer to be correct to many significant digits. Well, what to do now? That is the typical kind of dilemma I face when attempting Euler problems.

When you do solve a problem correctly you get access to a terrific forum in which people post their code. I am constantly amazed at the range of approaches people from all over the world use in their solutions.

Bottom line, start solving these problems if you like math, brainteasers and have a basic knowledge of programming. You will lean a lot and have fun doing it!