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

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

%%timeit
getEvenSum()

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

%%timeit
getEvenSum()

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:]

#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

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