project_euler_py

This project will consist of python solutions to Project Euler questions. Particular emphasis will be put on the efficiency and optimization of the solutions. If you are at all interested in working on Project Euler questions, or have a general interest in algorithms, I suggest trying some Project Euler questions out yourself prior to reading anyone else's solutions.

Notes

Timing Analysis

All timing analysis has been done using the time command in Debian 9 "Stretch". An example of running timing analysis would be:

time python pe_1.py

Issues

If you find anything in my code that you think is an incorrect working or a wholly inefficient one, I would be appreciative if you would submit an issue so that I can learn how to improve my code.

Problem #1 - Multiples of 3 and 5

Problem:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

Solution(s):

Solution 1:

This solution loops through the multiples of both 3 and 5 which are less than the limit, in this case 1000. It also loops through the multiples of 15 (3*5) in order to subtract the common multiples of 3 and 5.

Timing Analysis:

real	0m0.020s
user	0m0.016s
sys	0m0.000s

Timing Analysis with limit set to 1,000,000:

real	0m0.104s
user	0m0.100s
sys	0m0.000s

Solution 2:

This solution takes advantage of the formula for the sum of an arithmetic progression, S_n = n(a₁ + a_n)/2.

The first step is to find the maximum multiples of 3, 5 and 15. Once this is done, we can calculate the solution using the above equation three times, adding the solutions for 3 and 5 and subtracting the solution for 15 to account for common multiples. n can be found by dividing the maximum multiple by the number it is a multiple of (eg. n for 3 will be 999/3 = 333 where 1000 is the limit).

Timing Analysis:

real	0m0.019s
user	0m0.016s
sys	0m0.000s

Timing Analysis with limit set to 1,000,000:

real	0m0.019s
user	0m0.016s
sys	0m0.000s

The complexity of this algorithm is O(1).

Solution 3:

This solution checks each number below the limit for divisibility with 3 or 5 and adds those which are divisible to the final sum.

Timing Analysis:

real	0m0.019s
user	0m0.016s
sys	0m0.000s

Timing Analysis with limit set to 1,000,000:

real	0m0.191s
user	0m0.188s
sys	0m0.000s

Notes: If timing analysis is done only on the limit of 1000, all three algorithms complete in approximately the same time. Increasing the limit, however, gives solution 2 a clear advantage over both solution 1 and solution 3. This is due to the fact that the complexity of solution 2 is constant-time.

---

Problem #2 - Even Fibonacci Numbers

Problem:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Solution(s):

Solution 1:

Problem #3 - Largest Prime Factor

Problem #4 - Largest Palindrome Product

Problem #5 - Smallest Multiple

Problem #6 - Sum Square Difference