The famous hobbyist mathematician Pierre de Fermat had an amusing habit back in his time. He'd make these private breakthroughs about number theory or physics or geometry. Then he'd invent a problem that could be solved with his discovery and tease intelligent friends of his with the challenges. Through this challenge, he engaged in enjoyable communication with researchers while providing edification to his friends/victims. Project Euler (http://projecteuler.net/) is a modern-day Fermat, and to a lover of puzzles it is a highly addictive substance.
Project Euler is composed of a small collection of problems, all of which require some math to solve, and most of which are best-solved with the aid of a programming language. Some patient and skilled solvers use pencil and paper exclusively. Others even use Excel, which some computer scientists might sneer at. In the tradition of the hobbyist mathematician, little previous knowledge is needed to work through the problems. They start out simple and build on each other. Further, each correct answer unlocks a forum thread which provides greater insight from other solvers.
Eponymous
The site's name came from Colin Hughes who used the handle euler and started the project as a sub-section of a forum back in 2001. Now, many years past then, the project has its own site, and several people work together to make new and interesting problems, with one posted about every two weeks.
Exponential Growth
If you have no experience programming before Project Euler, you will quickly become familiar with the concept of exponential growth. Almost all problems give a test case in their description which can lead one into a false sense of early success. For instance, if you are asked to find all numbers under a million with a certain property, the test case might give the answer for all of the numbers under 100.
Many times a naive solution which will provide accurate results for the test case will run quickly, say in 10 seconds. But then, when tested for numbers through 1,000, it takes 100 seconds. And for numbers under 10,000 it takes 1,000 seconds. And then you may start wondering if it's worth over a day for you to get your (hopefully correct) answer. Often this means that you have to think about multiple ways of solving the same problem before you find a solution which is both correct and fast enough.
Ultra-Geeky tangent
Personally, I got drawn into playing with Project Euler by a friend of mine who was bemoaning a difficult problem with a recursive solution. It was running insanely slowly, and he was sure something was wrong with his algorithm, since he was using memoization to reduce the recursive calls. I thought I'd be clever and write the solution using C++ template meta-programming, since memoization is so trivial in that paradigm. Not only that, my program would be a single line of code, and the executable would run in a blink of an eye because it was printing out a constant. All of the calculation time would have already happened during compilation.
For the test case, my solution worked perfectly. But for the actual problem? gcc crashed after two minutes of compiling and told me to submit a bug report. Whoops.
I solved it in Python instead.
Esoteric Language
As with any specialized field, otherwise-rare languages are often over-represented which are particularly well suited to the problem space. For code golf, Golfscript is the king of town. For Project Euler, there's more of a senate of odd-bodies, but the best performing solvers use Frink, PARI/GP, Magma, MUMPS, Mathematica, and J. If you have never heard of most of those, don't worry, neither had I. Frink, PARI/GP, Magma, and Mathematica are all software specifically intended to aid mathematical calculations, so they aren't so surprising.
J, however, is a different beast entirely. It is a functional programming language in the same tradition as APL. And it is worth special mention for the solutions written in it.
The solution forums provide a few cool possibilities. For one, they allow people to expand upon the mathematical theory that underlies the problem, why it was chosen, and so on. Sometimes one might stumble upon these things researching a problem in order to solve it, but there's nothing like the directed insight of someone with a passion for the subject. For another, it is a place for people to post the code they used to solve the problem and to explain what it does. However, in some cases, the explanation is left off.
J programmers, in particular, seem to be fans of making punctuation-dense code which is hard to decipher. Here is an example solution to one problem by solver VrAbi:
+/?,/,/'(!10000;!1000){r*"123456789"~{x@
I would have warned you about spoilers if I had felt there was any risk a casual observer could decipher what was going on in that code.
Although I am vexed to a small degree by those who feel proud enough to display their code, but not generous enough to explain it, I do delight just a little. They are providing the same sort of teasing puzzle that I just solved, wrapped up in that very same problem. Devious.
Easy Mode
As the Project notes itself, there are now solutions out on the web for most Project Euler problems, both code and answers. Part of the intent of having private forums is to prevent someone accidentally spoiling a problem with a Google search, and that's now lost. On the other hand, it's nice that if a problem really has you stumped, you can still learn something by reading through somebody else's thought process to solve it. It does take away part of the fun of the ladderclimb knowing that the rankings are rife with people who didn't do the hard work to get there, but there are always going to people who game an automated system.
Despite the drawbacks of the mystery-destroying aspects of the Internet, searching for theory and background on a problem can result in some fairly neat discoveries. Being able to do research as easily and quickly as writing a program or a proof has fundamentally changed the nature of learning about math.
In one of the many cases of exponential difficulties, I had programmed a correct solution. It worked beautifully for the test case of a few items, but slowed down to a crawl as it progressed. It was, as I calculated, likely to finish only a little while after I perished of old age.
Since this problem was based on finding elements in a series, I took the first 20 items of the series and searched for them in a mathematical database, the On-Line Encyclopedia of Integer Sequences. This gave a result which was exactly the series I needed with references to multiple papers on related subject, but only the first 100 elements. I was already generating that many terms on my own, so it didn't get me any closer to a solution. However, I then read about these subjects on MathWorld, and I used that knowledge to vastly improve my algorithm and solve the problem. A combination of independent analysis and Internet-aided study won the day in a very pleasing evolution.
Epilogue
Although lulled in by the idea of doing a few neat math tricks to show off to my friend, I've continued to solve problems on Project Euler for a number of reasons, and I think they apply to anyone with an interest in solving math puzzles.
- Firstly, it is a great way to learn more about a programming language. Each problem is small enough to not be daunting, but introduces some novelty which often requires using a new facility of the language. Thus far I've solved 85 problems all using Python, a language I did not know at the start of finding Project Euler, and with which I am now surprisingly comfortable.
- Secondly, the problems themselves are intriguing, teaching things about not just mathematics but also programming tricks and optimizations in general. It is simply not possible to solve some of the problems without learning important lessons in algorithms. The problems did start out very easy for me due to some prior experience with similar challenges — I breezed through the first 49 in one day, at which point the site told me to chill out for a while. But almost all interested parties will eventually meet problems with difficulty matching or exceeding their current capabilities.
- Thirdly, it's self-paced. You can race to solve the latest problems for prestige, casually pick out interesting looking items from the middle, or step your way through all 300+, learning along the way. You can pick up any problem at any time with only the time constraints you place on yourself.
- Finally, there is this little bar on the site which slowly fills up as you get correct answers. Mmmmm, experience points.
If any of this sounded intriguing, I'd suggest you give Project Euler a shot. I find it's the most professionally-justifiable entertainment I engage in.