Matt's Blog

What I learned solving 70+ Project Euler problems

January 23rd, 2020 - 11 min read

Project Euler Badge

Project Euler is a website dedicated to mathematical/computational problems intended to be solved by computer programs. Today I just submitted my 70th correct answer, which places me near the top 2% out of nearly 1,000,000 users by number of problems solved.

In this post I will share some of my most and least favorite problems, what I learned through solving them, how my solutions compare to the solutions of others, and what makes certain programming languages well suited for solving these kinds of problems.

What makes a Project Euler problem?

The typical problem on Project Euler usually involves number theory. This usually means searching a large number range for numbers that meet certain criteria. The size of the search space usually makes brute force solutions very time consuming or difficult, but not impossible. A slow brute force solution often encourages (and sometimes demands) creativity in order to solve the problem in a reasonable amount of time.

For the simplest example, let’s take a look at Problem 1:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

In order to solve Problem 1, we have to check each number between 1 and 1000, determine if it is evenly divisible by 3 or 5, and if so, add it to our total. Of course the solution to this problem is easy, and it can be solved in one line of Python code:

print(sum(filter(lambda x: x % 5 == 0 or x % 3 == 0, range(1000))))

As we can see, problem 1 is simple enough to be brute forced in milliseconds. However, not all problems are this straightforward.

Cubic Permutations

Let’s take a look at one of my favorite problems, Problem 62:

The cube, 41063625 (345^3), can be permuted to produce two other cubes: 56623104 (384^3) and 66430125 (405^3). In fact, 41063625 is the smallest cube which has exactly three permutations of its digits which are also cube.

Find the smallest cube for which exactly five permutations of its digits are cube.

If this problem interests you, you should solve it on your own before continuing.

Typically whenever I solve a new problem, I try to implement the most naive brute-force solution that first comes to my mind and see how it does. On my first attempt, I usually rush to get something working. If the first attempt doesn’t solve it reasonably fast, it at least gives me an idea as to how difficult of a problem it is.

Attempt 1

On my first try, I put the first 1000 cubes in a list. Then I iterated from 125 to 1000 (can’t remember why I chose this range), testing the permutations of each cube. If any one of the permutations was found in the list, I increment the cube counter. Once it hits 5, I break.

from itertools import permutations

def cube(n):
    total = 1
    for i in range(0, 3):
        total = total * n
    return total

def problem62():
    cubes = []
    for i in range(0, int(1000)):
        cubes.append(str(cube(i)))

    for i in range(125, 1000):
        print(i)
        n = cube(i)
        perms = permutations(str(n))
        numCubes = 0
        for p in perms:
            s = ''.join(p)
            if s in cubes:
                numCubes += 1
        if numCubes == 5:
            break
    print(i)

This approach was very slow, and was only able to search about ~400 cubes in 11 minutes without an answer. This is also under the assumption that the answer could be found within the first 1000 cubes. If the answer was over i=1000, this algorithm would explode… This tells me that I need to take a different approach:

Attempt 2

This time around I didn’t store a list of cubes to search through. Continually searching through a large list is costly and can slow things to a crawl. Now I take every number, cube it, and for each permutation I use math to see if it’s a cubed number instead of looking the permutation up in a list of cubes.

from itertools import permutations
import math

def cube(n):
    return int(math.pow(n, 3))

def isCube(n):
    if n <= 1:
        return False
    return n == cube(round(n ** (1 / 3)))

def problem62():
    i = 2
    while True:
        print(i)
        n = cube(i)
        perms = list(filter(isCube, set(map(lambda x: int(''.join(x)), permutations(str(n))))))
        if len(perms) >= 5:
            lens = list(filter(lambda x: len(str(x)) == len(str(n)), perms))
            if len(lens) == 5:
                print(i, lens)
                break
        i += 1

This ended up being quite faster than my first attempt. The second attempt processed ~400 numbers in about 11 seconds, as opposed to 11 minutes. I felt more confident in this one. However, as the numbers grew, the program slowed again. After waiting nearly 2 hours, my program was only at i=2200 without an answer. Even though this seemed faster, it wasn’t good enough. It was time to go back to the drawing board for a third time.

