Tue, 08/04/2014 - 13:43 — asger

If you have looked at my book log recently, you may have noticed a drastic drop in the number of books I have been reading starting mid-2012. There are two reasons for this, one of them being Project Euler.

Project Euler is a math/programming puzzle web site. I can't remember where I read about it first — perhaps it was in an article on Slashdot? (Edit: Actually, yes, I think it was in this article — which also nails down the date I joined Project Euler: The 3rd of October 2012.) Anyway, the idea is this: Every weekend (more or less) a new problem is published. The problem is usually mathematical in nature, but almost always requires some programming to solve. When you have found the correct answer to the problem (most of the time in the form of a number), you submit it to the site and gain access to a forum where you can discuss the problem and the solution.

I have always been interested in math and programming, so I got hooked right away. At first it was easy: The early problems are simple, and even if you can't find the best algorithm, you can just brute-force the result and gain access to the problem forum, where you can read about better ways to solve the puzzle. For the later problems, this is rarely possible. You must find a good algorithm, or forever stay locked out of the forum, which can be very frustrating if you just *must* know how to solve a particular puzzle.

The first problem where I got stuck was problem 143: "Investigating the Torricelli point of a triangle". I never really appreciated geometry — I have always been of the opinion that geometry problems can be reduced to algebra/calculus problems (which may or may not be true, but I acknowledge that some problems are easier to solve using geometry), so geometry never interested me. At first, I skipped many of the geometry problems at Project Euler, but at some point I revisited them and noticed that they were all just hidden algebra / number theory problems, which I find much more interesting. This is a general theme in the puzzles; the problem as described is often a "cover" for an underlying problem — usually in number theory or combinatorics, two of my favorite subjects in mathematics.

I have been stuck in many other problems, but when I return to a problem that I have not thought about for a while, I often find that I can look at it in a new way, and get new ideas for how to proceed.

I have learned a lot from the puzzles; I have learned about new data structures, new algorithms, new math. Either by figuring it out myself, or by reading about it on the net — researching a problem online is encouraged, as long as you don't just copy a solution found elsewhere. Some of the methods/subjects that I have discovered (or rediscovered) in my research for the puzzles are:

- The Euler phi function (of course)
- The Möbius function and the Möbius inversion formula
- Pythagorean triples
- Fast matrix exponentiation
- The inclusion-exclusion principle
- Parametrization of Diophantine equations
- Finite State Machines
- Game theory / Nimbers / The Sprague–Grundy theorem
- The Union-Find data structure
- Fenwick trees
- The Hook length formula

Apart from the problems themselves, which in my opinion have very interesting subjects and just the right level of difficulty, there are other things about the site that I like: The fact that you have to find the answer for yourself — there are no hints, and the correct answer is never published — you can't give in to temptation and look up the solution. [This is not entirely true; the problem answers have been posted on other sites, but that is against the rules of Project Euler, and using these solutions is considered cheating. In fact, discussing the solution of a problem outside the problem forum is considered against the rules.] Also, you can skip a problem and get back to it later, when you get a new idea; the problems never expire. I like the fact that new problems are published so often; there is always a new problem to ponder every weekend.

To make solving puzzles more game-like, Project Euler also has achievements such as "Solve 100 consecutive problems" or "Be among the first 10 to solve a problem", and a level system. If you are among the first 50 to solve a problem, you get points for the Eulerians list — a way to rank the "players" based on how fast they are to solve the problems. There are also statistics by country or by programming language.

I can't tell you how much time I have spent on Project Euler in total, but it's measured in weeks rather than hours. Why spend money on books and movies when you can get literally weeks of entertainment for free? I realize that Project Euler is not what everybody would call entertainment, but for me it's better than movies. Even though I work as a programmer, I don't get many assignments that challenge me in the way that the puzzles of Project Euler do, so I guess it's also a way of keeping my math skills sharp.

If you want to discuss Project Euler or just math, you can contact me at Project Euler (my user name is of course *asgerix*) or use the contact form of my web site. Just don't ask for hints or answers to problems you haven't solved — I won't answer that kind of requests.

Oh, and in case you are wondering: The other reason — and probably the main one — for the drop in the number of books I have been reading is that I met my girlfriend (Edit: She is now my wife, since the 4th of July 2015) in June 2012.

- Login to post comments