Project Euler solutions

Introduction

I solve Project Euler problems to practice and extend my math and program­ming skills, all while having fun at the same time. Here I make my solutions publicly available for other enthusiasts to learn from and to critique. This page lists all of my Project Euler solution code, along with other helpful information like bench­mark timings and my overall thoughts on the nature of math and programming in Project Euler.

Each problem that I solved always includes a Java program. Almost all my solved problems also include a Python program (except for a few). Many problems additionally have a Mathematica and Haskell program. Numerous solutions contain a detailed mathematical proof to justify why the imple­mented algorithm is correct. Among the web, this is perhaps the largest collection of Project Euler solutions in the Java programming language. All my code is original work, not based on anyone else’s code, although a couple of times I obtained the high-level approach from reading various literature on the web.

Contents

• Introduction
• Solution code
• Language usage
• Benchmark timings
• More info

Solution code

Git repositories

Web host	Browse files	Download package	Numerical answers
GitHub (primary)	Browse files	Download ZIP	Answers.txt
GitLab (mirror)	Browse files	Download ZIP	Answers.txt

Individual files

Every Java solution depends on these shared classes: EulerSolution.java, Library.java.
Many Python solutions depend on my shared math library module: eulerlib.py.
Many Haskell solutions depend on my shared math library module: EulerLib.hs.
Some solution code contains a detailed mathematical proof of correctness.

Language usage

Java

For every problem that I solved, I have a Java solution for it (and possibly code in other languages as well). I like using Java because it is fast, safe, and expressive. To elaborate on these points, I will compare it to other program­ming languages: Python and Mathematica are slow for basic integer arithmetic (~1/30× of Java speed) because they natively use bigint and are also dynami­cally typed. Also, Mathematica uses a lot of memory to store an array of integers because it doesn’t have packed fixed-width integers. C and C++ are unsafe because of the lack of array bounds checking, having signed integer overflow, and having tons of easily invoked undefined behaviors. Custom data structures like graphs are difficult to express cleanly in Mathematica. Custom algorithms like the sieve of Eratosthenes, especially ones most naturally expressed in terms of imperative state updates, are difficult to implement correctly or efficiently in Haskell. Non-strict evaluation in Haskell makes it easy to accidentally leak large amounts of memory in unexpected places.

However on the flip side, I prefer to solve a problem in Mathematica first if it’s possible. This is because it has many useful built-in mathematical functions (like prime testing) and objects (like fractions) that would require manual effort to implement in Java. Also, my Java solutions tend to be long due to types on every variable, lots of custom code, and low-level loops instead of higher-order functions. If I was aiming for raw execution speed, writing comparable code in C or C++ would probably run 3× as fast as Java.

Note that for problems involving non-whole numbers, I try to use exact integer arithmetic or fractions as much as possible, which ensures that the solution is provably correct. As a result I strongly avoid any floating-point arithmetic at all, unless there is no other reasonable way (that I know of) to solve the problem. Also I study the numerical bounds carefully to avoid integer overflow, and use the most reasonably narrow type for speed (choosing between int, long, or BigInteger).

To run a Java solution, compile the Java file (e.g. p001.java) and also the shared classes EulerSolution.java and Library.java. Then run with a command like java p001, and the answer will be printed to standard output.

Sample code (problem 117) (most other solutions are many times longer):

public class p117 {
  private static final int LENGTH = 50;
  public static void main(String[] args) {
    // Dynamic programming
    long[] ways = new long[LENGTH + 1];
    ways[0] = 1;
    for (int n = 1; n <= LENGTH; n++) {
      for (int k = 1; k <= 4 && k <= n; k++)
        ways[n] += ways[n - k];
      }
    System.out.println(ways[LENGTH]);
  }
}

Resources:

• Official site: Oracle Java

Python

Almost all solutions are made available in Python, which is an imperative object-oriented language with many conceptual similarities to Java. These pieces of code are interesting for a couple of reasons: One is that it caters to programmers who prefer to read Python code over Java due to familiar­ity with the language. Another is that the Python code has less syntactic “noise” due to the lack of types, variable declarations, and integer size distinctions – so the Python code expresses the essential ideas of the mathematical algorithms more directly. My code requires Python 3 (but old versions can be found that support both 2 and 3).

The Python solutions were initially based on the Java solutions, often starting with a direct literal port of the Java code into Python. Over time, the Python code was adapted to fit the characteristics of the language – such as using idiomatic/Pythonic approaches, tweaking or changing algorithms to increase speed (whereas Java can sometimes get away with less efficient but simpler algorithms), and making heavy use of generators. The style of using generators/filters/itertools can be considered about halfway between Java’s imperative style and {Haskell or Mathematica}’s functional style. Unfortunately due to Python’s slow performance on arrays and machine-word-sized integer values, many solutions are not worth the time to run it compared to the Java implementations.

