#100DaysOfCode Day 1: Project Euler Problems 1, 2 & 3
Solutions in Python with explanations!
#100DaysOfCode Day 1: Project Euler Problems 1, 2 & 3
For the first day of my #100DaysToCode, I will be solving problems from Project Euler, uploading the solutions to my GitHub, and producing a blog post explaining my solutions to them with code snippets to improve my use of HTML, CSS & Markdown. I will not be posting the actual answers to these problems as to spoil anyones fun!
Problem 1 - Multiples of 3 and 5
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.
Click here to see the solution on GitHub
This is a very simple problem to solve, with a single issue to take note of:
- Multiples of 3 and 5 exist (multiples of 15) and they may be counted twice.
In order to avoid this problem, one can use the condition if x % 3 == 0 or x % 5 == 0, for which multiples of 15 will satisfy this condition - and not require separate arithmetic. Therefore one simple way to solve this problem is the following!
def solution():
answer = sum(x for x in range(1000) if (x % 3 == 0 or x % 5 == 0))
return str(answer)
print(solution())
Problem 2 - Even Fibonacci Numbers
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.
Click here to see the solution on GitHub
This is a classic fibonacci problem, with a summation. The fibonacci sequence is defined as f(n) = f(n-1) + f(n-2), meaning that the next number in the sequence is the sum of the two preceding numbers. We simply need to find the even numbers in this sequence from 0 to 4,000,000 and sum them together.
We can use the same condition as problem 1 (x % 2) to only sum the numbers evenly divisible by 2, and then add them to the answer variable and repeat this until our current fibonacci number x reachs the limit.
This problem could potentially take quite a long time, so to solve this, one could use a simple loop with two variables, x and y, and accumulating the answer along the way!
def solution():
answer = 0
x = 1 # The current fibonacci number
y = 2 # The next fibonacci number
while x <= 4000000: # This is the 4 million limit
if x % 2 == 0:
answer += x
x, y = y, x + y # f(n-1) -> f(n) and f(n) -> f(n+1)
return str(answer)
print(solution())
Problem 3 - Largest Prime Factor
The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?
Click here to see the solution on GitHub
To solve this problem it is helpful to look at what exactly a prime number is. An integer n is prime if, and only if, the only divisors of n are itself, and 1. If a number is not prime, then it is composite, meaning that it has some integer divisions other than itself and 1.
The fundamental theorem of arithmetic source: wikipedia states that every integer greater than 1 is prime, or the product of 2 or more primes.
We know that 2 and 3 are both prime numbers - so as such we can immediately eliminate even numbers and multiple of three, but we can significantly cut down the amount of work needed to determine whether a number is prime by realising the if a number is not prime, then it must have at least one divisor which is less, or equal to it’s square root! Any two integer factors of a number but balance around that numbers square root, for example if you consider the number 16, the square root is 4, so for a * b = 16, a = b = 4. If a were to increase to 8, then b must decrease to 2, and vice versa.
Therefore, to check whether a number is prime, we can simply check to see if it has any divisors less than its square root! This means instead of generating every factor and checking if each number n is a prime, we can simply start at the smallest factor 3, and limit our search at the square root of n.
This time we will make use of Python’s numpy library for the sqrt function!
import numpy as np
def smallest_prime(n):
square_root = int(np.sqrt(n))
for i in range(3, square_root + 1):
if n % i == 0:
return i
return n
def solution():
p = 3
n = 600851475143
while p < n:
p = smallest_prime(int(n))
if p < n:
n = n // p
else:
return str(n)
print(solution())
Closing Thoughts: I’ve really enjoyed taking these problems and deconstructing them bit by bit, and I’m looking forward to trying the harder problems. I might start doing these regularly, maybe separate to #100DaysOfCode, but it’s certainly put me in a very enthusiatic mood to continue to improve.
Peace xo