Project Euler solutions
I solve Project Euler problems for fun to practice my math and programming skills. On this page and also at GitHub, I am making all my solution code available to the public.
My code is written in a mix of Java, Mathematica, and Haskell. For each problem, I first used whichever language was the most convenient to solve the problem. I wrote all the code myself and did not base it on anyone else’s code (though I have sometimes adopted others’ high-level approach to solving a problem).
Solutions
Numerical answers to all problems I solved: Answers.txt
Java solutions depend on these shared classes: EulerSolution.java, Library.java
Some solution codes include detailed comments to explain and justify the mathematics involved in the algorithm. The solutions without explanations generally use straightforward techniques and are self-explanatory from the code.
Source code
My Project Euler solution code is available at GitHub: https://github.com/nayuki/Project-Euler-solutions
You can browse individual files on GitHub, or download a ZIP of everything.
Below, I discuss the way I use various programming languages (Java, Mathematica, Haskell) to solve Project Euler problems.
Java
The majority of my solutions are first implemented in Java, my preferred general-purpose programming language. I use this language to implement algorithms from scratch (especially ones that heavily use imperative state updates) to take advantage of the speed and compactness of fixed-width integers, or to precisely control which values are memoized. However, my Java solutions tend to be quite long, so I prefer to first solve in Mathematica when possible.
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.
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];
}
return Long.toString(ways[LENGTH]);
}
}
Resources:
- Official site: Oracle Java
Mathematica
I used Mathematica for many of the earlier problems, because compactness and convenient library functions were more important 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 runs out of memory.
In Mathematica, I make heavy use of nested expressions, functional programming core functions like Map and Select, and aggregation functions like Total, Length, Sum. Occasionally I write imperative code in Mathematica, usually for unbounded searching.
To run a Mathematica solution, copy the entire code into a new Mathematica notebook and evaluate the whole block. 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 rarely use Haskell to solve Project Euler problems. When I do use Haskell, I find it to be ideal for defining simple functions that are unrelated to number theory.
To run a Haskell solution, run the Haskell file as a main program.
Sample code (problem 22):
import List (sort) import Char (ord) names = ["MARY", ... (omitted) ... "ALONSO"] strSum = sum . (map (\c -> (ord c) - (ord 'A') + 1)) ans = sum (zipWith (*) [1..] (map strSum (sort names))) main = putStrLn (show ans)
Resources:
- Official site: The Haskell Programming Language
- Tutorial: Learn You a Haskell for Great Good!