Sample code (problem 10):

# Sieve of Eratosthenes
ans = 0
isprime = [True] * 2000001
for i in range(2, len(isprime)):
	if isprime[i]:
		ans += i
		for j in range(i * i, len(isprime), i):
			isprime[j] = False
print(ans)

Resources:

• Official site: Python.org

Mathematica

I used Mathematica for many of the earlier problems, because compactness and convenient library functions were more impor­tant than running time or memory. Mathematica provides easy access to prime numbers, big integers, high-precision floats, fractions, continued fractions, and more. My code tends to be quite short: one-liners are very common, and typically the solution is less than 5 lines of code. For problems that involve computing and/or storing millions of numbers, my experience has been that Mathematica takes too long to run my algorithm or exceeds the memory limit.

In Mathematica, I make heavy use of nested expressions, functional program­ming core functions like Map and Select, and aggregation functions like Total, Length, Sum. Occasionally I write imperative code in Mathematica, usually for unbounded searching. I write Mathematica code in a rather plain style, using only [] for function application (not @ or //), avoid pattern processing, and avoid declaring functions with the #-and-& syntax.

To run a Mathematica solution, copy the entire code into a new Mathematica notebook and evaluate the whole block of text. The solution is shown in the output.

Sample code (problem 7):

Prime[10001]

Sample code (problem 20):

Total[IntegerDigits[100!]]

Sample code (problem 29):

Length[Union[Flatten[Table[a^b, {a, 2, 100}, {b, 2, 100}]]]]

Sample code (problem 323):

cdf[n_] := (1 - (1/2)^n) ^ 32
pdf[n_] := cdf[n] - cdf[n - 1]
Sum[n * pdf[n], {n, Infinity}]  (* Exact *)
N[%, 11]  (* Rounded *)

Resources:

• Official site: Wolfram Mathematica
• Function reference: Wolfram Mathematica Documentation

Haskell

I’m a beginner at Haskell programming, and only know how to use it to solve the easier problems in Project Euler. When I do use it, I end up learning many new concepts in functional program­ming, such map/filter/fold, infinite lists, converting iterative algorithms to recursive functions, memoization, etc. When a problem can be solved in a purely functional way without impera­tively updating variables, my Haskell solution will be structured very similarly to my Mathematica solution.

To run a Haskell solution, run the Haskell file as a main program.

Sample code (problem 21):

main = putStrLn (show ans)
ans = sum [n | n <- [1..10^4], amicable n]

amicable :: Int -> Bool
amicable n = let m = divisorSum n in (m /= n) && (divisorSum m) == n

divisorSum :: Int -> Int
divisorSum n = sum [k | k <- [1..n-1], (mod n k) == 0]

Resources:

• Official site: The Haskell Programming Language
• Tutorial: Learn You a Haskell for Great Good!

Benchmark timings

The Project Euler solution programs listed above were bench­marked to see how much time it took to compute the answer. This information gives a rough sense of which problems are easy or hard, and how the choice of program­ming language affects the running time.

Note that the benchmark does not attempt to be “fair” in any way. My solution code is first designed to run within an “accept­able” running time (not targeting absolute fastest code), and then heavily optimized for human clarity (both in terms of the code implementation and the underlying mathematical concepts). Sometimes, slightly inefficient constructs (such as list comprehen­sions) are used for the sake of clarity. The algorithms between different languages are not exactly the same; instead I try to write code that is most idiomatic and clear for the given language. However, it can still be observed that Python is generally 10× to 30× slower than Java for pure number-crunching code.

All the numbers listed in the table below are in seconds, and these computing environments were used:

• Oracle Java 10.0.2+13 (64-bit), Intel Core i5-4690 (Haswell) 3.50 GHz, Windows 8.1 Pro (64-bit).
• CPython 3.7.0 (64-bit), Intel Core i5-4690 (Haswell) 3.50 GHz, Windows 8.1 Pro (64-bit).
• Wolfram Mathematica 5.1 (32-bit), Intel Core i5-2450M (Sandy Bridge) 2.50 GHz, Windows 7 Pro SP1 (64-bit).
• Glasgow Haskell Compiler 7.10.3, compiling with -O option to 64-bit executables, Intel Core i5-4690 (Haswell) 3.50 GHz, Ubuntu Linux 16.04 (64-bit).

More info

• GitHub: luckytoilet: projecteuler-solutions (over 700 numerical answers)
• MathBlog: C# Solutions for Project Euler (146 solutions with explanations)
• Stephan Brumme: Project Euler C++ solutions (over 300 solutions)
• HaskellWiki: Euler problems (nearly 200 solutions, with concise code)