Project Euler

MIT Licence Documentation Status C.I. Build Status Code Coverage Code Quality (Scrutinizer) Code Quality (Codacy) Code Quality (CodeFactor)

A collection of my solutions to Project Euler challenges. All code is my own work and I have solved all problems before reviewing others’ approaches. On occasion, I have incorporated superior ideas into these solutions when I have come across something particularly novel/clever.

Overview

here here

According to its website, Project Euler was created by Colin Hughes (a.k.a. euler) in October 2001 as a sub-section on http://mathschallenge.net

Project Euler is an ever-growing collection of computational problems with a particular mathematical bent, contributed by community members.

Each problem has a numeric answer, which can be submitted to the website to check its correctness. Doing so provides access to a forum discussing others’ answers to that same problem.

All problems have been designed to adhere to the “one-minute rule”. That is, there is an efficient algorithm to solve each and every problem that will run on a modestly powerful computer in less than one minute. Distributed computing is not required and your choice of language is irrelevant - if you have found an efficient solution ☺

Happy coding!

Usage Instructions

This project contains a collection of solutions to Project Euler problems and a series of useful components:

  • a library of mathematical functions (and corresponding unit testing)
  • an API for solutions to conform to
  • a command-line application providing high-level functions (see below)

This is a Python 3.6 project and utilises a number of extra dependencies as specified in requirements.txt. You can manually configure a corresponding Python environment, or alternatively deploy a Python virtual environment and use pip to install all necessary dependencies.

For example, in Linux, the following steps will deploy a virtual environment with the required dependencies:

python3 -m venv env              # create a virtual environment called env
source env/bin/activate          # enter the virtual environment
pip install -r requirements.txt  # install all dependencies

You can find detailed usage instructions in the synopsis for this project, however, here is a short cheat sheet.

To begin work on a new problem (identified by PROBLEM_NUMBER) use the following:

python main.py start PROBLEM_NUMBER

The start function will scrape the Project Euler website and create boilerplate files to hold your solution implementation and its associated documentation describing that solution. The problem description will be captured in this boiler-plating and any associated datafiles that are linked from the problem on the Project Euler website will also be downloaded into the data/problems directory.

Each solution is contained in a Python module in the solutions directory and exposes two key elements:

  1. The solve() function which computes and returns the putative answer
  2. The expected_answer member which contains the expected answer if it is known (None otherwise)

To compute your solution to PROBLEM_NUMBER use the following:

python main.py solve PROBLEM_NUMBER

Finally, you may want to compute and validate all solutions:

python main.py validate

My Solutions

The following tables provide links to my solutions where they exist. The table indicates which problems I’ve solved, which ones compute the correct answer and their run-times in seconds.

1-100
101-200
201-300
301-400
401-500
501-600
601-700
  *1 *2 *3 *4 *5 *6 *7 *8 *9 *0
1 - 10 tick 0.00 tick 0.00 tick 0.07 tick 0.10 tick 0.02 tick 0.00 tick 0.02 tick 0.00 tick 0.08 tick 0.48
11 - 20 tick 0.00 tick 0.09 tick 0.00 tick 2.88 tick 0.00 tick 0.00 tick 0.00 tick 0.00 tick 0.01 tick 0.00
21 - 30 tick 0.02 tick 0.04 tick 0.57 tick 0.03 tick 0.01 tick 0.01 tick 0.11 tick 0.36 tick 0.01 tick 0.04
31 - 40 tick 0.02 tick 1.87 tick 0.03 tick 0.06 tick 0.51 tick 0.69 tick 0.19 tick 0.09 tick 0.19 tick 0.07
41 - 50 tick 0.09 tick 0.02 tick 4.19 tick 0.16 tick 0.08 tick 0.20 tick 0.05 tick 0.00 tick 0.01 tick 0.06
51 - 60 cross cross cross cross cross cross cross cross cross cross
61 - 70 cross cross cross cross cross cross cross cross cross cross
71 - 80 cross cross cross cross cross cross cross cross cross cross
81 - 90 cross cross cross cross cross cross cross cross cross cross
91 - 100 cross cross cross cross cross cross cross cross cross cross
  *1 *2 *3 *4 *5 *6 *7 *8 *9 *0
