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

pic tag

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.

There are several optimizations adopted:

  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

Next post: Jekyll development environment via Vagrant and PuPHPet