# Project Euler Problems 1-4

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