{
 "metadata": {
  "name": "",
  "signature": "sha256:7112cdc4949389799fc83c21e5fc3b266d6a8005d9ab110c0b75e03dd75dbc3a"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Problem 1"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "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.\n",
      "\n",
      "Find the sum of all the multiples of 3 or 5 below 1000.\n",
      "\n",
      "---"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#trivial with python's comprehensions\n",
      "sum(x for x in xrange(1,1000) if x%5==0 or x%3==0)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 1,
       "text": [
        "233168"
       ]
      }
     ],
     "prompt_number": 1
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Problem 2"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "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:\n",
      "\n",
      "1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...\n",
      "\n",
      "By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.\n",
      "\n",
      "---"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "**Method 1: memoization**\n"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#set base case\n",
      "fibs = {0:0, 1:1}\n",
      "\n",
      "def fib(n):\n",
      "    ret = fibs.get(n, None)\n",
      "    if ret != None:\n",
      "        return ret\n",
      "    ret = fib(n-2) + fib(n-1)\n",
      "    fibs[n] = ret\n",
      "    return ret\n",
      "\n",
      "def getEvenSum(upperBound = 4000000):\n",
      "    evenValued = []\n",
      "    for i in range(upperBound):\n",
      "        v = fib(i)\n",
      "        if v > upperBound:\n",
      "            break\n",
      "        if v%2 == 0:\n",
      "            evenValued.append(v)\n",
      "\n",
      "    return sum(evenValued)\n",
      "\n",
      "getEvenSum()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 2,
       "text": [
        "4613732"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%%timeit\n",
      "getEvenSum()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "10 loops, best of 3: 65.6 ms per loop\n"
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "This isn't terrible, but we can do a lot better by iterating from the bottom up.\n",
      "\n",
      "**Method 2: iterative**"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def getEvenSum(upperBound = 4000000):\n",
      "    previous = 0\n",
      "    total = 1\n",
      "    even = 0\n",
      "\n",
      "    while total < upperBound:\n",
      "        temp = total\n",
      "        total += previous\n",
      "        if total %2 == 0:\n",
      "            even += total\n",
      "        previous = temp\n",
      "\n",
      "    return even\n",
      "\n",
      "getEvenSum()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 4,
       "text": [
        "4613732"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%%timeit\n",
      "getEvenSum()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "100000 loops, best of 3: 3.88 \u00b5s per loop\n"
       ]
      }
     ],
     "prompt_number": 5
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Problem 3"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The prime factors of 13195 are 5, 7, 13 and 29.\n",
      "\n",
      "What is the largest prime factor of the number 600851475143 ?\n",
      "\n",
      "---"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "This is an uninspired brute force solution, see problem 6 for a better way to find primes"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def isPrime(x):\n",
      "    if (x==1):\n",
      "        return False\n",
      "    for i in range(2,x):\n",
      "        if x%i==0:\n",
      "            return False\n",
      "    return True\n",
      "    \n",
      "#build a list of all primes <=20000\n",
      "primes = []\n",
      "for i in range(1,20000):\n",
      "    if isPrime(i):\n",
      "        primes.append(i)\n",
      "        \n",
      "primes[-3:]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 6,
       "text": [
        "[19991, 19993, 19997]"
       ]
      }
     ],
     "prompt_number": 6
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#find the complete prime factorisation for the target number\n",
      "target = 600851475143\n",
      "factors = []\n",
      "for p in reversed(primes):\n",
      "    if target % p == 0:\n",
      "        factors.append(p)\n",
      "factors"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 7,
       "text": [
        "[6857, 1471, 839, 71]"
       ]
      }
     ],
     "prompt_number": 7
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Problem 4"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 \u00d7 99.\n",
      "\n",
      "Find the largest palindrome made from the product of two 3-digit numbers.\n",
      "\n",
      "---"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#nothing clever here, brute force over the search space and pick out all the palindromes\n",
      "palindromes = []\n",
      "\n",
      "def isPalindrome(x):\n",
      "    s = str(x)\n",
      "    return s == s[::-1]\n",
      "\n",
      "#note the inner loop doesn't cover the entire search space but starts at x\n",
      "#this halves work by not calculating redundant products like (1*2, 2*1)\n",
      "for x in reversed(range(100, 1000)):\n",
      "    for y in reversed(range(x, 1000)):\n",
      "        n = x*y\n",
      "        if (isPalindrome(n)):\n",
      "            palindromes.append(n)\n",
      "            \n",
      "max(palindromes)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 8,
       "text": [
        "906609"
       ]
      }
     ],
     "prompt_number": 8
    }
   ],
   "metadata": {}
  }
 ]
}