Attempt 3

At this point it was clear that any kind of brute force search or calculations of permutations was going to take too long. There had to be a clever way. Then the lightbulb went off in my head. If two numbers are permutations of each other, they must have the same amount and number of individual digits. If I treat the cube as a string and sort the individual numbers, that result could be used as a key in a dictionary. Effectively, I could have a dictionary which holds lists of numbers which are indexed by their sorted cube hash. When a list reaches 5 elements, that is the list that we care about.

def cube(n):
    return n ** 3

def toKey(n):
    return ''.join(sorted(str(n)))

def problem62():
    cubes = {}
    i = 1
    while True:
        key = toKey(cube(i))
        perms = cubes.get(key)
        if perms == None:
            cubes[key] = [i]
        else:
            cubes[key].append(i)
            if len(cubes[key]) == 5:
                print(min(map(cube, cubes[key])))
                break
        i += 1

The results were amazing! The correct answer is found in 30 milliseconds! Not only is the answer found so quickly, but the code is much simpler. We also don’t have to import anything or create permutations of numbers.

One of the best things that Project Euler offers is this “eureka” moment that you get when figuring out a clever solution to a problem.

A Comparison of Languages

I originally started working on these problems as a way to learn Common Lisp, Clojure, and functional programming. However, as time went on, I found it more fun to see how elegantly I could solve the problems with a language I felt more comfortable with. I began using Python to solve the problems. I also wrote a handy little wrapper script which can run any problem simply by calling python run.py [problem number]. This script would execute the problem and return the amount of time taken for it to run, or the amount of time taken if exited prematurely. This script was very nice for quickly running code and having performance feedback, as well as keeping timing code separated from the actual problem code.

Python proved to be the real winner for these kinds of problems. The ability to take an imperative approach when needed, effortlessly print anything from any part of the code for debugging, batteries-included support for big numbers, decimals, fractions, etc. as well as being a dynamic language made transformations of numbers between datatypes a breeze. No other language comes close to this simplicity. With Python I spent 99% of my time working on the actual problem, not fighting against the language.

Clojure is worth mentioning as well. I found that the Clojure code I wrote ended up being prettier and easier to follow than some of the other submissions. For example, this is my solution to Problem 23:

(defn divisors [n]
  (if (= n 1)
    []
    (filter #(= 0 (rem n %)) (range 1 n))))

(defn is-abundant [n] (< n (reduce + (divisors n))))

(def abundants (set (filter is-abundant (range 1 28123))))

(defn is-non-abundant-sum [n]
  (not-any? #(contains? abundants (- n %)) abundants))

(defn problem23 [] (reduce + (filter is-non-abundant-sum (range 1 28123))))

Only 9 lines of code to find the answer in 12 seconds. Compare this to an average C++ solution found in the solution thread. One is easier to read and understand than the other:

int main()
{
    int n=28123;
    long long int sum1=0;
     int arr[7000]={0},a=0;
    for(int i=1;i<=n;i++)
    {
        int sum=0;
        for(int j=1;j<i;j++)
        {
            if(i%j==0)
            {
                sum=sum+j;
            }
        }
        if(sum>i)
        {
            arr[a]=i;
            a++;
        }
    }
    int arr1[28123]={0};
    int sum=0;
    for(int i=0;i<a;i++)
    {
        for(int j=i;j<a;j++)
        {
            if((arr[i]+arr[j])<=n)
            {
                sum=arr[i]+arr[j];
                arr1∑++;
            }
            else
                break;
        }
    }
    sum=0;
    for(int i=0;i<=n;i++)
    {
        if(arr1[i]==0)
            sum=sum+i;
    }
        printf("%d",sum);
}

However Clojure is far from perfect. After using it for a handful of problems I am somewhat indifferent to it. The long REPL load times, the obnoxiously verbose, cryptic, and unhelpful stack trace/error messages, and the foul stench of the Java ecosystem underneath it was enough to turn me off from the language.

Conclusion

After solving 70 problems, I’ve learned the following:

Overall, the site offers good mathematically inclined challenges that push you to think about the problem and write better code.