ProjectEuler.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import math\n",
    "import timeit\n",
    "from collections import defaultdict, Counter\n",
    "from functools import reduce, lru_cache\n",
    "from multiprocessing import Pool\n",
    "import itertools\n",
    "import tqdm\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "import datetime\n",
    "import string\n",
    "\n",
    "from math import sqrt\n",
    "\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def is_prime(number):\n",
    "    if number > 1:\n",
    "        if number == 2:\n",
    "            return True\n",
    "        if number % 2 == 0:\n",
    "            return False\n",
    "        for current in range(3, int(math.sqrt(number) + 1), 2):\n",
    "            if number % current == 0:\n",
    "                return False\n",
    "        return True\n",
    "    else:\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6857\n"
     ]
    }
   ],
   "source": [
    "num = 600851475143\n",
    "sqr = math.ceil(math.sqrt(num))\n",
    "if sqr % 2 == 0:\n",
    "    sqr -= 1\n",
    "for i in range(sqr, 3, -2):\n",
    "    if num % i == 0 and is_prime(i):\n",
    "        print(i)\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def prime_list(n):\n",
    "    if n > 2:\n",
    "        list_of_primes = [2]    \n",
    "    else: \n",
    "        return []\n",
    "    for i in range(3, n, 2):\n",
    "        if is_prime(i):\n",
    "            list_of_primes.append(i)\n",
    "    return list_of_primes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def prime_generator(n):\n",
    "    if n % 2 == 0:\n",
    "        i = n-1\n",
    "    else:\n",
    "        i = n\n",
    "    while i > 1:\n",
    "        if is_prime(i):\n",
    "            yield i\n",
    "        i -= 2\n",
    "    if n > 1:\n",
    "        yield 2\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "pg = prime_generator(13)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 5, 7]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prime_list(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6857\n"
     ]
    }
   ],
   "source": [
    "test_number = 600851475143\n",
    "for prime in prime_generator(math.ceil(math.sqrt(test_number))):\n",
    "    if test_number % prime == 0:\n",
    "        print(prime)\n",
    "        break\n",
    "else:\n",
    "    print(\"Something went wrong\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Problem 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2520"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "8*9*5*7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def prime_factorization(n):\n",
    "    factor = 2\n",
    "    factors = defaultdict(int)\n",
    "    while n > 1:\n",
    "        if n % factor == 0:\n",
    "            n /= factor\n",
    "            factors[factor] += 1\n",
    "        else:\n",
    "            break\n",
    "    factor = 3\n",
    "    while n > 1:\n",
    "        if n % factor == 0:\n",
    "            n /= factor\n",
    "            factors[factor] += 1\n",
    "        else:\n",
    "            factor += 2\n",
    "    return factors\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "most_prime_factors = defaultdict(int)  # defaults to 0\n",
    "for divisor in range(2, 21):\n",
    "    for prime_factor, occurances in prime_factorization(divisor).items():\n",
    "        if occurances > most_prime_factors[prime_factor]:\n",
    "            most_prime_factors[prime_factor] = occurances\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "232792560\n"
     ]
    }
   ],
   "source": [
    "total = 1\n",
    "for prime_factor, occurance in most_prime_factors.items():\n",
    "    total *= prime_factor**occurance\n",
    "    \n",
    "print(total)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "232792560"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reduce(lambda x, y: x*y, [prime_factor**occurances for prime_factor, occurances in most_prime_factors.items()])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "pool = Pool()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def is_prime(number, list_of_primes):\n",
    "    for old_prime in list_of_primes:\n",
    "        if old_prime**2 > number:  # if we have gotten past the point of no return\n",
    "            return True\n",
    "            \n",
    "        if number % old_prime == 0:\n",
    "            return False\n",
    "\n",
    "    raise RuntimeError(\"Should not have gotten here\")\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def is_prime2(number, list_of_primes, number_of_primes):\n",
    "    #print(list_of_primes, number_of_primes)\n",
    "    for old_prime in list_of_primes[:number_of_primes]:\n",
    "        if old_prime**2 > number:  # if we have gotten past the point of no return\n",
    "            return True\n",
    "            \n",
    "        if number % old_prime == 0:\n",
    "            return False\n",
    "\n",
    "    raise RuntimeError(\"Should not have gotten here\")\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def tester(args):\n",
    "    old_prime = args[0]\n",
    "    number = args[1]\n",
    "\n",
    "    if old_prime**2 > number:  # if we have gotten past the point of no return\n",
    "        return True\n",
    "            \n",
    "    if number % old_prime == 0:\n",
    "        return False\n",
    "    \n",
    "    return True\n",
    "\n",
    "    \n",
    "def is_prime3(number, list_of_primes):\n",
    "    new_list = [(prime, number) for prime in list_of_primes]\n",
    "    list_of_bools = pool.map(tester, new_list)\n",
    "    return all(list_of_bools)\n",
    "    #for old_prime in list_of_primes:\n",
    "\n",
    "\n",
    "    #raise RuntimeError(\"Should not have gotten here\")\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "104743\n"
     ]
    }
   ],
   "source": [
    "n = 10001\n",
    "prime_count = 1\n",
    "list_of_primes = [2]  # make a list of length n\n",
    "number = 3\n",
    "while(prime_count < n):\n",
    "    if is_prime(number, list_of_primes):  # if number is prime\n",
    "        #list_of_primes[prime_count] = number\n",
    "        prime_count += 1\n",
    "        list_of_primes.append(number)\n",
    "    \n",
    "    number += 1\n",
    "    \n",
    "print(list_of_primes[-1])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "n = 10001\n",
    "prime_count = 1\n",
    "list_of_primes = [2]  # make a list of length n\n",
    "number = 3\n",
    "while(prime_count < n):\n",
    "    if is_prime3(number, list_of_primes):  # if number is prime\n",
    "        #list_of_primes[prime_count] = number\n",
    "        prime_count += 1\n",
    "        list_of_primes.append(number)\n",
    "    \n",
    "    number += 1\n",
    "    \n",
    "print(list_of_primes[-1])\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "in_string = \"\"\"\n",
    "73167176531330624919225119674426574742355349194934\n",
    "96983520312774506326239578318016984801869478851843\n",
    "85861560789112949495459501737958331952853208805511\n",
    "12540698747158523863050715693290963295227443043557\n",
    "66896648950445244523161731856403098711121722383113\n",
    "62229893423380308135336276614282806444486645238749\n",
    "30358907296290491560440772390713810515859307960866\n",
    "70172427121883998797908792274921901699720888093776\n",
    "65727333001053367881220235421809751254540594752243\n",
    "52584907711670556013604839586446706324415722155397\n",
    "53697817977846174064955149290862569321978468622482\n",
    "83972241375657056057490261407972968652414535100474\n",
    "82166370484403199890008895243450658541227588666881\n",
    "16427171479924442928230863465674813919123162824586\n",
    "17866458359124566529476545682848912883142607690042\n",
    "24219022671055626321111109370544217506941658960408\n",
    "07198403850962455444362981230987879927244284909188\n",
    "84580156166097919133875499200524063689912560717606\n",
    "05886116467109405077541002256983155200055935729725\n",
    "71636269561882670428252483600823257530420752963450\n",
    "\"\"\".replace('\\n', '')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "in_list = np.array(list(in_string), dtype=int)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 2 µs, sys: 1 µs, total: 3 µs\n",
      "Wall time: 4.05 µs\n",
      "23514624000 [5 5 7 6 6 8 9 6 6 4 8 9 5]\n"
     ]
    }
   ],
   "source": [
    "%time\n",
    "def mult(letters):\n",
    "    accum = 1\n",
    "    for letter in letters:\n",
    "        accum *= int(letter)\n",
    "        \n",
    "    return accum\n",
    "\n",
    "ln = len(in_list)\n",
    "N = 13\n",
    "\n",
    "biggest = 0\n",
    "biggest_i = -1\n",
    "\n",
    "for i in range(ln-N+1):\n",
    "    product = mult(in_list[i:i+N])\n",
    "    if product > biggest:\n",
    "        biggest_i = i\n",
    "        biggest = product\n",
    "\n",
    "print(mult(in_list[biggest_i:biggest_i+N]), in_list[biggest_i:biggest_i+N])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 2 µs, sys: 1 µs, total: 3 µs\n",
      "Wall time: 4.05 µs\n",
      "23514624000 [5 5 7 6 6 8 9 6 6 4 8 9 5]\n"
     ]
    }
   ],
   "source": [
    "%time\n",
    "N = 13\n",
    "\n",
    "biggest = 0\n",
    "biggest_i = -1\n",
    "\n",
    "i = 0\n",
    "while i < ln - N:\n",
    "    sub_number = in_list[i:i+N]\n",
    "    for j, sub_sub in enumerate(sub_number):\n",
    "        if sub_sub == 0:\n",
    "            #print(\"Found 0 at index {:d}\".format(i+j))\n",
    "            i += j + 1\n",
    "            break\n",
    "    #if ('0' in sub_number):\n",
    "    else:  # no zeros\n",
    "        product = mult(sub_number)\n",
    "        \n",
    "        if product > biggest:\n",
    "            biggest_i = i\n",
    "            biggest = product\n",
    " \n",
    "        i = i + 1\n",
    "    \n",
    "    #print(\"Current index: {:d}\".format(i))\n",
    "       \n",
    "print(mult(in_list[biggest_i:biggest_i+N]), in_list[biggest_i:biggest_i+N])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 2 µs, sys: 1 µs, total: 3 µs\n",
      "Wall time: 4.05 µs\n",
      "23514624000 [5 5 7 6 6 8 9 6 6 4 8 9 5]\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/usr/local/lib/python3.5/site-packages/ipykernel/__main__.py:20: RuntimeWarning: invalid value encountered in double_scalars\n",
      "/usr/local/lib/python3.5/site-packages/ipykernel/__main__.py:20: RuntimeWarning: invalid value encountered in long_scalars\n"
     ]
    }
   ],
   "source": [
    "%time\n",
    "N = 13\n",
    "\n",
    "biggest = 0\n",
    "biggest_i = -1\n",
    "\n",
    "product = None #mult(in_list[:N])\n",
    "\n",
    "i = 0\n",
    "while i < ln - N:\n",
    "    new_number = in_list[i+N-1]\n",
    "    \n",
    "    if new_number == 0:\n",
    "        i = i + N \n",
    "        product = None\n",
    "    else:  # not zero\n",
    "        if product is None:\n",
    "            product = mult(in_list[i:i+N])\n",
    "        else:\n",
    "            product /= in_list[i-1]\n",
    "            product *= new_number\n",
    "        \n",
    "        if product > biggest:\n",
    "            biggest_i = i\n",
    "            biggest = product\n",
    " \n",
    "        i = i + 1\n",
    "    \n",
    "    #print(\"Current index: {:d}\".format(i))\n",
    "       \n",
    "print(mult(in_list[biggest_i:biggest_i+N]), in_list[biggest_i:biggest_i+N])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for i, letter in enumerate(['a', 'b', 'c']):\n",
    "    print(i, letter)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 2 µs, sys: 1 µs, total: 3 µs\n",
      "Wall time: 5.01 µs\n",
      "5576689664895\n"
     ]
    }
   ],
   "source": [
    "%time\n",
    "N = 13\n",
    "\n",
    "def test_key(ind_letter):\n",
    "    index = ind_letter[0]\n",
    "    letter = ind_letter[1]\n",
    "    return mult(in_string[index:index+N])\n",
    "\n",
    "biggest_i, _ = max(enumerate(in_string), key=test_key)\n",
    "print(in_string[biggest_i:biggest_i+N])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2000 3750 4250 31875000000\n"
     ]
    }
   ],
   "source": [
    "target = 10000\n",
    "for a in range(1, target):\n",
    "    for b in range(a+1, (target - a)//2+1):\n",
    "        c = target - b - a\n",
    "        if a**2 + b**2 == c**2:\n",
    "            print(a, b, c, a*b*c)\n",
    "            \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "20 5\n",
      "a = 200 b = 375 c = 425\n"
     ]
    }
   ],
   "source": [
    "# m(m+n) == 5000\n",
    "# m > n\n",
    "target = 500\n",
    "for n in range(1, target):\n",
    "    for m in range(n+1, target):\n",
    "        if m*(m + n) == target:\n",
    "            print(m, n)\n",
    "            print(\"a = {:d} b = {:d} c = {:d}\".format(2*m*n, (m**2 - n**2), (m**2 + n**2)))\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def is_prime(number):\n",
    "    if number > 1:\n",
    "        if number == 2:\n",
    "            return True\n",
    "        if number % 2 == 0:\n",
    "            return False\n",
    "        for current in range(3, int(math.sqrt(number) + 1), 2):\n",
    "            if number % current == 0:\n",
    "                return False\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "    \n",
    "def prime_generator(n):\n",
    "    if n % 2 == 0:\n",
    "        i = n-1\n",
    "    else:\n",
    "        i = n\n",
    "    while i > 1:\n",
    "        if is_prime(i):\n",
    "            yield i\n",
    "        i -= 2\n",
    "    if n > 1:\n",
    "        yield 2\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "142913828922"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(prime_generator(2000000))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:\n",
    "Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n).\n",
    "Initially, let p equal 2, the smallest prime number.\n",
    "Enumerate the multiples of p by counting to n from 2p in increments of p, and mark them in the list (these will be 2p, 3p, 4p, ...; the p itself should not be marked).\n",
    "Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.\n",
    "When the algorithm terminates, the numbers remaining not marked in the list are all the primes below n.\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def sieve(N):\n",
    "    list_of_numbers = [False, False, True] + [True]*(N-3)\n",
    "    p = 2\n",
    "\n",
    "    while p*p < N:\n",
    "        for i in range(p+p, N, p):\n",
    "            list_of_numbers[i] = False\n",
    "        # set p to next prime\n",
    "\n",
    "        p += 1\n",
    "        while not list_of_numbers[p]:\n",
    "            p += 1\n",
    "\n",
    "    return np.nonzero(list_of_numbers)[0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "142913828922"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(sieve(2000000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 11"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "number_array = np.loadtxt('Data/pe_problem11.txt', dtype='int')\n",
    "window_size = (4, 4)\n",
    "row_size, column_size = number_array.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "70600674\n"
     ]
    }
   ],
   "source": [
    "largest_product = 0\n",
    "for r in range(row_size-window_size[0]+1):\n",
    "    for c in range(column_size-window_size[1]+1):\n",
    "        # select subset\n",
    "        subset = number_array[r:r+window_size[0],\n",
    "                              c:c+window_size[1]]\n",
    "        horizontal = subset[0]\n",
    "        vertical = subset[:, 0]\n",
    "        diagonal = subset.diagonal()\n",
    "        cross_diagonal = subset.ravel()[3:13:3]\n",
    "        largest_product = max((largest_product, \n",
    "                               np.prod(horizontal),\n",
    "                               np.prod(vertical),\n",
    "                               np.prod(diagonal),\n",
    "                               np.prod(cross_diagonal)))\n",
    "        \n",
    "print(largest_product)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 12"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def prime_factorization(n):\n",
    "    factor = 2\n",
    "    factors = defaultdict(int)\n",
    "    while n > 1:\n",
    "        if n % factor == 0:\n",
    "            n /= factor\n",
    "            factors[factor] += 1\n",
    "        else:\n",
    "            break\n",
    "    factor = 3\n",
    "    while n > 1:\n",
    "        if n % factor == 0:\n",
    "            n /= factor\n",
    "            factors[factor] += 1\n",
    "        else:\n",
    "            factor += 2\n",
    "    return factors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def get_num_factors(n):\n",
    "    prime_factors = prime_factorization(n)\n",
    "    return np.prod(np.array(list(prime_factors.values()))+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "num_factors(28)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "12375 76576500 576\n"
     ]
    }
   ],
   "source": [
    "triangle = 0\n",
    "i = 1\n",
    "num_factors = 0\n",
    "while num_factors < 500:\n",
    "    triangle += i\n",
    "    i += 1\n",
    "    num_factors = get_num_factors(triangle)\n",
    "\n",
    "    \n",
    "print(i-1, triangle, num_factors)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 13"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "numbers = \"\"\"37107287533902102798797998220837590246510135740250\n",
    "46376937677490009712648124896970078050417018260538\n",
    "74324986199524741059474233309513058123726617309629\n",
    "91942213363574161572522430563301811072406154908250\n",
    "23067588207539346171171980310421047513778063246676\n",
    "89261670696623633820136378418383684178734361726757\n",
    "28112879812849979408065481931592621691275889832738\n",
    "44274228917432520321923589422876796487670272189318\n",
    "47451445736001306439091167216856844588711603153276\n",
    "70386486105843025439939619828917593665686757934951\n",
    "62176457141856560629502157223196586755079324193331\n",
    "64906352462741904929101432445813822663347944758178\n",
    "92575867718337217661963751590579239728245598838407\n",
    "58203565325359399008402633568948830189458628227828\n",
    "80181199384826282014278194139940567587151170094390\n",
    "35398664372827112653829987240784473053190104293586\n",
    "86515506006295864861532075273371959191420517255829\n",
    "71693888707715466499115593487603532921714970056938\n",
    "54370070576826684624621495650076471787294438377604\n",
    "53282654108756828443191190634694037855217779295145\n",
    "36123272525000296071075082563815656710885258350721\n",
    "45876576172410976447339110607218265236877223636045\n",
    "17423706905851860660448207621209813287860733969412\n",
    "81142660418086830619328460811191061556940512689692\n",
    "51934325451728388641918047049293215058642563049483\n",
    "62467221648435076201727918039944693004732956340691\n",
    "15732444386908125794514089057706229429197107928209\n",
    "55037687525678773091862540744969844508330393682126\n",
    "18336384825330154686196124348767681297534375946515\n",
    "80386287592878490201521685554828717201219257766954\n",
    "78182833757993103614740356856449095527097864797581\n",
    "16726320100436897842553539920931837441497806860984\n",
    "48403098129077791799088218795327364475675590848030\n",
    "87086987551392711854517078544161852424320693150332\n",
    "59959406895756536782107074926966537676326235447210\n",
    "69793950679652694742597709739166693763042633987085\n",
    "41052684708299085211399427365734116182760315001271\n",
    "65378607361501080857009149939512557028198746004375\n",
    "35829035317434717326932123578154982629742552737307\n",
    "94953759765105305946966067683156574377167401875275\n",
    "88902802571733229619176668713819931811048770190271\n",
    "25267680276078003013678680992525463401061632866526\n",
    "36270218540497705585629946580636237993140746255962\n",
    "24074486908231174977792365466257246923322810917141\n",
    "91430288197103288597806669760892938638285025333403\n",
    "34413065578016127815921815005561868836468420090470\n",
    "23053081172816430487623791969842487255036638784583\n",
    "11487696932154902810424020138335124462181441773470\n",
    "63783299490636259666498587618221225225512486764533\n",
    "67720186971698544312419572409913959008952310058822\n",
    "95548255300263520781532296796249481641953868218774\n",
    "76085327132285723110424803456124867697064507995236\n",
    "37774242535411291684276865538926205024910326572967\n",
    "23701913275725675285653248258265463092207058596522\n",
    "29798860272258331913126375147341994889534765745501\n",
    "18495701454879288984856827726077713721403798879715\n",
    "38298203783031473527721580348144513491373226651381\n",
    "34829543829199918180278916522431027392251122869539\n",
    "40957953066405232632538044100059654939159879593635\n",
    "29746152185502371307642255121183693803580388584903\n",
    "41698116222072977186158236678424689157993532961922\n",
    "62467957194401269043877107275048102390895523597457\n",
    "23189706772547915061505504953922979530901129967519\n",
    "86188088225875314529584099251203829009407770775672\n",
    "11306739708304724483816533873502340845647058077308\n",
    "82959174767140363198008187129011875491310547126581\n",
    "97623331044818386269515456334926366572897563400500\n",
    "42846280183517070527831839425882145521227251250327\n",
    "55121603546981200581762165212827652751691296897789\n",
    "32238195734329339946437501907836945765883352399886\n",
    "75506164965184775180738168837861091527357929701337\n",
    "62177842752192623401942399639168044983993173312731\n",
    "32924185707147349566916674687634660915035914677504\n",
    "99518671430235219628894890102423325116913619626622\n",
    "73267460800591547471830798392868535206946944540724\n",
    "76841822524674417161514036427982273348055556214818\n",
    "97142617910342598647204516893989422179826088076852\n",
    "87783646182799346313767754307809363333018982642090\n",
    "10848802521674670883215120185883543223812876952786\n",
    "71329612474782464538636993009049310363619763878039\n",
    "62184073572399794223406235393808339651327408011116\n",
    "66627891981488087797941876876144230030984490851411\n",
    "60661826293682836764744779239180335110989069790714\n",
    "85786944089552990653640447425576083659976645795096\n",
    "66024396409905389607120198219976047599490197230297\n",
    "64913982680032973156037120041377903785566085089252\n",
    "16730939319872750275468906903707539413042652315011\n",
    "94809377245048795150954100921645863754710598436791\n",
    "78639167021187492431995700641917969777599028300699\n",
    "15368713711936614952811305876380278410754449733078\n",
    "40789923115535562561142322423255033685442488917353\n",
    "44889911501440648020369068063960672322193204149535\n",
    "41503128880339536053299340368006977710650566631954\n",
    "81234880673210146739058568557934581403627822703280\n",
    "82616570773948327592232845941706525094512325230608\n",
    "22918802058777319719839450180888072429661980811197\n",
    "77158542502016545090413245809786882778948721859617\n",
    "72107838435069186155435662884062257473692284509516\n",
    "20849603980134001723930671666823555245252804609722\n",
    "53503534226472524250874054075591789781264330331690\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5537376230390876637302048746832985971773659831892672"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum([int(n) for n in numbers.split('\\n')])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "'5537376230'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "55373762303860"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum([int(n[:12]) for n in numbers.split('\\n')])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 14"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "@lru_cache(maxsize=None)\n",
    "def collatz_chain(N):\n",
    "    #print(N)\n",
    "    if N <= 1:\n",
    "        return 1\n",
    "    elif (N % 2 == 0):\n",
    "        return 1 + collatz_chain(N//2)\n",
    "    else:\n",
    "        return 1 + collatz_chain(3*N + 1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "max_chain = 0\n",
    "max_index = 0\n",
    "for N in range(1, 1000000):\n",
    "    if collatz_chain(N) > max_chain:\n",
    "        max_chain = collatz_chain(N)\n",
    "        max_index = N\n",
    "    #max_chain = max(max_chain, collatz_chain(N))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(525, 837799) 837799\n"
     ]
    }
   ],
   "source": [
    "print(max_chain, max_index)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, 2), (1, 0)]"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tuple1 = (0, 2)\n",
    "tuple2 = (1, 0)\n",
    "\n",
    "def second_value(t):\n",
    "    return t[1]\n",
    "\n",
    "def first_value(t):\n",
    "    return t[0]\n",
    "\n",
    "sorted([tuple1, tuple2], key=lambda t: t[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "second_value(tuple1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "max_chain = (0, 0)\n",
    "for N in range(1, 1000000):\n",
    "    max_chain = max(max_chain, (collatz_chain(N), N), key=lambda t: t[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 15"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['r', 'r', 'r', 'd', 'd', 'd']"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "['r']*3+['d']*3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n",
      "20\n",
      "70\n",
      "252\n"
     ]
    }
   ],
   "source": [
    "for N in range(2, 6):\n",
    "    print(len(set(itertools.permutations(['r']*N+['d']*N))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "137846528820.0\n"
     ]
    }
   ],
   "source": [
    "for N in [20]:\n",
    "    print(math.factorial(2*N)/(math.factorial(N)*\n",
    "                               math.factorial(N)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 16"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "big_num = 2 << 999"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def sum_digits(n):\n",
    "    r = 0\n",
    "    while n:\n",
    "        r, n = r + n % 10, n // 10\n",
    "    return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1366"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum_digits(big_num)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 17"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 528,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " one 3\n",
      " two 3\n",
      " three 5\n",
      " four 4\n",
      " five 4\n",
      " six 3\n",
      " seven 5\n",
      " eight 5\n",
      " nine 4\n",
      " ten 3\n",
      " eleven 6\n",
      " twelve 6\n",
      " thirteen 8\n",
      " fourteen 8\n",
      " fifteen 7\n",
      " sixteen 7\n",
      " seventeen 9\n",
      " eighteen 8\n",
      " nineteen 8\n",
      "twenty  6\n",
      "twenty one 9\n",
      "twenty two 9\n",
      "twenty three 11\n",
      "twenty four 10\n",
      "twenty five 10\n",
      "twenty six 9\n",
      "twenty seven 11\n",
      "twenty eight 11\n",
      "twenty nine 10\n",
      "thirty  6\n",
      "thirty one 9\n",
      "thirty two 9\n",
      "thirty three 11\n",
      "thirty four 10\n",
      "thirty five 10\n",
      "thirty six 9\n",
      "thirty seven 11\n",
      "thirty eight 11\n",
      "thirty nine 10\n",
      "forty  5\n",
      "forty one 8\n",
      "forty two 8\n",
      "forty three 10\n",
      "forty four 9\n",
      "forty five 9\n",
      "forty six 8\n",
      "forty seven 10\n",
      "forty eight 10\n",
      "forty nine 9\n",
      "fifty  5\n",
      "fifty one 8\n",
      "fifty two 8\n",
      "fifty three 10\n",
      "fifty four 9\n",
      "fifty five 9\n",
      "fifty six 8\n",
      "fifty seven 10\n",
      "fifty eight 10\n",
      "fifty nine 9\n",
      "sixty  5\n",
      "sixty one 8\n",
      "sixty two 8\n",
      "sixty three 10\n",
      "sixty four 9\n",
      "sixty five 9\n",
      "sixty six 8\n",
      "sixty seven 10\n",
      "sixty eight 10\n",
      "sixty nine 9\n",
      "seventy  7\n",
      "seventy one 10\n",
      "seventy two 10\n",
      "seventy three 12\n",
      "seventy four 11\n",
      "seventy five 11\n",
      "seventy six 10\n",
      "seventy seven 12\n",
      "seventy eight 12\n",
      "seventy nine 11\n",
      "eighty  6\n",
      "eighty one 9\n",
      "eighty two 9\n",
      "eighty three 11\n",
      "eighty four 10\n",
      "eighty five 10\n",
      "eighty six 9\n",
      "eighty seven 11\n",
      "eighty eight 11\n",
      "eighty nine 10\n",
      "ninety  6\n",
      "ninety one 9\n",
      "ninety two 9\n",
      "ninety three 11\n",
      "ninety four 10\n",
      "ninety five 10\n",
      "ninety six 9\n",
      "ninety seven 11\n",
      "ninety eight 11\n",
      "ninety nine 10\n",
      "one hundred  10\n",
      "one hundred and  one 16\n",
      "one hundred and  two 16\n",
      "one hundred and  three 18\n",
      "one hundred and  four 17\n",
      "one hundred and  five 17\n",
      "one hundred and  six 16\n",
      "one hundred and  seven 18\n",
      "one hundred and  eight 18\n",
      "one hundred and  nine 17\n",
      "one hundred and  ten 16\n",
      "one hundred and  eleven 19\n",
      "one hundred and  twelve 19\n",
      "one hundred and  thirteen 21\n",
      "one hundred and  fourteen 21\n",
      "one hundred and  fifteen 20\n",
      "one hundred and  sixteen 20\n",
      "one hundred and  seventeen 22\n",
      "one hundred and  eighteen 21\n",
      "one hundred and  nineteen 21\n",
      "one hundred and twenty  19\n",
      "one hundred and twenty one 22\n",
      "one hundred and twenty two 22\n",
      "one hundred and twenty three 24\n",
      "one hundred and twenty four 23\n",
      "one hundred and twenty five 23\n",
      "one hundred and twenty six 22\n",
      "one hundred and twenty seven 24\n",
      "one hundred and twenty eight 24\n",
      "one hundred and twenty nine 23\n",
      "one hundred and thirty  19\n",
      "one hundred and thirty one 22\n",
      "one hundred and thirty two 22\n",
      "one hundred and thirty three 24\n",
      "one hundred and thirty four 23\n",
      "one hundred and thirty five 23\n",
      "one hundred and thirty six 22\n",
      "one hundred and thirty seven 24\n",
      "one hundred and thirty eight 24\n",
      "one hundred and thirty nine 23\n",
      "one hundred and forty  18\n",
      "one hundred and forty one 21\n",
      "one hundred and forty two 21\n",
      "one hundred and forty three 23\n",
      "one hundred and forty four 22\n",
      "one hundred and forty five 22\n",
      "one hundred and forty six 21\n",
      "one hundred and forty seven 23\n",
      "one hundred and forty eight 23\n",
      "one hundred and forty nine 22\n",
      "one hundred and fifty  18\n",
      "one hundred and fifty one 21\n",
      "one hundred and fifty two 21\n",
      "one hundred and fifty three 23\n",
      "one hundred and fifty four 22\n",
      "one hundred and fifty five 22\n",
      "one hundred and fifty six 21\n",
      "one hundred and fifty seven 23\n",
      "one hundred and fifty eight 23\n",
      "one hundred and fifty nine 22\n",
      "one hundred and sixty  18\n",
      "one hundred and sixty one 21\n",
      "one hundred and sixty two 21\n",
      "one hundred and sixty three 23\n",
      "one hundred and sixty four 22\n",
      "one hundred and sixty five 22\n",
      "one hundred and sixty six 21\n",
      "one hundred and sixty seven 23\n",
      "one hundred and sixty eight 23\n",
      "one hundred and sixty nine 22\n",
      "one hundred and seventy  20\n",
      "one hundred and seventy one 23\n",
      "one hundred and seventy two 23\n",
      "one hundred and seventy three 25\n",
      "one hundred and seventy four 24\n",
      "one hundred and seventy five 24\n",
      "one hundred and seventy six 23\n",
      "one hundred and seventy seven 25\n",
      "one hundred and seventy eight 25\n",
      "one hundred and seventy nine 24\n",
      "one hundred and eighty  19\n",
      "one hundred and eighty one 22\n",
      "one hundred and eighty two 22\n",
      "one hundred and eighty three 24\n",
      "one hundred and eighty four 23\n",
      "one hundred and eighty five 23\n",
      "one hundred and eighty six 22\n",
      "one hundred and eighty seven 24\n",
      "one hundred and eighty eight 24\n",
      "one hundred and eighty nine 23\n",
      "one hundred and ninety  19\n",
      "one hundred and ninety one 22\n",
      "one hundred and ninety two 22\n",
      "one hundred and ninety three 24\n",
      "one hundred and ninety four 23\n",
      "one hundred and ninety five 23\n",
      "one hundred and ninety six 22\n",
      "one hundred and ninety seven 24\n",
      "one hundred and ninety eight 24\n",
      "one hundred and ninety nine 23\n",
      "two hundred  10\n",
      "two hundred and  one 16\n",
      "two hundred and  two 16\n",
      "two hundred and  three 18\n",
      "two hundred and  four 17\n",
      "two hundred and  five 17\n",
      "two hundred and  six 16\n",
      "two hundred and  seven 18\n",
      "two hundred and  eight 18\n",
      "two hundred and  nine 17\n",
      "two hundred and  ten 16\n",
      "two hundred and  eleven 19\n",
      "two hundred and  twelve 19\n",
      "two hundred and  thirteen 21\n",
      "two hundred and  fourteen 21\n",
      "two hundred and  fifteen 20\n",
      "two hundred and  sixteen 20\n",
      "two hundred and  seventeen 22\n",
      "two hundred and  eighteen 21\n",
      "two hundred and  nineteen 21\n",
      "two hundred and twenty  19\n",
      "two hundred and twenty one 22\n",
      "two hundred and twenty two 22\n",
      "two hundred and twenty three 24\n",
      "two hundred and twenty four 23\n",
      "two hundred and twenty five 23\n",
      "two hundred and twenty six 22\n",
      "two hundred and twenty seven 24\n",
      "two hundred and twenty eight 24\n",
      "two hundred and twenty nine 23\n",
      "two hundred and thirty  19\n",
      "two hundred and thirty one 22\n",
      "two hundred and thirty two 22\n",
      "two hundred and thirty three 24\n",
      "two hundred and thirty four 23\n",
      "two hundred and thirty five 23\n",
      "two hundred and thirty six 22\n",
      "two hundred and thirty seven 24\n",
      "two hundred and thirty eight 24\n",
      "two hundred and thirty nine 23\n",
      "two hundred and forty  18\n",
      "two hundred and forty one 21\n",
      "two hundred and forty two 21\n",
      "two hundred and forty three 23\n",
      "two hundred and forty four 22\n",
      "two hundred and forty five 22\n",
      "two hundred and forty six 21\n",
      "two hundred and forty seven 23\n",
      "two hundred and forty eight 23\n",
      "two hundred and forty nine 22\n",
      "two hundred and fifty  18\n",
      "two hundred and fifty one 21\n",
      "two hundred and fifty two 21\n",
      "two hundred and fifty three 23\n",
      "two hundred and fifty four 22\n",
      "two hundred and fifty five 22\n",
      "two hundred and fifty six 21\n",
      "two hundred and fifty seven 23\n",
      "two hundred and fifty eight 23\n",
      "two hundred and fifty nine 22\n",
      "two hundred and sixty  18\n",
      "two hundred and sixty one 21\n",
      "two hundred and sixty two 21\n",
      "two hundred and sixty three 23\n",
      "two hundred and sixty four 22\n",
      "two hundred and sixty five 22\n",
      "two hundred and sixty six 21\n",
      "two hundred and sixty seven 23\n",
      "two hundred and sixty eight 23\n",
      "two hundred and sixty nine 22\n",
      "two hundred and seventy  20\n",
      "two hundred and seventy one 23\n",
      "two hundred and seventy two 23\n",
      "two hundred and seventy three 25\n",
      "two hundred and seventy four 24\n",
      "two hundred and seventy five 24\n",
      "two hundred and seventy six 23\n",
      "two hundred and seventy seven 25\n",
      "two hundred and seventy eight 25\n",
      "two hundred and seventy nine 24\n",
      "two hundred and eighty  19\n",
      "two hundred and eighty one 22\n",
      "two hundred and eighty two 22\n",
      "two hundred and eighty three 24\n",
      "two hundred and eighty four 23\n",
      "two hundred and eighty five 23\n",
      "two hundred and eighty six 22\n",
      "two hundred and eighty seven 24\n",
      "two hundred and eighty eight 24\n",
      "two hundred and eighty nine 23\n",
      "two hundred and ninety  19\n",
      "two hundred and ninety one 22\n",
      "two hundred and ninety two 22\n",
      "two hundred and ninety three 24\n",
      "two hundred and ninety four 23\n",
      "two hundred and ninety five 23\n",
      "two hundred and ninety six 22\n",
      "two hundred and ninety seven 24\n",
      "two hundred and ninety eight 24\n",
      "two hundred and ninety nine 23\n",
      "three hundred  12\n",
      "three hundred and  one 18\n",
      "three hundred and  two 18\n",
      "three hundred and  three 20\n",
      "three hundred and  four 19\n",
      "three hundred and  five 19\n",
      "three hundred and  six 18\n",
      "three hundred and  seven 20\n",
      "three hundred and  eight 20\n",
      "three hundred and  nine 19\n",
      "three hundred and  ten 18\n",
      "three hundred and  eleven 21\n",
      "three hundred and  twelve 21\n",
      "three hundred and  thirteen 23\n",
      "three hundred and  fourteen 23\n",
      "three hundred and  fifteen 22\n",
      "three hundred and  sixteen 22\n",
      "three hundred and  seventeen 24\n",
      "three hundred and  eighteen 23\n",
      "three hundred and  nineteen 23\n",
      "three hundred and twenty  21\n",
      "three hundred and twenty one 24\n",
      "three hundred and twenty two 24\n",
      "three hundred and twenty three 26\n",
      "three hundred and twenty four 25\n",
      "three hundred and twenty five 25\n",
      "three hundred and twenty six 24\n",
      "three hundred and twenty seven 26\n",
      "three hundred and twenty eight 26\n",
      "three hundred and twenty nine 25\n",
      "three hundred and thirty  21\n",
      "three hundred and thirty one 24\n",
      "three hundred and thirty two 24\n",
      "three hundred and thirty three 26\n",
      "three hundred and thirty four 25\n",
      "three hundred and thirty five 25\n",
      "three hundred and thirty six 24\n",
      "three hundred and thirty seven 26\n",
      "three hundred and thirty eight 26\n",
      "three hundred and thirty nine 25\n",
      "three hundred and forty  20\n",
      "three hundred and forty one 23\n",
      "three hundred and forty two 23\n",
      "three hundred and forty three 25\n",
      "three hundred and forty four 24\n",
      "three hundred and forty five 24\n",
      "three hundred and forty six 23\n",
      "three hundred and forty seven 25\n",
      "three hundred and forty eight 25\n",
      "three hundred and forty nine 24\n",
      "three hundred and fifty  20\n",
      "three hundred and fifty one 23\n",
      "three hundred and fifty two 23\n",
      "three hundred and fifty three 25\n",
      "three hundred and fifty four 24\n",
      "three hundred and fifty five 24\n",
      "three hundred and fifty six 23\n",
      "three hundred and fifty seven 25\n",
      "three hundred and fifty eight 25\n",
      "three hundred and fifty nine 24\n",
      "three hundred and sixty  20\n",
      "three hundred and sixty one 23\n",
      "three hundred and sixty two 23\n",
      "three hundred and sixty three 25\n",
      "three hundred and sixty four 24\n",
      "three hundred and sixty five 24\n",
      "three hundred and sixty six 23\n",
      "three hundred and sixty seven 25\n",
      "three hundred and sixty eight 25\n",
      "three hundred and sixty nine 24\n",
      "three hundred and seventy  22\n",
      "three hundred and seventy one 25\n",
      "three hundred and seventy two 25\n",
      "three hundred and seventy three 27\n",
      "three hundred and seventy four 26\n",
      "three hundred and seventy five 26\n",
      "three hundred and seventy six 25\n",
      "three hundred and seventy seven 27\n",
      "three hundred and seventy eight 27\n",
      "three hundred and seventy nine 26\n",
      "three hundred and eighty  21\n",
      "three hundred and eighty one 24\n",
      "three hundred and eighty two 24\n",
      "three hundred and eighty three 26\n",
      "three hundred and eighty four 25\n",
      "three hundred and eighty five 25\n",
      "three hundred and eighty six 24\n",
      "three hundred and eighty seven 26\n",
      "three hundred and eighty eight 26\n",
      "three hundred and eighty nine 25\n",
      "three hundred and ninety  21\n",
      "three hundred and ninety one 24\n",
      "three hundred and ninety two 24\n",
      "three hundred and ninety three 26\n",
      "three hundred and ninety four 25\n",
      "three hundred and ninety five 25\n",
      "three hundred and ninety six 24\n",
      "three hundred and ninety seven 26\n",
      "three hundred and ninety eight 26\n",
      "three hundred and ninety nine 25\n",
      "four hundred  11\n",
      "four hundred and  one 17\n",
      "four hundred and  two 17\n",
      "four hundred and  three 19\n",
      "four hundred and  four 18\n",
      "four hundred and  five 18\n",
      "four hundred and  six 17\n",
      "four hundred and  seven 19\n",
      "four hundred and  eight 19\n",
      "four hundred and  nine 18\n",
      "four hundred and  ten 17\n",
      "four hundred and  eleven 20\n",
      "four hundred and  twelve 20\n",
      "four hundred and  thirteen 22\n",
      "four hundred and  fourteen 22\n",
      "four hundred and  fifteen 21\n",
      "four hundred and  sixteen 21\n",
      "four hundred and  seventeen 23\n",
      "four hundred and  eighteen 22\n",
      "four hundred and  nineteen 22\n",
      "four hundred and twenty  20\n",
      "four hundred and twenty one 23\n",
      "four hundred and twenty two 23\n",
      "four hundred and twenty three 25\n",
      "four hundred and twenty four 24\n",
      "four hundred and twenty five 24\n",
      "four hundred and twenty six 23\n",
      "four hundred and twenty seven 25\n",
      "four hundred and twenty eight 25\n",
      "four hundred and twenty nine 24\n",
      "four hundred and thirty  20\n",
      "four hundred and thirty one 23\n",
      "four hundred and thirty two 23\n",
      "four hundred and thirty three 25\n",
      "four hundred and thirty four 24\n",
      "four hundred and thirty five 24\n",
      "four hundred and thirty six 23\n",
      "four hundred and thirty seven 25\n",
      "four hundred and thirty eight 25\n",
      "four hundred and thirty nine 24\n",
      "four hundred and forty  19\n",
      "four hundred and forty one 22\n",
      "four hundred and forty two 22\n",
      "four hundred and forty three 24\n",
      "four hundred and forty four 23\n",
      "four hundred and forty five 23\n",
      "four hundred and forty six 22\n",
      "four hundred and forty seven 24\n",
      "four hundred and forty eight 24\n",
      "four hundred and forty nine 23\n",
      "four hundred and fifty  19\n",
      "four hundred and fifty one 22\n",
      "four hundred and fifty two 22\n",
      "four hundred and fifty three 24\n",
      "four hundred and fifty four 23\n",
      "four hundred and fifty five 23\n",
      "four hundred and fifty six 22\n",
      "four hundred and fifty seven 24\n",
      "four hundred and fifty eight 24\n",
      "four hundred and fifty nine 23\n",
      "four hundred and sixty  19\n",
      "four hundred and sixty one 22\n",
      "four hundred and sixty two 22\n",
      "four hundred and sixty three 24\n",
      "four hundred and sixty four 23\n",
      "four hundred and sixty five 23\n",
      "four hundred and sixty six 22\n",
      "four hundred and sixty seven 24\n",
      "four hundred and sixty eight 24\n",
      "four hundred and sixty nine 23\n",
      "four hundred and seventy  21\n",
      "four hundred and seventy one 24\n",
      "four hundred and seventy two 24\n",
      "four hundred and seventy three 26\n",
      "four hundred and seventy four 25\n",
      "four hundred and seventy five 25\n",
      "four hundred and seventy six 24\n",
      "four hundred and seventy seven 26\n",
      "four hundred and seventy eight 26\n",
      "four hundred and seventy nine 25\n",
      "four hundred and eighty  20\n",
      "four hundred and eighty one 23\n",
      "four hundred and eighty two 23\n",
      "four hundred and eighty three 25\n",
      "four hundred and eighty four 24\n",
      "four hundred and eighty five 24\n",
      "four hundred and eighty six 23\n",
      "four hundred and eighty seven 25\n",
      "four hundred and eighty eight 25\n",
      "four hundred and eighty nine 24\n",
      "four hundred and ninety  20\n",
      "four hundred and ninety one 23\n",
      "four hundred and ninety two 23\n",
      "four hundred and ninety three 25\n",
      "four hundred and ninety four 24\n",
      "four hundred and ninety five 24\n",
      "four hundred and ninety six 23\n",
      "four hundred and ninety seven 25\n",
      "four hundred and ninety eight 25\n",
      "four hundred and ninety nine 24\n",
      "five hundred  11\n",
      "five hundred and  one 17\n",
      "five hundred and  two 17\n",
      "five hundred and  three 19\n",
      "five hundred and  four 18\n",
      "five hundred and  five 18\n",
      "five hundred and  six 17\n",
      "five hundred and  seven 19\n",
      "five hundred and  eight 19\n",
      "five hundred and  nine 18\n",
      "five hundred and  ten 17\n",
      "five hundred and  eleven 20\n",
      "five hundred and  twelve 20\n",
      "five hundred and  thirteen 22\n",
      "five hundred and  fourteen 22\n",
      "five hundred and  fifteen 21\n",
      "five hundred and  sixteen 21\n",
      "five hundred and  seventeen 23\n",
      "five hundred and  eighteen 22\n",
      "five hundred and  nineteen 22\n",
      "five hundred and twenty  20\n",
      "five hundred and twenty one 23\n",
      "five hundred and twenty two 23\n",
      "five hundred and twenty three 25\n",
      "five hundred and twenty four 24\n",
      "five hundred and twenty five 24\n",
      "five hundred and twenty six 23\n",
      "five hundred and twenty seven 25\n",
      "five hundred and twenty eight 25\n",
      "five hundred and twenty nine 24\n",
      "five hundred and thirty  20\n",
      "five hundred and thirty one 23\n",
      "five hundred and thirty two 23\n",
      "five hundred and thirty three 25\n",
      "five hundred and thirty four 24\n",
      "five hundred and thirty five 24\n",
      "five hundred and thirty six 23\n",
      "five hundred and thirty seven 25\n",
      "five hundred and thirty eight 25\n",
      "five hundred and thirty nine 24\n",
      "five hundred and forty  19\n",
      "five hundred and forty one 22\n",
      "five hundred and forty two 22\n",
      "five hundred and forty three 24\n",
      "five hundred and forty four 23\n",
      "five hundred and forty five 23\n",
      "five hundred and forty six 22\n",
      "five hundred and forty seven 24\n",
      "five hundred and forty eight 24\n",
      "five hundred and forty nine 23\n",
      "five hundred and fifty  19\n",
      "five hundred and fifty one 22\n",
      "five hundred and fifty two 22\n",
      "five hundred and fifty three 24\n",
      "five hundred and fifty four 23\n",
      "five hundred and fifty five 23\n",
      "five hundred and fifty six 22\n",
      "five hundred and fifty seven 24\n",
      "five hundred and fifty eight 24\n",
      "five hundred and fifty nine 23\n",
      "five hundred and sixty  19\n",
      "five hundred and sixty one 22\n",
      "five hundred and sixty two 22\n",
      "five hundred and sixty three 24\n",
      "five hundred and sixty four 23\n",
      "five hundred and sixty five 23\n",
      "five hundred and sixty six 22\n",
      "five hundred and sixty seven 24\n",
      "five hundred and sixty eight 24\n",
      "five hundred and sixty nine 23\n",
      "five hundred and seventy  21\n",
      "five hundred and seventy one 24\n",
      "five hundred and seventy two 24\n",
      "five hundred and seventy three 26\n",
      "five hundred and seventy four 25\n",
      "five hundred and seventy five 25\n",
      "five hundred and seventy six 24\n",
      "five hundred and seventy seven 26\n",
      "five hundred and seventy eight 26\n",
      "five hundred and seventy nine 25\n",
      "five hundred and eighty  20\n",
      "five hundred and eighty one 23\n",
      "five hundred and eighty two 23\n",
      "five hundred and eighty three 25\n",
      "five hundred and eighty four 24\n",
      "five hundred and eighty five 24\n",
      "five hundred and eighty six 23\n",
      "five hundred and eighty seven 25\n",
      "five hundred and eighty eight 25\n",
      "five hundred and eighty nine 24\n",
      "five hundred and ninety  20\n",
      "five hundred and ninety one 23\n",
      "five hundred and ninety two 23\n",
      "five hundred and ninety three 25\n",
      "five hundred and ninety four 24\n",
      "five hundred and ninety five 24\n",
      "five hundred and ninety six 23\n",
      "five hundred and ninety seven 25\n",
      "five hundred and ninety eight 25\n",
      "five hundred and ninety nine 24\n",
      "six hundred  10\n",
      "six hundred and  one 16\n",
      "six hundred and  two 16\n",
      "six hundred and  three 18\n",
      "six hundred and  four 17\n",
      "six hundred and  five 17\n",
      "six hundred and  six 16\n",
      "six hundred and  seven 18\n",
      "six hundred and  eight 18\n",
      "six hundred and  nine 17\n",
      "six hundred and  ten 16\n",
      "six hundred and  eleven 19\n",
      "six hundred and  twelve 19\n",
      "six hundred and  thirteen 21\n",
      "six hundred and  fourteen 21\n",
      "six hundred and  fifteen 20\n",
      "six hundred and  sixteen 20\n",
      "six hundred and  seventeen 22\n",
      "six hundred and  eighteen 21\n",
      "six hundred and  nineteen 21\n",
      "six hundred and twenty  19\n",
      "six hundred and twenty one 22\n",
      "six hundred and twenty two 22\n",
      "six hundred and twenty three 24\n",
      "six hundred and twenty four 23\n",
      "six hundred and twenty five 23\n",
      "six hundred and twenty six 22\n",
      "six hundred and twenty seven 24\n",
      "six hundred and twenty eight 24\n",
      "six hundred and twenty nine 23\n",
      "six hundred and thirty  19\n",
      "six hundred and thirty one 22\n",
      "six hundred and thirty two 22\n",
      "six hundred and thirty three 24\n",
      "six hundred and thirty four 23\n",
      "six hundred and thirty five 23\n",
      "six hundred and thirty six 22\n",
      "six hundred and thirty seven 24\n",
      "six hundred and thirty eight 24\n",
      "six hundred and thirty nine 23\n",
      "six hundred and forty  18\n",
      "six hundred and forty one 21\n",
      "six hundred and forty two 21\n",
      "six hundred and forty three 23\n",
      "six hundred and forty four 22\n",
      "six hundred and forty five 22\n",
      "six hundred and forty six 21\n",
      "six hundred and forty seven 23\n",
      "six hundred and forty eight 23\n",
      "six hundred and forty nine 22\n",
      "six hundred and fifty  18\n",
      "six hundred and fifty one 21\n",
      "six hundred and fifty two 21\n",
      "six hundred and fifty three 23\n",
      "six hundred and fifty four 22\n",
      "six hundred and fifty five 22\n",
      "six hundred and fifty six 21\n",
      "six hundred and fifty seven 23\n",
      "six hundred and fifty eight 23\n",
      "six hundred and fifty nine 22\n",
      "six hundred and sixty  18\n",
      "six hundred and sixty one 21\n",
      "six hundred and sixty two 21\n",
      "six hundred and sixty three 23\n",
      "six hundred and sixty four 22\n",
      "six hundred and sixty five 22\n",
      "six hundred and sixty six 21\n",
      "six hundred and sixty seven 23\n",
      "six hundred and sixty eight 23\n",
      "six hundred and sixty nine 22\n",
      "six hundred and seventy  20\n",
      "six hundred and seventy one 23\n",
      "six hundred and seventy two 23\n",
      "six hundred and seventy three 25\n",
      "six hundred and seventy four 24\n",
      "six hundred and seventy five 24\n",
      "six hundred and seventy six 23\n",
      "six hundred and seventy seven 25\n",
      "six hundred and seventy eight 25\n",
      "six hundred and seventy nine 24\n",
      "six hundred and eighty  19\n",
      "six hundred and eighty one 22\n",
      "six hundred and eighty two 22\n",
      "six hundred and eighty three 24\n",
      "six hundred and eighty four 23\n",
      "six hundred and eighty five 23\n",
      "six hundred and eighty six 22\n",
      "six hundred and eighty seven 24\n",
      "six hundred and eighty eight 24\n",
      "six hundred and eighty nine 23\n",
      "six hundred and ninety  19\n",
      "six hundred and ninety one 22\n",
      "six hundred and ninety two 22\n",
      "six hundred and ninety three 24\n",
      "six hundred and ninety four 23\n",
      "six hundred and ninety five 23\n",
      "six hundred and ninety six 22\n",
      "six hundred and ninety seven 24\n",
      "six hundred and ninety eight 24\n",
      "six hundred and ninety nine 23\n",
      "seven hundred  12\n",
      "seven hundred and  one 18\n",
      "seven hundred and  two 18\n",
      "seven hundred and  three 20\n",
      "seven hundred and  four 19\n",
      "seven hundred and  five 19\n",
      "seven hundred and  six 18\n",
      "seven hundred and  seven 20\n",
      "seven hundred and  eight 20\n",
      "seven hundred and  nine 19\n",
      "seven hundred and  ten 18\n",
      "seven hundred and  eleven 21\n",
      "seven hundred and  twelve 21\n",
      "seven hundred and  thirteen 23\n",
      "seven hundred and  fourteen 23\n",
      "seven hundred and  fifteen 22\n",
      "seven hundred and  sixteen 22\n",
      "seven hundred and  seventeen 24\n",
      "seven hundred and  eighteen 23\n",
      "seven hundred and  nineteen 23\n",
      "seven hundred and twenty  21\n",
      "seven hundred and twenty one 24\n",
      "seven hundred and twenty two 24\n",
      "seven hundred and twenty three 26\n",
      "seven hundred and twenty four 25\n",
      "seven hundred and twenty five 25\n",
      "seven hundred and twenty six 24\n",
      "seven hundred and twenty seven 26\n",
      "seven hundred and twenty eight 26\n",
      "seven hundred and twenty nine 25\n",
      "seven hundred and thirty  21\n",
      "seven hundred and thirty one 24\n",
      "seven hundred and thirty two 24\n",
      "seven hundred and thirty three 26\n",
      "seven hundred and thirty four 25\n",
      "seven hundred and thirty five 25\n",
      "seven hundred and thirty six 24\n",
      "seven hundred and thirty seven 26\n",
      "seven hundred and thirty eight 26\n",
      "seven hundred and thirty nine 25\n",
      "seven hundred and forty  20\n",
      "seven hundred and forty one 23\n",
      "seven hundred and forty two 23\n",
      "seven hundred and forty three 25\n",
      "seven hundred and forty four 24\n",
      "seven hundred and forty five 24\n",
      "seven hundred and forty six 23\n",
      "seven hundred and forty seven 25\n",
      "seven hundred and forty eight 25\n",
      "seven hundred and forty nine 24\n",
      "seven hundred and fifty  20\n",
      "seven hundred and fifty one 23\n",
      "seven hundred and fifty two 23\n",
      "seven hundred and fifty three 25\n",
      "seven hundred and fifty four 24\n",
      "seven hundred and fifty five 24\n",
      "seven hundred and fifty six 23\n",
      "seven hundred and fifty seven 25\n",
      "seven hundred and fifty eight 25\n",
      "seven hundred and fifty nine 24\n",
      "seven hundred and sixty  20\n",
      "seven hundred and sixty one 23\n",
      "seven hundred and sixty two 23\n",
      "seven hundred and sixty three 25\n",
      "seven hundred and sixty four 24\n",
      "seven hundred and sixty five 24\n",
      "seven hundred and sixty six 23\n",
      "seven hundred and sixty seven 25\n",
      "seven hundred and sixty eight 25\n",
      "seven hundred and sixty nine 24\n",
      "seven hundred and seventy  22\n",
      "seven hundred and seventy one 25\n",
      "seven hundred and seventy two 25\n",
      "seven hundred and seventy three 27\n",
      "seven hundred and seventy four 26\n",
      "seven hundred and seventy five 26\n",
      "seven hundred and seventy six 25\n",
      "seven hundred and seventy seven 27\n",
      "seven hundred and seventy eight 27\n",
      "seven hundred and seventy nine 26\n",
      "seven hundred and eighty  21\n",
      "seven hundred and eighty one 24\n",
      "seven hundred and eighty two 24\n",
      "seven hundred and eighty three 26\n",
      "seven hundred and eighty four 25\n",
      "seven hundred and eighty five 25\n",
      "seven hundred and eighty six 24\n",
      "seven hundred and eighty seven 26\n",
      "seven hundred and eighty eight 26\n",
      "seven hundred and eighty nine 25\n",
      "seven hundred and ninety  21\n",
      "seven hundred and ninety one 24\n",
      "seven hundred and ninety two 24\n",
      "seven hundred and ninety three 26\n",
      "seven hundred and ninety four 25\n",
      "seven hundred and ninety five 25\n",
      "seven hundred and ninety six 24\n",
      "seven hundred and ninety seven 26\n",
      "seven hundred and ninety eight 26\n",
      "seven hundred and ninety nine 25\n",
      "eight hundred  12\n",
      "eight hundred and  one 18\n",
      "eight hundred and  two 18\n",
      "eight hundred and  three 20\n",
      "eight hundred and  four 19\n",
      "eight hundred and  five 19\n",
      "eight hundred and  six 18\n",
      "eight hundred and  seven 20\n",
      "eight hundred and  eight 20\n",
      "eight hundred and  nine 19\n",
      "eight hundred and  ten 18\n",
      "eight hundred and  eleven 21\n",
      "eight hundred and  twelve 21\n",
      "eight hundred and  thirteen 23\n",
      "eight hundred and  fourteen 23\n",
      "eight hundred and  fifteen 22\n",
      "eight hundred and  sixteen 22\n",
      "eight hundred and  seventeen 24\n",
      "eight hundred and  eighteen 23\n",
      "eight hundred and  nineteen 23\n",
      "eight hundred and twenty  21\n",
      "eight hundred and twenty one 24\n",
      "eight hundred and twenty two 24\n",
      "eight hundred and twenty three 26\n",
      "eight hundred and twenty four 25\n",
      "eight hundred and twenty five 25\n",
      "eight hundred and twenty six 24\n",
      "eight hundred and twenty seven 26\n",
      "eight hundred and twenty eight 26\n",
      "eight hundred and twenty nine 25\n",
      "eight hundred and thirty  21\n",
      "eight hundred and thirty one 24\n",
      "eight hundred and thirty two 24\n",
      "eight hundred and thirty three 26\n",
      "eight hundred and thirty four 25\n",
      "eight hundred and thirty five 25\n",
      "eight hundred and thirty six 24\n",
      "eight hundred and thirty seven 26\n",
      "eight hundred and thirty eight 26\n",
      "eight hundred and thirty nine 25\n",
      "eight hundred and forty  20\n",
      "eight hundred and forty one 23\n",
      "eight hundred and forty two 23\n",
      "eight hundred and forty three 25\n",
      "eight hundred and forty four 24\n",
      "eight hundred and forty five 24\n",
      "eight hundred and forty six 23\n",
      "eight hundred and forty seven 25\n",
      "eight hundred and forty eight 25\n",
      "eight hundred and forty nine 24\n",
      "eight hundred and fifty  20\n",
      "eight hundred and fifty one 23\n",
      "eight hundred and fifty two 23\n",
      "eight hundred and fifty three 25\n",
      "eight hundred and fifty four 24\n",
      "eight hundred and fifty five 24\n",
      "eight hundred and fifty six 23\n",
      "eight hundred and fifty seven 25\n",
      "eight hundred and fifty eight 25\n",
      "eight hundred and fifty nine 24\n",
      "eight hundred and sixty  20\n",
      "eight hundred and sixty one 23\n",
      "eight hundred and sixty two 23\n",
      "eight hundred and sixty three 25\n",
      "eight hundred and sixty four 24\n",
      "eight hundred and sixty five 24\n",
      "eight hundred and sixty six 23\n",
      "eight hundred and sixty seven 25\n",
      "eight hundred and sixty eight 25\n",
      "eight hundred and sixty nine 24\n",
      "eight hundred and seventy  22\n",
      "eight hundred and seventy one 25\n",
      "eight hundred and seventy two 25\n",
      "eight hundred and seventy three 27\n",
      "eight hundred and seventy four 26\n",
      "eight hundred and seventy five 26\n",
      "eight hundred and seventy six 25\n",
      "eight hundred and seventy seven 27\n",
      "eight hundred and seventy eight 27\n",
      "eight hundred and seventy nine 26\n",
      "eight hundred and eighty  21\n",
      "eight hundred and eighty one 24\n",
      "eight hundred and eighty two 24\n",
      "eight hundred and eighty three 26\n",
      "eight hundred and eighty four 25\n",
      "eight hundred and eighty five 25\n",
      "eight hundred and eighty six 24\n",
      "eight hundred and eighty seven 26\n",
      "eight hundred and eighty eight 26\n",
      "eight hundred and eighty nine 25\n",
      "eight hundred and ninety  21\n",
      "eight hundred and ninety one 24\n",
      "eight hundred and ninety two 24\n",
      "eight hundred and ninety three 26\n",
      "eight hundred and ninety four 25\n",
      "eight hundred and ninety five 25\n",
      "eight hundred and ninety six 24\n",
      "eight hundred and ninety seven 26\n",
      "eight hundred and ninety eight 26\n",
      "eight hundred and ninety nine 25\n",
      "nine hundred  11\n",
      "nine hundred and  one 17\n",
      "nine hundred and  two 17\n",
      "nine hundred and  three 19\n",
      "nine hundred and  four 18\n",
      "nine hundred and  five 18\n",
      "nine hundred and  six 17\n",
      "nine hundred and  seven 19\n",
      "nine hundred and  eight 19\n",
      "nine hundred and  nine 18\n",
      "nine hundred and  ten 17\n",
      "nine hundred and  eleven 20\n",
      "nine hundred and  twelve 20\n",
      "nine hundred and  thirteen 22\n",
      "nine hundred and  fourteen 22\n",
      "nine hundred and  fifteen 21\n",
      "nine hundred and  sixteen 21\n",
      "nine hundred and  seventeen 23\n",
      "nine hundred and  eighteen 22\n",
      "nine hundred and  nineteen 22\n",
      "nine hundred and twenty  20\n",
      "nine hundred and twenty one 23\n",
      "nine hundred and twenty two 23\n",
      "nine hundred and twenty three 25\n",
      "nine hundred and twenty four 24\n",
      "nine hundred and twenty five 24\n",
      "nine hundred and twenty six 23\n",
      "nine hundred and twenty seven 25\n",
      "nine hundred and twenty eight 25\n",
      "nine hundred and twenty nine 24\n",
      "nine hundred and thirty  20\n",
      "nine hundred and thirty one 23\n",
      "nine hundred and thirty two 23\n",
      "nine hundred and thirty three 25\n",
      "nine hundred and thirty four 24\n",
      "nine hundred and thirty five 24\n",
      "nine hundred and thirty six 23\n",
      "nine hundred and thirty seven 25\n",
      "nine hundred and thirty eight 25\n",
      "nine hundred and thirty nine 24\n",
      "nine hundred and forty  19\n",
      "nine hundred and forty one 22\n",
      "nine hundred and forty two 22\n",
      "nine hundred and forty three 24\n",
      "nine hundred and forty four 23\n",
      "nine hundred and forty five 23\n",
      "nine hundred and forty six 22\n",
      "nine hundred and forty seven 24\n",
      "nine hundred and forty eight 24\n",
      "nine hundred and forty nine 23\n",
      "nine hundred and fifty  19\n",
      "nine hundred and fifty one 22\n",
      "nine hundred and fifty two 22\n",
      "nine hundred and fifty three 24\n",
      "nine hundred and fifty four 23\n",
      "nine hundred and fifty five 23\n",
      "nine hundred and fifty six 22\n",
      "nine hundred and fifty seven 24\n",
      "nine hundred and fifty eight 24\n",
      "nine hundred and fifty nine 23\n",
      "nine hundred and sixty  19\n",
      "nine hundred and sixty one 22\n",
      "nine hundred and sixty two 22\n",
      "nine hundred and sixty three 24\n",
      "nine hundred and sixty four 23\n",
      "nine hundred and sixty five 23\n",
      "nine hundred and sixty six 22\n",
      "nine hundred and sixty seven 24\n",
      "nine hundred and sixty eight 24\n",
      "nine hundred and sixty nine 23\n",
      "nine hundred and seventy  21\n",
      "nine hundred and seventy one 24\n",
      "nine hundred and seventy two 24\n",
      "nine hundred and seventy three 26\n",
      "nine hundred and seventy four 25\n",
      "nine hundred and seventy five 25\n",
      "nine hundred and seventy six 24\n",
      "nine hundred and seventy seven 26\n",
      "nine hundred and seventy eight 26\n",
      "nine hundred and seventy nine 25\n",
      "nine hundred and eighty  20\n",
      "nine hundred and eighty one 23\n",
      "nine hundred and eighty two 23\n",
      "nine hundred and eighty three 25\n",
      "nine hundred and eighty four 24\n",
      "nine hundred and eighty five 24\n",
      "nine hundred and eighty six 23\n",
      "nine hundred and eighty seven 25\n",
      "nine hundred and eighty eight 25\n",
      "nine hundred and eighty nine 24\n",
      "nine hundred and ninety  20\n",
      "nine hundred and ninety one 23\n",
      "nine hundred and ninety two 23\n",
      "nine hundred and ninety three 25\n",
      "nine hundred and ninety four 24\n",
      "nine hundred and ninety five 24\n",
      "nine hundred and ninety six 23\n",
      "nine hundred and ninety seven 25\n",
      "nine hundred and ninety eight 25\n",
      "nine hundred and ninety nine 24\n",
      "one thousand  11\n"
     ]
    }
   ],
   "source": [
    "below_20 = {0: '', 1: 'one', 2: 'two', 3: 'three', 4: 'four', 5: 'five', 6: 'six', 7: 'seven', 8: 'eight', 9: 'nine',\n",
    "         10: 'ten', 11: 'eleven', 12: 'twelve', 13: 'thirteen', 14: 'fourteen', 15: 'fifteen', 16: 'sixteen',\n",
    "         17: 'seventeen', 18: 'eighteen', 19: 'nineteen'}\n",
    "tens = {2: 'twenty', 3: 'thirty', 4: 'forty', 5: 'fifty', 6: 'sixty', 7: 'seventy', 8: 'eighty', 9: 'ninety'}\n",
    "\n",
    "total_length = 0\n",
    "for number in range(1, 1001):\n",
    "#for number in [342, 115]:\n",
    "    if number == 1000:\n",
    "        hundreds_string = 'one thousand'\n",
    "        tens_string = ''\n",
    "        separator_string = ''\n",
    "        ones_string = ''\n",
    "    else:\n",
    "        \n",
    "        tens_place = (number % 100)//10\n",
    "        hundreds_place = (number)//100\n",
    "\n",
    "        if hundreds_place > 0:\n",
    "            hundreds_string = below_20[hundreds_place] + ' hundred'\n",
    "            separator_string = ' and '\n",
    "        else:\n",
    "            hundreds_string = ''\n",
    "            separator_string = ''\n",
    "\n",
    "        if tens_place > 1:\n",
    "            ones_place = number % 10 \n",
    "            tens_string = tens[tens_place]\n",
    "            ones_string = below_20[ones_place]\n",
    "        elif tens_place == 1:\n",
    "            ones_place = number % 100\n",
    "            tens_string = ''\n",
    "            ones_string = below_20[ones_place]\n",
    "\n",
    "        elif tens_place == 0:\n",
    "            tens_string = ''\n",
    "            ones_place = number % 10\n",
    "            if ones_place == 0:\n",
    "                separator_string = ''\n",
    "\n",
    "            ones_string = below_20[ones_place]\n",
    "\n",
    "    full_string = \"{:s}{:s}{:s} {:s}\".format(hundreds_string, separator_string, tens_string, ones_string)\n",
    "    print(full_string, len(full_string.replace(' ', '') ))\n",
    "    total_length += len(full_string.replace(' ', ''))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 514,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 514,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(\"ten hundred\".replace(\" \", \"\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 510,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "11"
      ]
     },
     "execution_count": 510,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(\"onethousand\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 529,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "21124"
      ]
     },
     "execution_count": 529,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "total_length"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 18"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "A = np.array(((3, 0, 0, 0), (7, 4, 0, 0), (2, 4, 6, 0), (8, 5, 9, 3)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[3, 0, 0, 0],\n",
       "       [7, 4, 0, 0],\n",
       "       [2, 4, 6, 0],\n",
       "       [8, 5, 9, 3]])"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "num_rows, num_columns = A.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "path_sum = A[-1].copy()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[8 5 9 3]\n",
      "[10 13 15  3]\n",
      "[20 19 15  3]\n",
      "23\n"
     ]
    }
   ],
   "source": [
    "for r in range(num_rows - 1, 0, -1):  # from num_rows -1 to 1 inclusive\n",
    "    for c in range(0, r):  # to r-1 inclusive\n",
    "        path_sum[c] = max(path_sum[c] + A[r - 1, c],\n",
    "                          path_sum[c + 1] + A[r - 1, c])\n",
    "\n",
    "print(path_sum[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "A = pd.read_table('pe_prob18_triangle.txt', delimiter=' ',\n",
    "                  names=[str(i) for i in range(15)]).values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "num_rows, num_columns = A.shape\n",
    "path_sum = A[-1].copy()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1074.0\n"
     ]
    }
   ],
   "source": [
    "for r in range(num_rows - 1, 0, -1):  # from num_rows -1 to 1 inclusive\n",
    "    for c in range(0, r):  # to r-1 inclusive\n",
    "        path_sum[c] = max(path_sum[c] + A[r - 1, c],\n",
    "                          path_sum[c + 1] + A[r - 1, c])\n",
    "\n",
    "print(path_sum[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[23]\n"
     ]
    }
   ],
   "source": [
    "triangle = [\n",
    "[3],\n",
    "[7, 4],\n",
    "[2, 4, 6],\n",
    "[8, 5, 9, 3]\n",
    "]\n",
    "\n",
    "while len(triangle) > 1:\n",
    "    for i in range(len(triangle[-2])):\n",
    "        entry = triangle[-2][i]\n",
    "        triangle[-2][i] = max(entry+triangle[-1][i],\n",
    "                              entry+triangle[-1][i+1])\n",
    "\n",
    "    triangle = triangle[:-1]\n",
    "\n",
    "print(triangle[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1074]]\n"
     ]
    }
   ],
   "source": [
    "triangle = [\n",
    "[75],\n",
    "[95,64],\n",
    "[17,47,82],\n",
    "[18,35,87,10],\n",
    "[20,4,82,47,65],\n",
    "[19,1,23,75,3,34],\n",
    "[88,2,77,73,7,63,67],\n",
    "[99,65,4,28,6,16,70,92],\n",
    "[41,41,26,56,83,40,80,70,33],\n",
    "[41,48,72,33,47,32,37,16,94,29],\n",
    "[53,71,44,65,25,43,91,52,97,51,14],\n",
    "[70,11,33,28,77,73,17,78,39,68,17,57],\n",
    "[91,71,52,38,17,14,91,43,58,50,27,29,48],\n",
    "[63,66,4,68,89,53,67,30,73,16,69,87,40,31],\n",
    "[4,62,98,27,23,9,70,98,73,93,38,53,60,4,23]]\n",
    "\n",
    "while len(triangle) > 1:\n",
    "    for i in range(len(triangle[-2])):\n",
    "        entry = triangle[-2][i]\n",
    "        triangle[-2][i] = max(entry+triangle[-1][i],\n",
    "                              entry+triangle[-1][i+1])\n",
    "\n",
    "    triangle = triangle[:-1]\n",
    "    \n",
    "print(triangle)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 19"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "days_in_months = [31, 28, 31, 30, 31, 30, 31, 30, 31, 30, 31]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def is_sunday(datetime):\n",
    "    return datetime.weekday() == 6\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "171\n"
     ]
    }
   ],
   "source": [
    "num_first_sundays = 0\n",
    "for year in range(1901, 2001):\n",
    "    for month in range(1, 13):\n",
    "        num_first_sundays += is_sunday(datetime.datetime(year=year, month=month, day=1))\n",
    "        \n",
    "print(num_first_sundays)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 20"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def factorial1(N):  # restricted to positive\n",
    "    \n",
    "    if N == 0:\n",
    "        return 1\n",
    "    \n",
    "    if N < 0:\n",
    "        raise ValueError(\"Cannot use negatives\")\n",
    "\n",
    "    return N*factorial1(N-1)\n",
    "    \n",
    "    \n",
    "def factorial2(N):\n",
    "    holder = 1\n",
    "    for i in range(1, N+1):\n",
    "        holder *= i\n",
    "        \n",
    "    return holder\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "648\n"
     ]
    }
   ],
   "source": [
    "total = 0 \n",
    "for digit in str(factorial1(100)):\n",
    "    total += int(digit)\n",
    "    \n",
    "print(total)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Problem 21"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def prime_factorization(n):\n",
    "    factor = 2\n",
    "    factors = []\n",
    "    while n > 1:\n",
    "        if n % factor == 0:\n",
    "            n /= factor\n",
    "            factors.append(factor)\n",
    "        else:\n",
    "            break\n",
    "    factor = 3\n",
    "    while n > 1:\n",
    "        if n % factor == 0:\n",
    "            n /= factor\n",
    "            factors.append(factor)\n",
    "        else:\n",
    "            factor += 2\n",
    "    return factors\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def mul_reduce(l):\n",
    "    tot = 1\n",
    "    for i in l:\n",
    "        tot *= i\n",
    "        \n",
    "    return tot\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def sum_of_proper_divisors(N):\n",
    "    primes = prime_factorization(N)\n",
    "    primes.append(1)\n",
    "    Nprimes = len(primes)\n",
    "    proper_divisors = set()\n",
    "\n",
    "    for n in range(1, Nprimes+1):\n",
    "        for combo in itertools.combinations(primes, n):\n",
    "            proper_divisors.add(mul_reduce(combo))\n",
    "\n",
    "    d = sum(proper_divisors) - N\n",
    "    return d\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "N = 10000\n",
    "pairs = []\n",
    "\n",
    "for number in range(2, N):\n",
    "    if number in pairs:\n",
    "        continue\n",
    "\n",
    "    d = sum_of_proper_divisors(number)\n",
    "    if number == sum_of_proper_divisors(d) and d != number:\n",
    "        pairs.extend([number, d])\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[220, 284, 1184, 1210, 2620, 2924, 5020, 5564, 6232, 6368]"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pairs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "31626"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(pairs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 530,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def get_proper_divisors(n):\n",
    "    proper_divisors = []\n",
    "    for i in range(n//2, 0, -1):\n",
    "        if n%i == 0:\n",
    "            proper_divisors.append(i)\n",
    "    return proper_divisors\n",
    "\n",
    "\n",
    "def get_next_number(N, checked):\n",
    "    for i, c in enumerate(checked[N:]):\n",
    "        if c is False:\n",
    "            return i+N\n",
    "            break\n",
    "    else:  # no break\n",
    "        return len(checked)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "N = 10000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "i = 2\n",
    "checking = i\n",
    "checked = [False]*N\n",
    "\n",
    "checked[0] = True\n",
    "checked[1] = True\n",
    "\n",
    "amicable_numbers = []\n",
    "\n",
    "while checking < N:\n",
    "    sum_of_pds1 = sum(get_proper_divisors(checking))\n",
    "    checked[checking] = True\n",
    "    \n",
    "    if (sum_of_pds1 < N) and (not checked[sum_of_pds1]):\n",
    "        sum_of_pds2 = sum(get_proper_divisors(sum_of_pds1))\n",
    "        if checking == sum_of_pds2:\n",
    "            amicable_numbers += [checking, sum_of_pds1]  # append\n",
    "            checked[sum_of_pds1] = True\n",
    "            checking = get_next_number(i, checked)\n",
    "            \n",
    "        else:\n",
    "            checking = sum_of_pds1\n",
    "    else:\n",
    "        checking = get_next_number(i, checked)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "31626"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(amicable_numbers)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 22"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "alphadict = {k: i for i, k in enumerate(string.ascii_uppercase)}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "with open('./p022_names.txt') as name_file:\n",
    "    names = name_file.read().replace('\"', '').split(',')\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "name = names[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "STARTNUM = ord('A')-1  # want 'A' to give 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "57"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "871198282"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(map(lambda arg: sum(map(lambda l: ord(l)-(ord('A')-1), arg[1]))*(arg[0]+1),\n",
    "    enumerate(sorted(open('./p022_names.txt').read().replace('\"', '').split(',')))))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "STARTNUM = ord('A')-1  # want 'A' to give 1\n",
    "\n",
    "total_score = 0\n",
    "\n",
    "with open('./p022_names.txt') as name_file:\n",
    "    names= name_file.read().replace('\"', '').split(',')\n",
    "    for i, name in enumerate(sorted(names)):\n",
    "        name_score = sum(ord(letter)-STARTNUM for letter in name)\n",
    "        total_name_score = name_score*(i+1)  # 1 based indexing\n",
    "        total_score += total_name_score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "871198282"
      ]
     },
     "execution_count": 86,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "total_score"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 23"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 554,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def is_abundant(num):\n",
    "    return sum(proper_divs(num)) > num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\n",
    "MUL = int.__mul__\n",
    " \n",
    "def prime_factors(n):\n",
    "    'Map prime factors to their multiplicity for n'\n",
    "    d = _divs(n)\n",
    "    d = [] if d == [n] else (d[:-1] if d[-1] == d else d)\n",
    "    pf = Counter(d)\n",
    "    return dict(pf)\n",
    " \n",
    "@lru_cache(maxsize=None)\n",
    "def _divs(n):\n",
    "    'Memoized recursive function returning prime factors of n as a list'\n",
    "    for i in range(2, int(sqrt(n)+1)):\n",
    "        d, m  = divmod(n, i)\n",
    "        if not m:\n",
    "            return [i] + _divs(d)\n",
    "    return [n]\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def proper_divs(n):\n",
    "    '''Return the set of proper divisors of n.'''\n",
    "    pf = prime_factors(n)\n",
    "    pfactors, occurrences = pf.keys(), pf.values()\n",
    "    multiplicities = itertools.product(*(range(oc + 1) for oc in occurrences))\n",
    "    divs = {reduce(MUL, (pf**m for pf, m in zip(pfactors, multis)), 1)\n",
    "            for multis in multiplicities}\n",
    "    try:\n",
    "        divs.remove(n)\n",
    "    except KeyError:\n",
    "        pass\n",
    "    return divs or ({1} if n != 1 else set())\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1, 2, 4, 7, 14}"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "proper_divs(28)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 576,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "upper_bound = 28123\n",
    "abundant_numbers = []\n",
    "\n",
    "for i in range(1, upper_bound):\n",
    "    if is_abundant(i):\n",
    "        abundant_numbers.append(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 584,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "can_be_made = np.zeros(28124, dtype=bool) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 585,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for combination in itertools.combinations_with_replacement(abundant_numbers, 2):\n",
    "    try:\n",
    "        can_be_made[int(sum(combination))] = True\n",
    "    except IndexError:\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 586,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 586,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "can_be_made[24]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 587,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4179871\n"
     ]
    }
   ],
   "source": [
    "sum_cannot_be_made = 0\n",
    "for i, b in enumerate(can_be_made):\n",
    "    if not b:\n",
    "        sum_cannot_be_made += i\n",
    "        \n",
    "print(sum_cannot_be_made)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 24"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 401,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(2, 7, 8, 3, 9, 1, 5, 4, 6, 0)\n"
     ]
    }
   ],
   "source": [
    "for i, permutation in enumerate(itertools.permutations(list(range(10)), 10)):\n",
    "    if i == 999999:\n",
    "        print(permutation)\n",
    "        break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 25"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def fibonacci(N):\n",
    "    \"\"\"\n",
    "    Return fibonacci number, where N must be > 2\n",
    "    \"\"\"\n",
    "    f1, f2 = 1, 1\n",
    "    yield 1\n",
    "    yield 1\n",
    "    i = 2\n",
    "    while i < N:\n",
    "        f2, f1 = f1 + f2, f2\n",
    "        yield f2\n",
    "        i += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 134,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4782 1070066266382758936764980584457396885083683896632151665013235203375314520604694040621889147582489792657804694888177591957484336466672569959512996030461262748092482186144069433051234774442750273781753087579391666192149259186759553966422837148943113074699503439547001985432609723067290192870526447243726117715821825548491120525013201478612965931381792235559657452039506137551467837543229119602129934048260706175397706847068202895486902666185435124521900369480641357447470911707619766945691070098024393439617474103736912503231365532164773697023167755051595173518460579954919410967778373229665796581646513903488154256310184224190259846088000110186255550245493937113651657039447629584714548523425950428582425306083544435428212611008992863795048006894330309773217834864543113205765659868456288616808718693835297350643986297640660000723562917905207051164077614812491885830945940566688339109350944456576357666151619317753792891661581327159616877487983821820492520348473874384736771934512787029218636250627816\n"
     ]
    }
   ],
   "source": [
    "for i, fib in enumerate(fibonacci(10000)):\n",
    "    if len(str(fib)) >= 1000:\n",
    "        print(i+1, fib)\n",
    "        break\n",
    "else:\n",
    "    print(\"Not found\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 27"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def make_quadratic(a, b):\n",
    "    def _quadratic(n):\n",
    "        return n**2 + a*n + b\n",
    "    \n",
    "    return _quadratic\n",
    "\n",
    "quadratic = make_quadratic(1, 41)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def prime_chain(a, b):\n",
    "    quadratic = make_quadratic(a, b)\n",
    "    N = 0\n",
    "    while is_prime(quadratic(N)):\n",
    "        N += 1\n",
    "        \n",
    "    return N\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(71, -61, 971)\n"
     ]
    }
   ],
   "source": [
    "max_chain = (0, 0, 0)\n",
    "for a in range(-999, 1000):\n",
    "    for b in range(-1000, 1001):\n",
    "        max_chain = max(max_chain, (prime_chain(a, b), a, b), key=lambda x: x[0])\n",
    "        \n",
    "print(max_chain)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-59231"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "-61*971"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 29"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9183\n"
     ]
    }
   ],
   "source": [
    "unique_numbers = set()\n",
    "for a in range(2, 101):\n",
    "    for b in range(2, 101):\n",
    "        unique_numbers.add(a**b)\n",
    "        \n",
    "print(len(unique_numbers))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 30"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 369,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "power = 5\n",
    "accum = 0\n",
    "for i in range(2, 1000000):\n",
    "    str_num = str(i)\n",
    "    sum_ = sum([int(digit)**power for digit in str_num])\n",
    "    if sum_ == i:\n",
    "        accum += i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 370,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "443839\n"
     ]
    }
   ],
   "source": [
    "print(accum)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 32"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def is_pandigital(number):\n",
    "    return Counter(number) == Counter(['1', '2', '3', '4', '5', '6', '7', '8', '9'])\n",
    "           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "45228\n"
     ]
    }
   ],
   "source": [
    "pandigital_products = set()\n",
    "for multiplicand in range(10000):\n",
    "    for multiplier in range(100):\n",
    "        product = multiplicand * multiplier\n",
    "        if is_pandigital(list(str(multiplicand)) +\n",
    "                         list(str(multiplier)) +\n",
    "                         list(str(product))):\n",
    "            pandigital_products.add(product)\n",
    "            \n",
    "print(sum(pandigital_products))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{4396, 5346, 5796, 6952, 7254, 7632, 7852}"
      ]
     },
     "execution_count": 91,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pandigital_products"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 33"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\n",
    "MUL = int.__mul__\n",
    " \n",
    "def prime_factors(n):\n",
    "    'Map prime factors to their multiplicity for n'\n",
    "    d = _divs(n)\n",
    "    d = [] if d == [n] else (d[:-1] if d[-1] == d else d)\n",
    "    pf = Counter(d)\n",
    "    return dict(pf)\n",
    " \n",
    "@lru_cache(maxsize=None)\n",
    "def _divs(n):\n",
    "    'Memoized recursive function returning prime factors of n as a list'\n",
    "    for i in range(2, int(sqrt(n)+1)):\n",
    "        d, m  = divmod(n, i)\n",
    "        if not m:\n",
    "            return [i] + _divs(d)\n",
    "    return [n]\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def proper_divs(n):\n",
    "    '''Return the set of proper divisors of n.'''\n",
    "    pf = prime_factors(n)\n",
    "    pfactors, occurrences = pf.keys(), pf.values()\n",
    "    multiplicities = itertools.product(*(range(oc + 1) for oc in occurrences))\n",
    "    divs = {reduce(MUL, (pf**m for pf, m in zip(pfactors, multis)), 1)\n",
    "            for multis in multiplicities}\n",
    "    try:\n",
    "        divs.remove(n)\n",
    "    except KeyError:\n",
    "        pass\n",
    "    return divs or ({1} if n != 1 else set())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(7.0, 14.0)"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "numerator = 49\n",
    "denomenator = 98\n",
    "largest_common = max(proper_divs(numerator).intersection(proper_divs(denomenator)))\n",
    "numerator/largest_common, denomenator/largest_common"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.5"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "49/98"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 34"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 371,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def factorial(n):\n",
    "    accum = 1\n",
    "    for i in range(1, n+1):\n",
    "        accum *= i\n",
    "    \n",
    "    return accum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 391,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "factorials = [factorial(i) for i in range(10)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 392,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]"
      ]
     },
     "execution_count": 392,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factorials"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 393,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "145\n",
      "40585\n"
     ]
    }
   ],
   "source": [
    "for num in range(3, 1000000):\n",
    "    str_num = str(num)\n",
    "    sum_ = sum([factorials[int(digit)] for digit in str_num])\n",
    "    if sum_ == num:\n",
    "        print(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 394,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "40730"
      ]
     },
     "execution_count": 394,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "145+40585"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 37"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def is_prime(number, list_of_primes):\n",
    "    if number > 1:\n",
    "        for old_prime in list_of_primes:\n",
    "            if old_prime**2 > number:  # if we have gotten past the point of no return\n",
    "                return True\n",
    "\n",
    "            if number % old_prime == 0:\n",
    "                return False\n",
    "\n",
    "        raise RuntimeError(\"Should not have gotten here\")\n",
    "    else:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "n = 11\n",
    "prime_count = 0\n",
    "truncatable_primes = []\n",
    "list_of_primes = [2, 3, 5, 7]  # make a list of length n\n",
    "number = 11\n",
    "while(prime_count < n):\n",
    "    if is_prime(number, list_of_primes):  # if number is prime\n",
    "        list_of_primes.append(number)\n",
    "        \n",
    "        # left -> right\n",
    "        num_str = str(number) \n",
    "        for i in range(len(num_str)):\n",
    "            if not is_prime(int(num_str[i:]), list_of_primes):\n",
    "                break\n",
    "        else:  # no break must be truncatable from left-> right\n",
    "            # Check right -> left\n",
    "            for i in range(len(num_str)):\n",
    "                if not is_prime(int(num_str[:len(num_str)-i]), list_of_primes):\n",
    "                    break\n",
    "            else:  # no break\n",
    "                truncatable_primes.append(number)\n",
    "                prime_count += 1\n",
    "        \n",
    "    number += 2\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "748317"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(truncatable_primes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 38"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "pandigitals = [i for i in itertools.permutations('123456789')]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "N = 500\n",
    "Ns = np.arange(1, 2001)\n",
    "ints = np.arange(1, 11)\n",
    "numbers = Ns[:, None]*ints[None, :]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def is_pandigital(s):\n",
    "    return Counter(s) == Counter('123456789')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "largest_pandigital = (0, 0, 0)\n",
    "for i, number_list in enumerate(map(lambda a: [\"\".join(a.astype('str')[:i])\n",
    "                                          for i in range(1, len(a.astype('str')))],\n",
    "                               numbers)):\n",
    "    for j, number in enumerate(number_list):\n",
    "        if is_pandigital(number):\n",
    "            largest_pandigital = max(largest_pandigital, (int(number), i, j),\n",
    "                                     key=lambda t: t[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "19572"
      ]
     },
     "execution_count": 114,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "9786*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(918273645, 8, 4)"
      ]
     },
     "execution_count": 111,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "largest_pandigital"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "978654312"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 40"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 1\n",
      "10 1\n",
      "100 5\n",
      "1000 3\n",
      "10000 7\n",
      "100000 2\n",
      "1000000 1\n"
     ]
    }
   ],
   "source": [
    "# Empty to start\n",
    "digits = {1: 0, 10: 0, 100: 0, 1000: 0, 10000: 0, 100000: 0, 1000000: 0}\n",
    "num = 0\n",
    "i = 0\n",
    "while i < 1000000:\n",
    "    num += 1\n",
    "    for digit in str(num):\n",
    "        i += 1\n",
    "        if i in digits:\n",
    "            digits[i] = int(digit)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "210"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reduce(int.__mul__, digits.values(), 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 41"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def is_prime(number):\n",
    "    if number > 1:\n",
    "        if number == 2:\n",
    "            return True\n",
    "        if number % 2 == 0:\n",
    "            return False\n",
    "        for current in range(3, int(math.sqrt(number) + 1), 2):\n",
    "            if number % current == 0:\n",
    "                return False\n",
    "        return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "45"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(range(1, 10))  # a 9 digit pandigital is never prime"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "36"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(range(1, 9))  # neither is a 8 digit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 1 False\n",
      "3 3 True\n",
      "4 6 True\n",
      "5 10 False\n",
      "6 15 True\n",
      "7 21 True\n",
      "8 28 False\n",
      "9 36 True\n"
     ]
    }
   ],
   "source": [
    "for N in range(2, 10):\n",
    "    print(N, sum(range(1, N)), sum(range(1, N)) % 3 == 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'123'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reduce(str.__add__, ('1', '2', '3'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n"
     ]
    }
   ],
   "source": [
    "#digits 1-7 give a possibly prime pandigital\n",
    "largest_pandigital = 7654321\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7652413\n"
     ]
    }
   ],
   "source": [
    "for i in itertools.permutations(str(largest_pandigital)):\n",
    "    i = int(reduce(str.__add__, i))\n",
    "    if is_prime(i):\n",
    "        print(i)\n",
    "        break\n",
    "else:\n",
    "    print('None found')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 48"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'9110846700'"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "str(sum(i**i for i in range(1, 1001)))[-10:]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 49"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def is_prime(number):\n",
    "    if number > 1:\n",
    "        if number == 2:\n",
    "            return True\n",
    "        if number % 2 == 0:\n",
    "            return False\n",
    "        for current in range(3, int(math.sqrt(number) + 1), 2):\n",
    "            if number % current == 0:\n",
    "                return False\n",
    "        return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def prime_generator(n):\n",
    "    if n % 2 == 0:\n",
    "        i = n-1\n",
    "    else:\n",
    "        i = n\n",
    "    while i > 1:\n",
    "        if is_prime(i):\n",
    "            yield i\n",
    "        i -= 2\n",
    "    if n > 1:\n",
    "        yield 2\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "prime_list = np.array([prime for prime in prime_generator(10000) if prime > 999])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2969 6299 9629\n"
     ]
    }
   ],
   "source": [
    "class Found(Exception): pass\n",
    "\n",
    "try:\n",
    "    for incr in range(2, 10000, 2):\n",
    "        for prime in prime_list:\n",
    "            if (prime + incr) in prime_list:\n",
    "                if (prime + 2*incr) in prime_list:\n",
    "                    if Counter(str(prime)) == Counter(str(prime + incr)) and\\\n",
    "                       Counter(str(prime)) == Counter(str(prime + incr*2)):\n",
    "                        raise Found\n",
    "except Found:\n",
    "    print(prime, prime + incr, prime + incr*2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(Counter(str(1487)) == Counter(str(1487 + 3330))) and (Counter(str(1487)) == Counter(str(1487 + 3330*2)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 63"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 177,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "49\n"
     ]
    }
   ],
   "source": [
    "# need to also include the number 1\n",
    "\n",
    "number_of_powerful_digits = 1  # 1^1 = 1\n",
    "\n",
    "for power in range(1, 50):\n",
    "    number = str(2**power)\n",
    "    if len(number) == power:\n",
    "        number_of_powerful_digits += 1\n",
    "        #print(\"{number} = {num}^{power}\".format(number=number,\n",
    "        #                                        num=2,\n",
    "        #                                        power=power))\n",
    "    elif len(number) > power:\n",
    "        break # out of outer loop - will never get smaller\n",
    "\n",
    "    for num in range(3, 20):  # don't include 1 so that we can check if we have gone too far\n",
    "        number = str(num**power)\n",
    "        if len(number) == power:\n",
    "            #print(\"{number} = {num}^{power}\".format(number=number,\n",
    "            #                                        num=num,\n",
    "            #                                        power=power))\n",
    "            number_of_powerful_digits += 1\n",
    "        elif len(number) > power:\n",
    "            break # out of inner loop - will never get smaller\n",
    "            \n",
    "print(number_of_powerful_digits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 67"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "triangle = [] \n",
    "with open('p067_triangle.txt', 'r') as f:\n",
    "    for line in f.readlines():\n",
    "        triangle.append([int(n) for n in line.replace('\\n', '').split(' ')])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[7273]\n"
     ]
    }
   ],
   "source": [
    "while len(triangle) > 1:\n",
    "    for i in range(len(triangle[-2])):\n",
    "        entry = triangle[-2][i]\n",
    "        triangle[-2][i] = max(entry+triangle[-1][i],\n",
    "                              entry+triangle[-1][i+1])\n",
    "\n",
    "    triangle = triangle[:-1]\n",
    "\n",
    "print(triangle[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 75"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "sums = defaultdict(int)\n",
    "for n in range(1, 2000):\n",
    "    for m in range(n+1, 2000):\n",
    "        a, b, c = m**2 - n**2, 2*m*n, m**2 + n**2\n",
    "        sums[a+b+c] += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "74035\n"
     ]
    }
   ],
   "source": [
    "count = 0\n",
    "for _sum, val in sums.items():\n",
    "    if _sum <= 1500000 and val == 1:\n",
    "        count += 1\n",
    "\n",
    "print(count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "sums = defaultdict(list)\n",
    "for n in range(1, 1000):\n",
    "    for m in range(n+1, 1000):\n",
    "        for k in range(1, 100):\n",
    "            a, b, c = k*(m**2 - n**2), k*(2*m*n), k*(m**2 + n**2)\n",
    "            if set((a, b, c)) not in sums[a+b+c]:   \n",
    "                sums[a+b+c].append(set((a, b, c)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "109966\n"
     ]
    }
   ],
   "source": [
    "count = 0\n",
    "for _sum, val in sums.items():\n",
    "    if _sum <= 1500000 and len(val) == 1:\n",
    "        count += 1\n",
    "\n",
    "print(count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[{30, 40, 50}, {24, 45, 51}, {20, 48, 52}]"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sums[120]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "sums = defaultdict(list)\n",
    "for combination in itertools.combinations(range(1, 30), 2):\n",
    "    m, n = combination\n",
    "    if n > m:\n",
    "        m, n = n, m\n",
    "    for k in range(1, 20):\n",
    "        a, b, c = k*(m**2 - n**2), k*(2*m*n), k*(m**2 + n**2)\n",
    "        sums[a+b+c].append((a, b, c))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(30, 40, 50),\n",
       " (40, 30, 50),\n",
       " (45, 24, 51),\n",
       " (48, 20, 52),\n",
       " (20, 48, 52),\n",
       " (20, 48, 52)]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sums[120]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 92"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "@lru_cache(maxsize=None)\n",
    "def square_digits(num):\n",
    "    return sum([int(d)**2 for d in str(num)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "get_to_89 = 0\n",
    "for num in range(1, 10000000):\n",
    "    while (num != 1) and (num != 89):\n",
    "        num = square_digits(num)\n",
    "        \n",
    "    if num == 89:\n",
    "        get_to_89 += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8581146"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_to_89"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 97"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8739992577\n"
     ]
    }
   ],
   "source": [
    "last_ten = (2**7830457)%(10**10)\n",
    "last_ten *= 28433\n",
    "last_ten %= (10**10)\n",
    "last_ten += 1\n",
    "print(last_ten)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 98"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 191,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "word_list = []\n",
    "\n",
    "with open('p098_words.txt') as words:\n",
    "    for word in words.readline().split(','):\n",
    "        word_list.append(word.replace('\"', ''))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 213,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def is_anagram(word1, word2):\n",
    "    return Counter(word1) == Counter(word2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 250,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "word_length = defaultdict(list)\n",
    "for word in word_list:\n",
    "    word_length[len(word)].append(word)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 268,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<Container object of 14 artists>"
      ]
     },
     "execution_count": 268,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXoAAAD8CAYAAAB5Pm/hAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAEVdJREFUeJzt3X+s3XV9x/Hna4XhzwiMa1fbuhLXadDMQu4Qx7I4mMoP\nYzFxBLJh51jqEthwIXPgkqnJWFimMs02lipI3RhIEEOj6OyQxJgMsGApPyqjkyLtCr2KII4MB773\nx/12HkrvPefecw/n9rPnIzk53/P5fr/nvG5z+7rf+7nf8z2pKiRJ7fqZcQeQJI2WRS9JjbPoJalx\nFr0kNc6il6TGWfSS1DiLXpIaZ9FLUuMseklq3CHjDgBw1FFH1apVq8YdQ5IOKnfcccf3qmqi33aL\nouhXrVrFli1bxh1Dkg4qSR4aZDunbiSpcX2LPsmLktye5K4k9yb5SDd+VZIHk2ztbmu68ST5ZJId\nSbYlOW7UX4QkaWaDTN08DZxUVT9KcijwjSRf7tb9SVVdv9/2pwKru9ubgMu7e0nSGPQ9oq9pP+oe\nHtrdZru28Vrgs91+twKHJ1k2fFRJ0nwMNEefZEmSrcBeYHNV3datuqSbnrksyWHd2HLg4Z7dd3Vj\n+z/n+iRbkmyZmpoa4kuQJM1moKKvqmerag2wAjg+yRuAi4HXAb8CHAn86VxeuKo2VNVkVU1OTPQ9\nO0iSNE9zOuumqh4HbgFOqao93fTM08BngOO7zXYDK3t2W9GNSZLGYJCzbiaSHN4tvxh4K/DtffPu\nSQKcAdzT7bIJeE939s0JwBNVtWck6SVJfQ1y1s0yYGOSJUz/YLiuqr6Y5GtJJoAAW4E/6La/CTgN\n2AE8Bbx34WNLkgbVt+irahtw7AHGT5ph+wLOGz6a5mrVRV8a+jl2Xnr6AiSRtJj4zlhJapxFL0mN\ns+glqXEWvSQ1zqKXpMZZ9JLUOItekhpn0UtS4yx6SWqcRS9JjbPoJalxFr0kNc6il6TGWfSS1DiL\nXpIaZ9FLUuMG+YQpaST8oBTpheERvSQ1zqKXpMZZ9JLUOItekhrXt+iTvCjJ7UnuSnJvko9040cn\nuS3JjiSfS/Kz3fhh3eMd3fpVo/0SJEmzGeSI/mngpKp6I7AGOCXJCcBfAZdV1S8CPwDO7bY/F/hB\nN35Zt50kaUz6Fn1N+1H38NDuVsBJwPXd+EbgjG55bfeYbv3JSbJgiSVJczLQHH2SJUm2AnuBzcB/\nAI9X1TPdJruA5d3ycuBhgG79E8DPLWRoSdLgBir6qnq2qtYAK4DjgdcN+8JJ1ifZkmTL1NTUsE8n\nSZrBnM66qarHgVuANwOHJ9n3ztoVwO5ueTewEqBb/wrg+wd4rg1VNVlVkxMTE/OML0nqZ5CzbiaS\nHN4tvxh4K7Cd6cJ/d7fZOuDGbnlT95hu/deqqhYytCRpcINc62YZsDHJEqZ/MFxXVV9Mch9wbZK/\nAL4FXNFtfwXwj0l2AI8BZ40gtyRpQH2Lvqq2AcceYPw7TM/X7z/+38BvLUg6SdLQfGesJDXOopek\nxln0ktQ4i16SGucnTKkvPwlKOrh5RC9JjbPoJalxFr0kNc6il6TGWfSS1DiLXpIaZ9FLUuMseklq\nnEUvSY2z6CWpcRa9JDXOopekxln0ktQ4i16SGmfRS1LjLHpJalzfok+yMsktSe5Lcm+SC7rxDyfZ\nnWRrdzutZ5+Lk+xIcn+St4/yC5AkzW6QT5h6Briwqu5M8nLgjiSbu3WXVdVHezdOcgxwFvB64FXA\nvyb5pap6diGDSzPxE7Gk5+p7RF9Ve6rqzm75SWA7sHyWXdYC11bV01X1ILADOH4hwkqS5m5Oc/RJ\nVgHHArd1Q+cn2ZbkyiRHdGPLgYd7dtvF7D8YJEkjNHDRJ3kZ8Hng/VX1Q+By4DXAGmAP8LG5vHCS\n9Um2JNkyNTU1l10lSXMwUNEnOZTpkr+6qm4AqKpHq+rZqvoJ8Cl+Oj2zG1jZs/uKbuw5qmpDVU1W\n1eTExMQwX4MkaRaDnHUT4Apge1V9vGd8Wc9m7wLu6ZY3AWclOSzJ0cBq4PaFiyxJmotBzro5ETgH\nuDvJ1m7sg8DZSdYABewE3gdQVfcmuQ64j+kzds7zjBtJGp++RV9V3wBygFU3zbLPJcAlQ+SSJC0Q\n3xkrSY2z6CWpcRa9JDXOopekxln0ktQ4i16SGmfRS1LjLHpJapxFL0mNs+glqXEWvSQ1zqKXpMZZ\n9JLUOItekhpn0UtS4yx6SWqcRS9JjbPoJalxFr0kNc6il6TGWfSS1Li+RZ9kZZJbktyX5N4kF3Tj\nRybZnOSB7v6IbjxJPplkR5JtSY4b9RchSZrZIEf0zwAXVtUxwAnAeUmOAS4Cbq6q1cDN3WOAU4HV\n3W09cPmCp5YkDaxv0VfVnqq6s1t+EtgOLAfWAhu7zTYCZ3TLa4HP1rRbgcOTLFvw5JKkgcxpjj7J\nKuBY4DZgaVXt6VY9AiztlpcDD/fstqsbkySNwcBFn+RlwOeB91fVD3vXVVUBNZcXTrI+yZYkW6am\npuayqyRpDgYq+iSHMl3yV1fVDd3wo/umZLr7vd34bmBlz+4rurHnqKoNVTVZVZMTExPzzS9J6mOQ\ns24CXAFsr6qP96zaBKzrltcBN/aMv6c7++YE4ImeKR5J0gvskAG2ORE4B7g7ydZu7IPApcB1Sc4F\nHgLO7NbdBJwG7ACeAt67oIklSXPSt+ir6htAZlh98gG2L+C8IXNJkhaI74yVpMZZ9JLUOItekhpn\n0UtS4yx6SWqcRS9JjbPoJalxFr0kNc6il6TGWfSS1DiLXpIaZ9FLUuMseklqnEUvSY0b5Hr0koBV\nF31p6OfYeenpC5BEmhuP6CWpcRa9JDXOopekxln0ktQ4i16SGmfRS1LjLHpJalzfok9yZZK9Se7p\nGftwkt1Jtna303rWXZxkR5L7k7x9VMElSYMZ5Ij+KuCUA4xfVlVruttNAEmOAc4CXt/t8/dJlixU\nWEnS3PUt+qr6OvDYgM+3Fri2qp6uqgeBHcDxQ+STJA1pmDn685Ns66Z2jujGlgMP92yzqxt7niTr\nk2xJsmVqamqIGJKk2cy36C8HXgOsAfYAH5vrE1TVhqqarKrJiYmJecaQJPUzr6Kvqker6tmq+gnw\nKX46PbMbWNmz6YpuTJI0JvMq+iTLeh6+C9h3Rs4m4KwkhyU5GlgN3D5cREnSMPpepjjJNcBbgKOS\n7AI+BLwlyRqggJ3A+wCq6t4k1wH3Ac8A51XVs6OJLkkaRN+ir6qzDzB8xSzbXwJcMkwoSdLC8Z2x\nktQ4i16SGmfRS1LjLHpJapxFL0mNs+glqXEWvSQ1zqKXpMZZ9JLUOItekhpn0UtS4/pe60YLb9VF\nXxr6OXZeevoCJJH0/4FH9JLUOItekhpn0UtS4yx6SWqcRS9JjfOsG2nMFuIsLPBMLM3MI3pJapxF\nL0mNs+glqXF9iz7JlUn2JrmnZ+zIJJuTPNDdH9GNJ8knk+xIsi3JcaMML0nqb5Aj+quAU/Ybuwi4\nuapWAzd3jwFOBVZ3t/XA5QsTU5I0X32Lvqq+Djy23/BaYGO3vBE4o2f8szXtVuDwJMsWKqwkae7m\nO0e/tKr2dMuPAEu75eXAwz3b7erGnifJ+iRbkmyZmpqaZwxJUj9D/zG2qgqoeey3oaomq2pyYmJi\n2BiSpBnMt+gf3Tcl093v7cZ3Ayt7tlvRjUmSxmS+Rb8JWNctrwNu7Bl/T3f2zQnAEz1TPJKkMeh7\nCYQk1wBvAY5Ksgv4EHApcF2Sc4GHgDO7zW8CTgN2AE8B7x1BZknSHPQt+qo6e4ZVJx9g2wLOGzaU\nJGnh+M5YSWqcRS9JjbPoJalxFr0kNc6il6TG+QlTUqP85Crt4xG9JDXOopekxln0ktQ4i16SGmfR\nS1LjLHpJapxFL0mNs+glqXEWvSQ1zqKXpMZZ9JLUOItekhpn0UtS4yx6SWqcRS9JjRvqevRJdgJP\nAs8Cz1TVZJIjgc8Bq4CdwJlV9YPhYkqS5mshjuh/o6rWVNVk9/gi4OaqWg3c3D2WJI3JKKZu1gIb\nu+WNwBkjeA1J0oCGLfoCvprkjiTru7GlVbWnW34EWDrka0iShjDsZ8b+WlXtTvJKYHOSb/eurKpK\nUgfasfvBsB7g1a9+9ZAxJEkzGaroq2p3d783yReA44FHkyyrqj1JlgF7Z9h3A7ABYHJy8oA/DCQt\nPn7o+MFn3lM3SV6a5OX7loG3AfcAm4B13WbrgBuHDSlJmr9hjuiXAl9Isu95/rmqvpLkm8B1Sc4F\nHgLOHD6mJGm+5l30VfUd4I0HGP8+cPIwoSRJC8d3xkpS4yx6SWqcRS9JjbPoJalxFr0kNc6il6TG\nWfSS1DiLXpIaZ9FLUuMseklqnEUvSY0b9nr0zfJSrJJa4RG9JDXOopekxln0ktQ45+glLQr+XWx0\nPKKXpMZZ9JLUOItekhrnHL2kpjn37xG9JDVvZEf0SU4BPgEsAT5dVZeO6rUk6YV2MP2mMJIj+iRL\ngL8DTgWOAc5OcswoXkuSNLtRTd0cD+yoqu9U1Y+Ba4G1I3otSdIsRjV1sxx4uOfxLuBNo3ihg+nX\nJ0kah1TVwj9p8m7glKr6/e7xOcCbqur8nm3WA+u7h68F7geOAr634IFGx7yjd7BlNu9omfe5fqGq\nJvptNKoj+t3Ayp7HK7qx/1NVG4ANvWNJtlTV5IgyLTjzjt7Bltm8o2Xe+RnVHP03gdVJjk7ys8BZ\nwKYRvZYkaRYjOaKvqmeSnA/8C9OnV15ZVfeO4rUkSbMb2Xn0VXUTcNMcd9vQf5NFxbyjd7BlNu9o\nmXceRvLHWEnS4uElECSpcYum6JOckuT+JDuSXDTuPLNJsjLJLUnuS3JvkgvGnWkQSZYk+VaSL447\nSz9JDk9yfZJvJ9me5M3jzjSbJH/cfS/ck+SaJC8ad6b9Jbkyyd4k9/SMHZlkc5IHuvsjxpmx1wx5\n/7r7ntiW5AtJDh9nxl4Hytuz7sIkleSocWRbFEV/EF4y4Rngwqo6BjgBOG+R593nAmD7uEMM6BPA\nV6rqdcAbWcS5kywH/giYrKo3MH0CwlnjTXVAVwGn7Dd2EXBzVa0Gbu4eLxZX8fy8m4E3VNUvA/8O\nXPxCh5rFVTw/L0lWAm8DvvtCB9pnURQ9B9klE6pqT1Xd2S0/yXQJLR9vqtklWQGcDnx63Fn6SfIK\n4NeBKwCq6sdV9fh4U/V1CPDiJIcALwH+c8x5nqeqvg48tt/wWmBjt7wROOMFDTWLA+Wtqq9W1TPd\nw1uZfo/OojDDvy/AZcAHgLH9QXSxFP2BLpmwqItznySrgGOB28abpK+/Yfqb7SfjDjKAo4Ep4DPd\nVNOnk7x03KFmUlW7gY8yfcS2B3iiqr463lQDW1pVe7rlR4Cl4wwzR78HfHncIWaTZC2wu6ruGmeO\nxVL0B6UkLwM+D7y/qn447jwzSfIOYG9V3THuLAM6BDgOuLyqjgX+i8U1pfAc3bz2WqZ/QL0KeGmS\n3xlvqrmr6VPwDorT8JL8GdNTqFePO8tMkrwE+CDw5+POsliKvu8lExabJIcyXfJXV9UN487Tx4nA\nO5PsZHpa7KQk/zTeSLPaBeyqqn2/JV3PdPEvVr8JPFhVU1X1P8ANwK+OOdOgHk2yDKC73zvmPH0l\n+V3gHcBv1+I+P/w1TP/wv6v7v7cCuDPJz7/QQRZL0R9Ul0xIEqbnj7dX1cfHnaefqrq4qlZU1Sqm\n/22/VlWL9oizqh4BHk7y2m7oZOC+MUbq57vACUle0n1vnMwi/uPxfjYB67rldcCNY8zSV/eBRh8A\n3llVT407z2yq6u6qemVVrer+7+0Cjuu+v19Qi6Louz+u7LtkwnbgukV+yYQTgXOYPjLe2t1OG3eo\nxvwhcHWSbcAa4C/HnGdG3W8e1wN3Ancz/f9qUbwjsleSa4B/A16bZFeSc4FLgbcmeYDp30wWzSfB\nzZD3b4GXA5u7/3f/MNaQPWbIuyj4zlhJatyiOKKXJI2ORS9JjbPoJalxFr0kNc6il6TGWfSS1DiL\nXpIaZ9FLUuP+F+odyyMUM+ApAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x108154be0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.bar([i for i in word_length.keys()], [len(val) for val in word_length.values()])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 273,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "anagrams = []\n",
    "for words in word_length.values():\n",
    "    checked = [False]*len(words)\n",
    "    for i, word in enumerate(words):\n",
    "        if checked[i]:\n",
    "            continue  # already checked this word\n",
    "\n",
    "        anagram_list = []\n",
    "        for j, other_word in enumerate(words):\n",
    "            if not checked[j] and is_anagram(word, other_word) and other_word != word:\n",
    "                anagram_list.append(other_word)\n",
    "                checked[j] = True\n",
    "                \n",
    "        if len(anagram_list) > 0:\n",
    "            anagram_list.append(word)\n",
    "            anagrams.append(anagram_list)\n",
    "            \n",
    "        checked[i] = True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 286,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "anagrams_by_length = defaultdict(list)\n",
    "for words in anagrams:\n",
    "    word_length = len(words[0])\n",
    "    anagrams_by_length[word_length].append(words)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 291,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def get_letter_values(word, number):\n",
    "    letter_values = {}\n",
    "    for letter, num in zip(word, number):\n",
    "        if letter in letter_values:\n",
    "            if num != letter_values[letter]:\n",
    "                return None\n",
    "        else:\n",
    "            letter_values[letter] = num \n",
    "\n",
    "    return letter_values\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 307,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "largest_square = int(math.sqrt(10**(max(anagrams_by_length.keys())+1)))\n",
    "square_numbers = [i*i for i in range(largest_square)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 312,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "GOD 169 13.0 DOG 961 31.0\n",
      "TEA 196 14.0 EAT 961 31.0\n",
      "WHO 196 14.0 HOW 961 31.0\n",
      "SIT 196 14.0 ITS 961 31.0\n",
      "OWN 256 16.0 NOW 625 25.0\n",
      "TEA 625 25.0 EAT 256 16.0\n",
      "WHO 625 25.0 HOW 256 16.0\n",
      "SIT 625 25.0 ITS 256 16.0\n",
      "GOD 961 31.0 DOG 169 13.0\n",
      "OWN 961 31.0 NOW 196 14.0\n",
      "NAME 1024 32.0 MEAN 2401 49.0\n",
      "RACE 1296 36.0 CARE 9216 96.0\n",
      "SEAT 1296 36.0 EAST 2916 54.0\n",
      "LIFE 1296 36.0 FILE 9216 96.0\n",
      "TONE 1296 36.0 NOTE 9216 96.0\n",
      "LEAD 1764 42.0 DEAL 4761 69.0\n",
      "THUS 1764 42.0 SHUT 4761 69.0\n",
      "HEAT 1936 44.0 HATE 1369 37.0\n",
      "MEAL 1936 44.0 MALE 1369 37.0\n",
      "RACE 2304 48.0 CARE 324 18.0\n",
      "LIFE 2304 48.0 FILE 324 18.0\n",
      "TONE 2304 48.0 NOTE 324 18.0\n",
      "TEAR 2401 49.0 RATE 1024 32.0\n",
      "NAME 4096 64.0 MEAN 9604 98.0\n",
      "LEAD 4761 69.0 DEAL 1764 42.0\n",
      "THUS 4761 69.0 SHUT 1764 42.0\n",
      "SEAT 7056 84.0 EAST 576 24.0\n",
      "RACE 9216 96.0 CARE 1296 36.0\n",
      "LIFE 9216 96.0 FILE 1296 36.0\n",
      "TONE 9216 96.0 NOTE 1296 36.0\n",
      "TEAR 9604 98.0 RATE 4096 64.0\n",
      "BROAD 18769 137.0 BOARD 17689 133.0\n"
     ]
    }
   ],
   "source": [
    "found_square_numbers = []\n",
    "\n",
    "for square_number in square_numbers:\n",
    "    square_str = str(square_number)\n",
    "    number_length = len(square_str)\n",
    "    try:\n",
    "        anagram_list = anagrams_by_length[number_length]\n",
    "    except KeyError:\n",
    "        continue\n",
    "        \n",
    "    for words in anagram_list:  # get the words that are anagrams with each other\n",
    "        word = words[0]\n",
    "        other_word = words[1]\n",
    "        \n",
    "        if len(set(word)) != len(set(square_str)):\n",
    "            break\n",
    "        \n",
    "        letter_values = get_letter_values(word, square_str)\n",
    "        if letter_values is None:\n",
    "            break  # break out of this loop -- there is not a match between this permutation and letters\n",
    "\n",
    "        number = 0 \n",
    "        for i, letter in enumerate(reversed(word)):\n",
    "            number += int(letter_values[letter])*(10**i)\n",
    "\n",
    "        sqrt = np.sqrt(number)\n",
    "        if sqrt - np.floor(sqrt) != 0:\n",
    "            break\n",
    "\n",
    "        other_number = 0 \n",
    "        for i, letter in enumerate(reversed(other_word)):\n",
    "            other_number += int(letter_values[letter])*(10**i)\n",
    "\n",
    "        other_sqrt = np.sqrt(other_number)\n",
    "        if other_sqrt - np.floor(other_sqrt) == 0:  # both numbers are perfect squares\n",
    "            found_square_numbers.append(number)\n",
    "            found_square_numbers.append(other_number)\n",
    "            print(word, number, sqrt, other_word, other_number, other_sqrt)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 104"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 474,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def is_pandigital(number):\n",
    "    return all([str(i) in number for i in range(1, 10)])\n",
    "\n",
    "def is_pandigital2(number):\n",
    "    return set(number) == set(['1', '2', '3', '4', '5', '6', '7', '8', '9'])\n",
    "           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 479,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def fibonacci_closed(N):\n",
    "    return ((1 + math.sqrt(5))**N - (1 - math.sqrt(5))**N )/(2**N * math.sqrt(5))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 485,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.542248481792631e+20"
      ]
     },
     "execution_count": 485,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fibonacci_closed(100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 478,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "182228it [17:44, 56.92it/s]"
     ]
    },
    {
     "ename": "ValueError",
     "evalue": "I/O operation on closed file",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mValueError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-478-fe8d5b94563a>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0;32mfor\u001b[0m \u001b[0mi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mnumber\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mtqdm\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mtqdm\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0menumerate\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mfibonacci\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1000000\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      2\u001b[0m     \u001b[0mstr_number\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mstr\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnumber\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0;32mif\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mstr_number\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m>\u001b[0m \u001b[0;36m8\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m         \u001b[0;32mif\u001b[0m \u001b[0mis_pandigital2\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mstr_number\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;36m9\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mand\u001b[0m \u001b[0mis_pandigital2\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mstr_number\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m9\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m             \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m+\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mnumber\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m/usr/local/lib/python3.5/site-packages/tqdm/_tqdm.py\u001b[0m in \u001b[0;36m__iter__\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m    739\u001b[0m                              else ncols),\n\u001b[1;32m    740\u001b[0m                             \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mdesc\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mascii\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0munit\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0munit_scale\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 741\u001b[0;31m                             1 / avg_time if avg_time else None, bar_format))\n\u001b[0m\u001b[1;32m    742\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    743\u001b[0m                         \u001b[0;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpos\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m/usr/local/lib/python3.5/site-packages/tqdm/_tqdm.py\u001b[0m in \u001b[0;36mprint_status\u001b[0;34m(s)\u001b[0m\n\u001b[1;32m    115\u001b[0m         \u001b[0;32mdef\u001b[0m \u001b[0mprint_status\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ms\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    116\u001b[0m             \u001b[0mlen_s\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ms\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 117\u001b[0;31m             \u001b[0mfp_write\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'\\r'\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0ms\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0;34m' '\u001b[0m \u001b[0;34m*\u001b[0m \u001b[0mmax\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mlast_len\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0mlen_s\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    118\u001b[0m             \u001b[0mlast_len\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mlen_s\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    119\u001b[0m         \u001b[0;32mreturn\u001b[0m \u001b[0mprint_status\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m/usr/local/lib/python3.5/site-packages/tqdm/_tqdm.py\u001b[0m in \u001b[0;36mfp_write\u001b[0;34m(s)\u001b[0m\n\u001b[1;32m    108\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    109\u001b[0m         \u001b[0;32mdef\u001b[0m \u001b[0mfp_write\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ms\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 110\u001b[0;31m             \u001b[0mfp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mwrite\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0m_unicode\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ms\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    111\u001b[0m             \u001b[0mfp_flush\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    112\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m/usr/local/lib/python3.5/site-packages/ipykernel/iostream.py\u001b[0m in \u001b[0;36mwrite\u001b[0;34m(self, string)\u001b[0m\n\u001b[1;32m    315\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    316\u001b[0m             \u001b[0mis_child\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0;32mnot\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_is_master_process\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 317\u001b[0;31m             \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_buffer\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mwrite\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mstring\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    318\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mis_child\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    319\u001b[0m                 \u001b[0;31m# newlines imply flush in subprocesses\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mValueError\u001b[0m: I/O operation on closed file"
     ]
    }
   ],
   "source": [
    "for i, number in tqdm.tqdm(enumerate(fibonacci(1000000))):\n",
    "    str_number = str(number)\n",
    "    if len(str_number) > 8:\n",
    "        if is_pandigital2(str_number[:9]) and is_pandigital2(str_number[-9:]):\n",
    "            print(i+1, number)\n",
    "            break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 464,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 4 µs, sys: 0 ns, total: 4 µs\n",
      "Wall time: 6.91 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'12343243'"
      ]
     },
     "execution_count": 464,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time str(12343243)[-9:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 470,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def func1():\n",
    "    return str(number)[-9:]\n",
    "\n",
    "def func2():\n",
    "    return str(number % (10**9))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 472,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100000000 loops, best of 3: 17.5 ns per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit func2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 473,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100000000 loops, best of 3: 17.4 ns per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit func1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 112"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 154,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def is_bouncing(str_num):\n",
    "    increasing = True\n",
    "    decreasing = True\n",
    "    bouncing = False\n",
    "\n",
    "    for digit, next_digit in zip(str_num[:-1], str_num[1:]):\n",
    "        if digit > next_digit:\n",
    "            increasing = False\n",
    "        elif digit != next_digit:\n",
    "            decreasing = False\n",
    "\n",
    "        if (not increasing) and (not decreasing):\n",
    "            bouncing = True\n",
    "            break\n",
    "            \n",
    "    return bouncing\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 169,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.99 1587000\n"
     ]
    }
   ],
   "source": [
    "target = 0.99  # percentage of bouncing numbers\n",
    "num_bouncing = 0\n",
    "i = 0\n",
    "percentage = 0\n",
    "while percentage < target:\n",
    "    i += 1\n",
    "    if is_bouncing(str(i)):\n",
    "        num_bouncing += 1\n",
    "    \n",
    "    percentage = num_bouncing/i\n",
    "\n",
    "\n",
    "print(percentage, i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 118"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def is_prime(number):\n",
    "    if number > 1:\n",
    "        if number == 2:\n",
    "            return True\n",
    "        if number % 2 == 0:\n",
    "            return False\n",
    "        for current in range(3, int(math.sqrt(number) + 1), 2):\n",
    "            if number % current == 0:\n",
    "                return False\n",
    "        return True\n",
    "    return False\n",
    "\n",
    "def prime_generator(n):\n",
    "    if n % 2 == 0:\n",
    "        i = n-1\n",
    "    else:\n",
    "        i = n\n",
    "    while i > 1:\n",
    "        if is_prime(i):\n",
    "            yield i\n",
    "        i -= 2\n",
    "    if n > 1:\n",
    "        yield 2\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1, 2, 3, 4, 5, 6, 7, 9) [8]\n",
      "(1, 2, 3, 4, 5, 6, 8, 9) [7]\n",
      "(1, 2, 3, 4, 6, 7, 8, 9) [5]\n",
      "(1, 2, 3, 5, 6, 7, 8, 9) [4]\n",
      "(1, 3, 4, 5, 6, 7, 8, 9) [2]\n",
      "(2, 3, 4, 5, 6, 7, 8, 9) [1]\n"
     ]
    }
   ],
   "source": [
    "digits = list(range(1, 10))\n",
    "for combo in itertools.combinations(digits, 8):\n",
    "    if sum(combo) % 3 != 0:\n",
    "        missing = [i for i in digits if i not in combo]\n",
    "        print(combo, missing)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 110,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "12456789 % 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 145"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def odds_n_evens(n):\n",
    "    if n < 10:\n",
    "        even = n % 2 == 0\n",
    "        return (int(not even), int(even))\n",
    "    n = str(n)\n",
    "    ln = len(n)\n",
    "    odds = 0\n",
    "    evens = 0\n",
    "    for digit1, digit2 in zip(n[:ln//2], n[ln//2:]):\n",
    "        even = int(digit1) % 2 == 0\n",
    "        evens += even\n",
    "        odds += (not even)\n",
    "        \n",
    "        even = int(digit2) % 2 == 0\n",
    "        evens += even\n",
    "        odds += (not even)        \n",
    "\n",
    "    return (odds, evens)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def odds_n_evens_ends(n):\n",
    "    n = str(n)\n",
    "    return (int(n[0]) % 2 == 0) != (int(n[-1]) % 2 == 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def reverse_number(n):\n",
    "    return int(str(n)[::-1])\n",
    "\n",
    "\n",
    "def all_odd(n):\n",
    "    for digit in str(n):\n",
    "        if int(digit) % 2 == 0:\n",
    "            return False\n",
    "    \n",
    "    return True\n",
    "\n",
    "\n",
    "def is_reversable(n):\n",
    "    if n % 10 == 0:\n",
    "        return False\n",
    "    \n",
    "    return all_odd(n+reverse_number(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The slowest run took 4.40 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "1000000 loops, best of 3: 1.64 µs per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "is_reversable(8452354) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The slowest run took 4.16 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "1000000 loops, best of 3: 841 ns per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "odds_n_evens_ends(8452354) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "def func1(N):\n",
    "    num_reversable = 0\n",
    "    for n in range(10, N):\n",
    "        num_reversable += is_reversable(n)    \n",
    "\n",
    "    print(num_reversable)\n",
    "\n",
    "def func2(N):\n",
    "    reversable = {}\n",
    "    for n in range(10, N):\n",
    "        if n not in reversable:\n",
    "            if n % 10 != 0:\n",
    "                rev = reverse_number(n)\n",
    "                result_all_odd = all_odd(n + rev)\n",
    "                reversable[n] = result_all_odd\n",
    "                reversable[rev] = result_all_odd\n",
    "            else:\n",
    "                reversable[n] = False\n",
    "\n",
    "    print(sum(reversable.values()))   \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def func3(N):\n",
    "    reversable = {}\n",
    "    #num_reversable = 0\n",
    "    for n in range(10, N, 10):\n",
    "        base = (10**math.floor(math.log10(n)))\n",
    "        rev_base = reverse_number(n)   \n",
    "        for i in range(1, 10):\n",
    "            if n+i not in reversable:\n",
    "                rev = rev_base + base*i \n",
    "                result_all_odd = all_odd(n+i + rev)\n",
    "                #num_reversable += result_all_odd\n",
    "                reversable[n+i] = result_all_odd\n",
    "                reversable[rev] = result_all_odd\n",
    "            #else:\n",
    "                #num_reversable += reversable[n+i]\n",
    "    \n",
    "    print(sum(reversable.values()))\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "120\n",
      "CPU times: user 1.76 ms, sys: 2 µs, total: 1.76 ms\n",
      "Wall time: 1.76 ms\n",
      "720\n",
      "CPU times: user 17 ms, sys: 319 µs, total: 17.3 ms\n",
      "Wall time: 17.1 ms\n",
      "720\n",
      "CPU times: user 174 ms, sys: 2.07 ms, total: 176 ms\n",
      "Wall time: 174 ms\n"
     ]
    }
   ],
   "source": [
    "for N in [1000, 10000, 100000]:\n",
    "    %time func1(N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "120\n",
      "CPU times: user 1.03 ms, sys: 6 µs, total: 1.03 ms\n",
      "Wall time: 1.04 ms\n",
      "720\n",
      "CPU times: user 9.6 ms, sys: 123 µs, total: 9.72 ms\n",
      "Wall time: 9.66 ms\n",
      "720\n",
      "CPU times: user 105 ms, sys: 1.52 ms, total: 107 ms\n",
      "Wall time: 106 ms\n"
     ]
    }
   ],
   "source": [
    "for N in [1000, 10000, 100000]:\n",
    "    %time func2(N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "120\n",
      "CPU times: user 941 µs, sys: 1 µs, total: 942 µs\n",
      "Wall time: 944 µs\n",
      "720\n",
      "CPU times: user 9.22 ms, sys: 269 µs, total: 9.49 ms\n",
      "Wall time: 9.24 ms\n",
      "720\n",
      "CPU times: user 100 ms, sys: 1.15 ms, total: 101 ms\n",
      "Wall time: 101 ms\n"
     ]
    }
   ],
   "source": [
    "for N in [1000, 10000, 100000]:\n",
    "    %time func3(N)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Problem 571"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "pandigitals = np.array([1023456789, 1023456798, 1023456879, 1023456897, 1023456978, 1023456987, 1023457689,\n",
    "                        1023457698, 1023457869, 1023457896, 1023457968, 1023457986, 1023458679, 1023458697,\n",
    "                        1023458769, 1023458796, 1023458967, 1023458976, 1023459678, 1023459687])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 171,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def change_base(number, orig_base, new_base):\n",
    "    ln = len(number) - 1\n",
    "    new_num = number_to_base(number[0]*(orig_base**(ln-0)), new_base)\n",
    "    for i, digit in enumerate(number[1:]):\n",
    "        new_num_ = number_to_base(digit*(orig_base**(ln-(i+1))), new_base)\n",
    "        next_digit = 0\n",
    "        for i, (digit_1, digit_2) in enumerate(zip(reversed(new_num), reversed(new_num_))):\n",
    "            _next_digit, cur_digit = divmod(digit_1 + digit_2, new_base)\n",
    "            new_num[-(i+1)] = cur_digit + next_digit\n",
    "            next_digit = _next_digit\n",
    "            \n",
    "    return new_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 176,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 86 µs, sys: 0 ns, total: 86 µs\n",
      "Wall time: 90.1 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[3, 2, 1, 1, 2, 3, 2, 0, 3]"
      ]
     },
     "execution_count": 176,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time change_base([1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1], 2, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 175,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 22 µs, sys: 0 ns, total: 22 µs\n",
      "Wall time: 25 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[3, 2, 1, 1, 2, 3, 2, 0, 3]"
      ]
     },
     "execution_count": 175,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time number_to_base(to_base_10([1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1], 2), 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 173,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1]\n",
      "[3, 2, 1, 1, 2, 3, 2, 0, 3]\n"
     ]
    }
   ],
   "source": [
    "print(number_to_base(235235, 2))\n",
    "print(number_to_base(235235, 4))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def number_to_base(n, b):\n",
    "    if n == 0:\n",
    "        return [0]\n",
    "    digits = []\n",
    "    while n:\n",
    "        digits.append(int(n % b))\n",
    "        n //= b\n",
    "    return digits[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def to_base_10(num, base):\n",
    "    output = 0\n",
    "    for i, digit in enumerate(reversed(num)):\n",
    "        output += digit * (base**i)\n",
    "    return output\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def is_pandigital(num, base):\n",
    "    for i in range(base):\n",
    "        if i not in num:\n",
    "            return False\n",
    "    \n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "base = 12\n",
    "starting = base**(base - 1) + sum([d*base**(base - 1 - d) for d in range(2, base)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 207,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 15.6 s, sys: 7.47 ms, total: 15.6 s\n",
      "Wall time: 15.6 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "base = 10\n",
    "super_pandigital = []\n",
    "starting = base**(base - 1) + sum([d*base**(base - 1 - d) for d in range(2, base)])\n",
    "starting = number_to_base(starting, base)\n",
    "for i, num in enumerate(itertools.permutations(starting, base)):\n",
    "    if (len(super_pandigital) > 9):\n",
    "        break\n",
    "    for b in range(base, 1, -1):\n",
    "        _num = number_to_base(to_base_10(num, base), b)\n",
    "        #print(_num, is_pandigital(_num, b))\n",
    "        if not is_pandigital(_num, b):\n",
    "            break\n",
    "    else:  # no break\n",
    "        super_pandigital.append(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "argument to reversed() must be a sequence",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-36-38f6a7fb24e5>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mnumber_to_base\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mto_base_10\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mstarting\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m10\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m12\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-32-77a7c3a7c445>\u001b[0m in \u001b[0;36mto_base_10\u001b[0;34m(num, base)\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mto_base_10\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnum\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mbase\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      2\u001b[0m     \u001b[0moutput\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m     \u001b[0;32mfor\u001b[0m \u001b[0mi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdigit\u001b[0m \u001b[0;32min\u001b[0m \u001b[0menumerate\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mreversed\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnum\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      4\u001b[0m         \u001b[0moutput\u001b[0m \u001b[0;34m+=\u001b[0m \u001b[0mdigit\u001b[0m \u001b[0;34m*\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mbase\u001b[0m\u001b[0;34m**\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m     \u001b[0;32mreturn\u001b[0m \u001b[0moutput\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mTypeError\u001b[0m: argument to reversed() must be a sequence"
     ]
    }
   ],
   "source": [
    "number_to_base(to_base_10(starting, 10), 12)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 202,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 202,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "super_pandigital"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 203,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8514629"
      ]
     },
     "execution_count": 203,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 191,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "479001600"
      ]
     },
     "execution_count": 191,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reduce(int.__mul__, range(1, base+1), 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 180,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "20319792309"
      ]
     },
     "execution_count": 180,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(to_base_10(num, 10) for num in super_pandigital)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "11"
      ]
     },
     "execution_count": 88,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(super_pandigital)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 195,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 0,  1,  3,  6, 10, 15, 21, 28, 36, 45, 55, 66, 78])"
      ]
     },
     "execution_count": 195,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.cumsum(range(13))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [default]",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}