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.
#trivial with python's comprehensions
sum(x for x in xrange(1,1000) if x%5==0 or x%3==0)
233168
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
#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()
4613732
%%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
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()
4613732
%%timeit
getEvenSum()
100000 loops, best of 3: 3.88 µs per loop
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
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:]
[19991, 19993, 19997]
#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
[6857, 1471, 839, 71]
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.
#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)
906609