Home - maccergit/Euler GitHub Wiki

This GitHub project contains my work on the first 100 problems at ProjectEuler.net (Note that there are many more than 100 problems, but they request that no solutions beyond the first 100 problems be published outside their site. I expect it will be a while before I have to worry about this limitation. Anything beyond that will need to be in a private repo).

General information about ProjectEuler.net

Project Euler is a free website that promotes exploration into computational mathematics by providing a series of problems to solve, each of which requires the writing of code to solve the problem in a reasonable amount of time. Often, a smaller version of the problem is provided as an example, and then the problem requests the answer for a much larger version of the problem. Often, the small version of the problem can be easily solved with a naive "brute force" approach - but the problems scale up so quickly that the same approach fails on the larger problem. In most case, a better algorithm can be used that solves the larger problem much faster (usually orders of magnitude faster). A classic example would be sorting a random list of numbers - a small list can be easily sorted with a simple shell sort, but shell sort execution time rapidly grows with the number of elements to sort, and a better sort algorithm (such as a quick sort) can produce much faster sorts on large numbers of elements.

The general goal is provide motivation to examine the backgrounds of the various problems, resulting in a deeper understanding of the mathematics behind these problems. Also, the problem spaces cover a range of areas in mathematics no typically covered outside advanced mathematics studies, and these problems can provide an introduction into these areas.

To learn more, follow this link to ProjectEuler.net

About these files

This repository contains my working files as I explore the Project Euler problems. My original intent was to get a deeper understanding of the Python programming language, and I figured these problems would be a good way to explore the numerical processing capabilities of Python - I have a strong professional background in C/C++, Java, COBOL and other languages, and wanted to add Python to the mix. As a result, Python is now my preferred scripting language - and I have picked up knowledge in various areas of mathematics as well.

Each problem has its own wiki page for notes and discussion about the problem, various solutions I have developed, and any other items I found interesting. However, there are some standards I have developed across all the problems:

• My IDE of choice is Eclipse, and Python development in Eclipse is done via PyDev - follow the link to see more : PyDev.org
• While I like the fact that PyDev supports CPython, Jython, and PyPy, I am currently restricting myself to CPython. All the libraries work with CPython, as it is the reference implementation of Python. The version I am using is Python3, specifically 3.11.5 on Mac OSX Ventura. I have another repository containing files for a talk I gave at a Boulder Python Users Group meeting comparing performance of CPython, Python, and PyPy - but it used Python2 and is now very out of date.
• I have refactored some common code to its own "utils" project. Projects that import this common code need to include the project in their "Project References" settings. Importing the PyDev project from the repository will automatically set this.
• Projects are named "probNNNN", as I expect problem numbers to reach 1000 soon. Each project includes a text description of the problem (copied from the problem description at Project Euler). I may also include some timing information for each solution (was in the text description, but should be pulled into its own file). Many problems have multiple implementations of the solution - often, an initial naive "brute force" implementation, along with alternative implementations using better algorithms or Python libraries. These other implementations are the "exploration" part of the problem.
• Each of the implementations follows a standard template - headers (note the explicit use of UTF-8 to allow characters beyond ANSI), the code for the solution, some assertion testing (usually confirming the small example in the problem description), the display of the actual answer, and then timing information in two formats : a table showing the timing of the sample and actual problem, and a graphical plot showing how the implementation scales over a range of problem sizes. For more timing details, see the wiki page for the utils project.

Project Pages

• Prob 0001 ‐ Multiples of 3 and 5
• Prob 0002 - Even Fibonacci Numbers
• Prob 0003 - Largest Prime Factor
• Prob 0004 - Largest Palindrome Product
• Prob 0005 - Smallest Multiple
• Prob 0006 - Sum Square Difference
• Prob 0007 - 10001st Prime
• Prob 0008 - Largest Product in a Series
• Prob 0009 - Special Pythagorean Triplet
• Prob 0010 - Summation of Primes
• Prob 0011 - Largest Product in a Grid
• Prob 0012 - Highly Divisible Triangular Number
• Prob 0013 - Large Sum
• Prob 0014 - Longest Collatz Sequence
• Prob 0015 - Lattice Paths
• Prob 0016 - Power Digit Sum
• Prob 0017 - Number Letter Counts
• Prob 0018 - Maximum Path Sum I
• Prob 0019 - Counting Sundays
• Prob 0020 - Factorial Digit Sum
• Prob 0021 - Amicable Numbers
• Prob 0022 - Names Scores
• Prob 0023 - Non-Abundant Sums
• Prob 0024 - Lexicographic Permutations
• Prob 0025 - 1000-Digit Fibonacci Number
• Prob 0026 - Reciprocal Cycles
• Prob 0067 - Maximum Path Sum II

Works In Progress / TODO / Areas to Investigate

This is work waiting to be done, listed here so I don't forget what still needs attention :

• Now including AI to help investigate deeper. I don't expect any big revelations in the simpler problems, but I've already discovered that the AI can help me dig deeper into lesser known areas. I expect it will help with the areas to investigate in the list below, but right now I'm running it through its paces on solved problems - next "investigation" is Prob 0003. One interesting tidbit - it's like a code review, suggesting best practices I may have skipped over.
• Prob 0009.07 : Matrix multiplication - see wikipedia "Tree of primitive Pythagorean triples"
• Prob 0009 : Dickson's method, when s and t are coprime - see wikipedia "Formulas for generating Pythagorean triples", "Dickson's method"
• Prob 0009 : code from problem discussion (builds on diophantine)
• Prob 0011 : Investigate using NumPy library stride_tricks for sliding window/successive slices in solutions.
• wiki pages for prob0027 - prob0033
• Latest probs to work on (currently prob0034)

Final Notes

This is a work in progress, and probably always will be. It is one hobby among many, and thus only sporadically gets attention. This repo was created because I discovered things were getting complex enough to need version control, and I needed a way to store projects that was not tied to a particular machine. For a similar project with a focus on Python string processing capabilities and bioinformatics, see the Rosalind repository.