Problem 011 through 020.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import euler # helper functions from previous problems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 11: Largest product in a grid\n",
    "In the 20×20 grid below, four numbers along a diagonal line have been marked in red.\n",
    "```\n",
    "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08\n",
    "49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00\n",
    "81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65\n",
    "52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91\n",
    "22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80\n",
    "24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50\n",
    "32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70\n",
    "67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21\n",
    "24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72\n",
    "21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95\n",
    "78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92\n",
    "16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57\n",
    "86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58\n",
    "19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40\n",
    "04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66\n",
    "88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69\n",
    "04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36\n",
    "20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16\n",
    "20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54\n",
    "01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48\n",
    "```\n",
    "The product of these numbers is 26 × 63 × 78 × 14 = 1788696.\n",
    "\n",
    "What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "window = 4\n",
    "gridstring = \"\"\"08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08\n",
    "49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00\n",
    "81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65\n",
    "52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91\n",
    "22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80\n",
    "24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50\n",
    "32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70\n",
    "67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21\n",
    "24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72\n",
    "21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95\n",
    "78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92\n",
    "16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57\n",
    "86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58\n",
    "19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40\n",
    "04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66\n",
    "88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69\n",
    "04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36\n",
    "20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16\n",
    "20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54\n",
    "01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48\"\"\"\n",
    "grid = [[int(char) for char in line.split(' ')] for line in gridstring.split('\\n')]\n",
    "def yieldhoriz(grid, window):\n",
    "    assert(len(grid[0]) >= window)\n",
    "    for i in grid:\n",
    "        for j in range(len(i) - window + 1):\n",
    "            yield i[j:j + window]\n",
    "def yieldvert(grid, window):\n",
    "    assert((len(grid)) >= window)\n",
    "    for i in range(len(grid[0])):\n",
    "        for j in range(len(grid) - window + 1):\n",
    "            search = []\n",
    "            for k in range(window):\n",
    "                search.append(grid[j + k][i])\n",
    "            yield search\n",
    "def yielddiag(grid, window):\n",
    "    assert(len(grid) >= window and len(grid[0]) >= window)\n",
    "    for i in range(len(grid[0]) - window + 1):\n",
    "        for j in range(len(grid) - window + 1):\n",
    "            search = []\n",
    "            for k in range(window):\n",
    "                search.append(grid[j + k][i + k])\n",
    "            yield search\n",
    "    for i in range(window - 1, len(grid[0])):\n",
    "        for j in range(len(grid) - window + 1):\n",
    "            search = []\n",
    "            for k in range(window):\n",
    "                search.append(grid[j + k][i - k])\n",
    "            yield search\n",
    "def yieldsearch(grid, window):\n",
    "    for x in yieldhoriz(grid, window):\n",
    "        yield x\n",
    "    for x in yieldvert(grid, window):\n",
    "        yield x\n",
    "    for x in yielddiag(grid, window):\n",
    "        yield x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77, 91, 8]\n",
      "Biggest product found was 70600674, which is the product of [89, 94, 97, 87]\n"
     ]
    }
   ],
   "source": [
    "biggest = 0\n",
    "biggestsearch = []\n",
    "print(grid[0])\n",
    "for search in yieldsearch(grid, window):\n",
    "    check = 1\n",
    "    # print(\"Checking\", search)\n",
    "    for number in search:\n",
    "        check *= number\n",
    "    if check > biggest:\n",
    "        biggest = check\n",
    "        biggestsearch = search\n",
    "print(\"Biggest product found was {}, which is the product of {}\".format(biggest, biggestsearch))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 12: Highly divisible triangular number\n",
    "The sequence of triangle numbers is generated by adding the natural numbers. So the 7<sup>th</sup> triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:\n",
    "```\n",
    "1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...\n",
    "```\n",
    "Let us list the factors of the first seven triangle numbers:\n",
    "```\n",
    " 1: 1\n",
    " 3: 1,3\n",
    " 6: 1,2,3,6\n",
    "10: 1,2,5,10\n",
    "15: 1,3,5,15\n",
    "21: 1,3,7,21\n",
    "28: 1,2,4,7,14,28\n",
    "```\n",
    "We can see that 28 is the first triangle number to have over five divisors.\n",
    "\n",
    "What is the value of the first triangle number to have over five hundred divisors?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# added to euler.py\n",
    "def factor_list(number):\n",
    "    \"\"\"Return a sorted list containing all factors of a positive integer, including 1 and itself.\"\"\"\n",
    "    factors = set()\n",
    "    for i in range(1, int(number ** 0.5) + 1):\n",
    "        if not(number % i):\n",
    "            factors.add(i)\n",
    "            factors.add(number // i)\n",
    "    factors = list(factors)\n",
    "    factors.sort()\n",
    "    return factors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# added to euler.py\n",
    "def gen_triangular_numbers():\n",
    "    tri = 0\n",
    "    seq = 0\n",
    "    while True:\n",
    "        seq = seq + 1\n",
    "        tri = tri + seq\n",
    "        yield tri"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Found new triangular number with most divisors:\n",
      " 1 with 1 divisors: [1]\n",
      "Found new triangular number with most divisors:\n",
      " 3 with 2 divisors: [1, 3]\n",
      "Found new triangular number with most divisors:\n",
      " 6 with 4 divisors: [1, 2, 3, 6]\n",
      "Found new triangular number with most divisors:\n",
      " 28 with 6 divisors: [1, 2, 4, 7, 14, 28]\n",
      "Found new triangular number with most divisors:\n",
      " 36 with 9 divisors: [1, 2, 3, 4, 6, 9, 12, 18, 36]\n",
      "Found new triangular number with most divisors:\n",
      " 120 with 16 divisors: [1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120]\n",
      "Found new triangular number with most divisors:\n",
      " 300 with 18 divisors: [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 25, 30, 50, 60, 75, 100, 150, 300]\n",
      "Found new triangular number with most divisors:\n",
      " 528 with 20 divisors: [1, 2, 3, 4, 6, 8, 11, 12, 16, 22, 24, 33, 44, 48, 66, 88, 132, 176, 264, 528]\n",
      "Found new triangular number with most divisors:\n",
      " 630 with 24 divisors: [1, 2, 3, 5, 6, 7, 9, 10, 14, 15, 18, 21, 30, 35, 42, 45, 63, 70, 90, 105, 126, 210, 315, 630]\n",
      "Found new triangular number with most divisors:\n",
      " 2016 with 36 divisors: [1, 2, 3, 4, 6, 7, 8, 9, 12, 14, 16, 18, 21, 24, 28, 32, 36, 42, 48, 56, 63, 72, 84, 96, 112, 126, 144, 168, 224, 252, 288, 336, 504, 672, 1008, 2016]\n",
      "Found new triangular number with most divisors:\n",
      " 3240 with 40 divisors: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 27, 30, 36, 40, 45, 54, 60, 72, 81, 90, 108, 120, 135, 162, 180, 216, 270, 324, 360, 405, 540, 648, 810, 1080, 1620, 3240]\n",
      "Found new triangular number with most divisors:\n",
      " 5460 with 48 divisors: [1, 2, 3, 4, 5, 6, 7, 10, 12, 13, 14, 15, 20, 21, 26, 28, 30, 35, 39, 42, 52, 60, 65, 70, 78, 84, 91, 105, 130, 140, 156, 182, 195, 210, 260, 273, 364, 390, 420, 455, 546, 780, 910, 1092, 1365, 1820, 2730, 5460]\n",
      "Found new triangular number with most divisors:\n",
      " 25200 with 90 divisors: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 28, 30, 35, 36, 40, 42, 45, 48, 50, 56, 60, 63, 70, 72, 75, 80, 84, 90, 100, 105, 112, 120, 126, 140, 144, 150, 168, 175, 180, 200, 210, 225, 240, 252, 280, 300, 315, 336, 350, 360, 400, 420, 450, 504, 525, 560, 600, 630, 700, 720, 840, 900, 1008, 1050, 1200, 1260, 1400, 1575, 1680, 1800, 2100, 2520, 2800, 3150, 3600, 4200, 5040, 6300, 8400, 12600, 25200]\n",
      "Found new triangular number with most divisors:\n",
      " 73920 with 112 divisors: [1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 14, 15, 16, 20, 21, 22, 24, 28, 30, 32, 33, 35, 40, 42, 44, 48, 55, 56, 60, 64, 66, 70, 77, 80, 84, 88, 96, 105, 110, 112, 120, 132, 140, 154, 160, 165, 168, 176, 192, 210, 220, 224, 231, 240, 264, 280, 308, 320, 330, 336, 352, 385, 420, 440, 448, 462, 480, 528, 560, 616, 660, 672, 704, 770, 840, 880, 924, 960, 1056, 1120, 1155, 1232, 1320, 1344, 1540, 1680, 1760, 1848, 2112, 2240, 2310, 2464, 2640, 3080, 3360, 3520, 3696, 4620, 4928, 5280, 6160, 6720, 7392, 9240, 10560, 12320, 14784, 18480, 24640, 36960, 73920]\n",
      "Found new triangular number with most divisors:\n",
      " 157080 with 128 divisors: [1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 14, 15, 17, 20, 21, 22, 24, 28, 30, 33, 34, 35, 40, 42, 44, 51, 55, 56, 60, 66, 68, 70, 77, 84, 85, 88, 102, 105, 110, 119, 120, 132, 136, 140, 154, 165, 168, 170, 187, 204, 210, 220, 231, 238, 255, 264, 280, 308, 330, 340, 357, 374, 385, 408, 420, 440, 462, 476, 510, 561, 595, 616, 660, 680, 714, 748, 770, 840, 924, 935, 952, 1020, 1122, 1155, 1190, 1309, 1320, 1428, 1496, 1540, 1785, 1848, 1870, 2040, 2244, 2310, 2380, 2618, 2805, 2856, 3080, 3570, 3740, 3927, 4488, 4620, 4760, 5236, 5610, 6545, 7140, 7480, 7854, 9240, 10472, 11220, 13090, 14280, 15708, 19635, 22440, 26180, 31416, 39270, 52360, 78540, 157080]\n",
      "Found new triangular number with most divisors:\n",
      " 437580 with 144 divisors: [1, 2, 3, 4, 5, 6, 9, 10, 11, 12, 13, 15, 17, 18, 20, 22, 26, 30, 33, 34, 36, 39, 44, 45, 51, 52, 55, 60, 65, 66, 68, 78, 85, 90, 99, 102, 110, 117, 130, 132, 143, 153, 156, 165, 170, 180, 187, 195, 198, 204, 220, 221, 234, 255, 260, 286, 306, 330, 340, 374, 390, 396, 429, 442, 468, 495, 510, 561, 572, 585, 612, 660, 663, 715, 748, 765, 780, 858, 884, 935, 990, 1020, 1105, 1122, 1170, 1287, 1326, 1430, 1530, 1683, 1716, 1870, 1980, 1989, 2145, 2210, 2244, 2340, 2431, 2574, 2652, 2805, 2860, 3060, 3315, 3366, 3740, 3978, 4290, 4420, 4862, 5148, 5610, 6435, 6630, 6732, 7293, 7956, 8415, 8580, 9724, 9945, 11220, 12155, 12870, 13260, 14586, 16830, 19890, 21879, 24310, 25740, 29172, 33660, 36465, 39780, 43758, 48620, 72930, 87516, 109395, 145860, 218790, 437580]\n",
      "Found new triangular number with most divisors:\n",
      " 749700 with 162 divisors: [1, 2, 3, 4, 5, 6, 7, 9, 10, 12, 14, 15, 17, 18, 20, 21, 25, 28, 30, 34, 35, 36, 42, 45, 49, 50, 51, 60, 63, 68, 70, 75, 84, 85, 90, 98, 100, 102, 105, 119, 126, 140, 147, 150, 153, 170, 175, 180, 196, 204, 210, 225, 238, 245, 252, 255, 294, 300, 306, 315, 340, 350, 357, 420, 425, 441, 450, 476, 490, 510, 525, 588, 595, 612, 630, 700, 714, 735, 765, 833, 850, 882, 900, 980, 1020, 1050, 1071, 1190, 1225, 1260, 1275, 1428, 1470, 1530, 1575, 1666, 1700, 1764, 1785, 2100, 2142, 2205, 2380, 2450, 2499, 2550, 2940, 2975, 3060, 3150, 3332, 3570, 3675, 3825, 4165, 4284, 4410, 4900, 4998, 5100, 5355, 5950, 6300, 7140, 7350, 7497, 7650, 8330, 8820, 8925, 9996, 10710, 11025, 11900, 12495, 14700, 14994, 15300, 16660, 17850, 20825, 21420, 22050, 24990, 26775, 29988, 35700, 37485, 41650, 44100, 49980, 53550, 62475, 74970, 83300, 107100, 124950, 149940, 187425, 249900, 374850, 749700]\n",
      "Found new triangular number with most divisors:\n",
      " 1385280 with 168 divisors: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 13, 15, 16, 18, 20, 24, 26, 30, 32, 36, 37, 39, 40, 45, 48, 52, 60, 64, 65, 72, 74, 78, 80, 90, 96, 104, 111, 117, 120, 130, 144, 148, 156, 160, 180, 185, 192, 195, 208, 222, 234, 240, 260, 288, 296, 312, 320, 333, 360, 370, 390, 416, 444, 468, 480, 481, 520, 555, 576, 585, 592, 624, 666, 720, 740, 780, 832, 888, 936, 960, 962, 1040, 1110, 1170, 1184, 1248, 1332, 1440, 1443, 1480, 1560, 1665, 1776, 1872, 1924, 2080, 2220, 2340, 2368, 2405, 2496, 2664, 2880, 2886, 2960, 3120, 3330, 3552, 3744, 3848, 4160, 4329, 4440, 4680, 4810, 5328, 5772, 5920, 6240, 6660, 7104, 7215, 7488, 7696, 8658, 8880, 9360, 9620, 10656, 11544, 11840, 12480, 13320, 14430, 15392, 17316, 17760, 18720, 19240, 21312, 21645, 23088, 26640, 28860, 30784, 34632, 35520, 37440, 38480, 43290, 46176, 53280, 57720, 69264, 76960, 86580, 92352, 106560, 115440, 138528, 153920, 173160, 230880, 277056, 346320, 461760, 692640, 1385280]\n",
      "Found new triangular number with most divisors:\n",
      " 1493856 with 192 divisors: [1, 2, 3, 4, 6, 7, 8, 9, 12, 13, 14, 16, 18, 19, 21, 24, 26, 27, 28, 32, 36, 38, 39, 42, 48, 52, 54, 56, 57, 63, 72, 76, 78, 84, 91, 96, 104, 108, 112, 114, 117, 126, 133, 144, 152, 156, 168, 171, 182, 189, 208, 216, 224, 228, 234, 247, 252, 266, 273, 288, 304, 312, 336, 342, 351, 364, 378, 399, 416, 432, 456, 468, 494, 504, 513, 532, 546, 608, 624, 672, 684, 702, 728, 741, 756, 798, 819, 864, 912, 936, 988, 1008, 1026, 1064, 1092, 1197, 1248, 1368, 1404, 1456, 1482, 1512, 1596, 1638, 1729, 1824, 1872, 1976, 2016, 2052, 2128, 2184, 2223, 2394, 2457, 2736, 2808, 2912, 2964, 3024, 3192, 3276, 3458, 3591, 3744, 3952, 4104, 4256, 4368, 4446, 4788, 4914, 5187, 5472, 5616, 5928, 6048, 6384, 6552, 6669, 6916, 7182, 7904, 8208, 8736, 8892, 9576, 9828, 10374, 11232, 11856, 12768, 13104, 13338, 13832, 14364, 15561, 16416, 17784, 19152, 19656, 20748, 23712, 26208, 26676, 27664, 28728, 31122, 35568, 38304, 39312, 41496, 46683, 53352, 55328, 57456, 62244, 71136, 78624, 82992, 93366, 106704, 114912, 124488, 165984, 186732, 213408, 248976, 373464, 497952, 746928, 1493856]\n",
      "Found new triangular number with most divisors:\n",
      " 2031120 with 240 divisors: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 18, 20, 21, 24, 26, 28, 30, 31, 35, 36, 39, 40, 42, 45, 48, 52, 56, 60, 62, 63, 65, 70, 72, 78, 80, 84, 90, 91, 93, 104, 105, 112, 117, 120, 124, 126, 130, 140, 144, 155, 156, 168, 180, 182, 186, 195, 208, 210, 217, 234, 240, 248, 252, 260, 273, 279, 280, 310, 312, 315, 336, 360, 364, 372, 390, 403, 420, 434, 455, 465, 468, 496, 504, 520, 546, 558, 560, 585, 620, 624, 630, 651, 720, 728, 744, 780, 806, 819, 840, 868, 910, 930, 936, 1008, 1040, 1085, 1092, 1116, 1170, 1209, 1240, 1260, 1302, 1365, 1395, 1456, 1488, 1560, 1612, 1638, 1680, 1736, 1820, 1860, 1872, 1953, 2015, 2170, 2184, 2232, 2340, 2418, 2480, 2520, 2604, 2730, 2790, 2821, 3120, 3224, 3255, 3276, 3472, 3627, 3640, 3720, 3906, 4030, 4095, 4340, 4368, 4464, 4680, 4836, 5040, 5208, 5460, 5580, 5642, 6045, 6448, 6510, 6552, 7254, 7280, 7440, 7812, 8060, 8190, 8463, 8680, 9360, 9672, 9765, 10416, 10920, 11160, 11284, 12090, 13020, 13104, 14105, 14508, 15624, 16120, 16380, 16926, 17360, 18135, 19344, 19530, 21840, 22320, 22568, 24180, 25389, 26040, 28210, 29016, 31248, 32240, 32760, 33852, 36270, 39060, 42315, 45136, 48360, 50778, 52080, 56420, 58032, 65520, 67704, 72540, 78120, 84630, 96720, 101556, 112840, 126945, 135408, 145080, 156240, 169260, 203112, 225680, 253890, 290160, 338520, 406224, 507780, 677040, 1015560, 2031120]\n",
      "Found new triangular number with most divisors:\n",
      " 2162160 with 320 divisors: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 21, 22, 24, 26, 27, 28, 30, 33, 35, 36, 39, 40, 42, 44, 45, 48, 52, 54, 55, 56, 60, 63, 65, 66, 70, 72, 77, 78, 80, 84, 88, 90, 91, 99, 104, 105, 108, 110, 112, 117, 120, 126, 130, 132, 135, 140, 143, 144, 154, 156, 165, 168, 176, 180, 182, 189, 195, 198, 208, 210, 216, 220, 231, 234, 240, 252, 260, 264, 270, 273, 280, 286, 297, 308, 312, 315, 330, 336, 351, 360, 364, 378, 385, 390, 396, 420, 429, 432, 440, 455, 462, 468, 495, 504, 520, 528, 540, 546, 560, 572, 585, 594, 616, 624, 630, 660, 693, 702, 715, 720, 728, 756, 770, 780, 792, 819, 840, 858, 880, 910, 924, 936, 945, 990, 1001, 1008, 1040, 1080, 1092, 1144, 1155, 1170, 1188, 1232, 1260, 1287, 1320, 1365, 1386, 1404, 1430, 1456, 1485, 1512, 1540, 1560, 1584, 1638, 1680, 1716, 1755, 1820, 1848, 1872, 1890, 1980, 2002, 2079, 2145, 2160, 2184, 2288, 2310, 2340, 2376, 2457, 2520, 2574, 2640, 2730, 2772, 2808, 2860, 2970, 3003, 3024, 3080, 3120, 3276, 3432, 3465, 3510, 3640, 3696, 3780, 3861, 3960, 4004, 4095, 4158, 4290, 4368, 4620, 4680, 4752, 4914, 5005, 5040, 5148, 5460, 5544, 5616, 5720, 5940, 6006, 6160, 6435, 6552, 6864, 6930, 7020, 7280, 7560, 7722, 7920, 8008, 8190, 8316, 8580, 9009, 9240, 9360, 9828, 10010, 10296, 10395, 10920, 11088, 11440, 11880, 12012, 12285, 12870, 13104, 13860, 14040, 15015, 15120, 15444, 16016, 16380, 16632, 17160, 18018, 18480, 19305, 19656, 20020, 20592, 20790, 21840, 23760, 24024, 24570, 25740, 27027, 27720, 28080, 30030, 30888, 32760, 33264, 34320, 36036, 38610, 39312, 40040, 41580, 45045, 48048, 49140, 51480, 54054, 55440, 60060, 61776, 65520, 72072, 77220, 80080, 83160, 90090, 98280, 102960, 108108, 120120, 135135, 144144, 154440, 166320, 180180, 196560, 216216, 240240, 270270, 308880, 360360, 432432, 540540, 720720, 1081080, 2162160]\n",
      "Found new triangular number with most divisors:\n",
      " 17907120 with 480 divisors: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 28, 30, 33, 34, 35, 36, 38, 40, 42, 44, 45, 48, 51, 55, 56, 57, 60, 63, 66, 68, 70, 72, 76, 77, 80, 84, 85, 88, 90, 95, 99, 102, 105, 110, 112, 114, 119, 120, 126, 132, 133, 136, 140, 144, 152, 153, 154, 165, 168, 170, 171, 176, 180, 187, 190, 198, 204, 209, 210, 220, 228, 231, 238, 240, 252, 255, 264, 266, 272, 280, 285, 304, 306, 308, 315, 323, 330, 336, 340, 342, 357, 360, 374, 380, 385, 396, 399, 408, 418, 420, 440, 456, 462, 476, 495, 504, 510, 528, 532, 560, 561, 570, 595, 612, 616, 627, 630, 646, 660, 665, 680, 684, 693, 714, 720, 748, 760, 765, 770, 792, 798, 816, 836, 840, 855, 880, 912, 924, 935, 952, 969, 990, 1008, 1020, 1045, 1064, 1071, 1122, 1140, 1155, 1190, 1197, 1224, 1232, 1254, 1260, 1292, 1309, 1320, 1330, 1360, 1368, 1386, 1428, 1463, 1496, 1520, 1530, 1540, 1584, 1596, 1615, 1672, 1680, 1683, 1710, 1785, 1848, 1870, 1881, 1904, 1938, 1980, 1995, 2040, 2090, 2128, 2142, 2244, 2261, 2280, 2310, 2380, 2394, 2448, 2508, 2520, 2584, 2618, 2640, 2660, 2736, 2772, 2805, 2856, 2907, 2926, 2992, 3060, 3080, 3135, 3192, 3230, 3344, 3366, 3420, 3465, 3553, 3570, 3696, 3740, 3762, 3876, 3927, 3960, 3990, 4080, 4180, 4284, 4389, 4488, 4522, 4560, 4620, 4760, 4788, 4845, 5016, 5040, 5168, 5236, 5320, 5355, 5544, 5610, 5712, 5814, 5852, 5985, 6120, 6160, 6270, 6384, 6460, 6545, 6732, 6783, 6840, 6930, 7106, 7140, 7315, 7480, 7524, 7752, 7854, 7920, 7980, 8360, 8415, 8568, 8778, 8976, 9044, 9240, 9405, 9520, 9576, 9690, 10032, 10472, 10640, 10659, 10710, 11088, 11220, 11305, 11628, 11704, 11781, 11970, 12240, 12540, 12920, 13090, 13167, 13464, 13566, 13680, 13860, 14212, 14280, 14535, 14630, 14960, 15048, 15504, 15708, 15960, 16720, 16830, 17136, 17556, 17765, 18088, 18480, 18810, 19152, 19380, 19635, 20349, 20944, 21318, 21420, 21945, 22440, 22610, 23256, 23408, 23562, 23940, 24871, 25080, 25840, 26180, 26334, 26928, 27132, 27720, 28424, 28560, 29070, 29260, 30096, 31416, 31920, 31977, 33660, 33915, 35112, 35530, 36176, 37620, 38760, 39270, 40698, 42636, 42840, 43890, 44880, 45220, 46512, 47124, 47880, 49742, 50160, 52360, 52668, 53295, 54264, 55440, 56848, 58140, 58520, 58905, 62832, 63954, 65835, 67320, 67830, 70224, 71060, 74613, 75240, 77520, 78540, 81396, 85272, 85680, 87780, 90440, 94248, 95760, 99484, 101745, 104720, 105336, 106590, 108528, 116280, 117040, 117810, 124355, 127908, 131670, 134640, 135660, 142120, 149226, 150480, 157080, 159885, 162792, 170544, 175560, 180880, 188496, 198968, 203490, 210672, 213180, 223839, 232560, 235620, 248710, 255816, 263340, 271320, 284240, 298452, 314160, 319770, 325584, 351120, 373065, 397936, 406980, 426360, 447678, 471240, 497420, 511632, 526680, 542640, 596904, 639540, 746130, 813960, 852720, 895356, 942480, 994840, 1053360, 1119195, 1193808, 1279080, 1492260, 1627920, 1790712, 1989680, 2238390, 2558160, 2984520, 3581424, 4476780, 5969040, 8953560, 17907120]\n",
      "Found new triangular number with most divisors:\n",
      " 76576500 with 576 divisors: [1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 18, 20, 21, 22, 25, 26, 28, 30, 33, 34, 35, 36, 39, 42, 44, 45, 50, 51, 52, 55, 60, 63, 65, 66, 68, 70, 75, 77, 78, 84, 85, 90, 91, 99, 100, 102, 105, 110, 117, 119, 125, 126, 130, 132, 140, 143, 150, 153, 154, 156, 165, 170, 175, 180, 182, 187, 195, 198, 204, 210, 220, 221, 225, 231, 234, 238, 250, 252, 255, 260, 273, 275, 286, 300, 306, 308, 315, 325, 330, 340, 350, 357, 364, 374, 375, 385, 390, 396, 420, 425, 429, 442, 450, 455, 462, 468, 476, 495, 500, 510, 525, 546, 550, 561, 572, 585, 595, 612, 630, 650, 660, 663, 693, 700, 714, 715, 748, 750, 765, 770, 780, 819, 825, 850, 858, 875, 884, 900, 910, 924, 935, 975, 990, 1001, 1020, 1050, 1071, 1092, 1100, 1105, 1122, 1125, 1155, 1170, 1190, 1260, 1275, 1287, 1300, 1309, 1326, 1365, 1375, 1386, 1428, 1430, 1500, 1530, 1540, 1547, 1575, 1625, 1638, 1650, 1683, 1700, 1716, 1750, 1785, 1820, 1870, 1925, 1950, 1980, 1989, 2002, 2100, 2125, 2142, 2145, 2210, 2244, 2250, 2275, 2310, 2340, 2380, 2431, 2475, 2550, 2574, 2618, 2625, 2652, 2730, 2750, 2772, 2805, 2860, 2925, 2975, 3003, 3060, 3094, 3150, 3250, 3276, 3300, 3315, 3366, 3465, 3500, 3570, 3575, 3740, 3825, 3850, 3900, 3927, 3978, 4004, 4095, 4125, 4250, 4284, 4290, 4420, 4500, 4550, 4620, 4641, 4675, 4862, 4875, 4950, 5005, 5100, 5148, 5236, 5250, 5355, 5460, 5500, 5525, 5610, 5775, 5850, 5950, 6006, 6188, 6300, 6375, 6435, 6500, 6545, 6630, 6732, 6825, 6930, 7140, 7150, 7293, 7650, 7700, 7735, 7854, 7875, 7956, 8190, 8250, 8415, 8500, 8580, 8925, 9009, 9100, 9282, 9350, 9625, 9724, 9750, 9900, 9945, 10010, 10500, 10710, 10725, 11050, 11220, 11375, 11550, 11700, 11781, 11900, 12012, 12155, 12375, 12750, 12870, 13090, 13260, 13650, 13860, 13923, 14025, 14300, 14586, 14625, 14875, 15015, 15300, 15470, 15708, 15750, 16380, 16500, 16575, 16830, 17017, 17325, 17850, 17875, 18018, 18564, 18700, 19125, 19250, 19500, 19635, 19890, 20020, 20475, 21420, 21450, 21879, 22100, 22750, 23100, 23205, 23375, 23562, 24310, 24750, 25025, 25500, 25740, 26180, 26775, 27300, 27625, 27846, 28050, 28875, 29172, 29250, 29750, 30030, 30940, 31500, 32175, 32725, 33150, 33660, 34034, 34125, 34650, 35700, 35750, 36036, 36465, 38250, 38500, 38675, 39270, 39780, 40950, 42075, 42900, 43758, 44625, 45045, 45500, 46410, 46750, 47124, 48620, 49500, 49725, 50050, 51051, 53550, 53625, 55250, 55692, 56100, 57750, 58500, 58905, 59500, 60060, 60775, 64350, 65450, 66300, 68068, 68250, 69300, 69615, 70125, 71500, 72930, 75075, 76500, 77350, 78540, 81900, 82875, 84150, 85085, 86625, 87516, 89250, 90090, 92820, 93500, 98175, 99450, 100100, 102102, 102375, 107100, 107250, 109395, 110500, 115500, 116025, 117810, 121550, 125125, 128700, 130900, 133875, 136500, 139230, 140250, 145860, 150150, 153153, 154700, 160875, 163625, 165750, 168300, 170170, 173250, 178500, 180180, 182325, 193375, 196350, 198900, 204204, 204750, 210375, 214500, 218790, 225225, 232050, 235620, 243100, 248625, 250250, 255255, 267750, 278460, 280500, 294525, 300300, 303875, 306306, 321750, 327250, 331500, 340340, 346500, 348075, 364650, 375375, 386750, 392700, 409500, 420750, 425425, 437580, 450450, 464100, 490875, 497250, 500500, 510510, 535500, 546975, 580125, 589050, 607750, 612612, 643500, 654500, 696150, 729300, 750750, 765765, 773500, 841500, 850850, 900900, 911625, 981750, 994500, 1021020, 1093950, 1126125, 1160250, 1178100, 1215500, 1276275, 1392300, 1472625, 1501500, 1531530, 1701700, 1740375, 1823250, 1963500, 2127125, 2187900, 2252250, 2320500, 2552550, 2734875, 2945250, 3063060, 3480750, 3646500, 3828825, 4254250, 4504500, 5105100, 5469750, 5890500, 6381375, 6961500, 7657650, 8508500, 10939500, 12762750, 15315300, 19144125, 25525500, 38288250, 76576500]\n"
     ]
    }
   ],
   "source": [
    "mostdivisors = 0\n",
    "for i in gen_triangular_numbers():\n",
    "    factors = factor_list(i)\n",
    "    if len(factors) > mostdivisors:\n",
    "        print(\"Found new triangular number with most divisors:\")\n",
    "        print(\" {} with {} divisors: {}\".format(i, len(factors), factors))\n",
    "        mostdivisors = len(factors)\n",
    "    if len(factors) > 500:\n",
    "        break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 13: Large sum\n",
    "Work out the first ten digits of the sum of the following one-hundred 50-digit numbers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5537376230390876637302048746832985971773659831892672"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "numberstring = \"\"\"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\"\"\"\n",
    "numberlist = [int(x) for x in numberstring.split('\\n')]\n",
    "sum(numberlist)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 14: Longest Collatz sequence\n",
    "The following iterative sequence is defined for the set of positive integers:\n",
    "$$\n",
    "n → n/2\\ (n\\ is\\ even)\\\\\n",
    "n → 3n + 1\\ (n\\ is\\ odd)\n",
    "$$\n",
    "Using the rule above and starting with 13, we generate the following sequence:\n",
    "\n",
    "13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1\n",
    "It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.\n",
    "\n",
    "Which starting number, under one million, produces the longest chain?\n",
    "\n",
    "NOTE: Once the chain starts the terms are allowed to go above one million."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# added to euler.py\n",
    "def gen_collatz(n):\n",
    "    \"\"\"Yield the Collatz sequence beginning with n, one term at a time.\"\"\"\n",
    "    yield n\n",
    "    while n != 1:\n",
    "        if n % 2:\n",
    "            n = n * 3 + 1\n",
    "            yield n\n",
    "        else:\n",
    "            n //= 2\n",
    "            yield n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "New longest chain found with 1, new length 1.\n",
      "New longest chain found with 2, new length 2.\n",
      "New longest chain found with 3, new length 8.\n",
      "New longest chain found with 6, new length 9.\n",
      "New longest chain found with 7, new length 17.\n",
      "New longest chain found with 9, new length 20.\n",
      "New longest chain found with 18, new length 21.\n",
      "New longest chain found with 25, new length 24.\n",
      "New longest chain found with 27, new length 112.\n",
      "New longest chain found with 54, new length 113.\n",
      "New longest chain found with 73, new length 116.\n",
      "New longest chain found with 97, new length 119.\n",
      "New longest chain found with 129, new length 122.\n",
      "New longest chain found with 171, new length 125.\n",
      "New longest chain found with 231, new length 128.\n",
      "New longest chain found with 313, new length 131.\n",
      "New longest chain found with 327, new length 144.\n",
      "New longest chain found with 649, new length 145.\n",
      "New longest chain found with 703, new length 171.\n",
      "New longest chain found with 871, new length 179.\n",
      "New longest chain found with 1161, new length 182.\n",
      "New longest chain found with 2223, new length 183.\n",
      "New longest chain found with 2463, new length 209.\n",
      "New longest chain found with 2919, new length 217.\n",
      "New longest chain found with 3711, new length 238.\n",
      "New longest chain found with 6171, new length 262.\n",
      "New longest chain found with 10971, new length 268.\n",
      "New longest chain found with 13255, new length 276.\n",
      "New longest chain found with 17647, new length 279.\n",
      "New longest chain found with 23529, new length 282.\n",
      "New longest chain found with 26623, new length 308.\n",
      "New longest chain found with 34239, new length 311.\n",
      "New longest chain found with 35655, new length 324.\n",
      "New longest chain found with 52527, new length 340.\n",
      "New longest chain found with 77031, new length 351.\n",
      "New longest chain found with 106239, new length 354.\n",
      "New longest chain found with 142587, new length 375.\n",
      "New longest chain found with 156159, new length 383.\n",
      "New longest chain found with 216367, new length 386.\n",
      "New longest chain found with 230631, new length 443.\n",
      "New longest chain found with 410011, new length 449.\n",
      "New longest chain found with 511935, new length 470.\n",
      "New longest chain found with 626331, new length 509.\n",
      "New longest chain found with 837799, new length 525.\n"
     ]
    }
   ],
   "source": [
    "longest = 0\n",
    "winner = 0\n",
    "for i in range(1, 1000000):\n",
    "    newcollatz = list(gen_collatz(i))\n",
    "    if len(newcollatz) > longest:\n",
    "        winner = i\n",
    "        longest = len(newcollatz)\n",
    "        print(\"New longest chain found with {}, new length {}.\".format(winner, len(newcollatz)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 15: Lattice paths\n",
    "Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.\n",
    "![diagram](http://projecteuler.net/project/images/p015.gif)\n",
    "How many such routes are there through a 20×20 grid?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Work\n",
    "For every column in the grid, there are height+1 paths through it (the +1 is the line which underscores the column). For a path taken through any column, the number of paths available in the next column is equal to the height+1 of the path we just took."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from functools import lru_cache\n",
    "\"\"\"Return the number of paths down and to the right through a x by y grid.\n",
    "Exponentially slower with large sizes.\"\"\"\n",
    "@lru_cache(10000)\n",
    "def gridpaths(xsize, ysize):\n",
    "    if xsize == 1: # last column\n",
    "        return ysize + 1 # height + 1\n",
    "    total = 0\n",
    "    for i in range(0, ysize + 1):\n",
    "        total += gridpaths(xsize - 1, i)\n",
    "    return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The number of paths through a 1x1 grid is 2.\n",
      "3.742411951179747e-05\n",
      "The number of paths through a 2x2 grid is 6.\n",
      "1.4845931673335144e-05\n",
      "The number of paths through a 3x3 grid is 20.\n",
      "1.1753029241390323e-05\n",
      "The number of paths through a 4x4 grid is 70.\n",
      "1.422735118694618e-05\n",
      "The number of paths through a 5x5 grid is 252.\n",
      "1.3299480485784443e-05\n",
      "The number of paths through a 6x6 grid is 924.\n",
      "1.3918060972173407e-05\n",
      "The number of paths through a 7x7 grid is 3432.\n",
      "2.2268897566846135e-05\n",
      "The number of paths through a 8x8 grid is 12870.\n",
      "0.00011691171215488794\n",
      "The number of paths through a 9x9 grid is 48620.\n",
      "2.1031736594068207e-05\n",
      "The number of paths through a 10x10 grid is 184756.\n",
      "1.4845931730178563e-05\n",
      "The number of paths through a 11x11 grid is 705432.\n",
      "1.1753029241390323e-05\n",
      "The number of paths through a 12x12 grid is 2704156.\n",
      "1.299019027101167e-05\n",
      "The number of paths through a 13x13 grid is 10400600.\n",
      "1.3918060972173407e-05\n",
      "The number of paths through a 14x14 grid is 40116600.\n",
      "1.0825158483385167e-05\n",
      "The number of paths through a 15x15 grid is 155117520.\n",
      "1.0825158540228585e-05\n",
      "The number of paths through a 16x16 grid is 601080390.\n",
      "1.422735118694618e-05\n",
      "The number of paths through a 17x17 grid is 2333606220.\n",
      "1.3918060972173407e-05\n",
      "The number of paths through a 18x18 grid is 9075135300.\n",
      "1.422735118694618e-05\n",
      "The number of paths through a 19x19 grid is 35345263800.\n",
      "8.350836583304044e-05\n",
      "The number of paths through a 20x20 grid is 137846528820.\n",
      "6.30952097253612e-05\n",
      "The number of paths through a 21x21 grid is 538257874440.\n",
      "1.6392382917729265e-05\n",
      "The number of paths through a 22x22 grid is 2104098963720.\n",
      "1.5155221944951336e-05\n",
      "The number of paths through a 23x23 grid is 8233430727600.\n",
      "1.4845931730178563e-05\n",
      "The number of paths through a 24x24 grid is 32247603683100.\n",
      "1.4536641458562372e-05\n",
      "The number of paths through a 25x25 grid is 126410606437752.\n",
      "1.4536641458562372e-05\n",
      "The number of paths through a 26x26 grid is 495918532948104.\n",
      "1.4536641458562372e-05\n",
      "The number of paths through a 27x27 grid is 1946939425648112.\n",
      "1.4536641458562372e-05\n",
      "The number of paths through a 28x28 grid is 7648690600760440.\n",
      "1.422735118694618e-05\n",
      "The number of paths through a 29x29 grid is 30067266499541040.\n",
      "1.422735118694618e-05\n",
      "The number of paths through a 30x30 grid is 118264581564861424.\n",
      "1.4536641458562372e-05\n",
      "The number of paths through a 31x31 grid is 465428353255261088.\n",
      "1.4536641458562372e-05\n",
      "The number of paths through a 32x32 grid is 1832624140942590534.\n",
      "1.4845931730178563e-05\n",
      "The number of paths through a 33x33 grid is 7219428434016265740.\n",
      "1.4536641458562372e-05\n",
      "The number of paths through a 34x34 grid is 28453041475240576740.\n",
      "1.4845931730178563e-05\n",
      "The number of paths through a 35x35 grid is 112186277816662845432.\n",
      "1.4227351243789599e-05\n",
      "The number of paths through a 36x36 grid is 442512540276836779204.\n",
      "1.701096340411823e-05\n",
      "The number of paths through a 37x37 grid is 1746130564335626209832.\n",
      "2.876399264550855e-05\n",
      "The number of paths through a 38x38 grid is 6892620648693261354600.\n",
      "1.57738024313403e-05\n",
      "The number of paths through a 39x39 grid is 27217014869199032015600.\n",
      "1.546451215972411e-05\n",
      "The number of paths through a 40x40 grid is 107507208733336176461620.\n",
      "1.4845931673335144e-05\n",
      "The number of paths through a 41x41 grid is 424784580848791721628840.\n",
      "1.5155221944951336e-05\n",
      "The number of paths through a 42x42 grid is 1678910486211891090247320.\n",
      "1.4536641458562372e-05\n",
      "The number of paths through a 43x43 grid is 6637553085023755473070800.\n",
      "1.5155221944951336e-05\n",
      "The number of paths through a 44x44 grid is 26248505381684851188961800.\n",
      "1.3918060972173407e-05\n",
      "The number of paths through a 45x45 grid is 103827421287553411369671120.\n",
      "1.3608770700557216e-05\n",
      "The number of paths through a 46x46 grid is 410795449442059149332177040.\n",
      "2.3506058539624064e-05\n",
      "The number of paths through a 47x47 grid is 1625701140345170250548615520.\n",
      "1.5155221944951336e-05\n",
      "The number of paths through a 48x48 grid is 6435067013866298908421603100.\n",
      "2.8145412215963006e-05\n",
      "The number of paths through a 49x49 grid is 25477612258980856902730428600.\n",
      "1.5155221944951336e-05\n",
      "The number of paths through a 50x50 grid is 100891344545564193334812497256.\n",
      "1.57738024313403e-05\n",
      "The number of paths through a 51x51 grid is 399608854866744452032002440112.\n",
      "1.4845931673335144e-05\n",
      "The number of paths through a 52x52 grid is 1583065848125949175357548128136.\n",
      "1.4845931673335144e-05\n",
      "The number of paths through a 53x53 grid is 6272525058612251449529907677520.\n",
      "1.4536641458562372e-05\n",
      "The number of paths through a 54x54 grid is 24857784491537440929618523018320.\n",
      "1.4845931730178563e-05\n",
      "The number of paths through a 55x55 grid is 98527218530093856775578873054432.\n",
      "1.4536641458562372e-05\n",
      "The number of paths through a 56x56 grid is 390590044887157789360330532465784.\n",
      "1.855741459166893e-05\n",
      "The number of paths through a 57x57 grid is 1548655265692941410446222812934512.\n",
      "1.3608770757400634e-05\n",
      "The number of paths through a 58x58 grid is 6141219157058215937976400809912720.\n",
      "1.7320253618891e-05\n",
      "The number of paths through a 59x59 grid is 24356699707654619143838606602026720.\n",
      "1.2371609727779287e-05\n",
      "The number of paths through a 60x60 grid is 96614908840363322603893139521372656.\n",
      "1.1753029298233741e-05\n",
      "The number of paths through a 61x61 grid is 383291933432261050330199012527412832.\n",
      "1.144373902661755e-05\n",
      "The number of paths through a 62x62 grid is 1520803477811874490019821888415218656.\n",
      "1.4536641458562372e-05\n",
      "The number of paths through a 63x63 grid is 6034934435761406706427864636568328000.\n",
      "2.010386583606305e-05\n",
      "The number of paths through a 64x64 grid is 23951146041928082866135587776380551750.\n",
      "1.5155221944951336e-05\n",
      "The number of paths through a 65x65 grid is 95067625827960698145584333020095113100.\n",
      "1.5155221944951336e-05\n",
      "The number of paths through a 66x66 grid is 377389666165540953244592352291892721700.\n",
      "0.00012000461464367618\n",
      "The number of paths through a 67x67 grid is 1498293301493043187508381577755872596600.\n",
      "1.4845931730178563e-05\n",
      "The number of paths through a 68x68 grid is 5949105755928259715106809205795376486500.\n",
      "1.4536641458562372e-05\n",
      "The number of paths through a 69x69 grid is 23623985175715118288974865541854103729000.\n",
      "0.001753984972822309\n",
      "The number of paths through a 70x70 grid is 93820969697840041204785894580506297666600.\n",
      "0.001848937077681967\n",
      "The number of paths through a 71x71 grid is 372641034574519600278163693967644731577200.\n",
      "0.0020403877385888336\n",
      "The number of paths through a 72x72 grid is 1480212998448786189993816895482588794876100.\n",
      "0.0018084200557382246\n",
      "The number of paths through a 73x73 grid is 5880298213015725960249409584793845897453000.\n",
      "0.0018653294605996962\n",
      "The number of paths through a 74x74 grid is 23362265873332749085315221863910685052043000.\n",
      "0.0021857541532313007\n",
      "The number of paths through a 75x75 grid is 92826069736708789698985814872605121940117520.\n",
      "0.0019256410581647287\n",
      "The number of paths through a 76x76 grid is 368861487637974401172285738046404563498888040.\n",
      "0.0020246139361574933\n",
      "The number of paths through a 77x77 grid is 1465865132691170996866486179768828525073503120.\n",
      "0.002171526801987511\n",
      "The number of paths through a 78x78 grid is 5825874245311064218315521996517139009907512400.\n",
      "0.00226988109955073\n",
      "The number of paths through a 79x79 grid is 23156006494021191956342707682359261381151378400.\n",
      "0.002364523914138772\n",
      "The number of paths through a 80x80 grid is 92045125813734238026462263037378063990076729140.\n",
      "0.002727012079958513\n",
      "The number of paths through a 81x81 grid is 365907784099042279561985786395502921046971688680.\n",
      "0.002944443121407403\n",
      "The number of paths through a 82x82 grid is 1454706556296192477283016662986999417820887445240.\n",
      "0.0023335948897624803\n",
      "The number of paths through a 83x83 grid is 5783773055153536355462596370912166360010757312400.\n",
      "0.00234380146781632\n",
      "The number of paths through a 84x84 grid is 22997383338348585032434609379579328145757058837400.\n",
      "0.002340089984897986\n",
      "The number of paths through a 85x85 grid is 91448418451315549893681152591738975450186892788720.\n",
      "0.002388339262950012\n",
      "The number of paths through a 86x86 grid is 363666966399417651902778537050868948883301364345840.\n",
      "0.002464424662946385\n",
      "The number of paths through a 87x87 grid is 1446307705450557558142084756547133980616347954754720.\n",
      "0.0025225712287806346\n",
      "The number of paths through a 88x88 grid is 5752360192132899378974200736267010150178656638229000.\n",
      "0.0030675406384261805\n",
      "The number of paths through a 89x89 grid is 22880174247360071687155809670095748237789263482394000.\n",
      "0.0026877322189875485\n",
      "The number of paths through a 90x90 grid is 91012248672832285155575331798825309656983959185522800.\n",
      "0.002395143648300291\n",
      "The number of paths through a 91x91 grid is 362048725489728431058442528694228154899210914562189600.\n",
      "0.002513911101971189\n",
      "The number of paths through a 92x92 grid is 1440324277491745714862934407631385920577295594888710800.\n",
      "0.002554118833643315\n",
      "The number of paths through a 93x93 grid is 5730322394321999080637480976597986995845154517299172000.\n",
      "0.0026070074653148367\n",
      "The number of paths through a 94x94 grid is 22799367824217315491046998779230288685596678611381812000.\n",
      "0.0032330109188478673\n",
      "The number of paths through a 95x95 grid is 90717484605833107953850163563674201296374152790550788800.\n",
      "0.003193112477390514\n",
      "The number of paths through a 96x96 grid is 360979990827377575399695442513786925991822149645733347100.\n",
      "0.004013350204047583\n",
      "The number of paths through a 97x97 grid is 1436477076900698392827654028972389210647869585188175999800.\n",
      "0.0029648562774582388\n",
      "The number of paths through a 98x98 grid is 5716592448890534420436582360196242777068052430850904489000.\n",
      "0.0028835129433559814\n",
      "The number of paths through a 99x99 grid is 22750883079422934966181954039568885395604168260154104734000.\n",
      "0.003998813562645864\n",
      "The number of paths through a 100x100 grid is 90548514656103281165404177077484163874504589675413336841320.\n",
      "0.0033100241896022453\n"
     ]
    }
   ],
   "source": [
    "from timeit import default_timer\n",
    "for i in range(1, 101):\n",
    "    start = default_timer()\n",
    "    print(\"The number of paths through a {}x{} grid is {}.\".format(i, i, gridpaths(i, i)))\n",
    "    print(default_timer() - start)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This function becomes exponentially slower noticeable around size (15, 15) so probably unsuitable for (20, 20).\n",
    "\n",
    "However, by running this function to 10 we have discovered that the sequence is the [central binomial coefficients](https://oeis.org/A000984)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\"\"\"Return the list of terms to the nth term from the sequence of central binomial coefficients.\"\"\"\n",
    "def centralbinomialcoefficient(n):\n",
    "    cbclist = [1]\n",
    "    term = 1\n",
    "    for i in range(n):\n",
    "        term = term * (4 * i + 2) // (i + 1)\n",
    "        cbclist.append(term)\n",
    "    print(cbclist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 6, 20, 70, 252, 924, 3432, 12870, 48620, 184756, 705432, 2704156, 10400600, 40116600, 155117520, 601080390, 2333606220, 9075135300, 35345263800, 137846528820]\n"
     ]
    }
   ],
   "source": [
    "centralbinomialcoefficient(20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 15: Lattice paths\n",
    "Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.\n",
    "![diagram](http://projecteuler.net/project/images/p015.gif)\n",
    "How many such routes are there through a 20×20 grid?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Work\n",
    "For every column in the grid, there are height+1 paths through it (the +1 is the line which underscores the column). For a path taken through any column, the number of paths available in the next column is equal to the height+1 of the path we just took."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\"\"\"Return the number of paths down and to the right through a x by y grid.\n",
    "Exponentially slower with large sizes.\"\"\"\n",
    "def gridpaths(xsize, ysize):\n",
    "    if xsize == 1: # last column\n",
    "        return ysize + 1 # height + 1\n",
    "    total = 0\n",
    "    for i in range(0, ysize + 1):\n",
    "        total += gridpaths(xsize - 1, i)\n",
    "    return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The number of paths through a 1x1 grid is 2.\n",
      "The number of paths through a 2x2 grid is 6.\n",
      "The number of paths through a 3x3 grid is 20.\n",
      "The number of paths through a 4x4 grid is 70.\n",
      "The number of paths through a 5x5 grid is 252.\n",
      "The number of paths through a 6x6 grid is 924.\n",
      "The number of paths through a 7x7 grid is 3432.\n",
      "The number of paths through a 8x8 grid is 12870.\n",
      "The number of paths through a 9x9 grid is 48620.\n",
      "The number of paths through a 10x10 grid is 184756.\n",
      "The number of paths through a 11x11 grid is 705432.\n",
      "The number of paths through a 12x12 grid is 2704156.\n",
      "The number of paths through a 13x13 grid is 10400600.\n",
      "The number of paths through a 14x14 grid is 40116600.\n"
     ]
    }
   ],
   "source": [
    "for i in range(1, 15):\n",
    "    print(\"The number of paths through a {}x{} grid is {}.\".format(i, i, gridpaths(i, i)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This function becomes exponentially slower noticeable around size (15, 15) so probably unsuitable for (20, 20).\n",
    "\n",
    "However, by running this function to 10 we have discovered that the sequence is the [central binomial coefficients](https://oeis.org/A000984)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\"\"\"Return the list of terms to the nth term from the sequence of central binomial coefficients.\"\"\"\n",
    "def centralbinomialcoefficient(n):\n",
    "    cbclist = [1]\n",
    "    term = 1\n",
    "    for i in range(n):\n",
    "        term = term * (4 * i + 2) // (i + 1)\n",
    "        cbclist.append(term)\n",
    "    print(cbclist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 6, 20, 70, 252, 924, 3432, 12870, 48620, 184756, 705432, 2704156, 10400600, 40116600, 155117520, 601080390, 2333606220, 9075135300, 35345263800, 137846528820]\n"
     ]
    }
   ],
   "source": [
    "centralbinomialcoefficient(20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 16: Power digit sum\n",
    "$2^{15} = 32768$ and the sum of its digits is $3 + 2 + 7 + 6 + 8 = 26$.\n",
    "\n",
    "What is the sum of the digits of the number $2^{1000}$?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1366"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(int(x) for x in str(2**1000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 17: Number letter counts\n",
    "If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are $3 + 3 + 5 + 4 + 4 = 19$ letters used in total.\n",
    "\n",
    "If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?\n",
    "\n",
    "NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of \"and\" when writing out numbers is in compliance with British usage."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "names = {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',\n",
    "         16:'sixteen',17:'seventeen',18:'eighteen',19:'nineteen',\n",
    "         20:'twenty',30:'thirty',40:'forty',50:'fifty',60:'sixty',70:'seventy',80:'eighty',90:'ninety',\n",
    "         100:'hundred',1000:'thousand',1000000:'million',1000000000:'billion',1000000000000:'trillion'}\n",
    "def pronounce(number):\n",
    "    result = \"\"\n",
    "    if number > 999:\n",
    "        result += names[int(str(number)[0])] + ' thousand'\n",
    "        number -= int(str(number)[0]) * 1000\n",
    "    if number > 99:\n",
    "        result += names[int(str(number)[0])] + ' hundred'\n",
    "        number -= int(str(number)[0]) * 100\n",
    "    if number > 0 and len(result) > 0:\n",
    "        result += ' and '\n",
    "    if number in names:\n",
    "        result += names[number]\n",
    "        number -= number # skips the next if, if the <100 number had a specific name\n",
    "    if number > 0: # number is between 1 and 99 inclusive and is a compound name (21-99 but not a multiple of ten)\n",
    "        result += names[int(str(number)[0]) * 10]\n",
    "        number -= int(str(number)[0]) * 10\n",
    "    if number != 0:\n",
    "        result += ' ' + names[number]\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "21124\n"
     ]
    }
   ],
   "source": [
    "bigresult = \"\"\n",
    "for i in range(1, 1001):\n",
    "    for j in pronounce(i).split(' '):\n",
    "        bigresult += j\n",
    "print(len(bigresult))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 18: Maximum path sum\n",
    "By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.\n",
    "<center>\n",
    "```\n",
    "3\n",
    "7 4\n",
    "2 4 6\n",
    "8 5 9 3\n",
    "```\n",
    "</center>\n",
    "That is, 3 + 7 + 4 + 9 = 23.\n",
    "\n",
    "Find the maximum total from top to bottom of the triangle below:\n",
    "<center>\n",
    "```\n",
    "75\n",
    "95 64\n",
    "17 47 82\n",
    "18 35 87 10\n",
    "20 04 82 47 65\n",
    "19 01 23 75 03 34\n",
    "88 02 77 73 07 63 67\n",
    "99 65 04 28 06 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 04 68 89 53 67 30 73 16 69 87 40 31\n",
    "04 62 98 27 23 09 70 98 73 93 38 53 60 04 23\n",
    "```\n",
    "</center>\n",
    "NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1074\n"
     ]
    }
   ],
   "source": [
    "tristring =\"\"\"75\n",
    "95 64\n",
    "17 47 82\n",
    "18 35 87 10\n",
    "20 04 82 47 65\n",
    "19 01 23 75 03 34\n",
    "88 02 77 73 07 63 67\n",
    "99 65 04 28 06 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 04 68 89 53 67 30 73 16 69 87 40 31\n",
    "04 62 98 27 23 09 70 98 73 93 38 53 60 04 23\"\"\"\n",
    "# build a list that looks just like what we see above\n",
    "tri = [[int(char) for char in line.split(' ')] for line in tristring.split('\\n')]\n",
    "def maxsum(line, col):\n",
    "    if line == len(tri) - 1: # are we in the bottom line?\n",
    "        return tri[line][col] # yes, just return the number here\n",
    "    # otherwise, return the number here plus the largest recursive option from below\n",
    "    return tri[line][col] + max(maxsum(line + 1, col), maxsum(line + 1, col + 1))\n",
    "print(maxsum(0, 0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 19: Counting Sundays\n",
    "\n",
    "You are given the following information, but you may prefer to do some research for yourself.\n",
    "\n",
    "- 1 Jan 1900 was a Monday.\n",
    "- Thirty days has September,\n",
    "- April, June and November.\n",
    "- All the rest have thirty-one,\n",
    "- Saving February alone,\n",
    "- Which has twenty-eight, rain or shine.\n",
    "- And on leap years, twenty-nine.\n",
    "- A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.\n",
    "\n",
    "How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "171\n"
     ]
    }
   ],
   "source": [
    "# Using the standard library\n",
    "import calendar\n",
    "numsundays = 0\n",
    "for year in range(1901, 2000 + 1):\n",
    "    for month in range(1, 12 + 1):\n",
    "        if calendar.weekday(year, month, 1) == 6: # 0 is Monday, 6 is Sunday (European convention)\n",
    "            numsundays += 1\n",
    "print(numsundays)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 20: Factorial digit sum\n",
    "n! means n × (n − 1) × ... × 3 × 2 × 1\n",
    "\n",
    "For example, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800,\n",
    "\n",
    "and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.\n",
    "\n",
    "Find the sum of the digits in the number 100!\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "648\n"
     ]
    }
   ],
   "source": [
    "import math\n",
    "print(sum([int(x) for x in str(math.factorial(100))]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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": 2
}