Project Euler Problems 1-4

View and download this notebook from nbviewer

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.


In [1]:
#trivial with python's comprehensions
sum(x for x in xrange(1,1000) if x%5==0 or x%3==0)
Out[1]:
233168

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.


Method 1: memoization

In [2]:
#set base case
fibs = {0:0, 1:1}

def fib(n):
    ret = fibs.get(n, None)
    if ret != None:
        return ret
    ret = fib(n-2) + fib(n-1)
    fibs[n] = ret
    return ret

def getEvenSum(upperBound = 4000000):
    evenValued = []
    for i in range(upperBound):
        v = fib(i)
        if v > upperBound:
            break
        if v%2 == 0:
            evenValued.append(v)

    return sum(evenValued)

getEvenSum()
Out[2]:
4613732
In [3]:
%%timeit
getEvenSum()
10 loops, best of 3: 65.6 ms per loop

This isn't terrible, but we can do a lot better by iterating from the bottom up.

Method 2: iterative

In [4]:
def getEvenSum(upperBound = 4000000):
    previous = 0
    total = 1
    even = 0

    while total < upperBound:
        temp = total
        total += previous
        if total %2 == 0:
            even += total
        previous = temp

    return even

getEvenSum()
Out[4]:
4613732
In [5]:
%%timeit
getEvenSum()
100000 loops, best of 3: 3.88 µs per loop

Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?


This is an uninspired brute force solution, see problem 6 for a better way to find primes

In [6]:
def isPrime(x):
    if (x==1):
        return False
    for i in range(2,x):
        if x%i==0:
            return False
    return True
    
#build a list of all primes <=20000
primes = []
for i in range(1,20000):
    if isPrime(i):
        primes.append(i)
        
primes[-3:]
Out[6]:
[19991, 19993, 19997]
In [7]:
#find the complete prime factorisation for the target number
target = 600851475143
factors = []
for p in reversed(primes):
    if target % p == 0:
        factors.append(p)
factors
Out[7]:
[6857, 1471, 839, 71]

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.


In [8]:
#nothing clever here, brute force over the search space and pick out all the palindromes
palindromes = []

def isPalindrome(x):
    s = str(x)
    return s == s[::-1]

#note the inner loop doesn't cover the entire search space but starts at x
#this halves work by not calculating redundant products like (1*2, 2*1)
for x in reversed(range(100, 1000)):
    for y in reversed(range(x, 1000)):
        n = x*y
        if (isPalindrome(n)):
            palindromes.append(n)
            
max(palindromes)
Out[8]:
906609

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>