Project Euler

Portrait of Leonhard Euler (1707-1783)

Fun and challenging problems

I've been working my way through these Project Euler exercises since September 2012. From what I gather, these problems originally spawned off of a thread on mathschallenge.net in 2001 and moved to a seperate domain in 2006. The gist of these tasks is that a problem is presented that requires the derivation of some mathematical truth (such as the number of twin primes below some value or the last 10 digits of !1000). All of the tasks are meant to be performed by algorithms implemented on a modern computer in under one minute.

For instance, the latest problem that I have solved is number fifty. It asks for the prime number less than 1,000,000 which is the sum of the largest chain of consecutive primes.

-----------------------------------------------------------------

Problem 50

The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

----------------------------------------------------------------

I like working through these problems as they challenge my quantitative reasoning skills and expose me to a diverse set of topics in math that I would be unlikely to come across otherwise. Further, the goal of keeping the solution time under a minute (usually I have been shooting for under 20s) requires me to explore optimization techniques; this requires investigation into the relationships governing the task at hand and a little bit of creativity and research. The most useful method that I have developed is to generate a list of all possible values and sieve out large chunks of those values based on some criteria. This can be less computationally expensive than stepping through a list and generating values at each step. My first introduction to this method was the Sieve of Eratosthenes which is the most efficient algorithm for generating all primes below a given number.

Another benefit of these exercises is that they have broadened my scope of solution methods while also developing my problem solving philosophy. I've learned to start by structuring my algorithm so that it scales easily to general maximum values and, if a maximum value isn't given, derive one using the information provided. I have learned to view these algorithms simply as glorified searches; since they are framed in terms of integers, there is always a way of determining a finite range of possible values. From there it is possible to reason as to which method to use: elimination , generation, or both. Elimination means that some criteria is determined that will indicate whether or not a value belongs in the solution set and that criteria is evaluated on every value in the candidate set. Generation means that you determine some criteria that must be exhibited by the solution set. Starting with an empty set, you step through some sequence of numbers and generate the set of solutions from those numbers. Whichever of these methods is the least expensive to compute - taking into account the number of times it must be computed - is the method that should be employed first.

Most of the problems on Project Euler are introduced with an example of the property that is to be investigated. The example is typically some computationally simple subset of the total problem. For example, in problem 50 above, the largest chain of primes that sums to a prime under one hundred is given. The first thing to do is solve this easier problem and check against the solution given in the problem as a sanity check.

Good for strengthening my skills with Octave/Matlab vectorization

One thing that I am doing that differs a little bit from my fellow problem solvers is that I'm using GNU Octave as my programming language. After solving a problem, a forum link becomes active which allows the solver to post their algorithm and discuss their methods. I rarely see GNU Octave or Matlab as programming languages on that forum (mostly because they aren't well suited to the task). This requires me to take advantage of the unique vector data structure that Octave utilizes. One consequence of Octave's matrix manipulation power is that its elementary operations take longer than most other languages; consequently, coding schemes that are based on very long or frequent "for" loops tend to be slow. Taking advantage of Octave's data structure is a technique called vectorization and it can require some unconventional and abstract thinking to translate a code from a loop format to a vectorized format. The process is more tedious (and likely unnecessarily so) but my purpose has been to grow from the experience rather than solving the problems.