# Python solutions for the Project Euler (problems 1-10)

Once I have found Project Euler’s website and started writing scripts to solve proposed problems. I’m not a regular visitor there, but over time a small collection of solutions has emerged. So, I decided to put results in order, push them to GitHub and share here a Python solutions for the first ten problems.

I think given examples may be helpful for Python beginners as mathematical nature of the problems assists in showing pure Python in action on the most abstract use cases. Solutions below contain examples of utilizing following Python concepts: generators, `lambda` functions, slices, `list` and `set` comprehensions.

Spoiler Warning

Subsequent sections provide ready-made solutions. It is highly recommended to read the next sections only if the subject problems are already solved by you. Otherwise it may cost you lots of inspirations and “Aha!” moments.

Real learning is an active process and seeing how it is done is a long way from experiencing that epiphany of discovery.

Jump to problem: 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10

## 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.

The solution is to produce a list of multiples of 3 and 5 using a list comprehension combined with the lambda function to check if a number is a valid multiple, and then `sum` the resulted list:

``````ismul = lambda x: x % 3 == 0 or x % 5 == 0
lst = [num for num in range(1000) if ismul(num)]
res = sum(lst)
print(res)``````

View at GitHub

## 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.

Let’s write a generator `genfib` for getting numbers from Fibonacci sequence and use list comprehension to create a list of the even Fibonacci numbers. Then `sum` the resulted list:

``````LIMIT = 4 * 10**6

def genfib(maxval):
a, b = 1, 1
while b < maxval:
yield b
a, b = b, a + b

def main():
even_fib_nums = [num for num in genfib(LIMIT) if num % 2 == 0]
res = sum(even_fib_nums)
print(res)

if __name__ == '__main__':
main()``````

View at GitHub

## 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 ?

This problem is the reference to the Fundamental Theorem of Arithmetic. So, our goal is to find all prime factors of the given number, or perform what is known as prime factorization. It is done by `prime_factors` function:

``````import math

def prime_factors(num):
"""
Returns a list of primes factors for the given number.
"""
factors = []
# Handle 2
while num % 2 == 0:
factors.append(2)
num /= 2

# Handle all odd nums <= sqrt(num)
for i in range(3, int(math.sqrt(num)) + 1, 2):
while num % i == 0:
factors.append(i)
num /= i

# Handle num is prime
if num > 2:
factors.append(num)

return factors``````

Here is an explanation of the implemented algorithm.

Now, having all prime factors, it’s easy enough to find the largest one:

``````factors = prime_factors(600851475143)
print(max(factors))``````

View at GitHub

## Problem 4

Largest palindrome product

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

Let’s find all possible products of two 3-digit numbers. It is done by set comprehension to avoid duplicate products. Then using `filter` we obtain only those products which are palindromes. The last step is simply to find `max`:

``````rng = range(100, 1000)
products_set = {i*j for i in rng for j in rng}
is_palindrome = lambda num: str(num) == str(num)[::-1]
palindromes = filter(is_palindrome, products_set)
print(max(palindromes))``````

View at GitHub

## Problem 5

Smallest multiple

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Evenly divisible means here divisible with no remainder. The approach to this problem is a simple bruteforce with some tweaks to minimize the number of unnecessary iterations:

``````def is_divisible(num):
"""
Checks if number is evenly divisible by all
of the numbers from 1 to 20.
"""
for i in [3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19]:
if num % i != 0:
return False
return True

def main():
num = 2520
while True:
if is_divisible(num):
print(num)
break
num += 20

if __name__ == '__main__':
main()``````

First tweak is to exclude checks with 2, 5 and 10 inside `is_divisible` function. Checks with 2 are omitted because if number is divisible by any even number from the checklist, then it’s obviously also divisible by 2. Checks for 5 and 10 are excluded because these checks are covered by 15.

Second tweak is to iterate only over a multiples of 20. That’s simply because by description the required number should be divisible by 20. This also implicitly covers checks with 20 which are intentionally avoided inside `is_divisible` function. Sorry Zen of Python.

View at GitHub

## Problem 6

Sum square difference

The sum of the squares of the first ten natural numbers is,

12 + 22 + ... + 102 = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + ... + 10)2 = 552 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

The solution is straightforward:

• find sum of the squares of the first one hundred natural numbers using list comprehension
• find square of the sum by using `sum` on `range(101)`
• print the difference
``````# Sum of the squares.
a = sum([i**2 for i in range(101)])

# Square of the sum.
b = sum(range(101))**2

# Result.
print(b - a)``````

View at GitHub

## Problem 7

10001st prime

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

The approach here is to iteratively perform a primality test until 10 001st prime is found. Primality test is done via `is_prime` function which returns `True` if the input number is a prime number or `False` otherwise:

``````import math

def is_prime(num):
"""
Checks that given number is a prime number.
"""
if num <= 3:
return num == 2 or num == 3

for i in range(5, int(math.sqrt(num)) + 1, 6):
if num % i == 0 or num % (i + 2) == 0:
return False
return True``````

Implementation is based on dividing the given number `num` by numbers of the form 6k ± 1 less than or equal to `sqrt(num)` and checking if `num` is divisible by these numbers.

1. We eliminate testing even divisors greater than 2.
2. We eliminate testing divisors greater than `sqrt(num)`.
3. Only divisors of the form 6k ± 1 are used.

Why numbers of the form 6k ± 1 are so special? It is known that all integers can be expressed as 6k + i, where k - some integer and i = -1, 0, 1, 2, 3 or 4.

Therefore,

• if number leaves a remainder: `num % 6 == 0, 2 or 4` then it is even and therefore non-prime (unless it is 2)
• if it leaves a remainder of 3: `num % 6 == 3`, it’s divisible of 3 and therefore non-prime (unless it is 3)
• only remainders of 1 or 5 are left, which are numbers of the form 6k ± 1.

Now, with `is_prime` function, solution is a simple loop which counts primes till it reaches 10 001st one:

``````counter = 1
num = 1
while counter < 10001:
num += 2
if is_prime(num):
counter += 1
print(num)``````

View at GitHub

## Problem 8

Largest product in a series

The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

The solution consists from the function `get_product` which calculates products of the digits inside input string and the loop which slices 13-digit strings, calculates products and pushes results into the `products` list. Then maximal value from the `products` is printed:

``````NUM = """
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
"""

def get_product(num_str):
"""
Returns a product of digits in the given `num_str`.
42  -> 4 * 2 = 8
"""
if '0' in num_str:
return 0
res = 1
for digit in num_str:
res *= int(digit)
return res

def main():
# Remove newlines.
input = NUM.replace('\n', '')

products = []
for i in range(len(NUM)):
num_slice = input[i:i+13]
products.append(get_product(num_slice))
print(max(products))

if __name__ == '__main__':
main()``````

View at GitHub

## Problem 9

Special Pythagorean triplet

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

Here we need a way to generate all possible pythagorean triples, meaning both primitive and non-primitive, till triple (a, b, c) is found, where a + b + c = 1000. Dickson’s method have been chosen for generating triples. It is easy to implement, fast enough and, most importantly, it generates all pythagorean triples.

### Dickson’s method in a nutshell

To find integer solutions to a2 + b2 + c2,
find positive integers r, s, and t such that r2 = 2st
(r is any even integer).

Then:

a = r + s
b = r + t
c = r + s + t

Example:

Choose r = 4. Then r2 / 2 = 8.
The two factor-pairs of 8 are: (1, 8), (2, 4).

Every factor-pair will produce a triple using above equations:

s = 1, t = 8 produces triple (5, 12, 13)
s = 2, t = 4 produces triple (6, 8, 10)

From the examples above it is clear that we need a means to generate a factor-pairs of the given number. Let’s implement this via following generator:

``````import math

def gen_divisor_pairs(num):
"""
Generates factor-pairs of the given number.
E.g. factor-pairs of 18 are: (1, 18), (2, 9), (3, 6)
"""
for divisor in range(1, int(math.sqrt(num)) + 1):
if num % divisor == 0:
yield divisor, num // divisor``````

Now, having `gen_divisor_pairs` in our toolset, implementation of Dickson’s method is straightforward:

``````def gen_triples():
"""
Generates Pythagorean triples using Dickson's method.
To find triples: a^2 + b^2 = c^2,
find ints r, s and t such that: r^2 = 2*s*t
Then:
a = r + s, b = r + t, c = r + s + t
"""
r = 2  # any even int.
while True:
st = r**2 // 2
pairs = [pair for pair in gen_divisor_pairs(st)]
for pair in pairs:
s, t = pair
yield r + s, r + t, r + s + t
r += 2``````

Finally, let’s find a pythagorean triple for which a + b + c = 1000 and calculate a product of abc:

``````for triple in gen_triples():
if sum(triple) == 1000:
a, b, c = triple
print(a * b * c)
break``````

View at GitHub

## Problem 10

Summation of primes

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

Here we need to find all primes below 2 000 000. To solve this problem we might have used `is_prime` function from Problem 7 to build a loop which checks odd numbers below two million and add them up if number being checked is prime. However such approach is very slow and inefficient. To find all primes below given number, commonly different kinds of sieves are used. We will utilize well-known sieve of Eratosthenes for our purposes:

``````import math

def sieve_Erat(num):
"""
Returns all primes below given number.
Sieve of Eratosthenes is used.
"""
sieve = [True] * (num + 1)
for i in range(2, int(math.sqrt(num)) + 1):
if sieve[i]:
sieve[i*i::i] = [False] * len(sieve[i*i::i])
return [i for i in range(2, num + 1) if sieve[i]]``````

Here list slice notation is used to speed up the process. It can be further improved by skipping even numbers in all loops, etc. But it’s not done for the sake of simplicity. Check fast sieve implementations in Python if you want to challenge yourself.

Finally:

``````res = sieve_Erat(2000000)
print(sum(res))``````

View at GitHub

## Summary

Of course given examples may be simplified further or we can work hard on our algorithms to optimize performance or try more advanced techniques. My goal here was to find a balance between simplicity and readability vs complexity of adopted algorithms, leaving a space to demonstrate some of Python concepts.

Previous post: How to implement Tags at Jekyll website