101 - 110 cross cross cross cross cross cross cross cross cross cross
111 - 120 cross cross cross cross cross cross cross cross cross cross
121 - 130 cross cross cross cross cross cross cross cross cross cross
131 - 140 cross cross cross cross cross cross cross cross cross cross
141 - 150 cross cross cross cross cross cross cross cross cross cross
151 - 160 cross cross cross cross cross cross cross cross cross cross
161 - 170 cross cross cross cross cross cross cross cross cross cross
171 - 180 cross cross cross cross cross cross cross cross cross cross
181 - 190 cross cross cross cross cross cross cross cross cross cross
191 - 200 cross cross cross cross cross cross cross cross cross cross
  *1 *2 *3 *4 *5 *6 *7 *8 *9 *0
201 - 210 cross cross cross cross cross cross cross cross cross cross
211 - 220 cross cross cross cross cross cross cross cross cross cross
221 - 230 cross cross cross cross cross cross cross cross cross cross
231 - 240 cross cross cross cross cross cross cross cross cross cross
241 - 250 cross cross cross cross cross cross cross cross cross cross
251 - 260 cross cross cross cross cross cross cross cross cross cross
261 - 270 cross cross cross cross cross cross cross cross cross cross
271 - 280 cross cross cross cross cross cross cross cross cross cross
281 - 290 cross cross cross cross cross cross cross cross cross cross
291 - 300 cross cross cross cross cross cross cross cross cross cross
  *1 *2 *3 *4 *5 *6 *7 *8 *9 *0
301 - 310 cross cross cross cross cross cross cross cross cross cross
311 - 320 cross cross cross cross cross cross cross cross cross cross
321 - 330 cross cross cross cross cross cross cross cross cross cross
331 - 340 cross cross cross cross cross cross cross cross cross cross
341 - 350 cross cross cross cross cross cross cross cross cross cross
351 - 360 cross cross cross cross cross cross cross cross cross cross
361 - 370 cross cross cross cross cross cross cross cross cross cross
371 - 380 cross cross cross cross cross cross cross cross cross cross
381 - 390 cross cross cross cross cross cross cross cross cross cross
391 - 400 cross cross cross cross cross cross cross cross cross cross
  *1 *2 *3 *4 *5 *6 *7 *8 *9 *0
401 - 410 cross cross cross cross cross cross cross cross cross cross
411 - 420 cross cross cross cross cross cross cross cross cross cross
421 - 430 cross cross cross cross cross cross cross cross cross cross
431 - 440 cross cross cross cross cross cross cross cross cross cross
441 - 450 cross cross cross cross cross cross cross cross cross cross
451 - 460 cross cross cross cross cross cross cross cross cross cross
461 - 470 cross cross cross cross cross cross cross cross cross cross
471 - 480 cross cross cross cross cross cross cross cross cross cross
481 - 490 cross cross cross cross cross cross cross cross cross cross
491 - 500 cross cross cross cross cross cross cross cross cross cross
  *1 *2 *3 *4 *5 *6 *7 *8 *9 *0
501 - 510 cross cross cross cross cross cross cross cross cross cross
511 - 520 cross cross cross cross cross cross cross cross cross cross
521 - 530 cross cross cross cross cross cross cross cross cross cross
531 - 540 cross cross cross cross cross cross cross cross cross cross
541 - 550 cross cross cross cross cross cross cross cross cross cross
551 - 560 cross cross cross cross cross cross cross cross cross cross
561 - 570 cross cross cross cross cross cross cross cross cross cross
571 - 580 cross cross cross cross cross cross cross cross cross cross
581 - 590 cross cross cross cross cross cross cross cross cross cross
591 - 600 cross cross cross cross cross cross cross cross cross cross
  *1 *2 *3 *4 *5 *6 *7 *8 *9 *0
601 - 610 cross cross cross cross cross cross cross cross cross cross
611 - 620 cross cross cross cross cross cross cross cross cross cross
621 - 630 cross cross cross cross cross cross cross cross cross cross
631 - 640 cross cross cross cross cross cross cross cross cross cross
641 - 650 cross cross cross cross cross cross cross cross cross cross
651 - 660 cross cross cross cross cross cross cross cross cross cross
661 - 670 cross cross cross cross cross cross cross cross cross cross
671 - 680 cross cross cross cross cross cross cross cross cross cross
681 - 690 cross cross cross cross cross cross cross cross cross cross
691 - 700 cross cross cross cross cross cross cross cross cross cross

Note

these run-times are measured on whatever build system is employed by Read the Docs running the standard Python 3.6 interpreter, CPython. All solutions are single-threaded.

Solution Run-time Legend

tick
the answer was computed correctly
warning
the answer was computed, but was incorrect
cross
a solution to this problem does not yet exist

Code Layout

This project consists of the following Python modules/packages:

This project is hosted on BitBucket.

Indices and Tables

Review

Written on 28 April 2018, proofread on 12 July 2018