Project Nayuki


Project Euler solutions

Nayuki’s stats on Project Euler

This page hosts a collection of my solutions to Project Euler problems.

All the problems I solved include a Java program, and some include one in Mathematica and Haskell as well. Among the web, this is perhaps the largest collection of Project Euler solutions in the Java programming language.

I solve Project Euler problems for fun to practice and extend my math and programming skills. Here I make my solutions publicly available for other enthusiasts to learn from and to critique. All my code is original work, not based on anyone else’s code, though sometimes I obtained the high-level approach from reading various literature on the web.

Solutions

All my files in this project are available in a Git repository:

Web site Browse files Download package
GitHub (primary) Browse files Download ZIP
Eigenstate (mirror) Browse files Download .tar.gz

Numerical answers to all problems I solved: Answers.txt

Some solution source code includes 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.

Every Java solution depends on these shared classes: EulerSolution.java, Library.java

Problem Java Mathematica Haskell Explanation
Problem 1 p001.java p001.mat.txt p001.hs
Problem 2 p002.java p002.mat.txt p002.hs
Problem 3 p003.java p003.mat.txt p003.hs Yes
Problem 4 p004.java p004.mat.txt p004.hs
Problem 5 p005.java p005.mat.txt p005.hs
Problem 6 p006.java p006.mat.txt p006.hs Yes
Problem 7 p007.java p007.mat.txt p007.hs
Problem 8 p008.java p008.mat.txt p008.hs
Problem 9 p009.java p009.mat.txt p009.hs
Problem 10 p010.java p010.mat.txt p010.hs
Problem 11 p011.java p011.mat.txt p011.hs
Problem 12 p012.java p012.mat.txt p012.hs
Problem 13 p013.java p013.mat.txt p013.hs
Problem 14 p014.java p014.mat.txt p014.hs
Problem 15 p015.java p015.mat.txt p015.hs
Problem 16 p016.java p016.mat.txt p016.hs
Problem 17 p017.java p017.mat.txt p017.hs
Problem 18 p018.java p018.mat.txt p018.hs
Problem 19 p019.java p019.mat.txt p019.hs
Problem 20 p020.java p020.mat.txt p020.hs
Problem 21 p021.java p021.mat.txt p021.hs
Problem 22 p022.java p022.mat.txt p022.hs
Problem 23 p023.java p023.mat.txt p023.hs
Problem 24 p024.java p024.mat.txt p024.hs
Problem 25 p025.java p025.mat.txt p025.hs
Problem 26 p026.java p026.mat.txt p026.hs
Problem 27 p027.java p027.mat.txt
Problem 28 p028.java p028.mat.txt p028.hs Yes
Problem 29 p029.java p029.mat.txt p029.hs
Problem 30 p030.java p030.mat.txt p030.hs Yes
Problem 31 p031.java p031.mat.txt p031.hs
Problem 32 p032.java p032.mat.txt Yes
Problem 33 p033.java p033.mat.txt Yes
Problem 34 p034.java p034.mat.txt p034.hs Yes
Problem 35 p035.java p035.mat.txt
Problem 36 p036.java p036.mat.txt p036.hs
Problem 37 p037.java p037.mat.txt
Problem 38 p038.java p038.mat.txt p038.hs
Problem 39 p039.java p039.mat.txt p039.hs
Problem 40 p040.java p040.mat.txt p040.hs
Problem 41 p041.java p041.mat.txt
Problem 42 p042.java p042.mat.txt p042.hs Yes
Problem 43 p043.java p043.mat.txt
Problem 44 p044.java Yes
Problem 45 p045.java p045.mat.txt
Problem 46 p046.java p046.mat.txt
Problem 47 p047.java p047.mat.txt
Problem 48 p048.java p048.mat.txt p048.hs
Problem 49 p049.java p049.mat.txt
Problem 50 p050.java p050.mat.txt
Problem 51 p051.java
Problem 52 p052.java p052.mat.txt
Problem 53 p053.java p053.mat.txt p053.hs
Problem 54 p054.java
Problem 55 p055.java p055.mat.txt p055.hs
Problem 56 p056.java p056.mat.txt p056.hs
Problem 57 p057.java p057.mat.txt
Problem 58 p058.java
Problem 59 p059.java
Problem 60 p060.java p060.hs Yes
Problem 61 p061.java
Problem 62 p062.java
Problem 63 p063.java p063.mat.txt p063.hs Yes
Problem 64 p064.java p064.mat.txt
Problem 65 p065.java p065.mat.txt
Problem 66 p066.java p066.mat.txt
Problem 67 p067.java p067.mat.txt p067.hs
Problem 68 p068.java
Problem 69 p069.java p069.mat.txt
Problem 70 p070.java p070.mat.txt
Problem 71 p071.java p071.mat.txt p071.hs
Problem 72 p072.java p072.mat.txt
Problem 73 p073.java Yes
Problem 74 p074.java
Problem 75 p075.java Yes
Problem 76 p076.java p076.mat.txt p076.hs
Problem 77 p077.java
Problem 78 p078.java Yes
Problem 79 p079.java
Problem 80 p080.java p080.mat.txt Yes
Problem 81 p081.java p081.mat.txt p081.hs
Problem 82 p082.java p082.mat.txt
Problem 83 p083.java p083.mat.txt
Problem 84 p084.java
Problem 85 p085.java
Problem 86 p086.java
Problem 87 p087.java
Problem 88 p088.java
Problem 89 p089.java p089.mat.txt p089.hs
Problem 90 p090.java
Problem 91 p091.java
Problem 92 p092.java p092.mat.txt p092.hs
Problem 93 p093.java
Problem 94 p094.java Yes
Problem 95 p095.java
Problem 96 p096.java
Problem 97 p097.java p097.mat.txt p097.hs
Problem 98 p098.java
Problem 99 p099.java
Problem 100 p100.java
Problem 101 p101.java p101.mat.txt Yes
Problem 102 p102.java p102.mat.txt p102.hs
Problem 104 p104.java p104.mat.txt Yes
Problem 105 p105.java
Problem 107 p107.java
Problem 108 p108.java Yes
Problem 109 p109.java
Problem 111 p111.java Yes
Problem 112 p112.java p112.mat.txt
Problem 113 p113.java p113.mat.txt p113.hs Yes
Problem 114 p114.java p114.mat.txt p114.hs Yes
Problem 115 p115.java p115.mat.txt p115.hs Yes
Problem 116 p116.java p116.mat.txt p116.hs Yes
Problem 117 p117.java p117.mat.txt p117.hs Yes
Problem 118 p118.java
Problem 119 p119.java Yes
Problem 120 p120.java p120.mat.txt p120.hs Yes
Problem 121 p121.java p121.mat.txt p121.hs Yes
Problem 122 p122.java
Problem 123 p123.java p123.mat.txt p123.hs Yes
Problem 124 p124.java
Problem 125 p125.java
Problem 127 p127.java
Problem 129 p129.java p129.mat.txt
Problem 130 p130.java
Problem 132 p132.java p132.mat.txt
Problem 133 p133.java p133.mat.txt Yes
Problem 134 p134.java p134.mat.txt Yes
Problem 135 p135.java Yes
Problem 142 p142.java Yes
Problem 145 p145.java Yes
Problem 146 p146.java Yes
Problem 149 p149.java
Problem 150 p150.java
Problem 151 p151.java
Problem 155 p155.java
Problem 160 p160.java p160.mat.txt p160.hs Yes
Problem 162 p162.java p162.mat.txt p162.hs Yes
Problem 164 p164.java p164.mat.txt p164.hs Yes
Problem 166 p166.java Yes
Problem 169 p169.java p169.mat.txt
Problem 171 p171.java p171.mat.txt Yes
Problem 172 p172.java p172.mat.txt Yes
Problem 173 p173.java p173.mat.txt p173.hs Yes
Problem 174 p174.java p174.mat.txt
Problem 179 p179.java p179.mat.txt
Problem 182 p182.java
Problem 186 p186.java
Problem 187 p187.java p187.mat.txt Yes
Problem 188 p188.java p188.mat.txt p188.hs
Problem 191 p191.java p191.mat.txt p191.hs
Problem 197 p197.java p197.mat.txt Yes
Problem 203 p203.java p203.mat.txt
Problem 204 p204.java
Problem 205 p205.java p205.mat.txt
Problem 206 p206.java Yes
Problem 211 p211.java
Problem 214 p214.java
Problem 218 p218.java p218.mat.txt p218.hs Yes
Problem 222 p222.java
Problem 225 p225.java
Problem 231 p231.java p231.mat.txt
Problem 243 p243.java p243.mat.txt
Problem 249 p249.java
Problem 250 p250.java p250.mat.txt
Problem 265 p265.java
Problem 271 p271.java
Problem 280 p280.java
Problem 301 p301.java p301.mat.txt p301.hs Yes
Problem 303 p303.java
Problem 304 p304.java
Problem 323 p323.java p323.mat.txt p323.hs Yes
Problem 345 p345.java
Problem 357 p357.java
Problem 381 p381.java p381.mat.txt Yes
Problem 401 p401.java p401.mat.txt Yes
Problem 407 p407.java Yes
Problem 417 p417.java Yes
Problem 425 p425.java Yes
Problem 429 p429.java p429.mat.txt Yes
Problem 431 p431.java
Problem 433 p433.java Yes
Problem 451 p451.java

Language usage

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:

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:

Haskell

I seldom use Haskell to solve Project Euler problems. When I do use it, I end up learning many new concepts in functional programming, such map/filter/fold, infinite lists, converting iterative algorithms to recursive functions, etc.

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: