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

13 January 2016Once 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

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)
```

## Problem 2

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()
```

## Problem 3

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))
```

## Problem 4

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))
```

## Problem 5

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

## Problem 6

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

1

^{2}+ 2^{2}+ ... + 10^{2}= 385The square of the sum of the first ten natural numbers is,

(1 + 2 + ... + 10)

^{2}= 55^{2}= 3025Hence 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)
```

## Problem 7

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 001*st* 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 6*k* ± 1 less than or equal to `sqrt(num)`

and checking if `num`

is *divisible* by these numbers.

There are several optimizations adopted:

- We eliminate testing
*even*divisors greater than 2. - We eliminate testing divisors greater than
`sqrt(num)`

. - Only divisors of the form 6
*k*± 1 are used.

Why numbers of the form 6*k* ± 1 are so special? It is known that *all* integers can be expressed as 6*k* + *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 6
*k*± 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)
```

## Problem 8

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

71636269561882670428252483600823257530420752963450Find 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()
```

## Problem 9

A Pythagorean triplet is a set of three natural numbers,

a<b<c, for which,

a^{2}+b^{2}=c^{2}For example, 3

^{2}+ 4^{2}= 9 + 16 = 25 = 5^{2}.There exists exactly one Pythagorean triplet for which

a+b+c= 1000.

Find the productabc.

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

a^{2}+b^{2}+c^{2},

find positive integersr,s, andtsuch thatr^{2}= 2st

(ris anyeveninteger).Then:

a=r+sb=r+tc=r+s+t

*Example*:

Choose

r= 4. Thenr^{2}/ 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
```

## Problem 10

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))
```

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

Next post: Jekyll development environment via Vagrant and PuPHPet