Python.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'[**81**](http://nbviewer.jupyter.org/github/ymer/euler-python/blob/master/Python.ipynb#p81), [**82**](http://nbviewer.jupyter.org/github/ymer/euler-python/blob/master/Python.ipynb#p82), [**83**](http://nbviewer.jupyter.org/github/ymer/euler-python/blob/master/Python.ipynb#p83), [**84**](http://nbviewer.jupyter.org/github/ymer/euler-python/blob/master/Python.ipynb#p84), [**85**](http://nbviewer.jupyter.org/github/ymer/euler-python/blob/master/Python.ipynb#p85), [**86**](http://nbviewer.jupyter.org/github/ymer/euler-python/blob/master/Python.ipynb#p86), [**87**](http://nbviewer.jupyter.org/github/ymer/euler-python/blob/master/Python.ipynb#p87), [**88**](http://nbviewer.jupyter.org/github/ymer/euler-python/blob/master/Python.ipynb#p88), [**89**](http://nbviewer.jupyter.org/github/ymer/euler-python/blob/master/Python.ipynb#p89), [**90**](http://nbviewer.jupyter.org/github/ymer/euler-python/blob/master/Python.ipynb#p90), [**91**](http://nbviewer.jupyter.org/github/ymer/euler-python/blob/master/Python.ipynb#p91), [**92**](http://nbviewer.jupyter.org/github/ymer/euler-python/blob/master/Python.ipynb#p92), [**93**](http://nbviewer.jupyter.org/github/ymer/euler-python/blob/master/Python.ipynb#p93), [**94**](http://nbviewer.jupyter.org/github/ymer/euler-python/blob/master/Python.ipynb#p94), [**95**](http://nbviewer.jupyter.org/github/ymer/euler-python/blob/master/Python.ipynb#p95), [**96**](http://nbviewer.jupyter.org/github/ymer/euler-python/blob/master/Python.ipynb#p96), [**97**](http://nbviewer.jupyter.org/github/ymer/euler-python/blob/master/Python.ipynb#p97), [**98**](http://nbviewer.jupyter.org/github/ymer/euler-python/blob/master/Python.ipynb#p98), [**99**](http://nbviewer.jupyter.org/github/ymer/euler-python/blob/master/Python.ipynb#p99), '"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = ''\n",
    "for n in range(81, 100):\n",
    "    if n < 10:\n",
    "        n = '0' + str(n)\n",
    "    s += '''[**{n}**](http://nbviewer.jupyter.org/github/ymer/euler-python/blob/master/Python.ipynb#p{n}), '''.format(n=n)\n",
    "s"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### General"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%load_ext autotime\n",
    "from itertools import takewhile, count, combinations_with_replacement, combinations, product, permutations\n",
    "from operator import itemgetter, mul\n",
    "from collections import defaultdict, Counter\n",
    "from math import sqrt, factorial, log, floor\n",
    "from functools import reduce, lru_cache\n",
    "\n",
    "#prod([1, 2, 3]) = 6\n",
    "def prod(a):\n",
    "    return reduce(mul, a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p1\"></a>[Problem 1](https://projecteuler.net/problem=1)\n",
    "\n",
    "Add all the natural numbers below one thousand that are multiples of 3 or 5."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "233168"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 30 ms\n"
     ]
    }
   ],
   "source": [
    "sum([n for n in range(1000) if n % 3 == 0 or n % 5 == 0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p2\"></a>[Problem 2](https://projecteuler.net/problem=2)\n",
    "\n",
    "Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4613732"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 7 ms\n"
     ]
    }
   ],
   "source": [
    "fsum = 0\n",
    "a, b = 0, 1\n",
    "\n",
    "while a < 4*10**6:\n",
    "    if a % 2 == 0:\n",
    "        fsum += a\n",
    "    a, b = b, a + b\n",
    "\n",
    "fsum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p3\"></a>[Problem 3](https://projecteuler.net/problem=3)\n",
    "\n",
    "What is the largest prime factor of the number 600851475143?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6857"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 801 ms\n"
     ]
    }
   ],
   "source": [
    "from sympy import factorint\n",
    "\n",
    "max(factorint(600851475143).keys())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"pp4\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id=\"pp5\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id=\"pp6\"></a>bjarne"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [Problem 4](https://projecteuler.net/problem=4)\n",
    "\n",
    "Find the largest palindrome made from the product of two 3-digit numbers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "906609"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 308 ms\n"
     ]
    }
   ],
   "source": [
    "def is_palindrome(n):\n",
    "    return str(n) == str(n)[::-1]\n",
    "\n",
    "max(n1*n2 for n1, n2 in combinations_with_replacement(range(100, 1000), 2) if is_palindrome(n1*n2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p5\"></a>[Problem 5](https://projecteuler.net/problem=5)\n",
    "\n",
    "What is the smallest number divisible by each of the numbers 1 to 20?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "232792560"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 5 ms\n"
     ]
    }
   ],
   "source": [
    "factordict = defaultdict(lambda: 0, {})\n",
    "for i in range(2, 21):\n",
    "    for prime, power in factorint(i).items():\n",
    "        factordict[prime] = max(factordict[prime], power)\n",
    "\n",
    "prod([prime ** power for prime, power in factordict.items()])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p6\"></a>[Problem 6](https://projecteuler.net/problem=6)\n",
    "\n",
    "Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "25164150"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 12 ms\n"
     ]
    }
   ],
   "source": [
    "sum(range(101))**2 - sum([n**2 for n in range(101)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p7\"></a>[Problem 7](https://projecteuler.net/problem=7)\n",
    "\n",
    "Find the 10001st prime."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "104743"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 74 ms\n"
     ]
    }
   ],
   "source": [
    "from sympy import prime\n",
    "\n",
    "prime(10001)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p8\"></a>[Problem 8](https://projecteuler.net/problem=8)\n",
    "\n",
    "Discover the largest product of 13 consecutive digits in the 1000-digit number."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "23514624000"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 9 ms\n"
     ]
    }
   ],
   "source": [
    "s = open('p/p008_number.txt').read()\n",
    "\n",
    "max([prod(int(digit) for digit in number) for number in [s[i:i+13] for i in range(len(s) - 13)]])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p9\"></a>[Problem 9](https://projecteuler.net/problem=9)\n",
    "\n",
    "Find the only Pythagorean triplet, {a, b, c}, for which a + b + c = 1000."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "31875000"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 242 ms\n"
     ]
    }
   ],
   "source": [
    "for a, b in combinations(range(1, 1000), 2):\n",
    "    c = 1000 - a -b\n",
    "    if a**2 + b**2 == c**2:\n",
    "        break\n",
    "        \n",
    "a*b*c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p10\"></a>[Problem 10](https://projecteuler.net/problem=10)\n",
    "\n",
    "Calculate the sum of all the primes below two million."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "142913828922"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 745 ms\n"
     ]
    }
   ],
   "source": [
    "from sympy import sieve\n",
    "\n",
    "sum(sieve.primerange(2, 2000000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p11\"></a>[Problem 11](https://projecteuler.net/problem=11)\n",
    "\n",
    "What is the greatest product of four numbers on the same straight line in the 20 by 20 grid?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "70600674"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 81 ms\n"
     ]
    }
   ],
   "source": [
    "with open('p/p011_grid.txt') as inp:\n",
    "    a = [[int(elem) for elem in line.split()] for line in inp]\n",
    "\n",
    "grid = [(x,y) for x in range(20) for y in range(20)]\n",
    "\n",
    "def up(pos, n):\n",
    "    for i in range(n):\n",
    "        yield pos[0] -i, pos[1]\n",
    "\n",
    "def right(pos, n):\n",
    "    for i in range(n):\n",
    "        yield pos[0], pos[1] +i\n",
    "\n",
    "def up_right(pos, n):\n",
    "    for i in range(n):\n",
    "        yield pos[0] -i, pos[1] +i\n",
    "        \n",
    "def down_right(pos, n):\n",
    "    for i in range(n):\n",
    "        yield pos[0] +i, pos[1] +i\n",
    "\n",
    "directions = [up, right, up_right, down_right]\n",
    "\n",
    "def value(pos):\n",
    "    return a[pos[0]][pos[1]] if pos in grid else 0\n",
    "\n",
    "def adjacent_product():\n",
    "    for pos, direction in product(grid, directions):\n",
    "        yield prod([value(pos) for pos in direction(pos, 4)])\n",
    "\n",
    "max(adjacent_product())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### <a name=\"p12\"></a>[Problem 12](https://projecteuler.net/problem=12)\n",
    "\n",
    "What is the value of the first triangle number to have over five hundred divisors?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "76576500"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 1.01 s\n"
     ]
    }
   ],
   "source": [
    "from sympy import divisors\n",
    "\n",
    "def triangle_numbers():\n",
    "    t = 0\n",
    "    for n in count(1):\n",
    "        t += n\n",
    "        yield t\n",
    "\n",
    "for number in triangle_numbers():\n",
    "    if len(divisors(number)) > 500:\n",
    "        break\n",
    "\n",
    "number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### <a name=\"p13\"></a>[Problem 13](https://projecteuler.net/problem=13)\n",
    "\n",
    "Find the first ten digits of the sum of one-hundred 50-digit numbers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5537376230"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 3 ms\n"
     ]
    }
   ],
   "source": [
    "numbers = [int(line) for line in open('p/p013_numbers.txt')]\n",
    "\n",
    "int(str(sum(numbers))[:10])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p14\"></a>[Problem 14](https://projecteuler.net/problem=14)\n",
    "\n",
    "Which starting number, under one million, produces the longest collatz chain?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "837799"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 2.31 s\n"
     ]
    }
   ],
   "source": [
    "@lru_cache(maxsize=None)\n",
    "def chain_length(n):\n",
    "    if n == 1:\n",
    "        return 1\n",
    "    if n % 2 == 0:\n",
    "        return(chain_length(n / 2)) + 1\n",
    "    else:\n",
    "        return chain_length(n * 3 + 1) + 1\n",
    "    \n",
    "max(range(1,10**6), key=chain_length)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p15\"></a>[Problem 15](https://projecteuler.net/problem=15)\n",
    "\n",
    "Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?\n",
    "\n",
    "Analysis: To get to the corner, you need to go down exactly 20 times in a total of 40 moves, with each step being a choice between two options. This is given by the binomial distribution.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "137846528820"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 3 ms\n"
     ]
    }
   ],
   "source": [
    "from sympy import binomial\n",
    "\n",
    "binomial(40, 20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p16\"></a>[Problem 16](https://projecteuler.net/problem=16)\n",
    "\n",
    "What is the sum of the digits of the number 2^1000?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1366"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 19 ms\n"
     ]
    }
   ],
   "source": [
    "sum(map(int, str(2**1000)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p17\"></a>[Problem 17](https://projecteuler.net/problem=17)\n",
    "\n",
    "How many letters would be needed to write all the numbers in words from 1 to 1000?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "21124"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 76 ms\n"
     ]
    }
   ],
   "source": [
    "import inflect\n",
    "p = inflect.engine()\n",
    "\n",
    "sum(len(p.number_to_words(n).replace('-', '').replace(' ', '')) for n in range(1, 1001))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p18\"></a>[Problem 18](https://projecteuler.net/problem=18)\n",
    "\n",
    "Find the maximum sum traveling from the top of the triangle to the base.\n",
    "\n",
    "Analysis: Start at the bottom and go up. Assign each tile the value of itself plus the largest of the two tiles that can lead to it. This will be the maximum sum leading to that tile."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1074"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 7 ms\n"
     ]
    }
   ],
   "source": [
    "with open('p/p018_triangle.txt') as inp:\n",
    "    a = [[int(elem) for elem in line.split()] for line in inp]\n",
    "\n",
    "for row in reversed(range(len(a) -1)):\n",
    "    for col in range(len(a[row])):\n",
    "        a[row][col] += max(a[row+1][col], a[row+1][col +1])\n",
    "\n",
    "a[0][0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p19\"></a>[Problem 19](https://projecteuler.net/problem=19)\n",
    "\n",
    "How many Sundays fell on the first of the month during the twentieth century?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "171"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 10 ms\n"
     ]
    }
   ],
   "source": [
    "from datetime import datetime\n",
    "\n",
    "sum(1 for year in range(1901, 2001) for month in range(1, 13) if datetime(year, month, 1).isoweekday() == 7)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p20\"></a>[Problem 20](https://projecteuler.net/problem=20)\n",
    "\n",
    "Find the sum of digits in 100!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "648"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 18 ms\n"
     ]
    }
   ],
   "source": [
    "from math import factorial\n",
    "\n",
    "sum(map(int, str(factorial(100))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p21\"></a>[Problem 21](https://projecteuler.net/problem=21)\n",
    "\n",
    "Evaluate the sum of all the amicable numbers under 10000."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "31626"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 350 ms\n"
     ]
    }
   ],
   "source": [
    "from sympy.ntheory import divisors\n",
    "\n",
    "def sum_of_proper_divisors(n):\n",
    "    return sum(divisors(n)) - n\n",
    "\n",
    "def amicable_numbers():\n",
    "    for a in range(1, 10000):\n",
    "        b = sum_of_proper_divisors(a)\n",
    "        if sum_of_proper_divisors(b) == a and a != b:\n",
    "            yield a\n",
    "        \n",
    "sum(amicable_numbers())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p22\"></a>[Problem 22](https://projecteuler.net/problem=22)\n",
    "\n",
    "What is the total of all the name scores in the file of first names?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "871198282"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 19 ms\n"
     ]
    }
   ],
   "source": [
    "words = open('p/p022_names.txt').read().strip('\"').split('\",\"')\n",
    "\n",
    "def value(word):\n",
    "    return sum(ord(char) - ord('A') + 1 for char in word)\n",
    "\n",
    "sum((i+1) * value(word) for i, word in enumerate(sorted(words)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p23\"></a>[Problem 23](https://projecteuler.net/problem=23)\n",
    "\n",
    "Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4179871"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 3.95 s\n"
     ]
    }
   ],
   "source": [
    "from sympy import divisors\n",
    "\n",
    "def sum_of_proper_divisors(n):\n",
    "    return sum(divisors(n)) - n\n",
    "\n",
    "ceiling = 28123\n",
    "\n",
    "abundant_numbers = [n for n in range(1, ceiling) if sum_of_proper_divisors(n) > n]\n",
    "\n",
    "sum(set(range(ceiling + 1)) - set(i+j for i, j in combinations_with_replacement(abundant_numbers, 2)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p24\"></a>[Problem 24](https://projecteuler.net/problem=24)\n",
    "\n",
    "What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2783915460"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 870 ms\n"
     ]
    }
   ],
   "source": [
    "int(''.join(list(permutations('0123456789'))[10**6-1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p25\"></a>[Problem 25](https://projecteuler.net/problem=25)\n",
    "\n",
    "What is the first term in the Fibonacci sequence to contain 1000 digits?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4782"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 757 ms\n"
     ]
    }
   ],
   "source": [
    "from sympy import fibonacci\n",
    "\n",
    "next(i for i in count(1) if len(str(fibonacci(i))) >= 1000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p26\"></a>[Problem 26](https://projecteuler.net/problem=26)\n",
    "\n",
    "Find the value of d < 1000 for which 1/d contains the longest recurring cycle.\n",
    "\n",
    "Analysis: https://en.wikipedia.org/wiki/Repeating_decimal#Fractions_with_prime_denominators.\n",
    "The length of the repetend (period of the repeating decimal) of 1/p is equal to the order of 10 modulo p."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "983"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 647 ms\n"
     ]
    }
   ],
   "source": [
    "def cycle_length(d):\n",
    "    for k in range(1, d):\n",
    "        if 10 ** k % d == 1:\n",
    "            return k\n",
    "    return 0\n",
    "\n",
    "max(range(1000), key=cycle_length)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p27\"></a>[Problem 27](https://projecteuler.net/problem=27)\n",
    "\n",
    "Find a quadratic formula with terms below 1000 that produces the maximum number of primes for consecutive values of n."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-59231"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 1.65 s\n"
     ]
    }
   ],
   "source": [
    "from sympy import primerange, isprime\n",
    "\n",
    "def quadratic(n, a, b):\n",
    "    return n **2 + a*n + b\n",
    "\n",
    "def quadratic_expressions():\n",
    "    for a, b in product(range(-999, 1000), primerange(2, 1000)):\n",
    "        n = next(n for n in count(1) if not isprime(quadratic(n, a, b)))\n",
    "        yield n, a*b\n",
    "\n",
    "max(quadratic_expressions(), key=itemgetter(0))[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p28\"></a>[Problem 28](https://projecteuler.net/problem=28)\n",
    "\n",
    "What is the sum of both diagonals in a 1001 by 1001 spiral?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "669171001"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 7 ms\n"
     ]
    }
   ],
   "source": [
    "def diagonals(size):\n",
    "    n = 1\n",
    "    yield n\n",
    "    for squaresize, corner in product(range(3, size + 1, 2), range(4)):\n",
    "        n += squaresize - 1\n",
    "        yield n\n",
    "            \n",
    "sum(diagonals(1001))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p29\"></a>[Problem 29](https://projecteuler.net/problem=29)\n",
    "\n",
    "How many distinct terms are in the sequence generated by a^b for 2 ≤ a ≤ 100 and \n",
    "2 ≤ b ≤ 100?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9183"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 24 ms\n"
     ]
    }
   ],
   "source": [
    "len(set(a**b for a, b in product(range(2, 101), range(2, 101))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p30\"></a>[Problem 30](https://projecteuler.net/problem=30)\n",
    "\n",
    "Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.\n",
    "\n",
    "Analysis: The highest sum of fifth powers of digits for a number with 7 digits is 9^5 * 7 = 413343, which has only 6 digits. So the number must have at most 6 digits."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "443839"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 3.99 s\n"
     ]
    }
   ],
   "source": [
    "ceiling = 10**6\n",
    "\n",
    "sum(n for n in range(2, ceiling) if n == sum(int(digit)**5 for digit in str(n)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p31\"></a>[Problem 31](https://projecteuler.net/problem=31)\n",
    "\n",
    "How many different ways can 2 pounds be made using any number of coins?\n",
    "\n",
    "Analysis: Dynamic programming. Approach described here: https://en.wikipedia.org/wiki/Change-making_problem"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "73682"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 4 ms\n"
     ]
    }
   ],
   "source": [
    "ways = [1] + [0] * 200\n",
    "for coin in [1, 2, 5, 10, 20, 50, 100, 200]:\n",
    "    for i in range(len(ways) - coin):\n",
    "        ways[i + coin] += ways[i]\n",
    "\n",
    "ways[-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p32\"></a>[Problem 32](https://projecteuler.net/problem=32)\n",
    "\n",
    "Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.\n",
    "\n",
    "Analysis: For *a* x *b* to be a 9-digit number, either *a* is 1-digit and *b* is 4-digit, or *a* is 2-digit and *b* is 3-digit. So *a* can be at most 2 digit and *b* at most 4 digit. (This could easily be optimized further.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "45228"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 2.33 s\n"
     ]
    }
   ],
   "source": [
    "def pandigital_products():\n",
    "    for i, j in product(range(1, 100), range(100, 10000)):\n",
    "        digits = ''.join((str(i*j), str(i), str(j)))\n",
    "        if ''.join(sorted(digits)) == '123456789':\n",
    "            yield i*j\n",
    "\n",
    "sum(set(pandigital_products()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p33\"></a>[Problem 33](https://projecteuler.net/problem=33)\n",
    "\n",
    "Discover all the fractions with an curious cancelling method."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "100"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 45 ms\n"
     ]
    }
   ],
   "source": [
    "from fractions import Fraction\n",
    "\n",
    "def curious_fractions():\n",
    "    for num, den in product(range(10, 100), range(10, 100)):\n",
    "        digits_num, digits_den = ([int(str(n)[i]) for i in range(2)] for n in (num, den))\n",
    "        if digits_num[1] == digits_den[0] and digits_den[1] != 0 and digits_num[0] / digits_den[1] == num / den:\n",
    "            yield Fraction(num, den)\n",
    "\n",
    "prod(list(curious_fractions())).denominator"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p34\"></a>[Problem 34](https://projecteuler.net/problem=34)\n",
    "\n",
    "Find the sum of all numbers which are equal to the sum of the factorial of their digits.\n",
    "\n",
    "Analysis: 9! x 8 has only 7 digits, so an upper bound is 9! * 7."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "40730"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 242 ms\n"
     ]
    }
   ],
   "source": [
    "ceiling = 10**5\n",
    "\n",
    "sum(n for n in range(3, ceiling) if sum(factorial(int(digit)) for digit in str(n)) == n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p35\"></a>[Problem 35](https://projecteuler.net/problem=35)\n",
    "\n",
    "How many circular primes are there below one million?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "55"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 206 ms\n"
     ]
    }
   ],
   "source": [
    "from sympy import sieve\n",
    "\n",
    "def rotations(n):\n",
    "    n = str(n)\n",
    "    for i in range(1, len(n)):\n",
    "        yield int(n[i:] + n[:i])\n",
    "\n",
    "primes = set(sieve.primerange(2, 10**6))\n",
    "        \n",
    "sum(1 for n in primes if all(rotation in primes for rotation in rotations(n)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p36\"></a>[Problem 36](https://projecteuler.net/problem=36)\n",
    "\n",
    "Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "872187"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 730 ms\n"
     ]
    }
   ],
   "source": [
    "def is_palindromic(n):\n",
    "    return str(n) == str(n)[::-1]\n",
    "\n",
    "def binary(n):\n",
    "    return str(bin(n))[2:]\n",
    "\n",
    "sum(n for n in range(10**6) if is_palindromic(n) and is_palindromic(binary(n)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p37\"></a>[Problem 37](https://projecteuler.net/problem=37)\n",
    "\n",
    "Find the sum of the only eleven primes that are both truncatable from left to right and right to left."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "748317"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 667 ms\n"
     ]
    }
   ],
   "source": [
    "from sympy import sieve, isprime\n",
    "\n",
    "def is_truncatable(prime):\n",
    "    s = str(prime) \n",
    "    return all(isprime(int(s[:i])) and int(isprime(s[i:])) for i in range(1, len(s)))\n",
    "\n",
    "truncatable_primes = []\n",
    "for prime in sieve:\n",
    "    if prime > 7 and is_truncatable(prime):\n",
    "        truncatable_primes.append(prime)\n",
    "        \n",
    "    if len(truncatable_primes) == 11:\n",
    "        break\n",
    "\n",
    "sum(truncatable_primes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p38\"></a>[Problem 38](https://projecteuler.net/problem=38)\n",
    "\n",
    "What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n)?\n",
    "\n",
    "Analysis: Each increment of *n* adds at least as many digits as the number has. So *n* must be less than 10, and the number of digits in the base number multiplied by n must be at most 9. (This could easily be optimized further.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "932718654"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 50 ms\n"
     ]
    }
   ],
   "source": [
    "def pandigital_concats():\n",
    "    for n in range(2, 10):\n",
    "        for i in range(1, 10**(9 // n)):\n",
    "            s = ''.join(str(i * j) for j in range(1, n + 1))\n",
    "            if ''.join(sorted(s)) == '123456789':\n",
    "                yield int(s)\n",
    "\n",
    "max(pandigital_concats())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p39\"></a>[Problem 39](https://projecteuler.net/problem=39)\n",
    "\n",
    "Find the perimeter <= 1000 for which there is the highest number of right-angled triangles with integer side lengths."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "840"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 181 ms\n"
     ]
    }
   ],
   "source": [
    "def perimeters():\n",
    "    for a, b in product(range(500), range(500)):\n",
    "        c = sqrt(a*a + b*b)\n",
    "        if c == int(c) and a+b+c <= 1000:\n",
    "            yield a+b+int(c)\n",
    "            \n",
    "Counter(perimeters()).most_common()[0][0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p40\"></a>[Problem 40](https://projecteuler.net/problem=40)\n",
    "\n",
    "An irrational decimal fraction is created by concatenating the positive integers: If dn represents the nth digit, find the value of the following expression: d1 x d10 x d100 x d1000 x d10000 x d100000 x d1000000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "210"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 71 ms\n"
     ]
    }
   ],
   "source": [
    "fraction = '0.' + ''.join([str(n) for n in range(1, 200000)])\n",
    "\n",
    "prod([int(fraction[10**power+1]) for power in range(7)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p41\"></a>[Problem 41](https://projecteuler.net/problem=41)\n",
    "\n",
    "What is the largest n-digit pandigital prime that exists?\n",
    "\n",
    "Analysis: 9 and 8 digit pandigital numbers are divisible by 3 and thus cannot be prime. We find the largest prime by starting from the highest pandigital number and going down until we find a prime."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7652413"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 82 ms\n"
     ]
    }
   ],
   "source": [
    "from sympy import isprime\n",
    "\n",
    "def number(s):\n",
    "    return int(''.join(str(digit) for digit in s))\n",
    "\n",
    "pandigital_numbers = [number(s) for ndigits in range(2, 8) for s in permutations(range(1, ndigits+1))]\n",
    "\n",
    "max(n for n in pandigital_numbers if isprime(n))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p42\"></a>[Problem 42](https://projecteuler.net/problem=42)\n",
    "\n",
    "Find the number of triangle words in a list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "162"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 256 ms\n"
     ]
    }
   ],
   "source": [
    "words = open('p/p042_words.txt').read().strip('\"').split('\",\"')\n",
    "\n",
    "def word_value(word):\n",
    "    return sum(ord(char) - ord('A') + 1 for char in word)\n",
    "\n",
    "triangle_numbers = {0.5 * n * (n + 1) for n in range(30)}\n",
    "\n",
    "sum(1 for word in words if word_value(word) in triangle_numbers)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p43\"></a>[Problem 43](https://projecteuler.net/problem=43)\n",
    "\n",
    "Find the sum of all pandigital numbers with a sub-string divisibility property."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "16695334890"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 6.79 s\n"
     ]
    }
   ],
   "source": [
    "from sympy import primerange\n",
    "\n",
    "divisors = list(primerange(1, 18))\n",
    "\n",
    "def pandigital_with_property():\n",
    "    for perm in permutations('0123456789'):\n",
    "        s = ''.join(perm)\n",
    "        if not any(int(s[start+1: start+4]) % divisor for start, divisor in enumerate(divisors)) and s[0] != \"0\":\n",
    "            yield int(s)\n",
    "        \n",
    "sum(pandigital_with_property())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p44\"></a>[Problem 44](https://projecteuler.net/problem=44)\n",
    "\n",
    "Find the pair of pentagonal numbers for which their sum and difference are pentagonal and the difference is minimized."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5482660"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 1.94 s\n"
     ]
    }
   ],
   "source": [
    "ceiling = 5000\n",
    "\n",
    "pentagonals = set(n*(3*n-1)//2 for n in range(1, ceiling))\n",
    "\n",
    "def pentagonal_pairs():\n",
    "    for p1, p2 in combinations_with_replacement(pentagonals, 2):\n",
    "        if abs(p1 - p2) in pentagonals and p1 + p2 in pentagonals:\n",
    "            yield abs(p1 - p2)\n",
    "\n",
    "min(pentagonal_pairs())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p45\"></a>[Problem 45](https://projecteuler.net/problem=45)\n",
    "\n",
    "Find the next triangle number that is also pentagonal and hexagonal."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1533776805"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 93 ms\n"
     ]
    }
   ],
   "source": [
    "ceiling = 100000\n",
    "\n",
    "tri = set([n*(n+1)//2 for n in range(ceiling)])\n",
    "pent = set([n*(3*n-1)//2 for n in range(ceiling)])\n",
    "hexa = set([n*(2*n-1) for n in range(ceiling)])\n",
    "\n",
    "min(elem for elem in tri & pent & hexa if elem > 40755)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p46\"></a>[Problem 46](https://projecteuler.net/problem=46)\n",
    "\n",
    "What is the smallest odd composite that is not a goldbach number (can be written as the sum of a prime and twice a square)?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5777"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 28 ms\n"
     ]
    }
   ],
   "source": [
    "from sympy import sieve\n",
    "\n",
    "ceiling = 10000\n",
    "primes = set(sieve.primerange(2, ceiling))\n",
    "odd_composites = set(range(3, ceiling, 2)) - primes\n",
    "squares = {i**2 for i in range(1, int(sqrt(ceiling)))}\n",
    "goldbachs = {prime + 2*square for prime, square in product(primes, squares)}\n",
    "\n",
    "min(list(odd_composites - goldbachs))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p47\"></a>[Problem 47](https://projecteuler.net/problem=47)\n",
    "\n",
    "Find the first four consecutive integers to have four distinct primes factors. What is the first of these numbers?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "134043"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 1.65 s\n"
     ]
    }
   ],
   "source": [
    "from sympy import factorint\n",
    "\n",
    "nconsecutive = nfactors = 4\n",
    "primefactorlist = []\n",
    "\n",
    "for n in count(1):\n",
    "    primefactorlist.append(factorint(n))\n",
    "    if all(len(factors) == nfactors for factors in primefactorlist[n - nconsecutive: n+1]):\n",
    "        break\n",
    "        \n",
    "n - nconsecutive + 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p48\"></a>[Problem 48](https://projecteuler.net/problem=48)\n",
    "\n",
    "Find the last ten digits of the series, 1^1 + 2^2 + 3^3 + ... + 1000^1000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9110846700"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 11 ms\n"
     ]
    }
   ],
   "source": [
    "int(str(sum([n**n for n in range(1, 1001)]))[-10:])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p49\"></a>[Problem 49](https://projecteuler.net/problem=49)\n",
    "\n",
    "Find the members of a 4-digits sequence."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "296962999629"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 38 ms\n"
     ]
    }
   ],
   "source": [
    "from sympy import isprime\n",
    "\n",
    "for n1 in range(1000, 3340):\n",
    "    n2, n3 = n1 + 3330, n1 + 6660\n",
    "    if all(isprime(n) for n in [n1, n2, n3]) and sorted(str(n1))==sorted(str(n2))==sorted(str(n3)) and n1 != 1487:\n",
    "        break\n",
    "        \n",
    "int(''.join([str(n1), str(n2), str(n3)]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p50\"></a>[Problem 50](https://projecteuler.net/problem=50)\n",
    "\n",
    "Which prime, below one-million, can be written as the sum of the most consecutive primes?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "997651"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 277 ms\n"
     ]
    }
   ],
   "source": [
    "from sympy import sieve\n",
    "\n",
    "ceiling = 10**6\n",
    "\n",
    "primes = list(sieve.primerange(2, ceiling))\n",
    "primeset = set(primes)\n",
    "\n",
    "max_consecutive = 0\n",
    "max_prime = 2\n",
    "for i in range(len(primes) -1):\n",
    "    consecutive = 0\n",
    "    primesum = primes[i]\n",
    "    while primesum < ceiling:\n",
    "        if consecutive > max_consecutive and primesum in primeset:\n",
    "            max_consecutive = consecutive\n",
    "            max_prime = primesum\n",
    "        consecutive += 1\n",
    "        primesum += primes[i+consecutive]\n",
    "\n",
    "max_prime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p51\"></a>[Problem 51](https://projecteuler.net/problem=51)\n",
    "\n",
    "Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "121313"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 3.55 s\n"
     ]
    }
   ],
   "source": [
    "from sympy import sieve\n",
    "from itertools import chain\n",
    "\n",
    "ndigits = 6\n",
    "family_size = 8\n",
    "digits = [str(i) for i in range(10)]\n",
    "primes = sieve.primerange(10**(ndigits-1), 10**ndigits)\n",
    "\n",
    "\n",
    "def replace_xs(m):\n",
    "    for i, prime in enumerate(m):\n",
    "        if prime[0] == 'x':\n",
    "            m[i] = prime.replace('x', '1')\n",
    "        else:\n",
    "            m[i] = prime.replace('x', '0') \n",
    "    return m\n",
    "\n",
    "\n",
    "def subsets(s):\n",
    "    return chain.from_iterable(combinations(s,n) for n in range(len(s)+1))\n",
    "\n",
    "\n",
    "def replace_with_xs(prime, x_indices):\n",
    "    p = list(str(prime))\n",
    "    for i in x_indices:\n",
    "        p[i] = 'x'\n",
    "    return ''.join(p)\n",
    "\n",
    "\n",
    "def primes_with_xs():\n",
    "    \"\"\"For each prime, find all possible x-containing numbers that could make that prime\"\"\"\n",
    "    for prime, digit in product(primes, digits):\n",
    "        for x_indices in subsets([i for i, elem in enumerate(str(prime)) if elem == digit]):\n",
    "            yield replace_with_xs(prime, x_indices)\n",
    "            \n",
    "m = [prime for prime, copies in Counter(primes_with_xs()).items() if copies == family_size]\n",
    "\n",
    "int(min(replace_xs(m)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p52\"></a>[Problem 52](https://projecteuler.net/problem=52)\n",
    "\n",
    "Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "142857"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 405 ms\n"
     ]
    }
   ],
   "source": [
    "next(n for n in count(1) if all(sorted(str(n)) == sorted(str(n*power)) for power in range(2,7)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p53\"></a>[Problem 53](https://projecteuler.net/problem=53)\n",
    "\n",
    "How many, not necessarily distinct, values of  nCr, for 1 ≤ n ≤ 100, are greater than one-million?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4075"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 15 ms\n"
     ]
    }
   ],
   "source": [
    "sum(1 for n in range(101) for r in range(n) if factorial(n) / (factorial(r) * factorial(n-r)) > 1000000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p54\"></a>[Problem 54](https://projecteuler.net/problem=54)\n",
    "\n",
    "How many poker hands does Player 1 win?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "376"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 103 ms\n"
     ]
    }
   ],
   "source": [
    "from itertools import groupby\n",
    "\n",
    "def rank(hand):\n",
    "    values = ['xx23456789TJQKA'.find(card[0]) for card in hand]\n",
    "    suits = [card[1] for card in hand]\n",
    "    flush = len(set(suits)) == 1\n",
    "    straight = any(i for i in range(1, 11) if all(i+j in values for j in range(5)))\n",
    "    counts = Counter(values).most_common()\n",
    "    order = []\n",
    "    for key, item in groupby(counts, itemgetter(1)):\n",
    "        order += sorted([elem[0] for elem in item], reverse=True)\n",
    "    if straight and flush:\n",
    "        return [8] + order\n",
    "    if counts[0][1] == 4:\n",
    "        return [7] + order\n",
    "    if counts[0][1] == 3 and counts[1][1] == 2:\n",
    "        return [6] + order\n",
    "    if flush:\n",
    "        return [5] + order\n",
    "    if straight:\n",
    "        return [4] + order\n",
    "    if counts[0][1] == 3:\n",
    "        return [3] + order\n",
    "    if counts[0][1] == 2 and counts[1][1] == 2:\n",
    "        return [2] + order\n",
    "    if counts[0][1] == 2:\n",
    "        return [1] + order\n",
    "    return [0] + order\n",
    "\n",
    "\n",
    "def hands():\n",
    "    with open('p/p054_poker.txt') as inp:\n",
    "        for line in inp.readlines():\n",
    "            yield line.split()[:5], line.split()[5:]\n",
    "\n",
    "sum(rank(hand1) > rank(hand2) for hand1, hand2 in hands())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p55\"></a>[Problem 55](https://projecteuler.net/problem=55)\n",
    "\n",
    "How many Lychrel numbers are there below ten-thousand?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "249"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 76 ms\n"
     ]
    }
   ],
   "source": [
    "max_iterations = 50\n",
    "\n",
    "def is_lychrel(n):\n",
    "    for _ in range(max_iterations):\n",
    "        n = str(int(n) + int(str(n)[::-1]))\n",
    "        if n == n[::-1]:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "sum(is_lychrel(n) for n in range(10000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p56\"></a>[Problem 56](https://projecteuler.net/problem=56)\n",
    "\n",
    "Considering natural numbers of the form, a^b, where a, b < 100, what is the maximum digital sum?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "972"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 248 ms\n"
     ]
    }
   ],
   "source": [
    "max(sum(int(digit) for digit in str(a**b)) for a, b in product(range(100), range(100)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p57\"></a>[Problem 57](https://projecteuler.net/problem=57)\n",
    "\n",
    "In the first one-thousand expansions of the square root of 2, how many fractions contain a numerator with more digits than denominator?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "153"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 83 ms\n"
     ]
    }
   ],
   "source": [
    "from fractions import Fraction\n",
    "\n",
    "co = 0\n",
    "expander = 2\n",
    "\n",
    "for _ in range(1000):\n",
    "    expander = Fraction(2 + 1/expander)\n",
    "    fraction = Fraction(1 + 1/expander)\n",
    "\n",
    "    if len(str(fraction.numerator)) > len(str(fraction.denominator)):\n",
    "        co += 1\n",
    "        \n",
    "co"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p58\"></a>[Problem 58](https://projecteuler.net/problem=58)\n",
    "\n",
    "What is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "26241"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 685 ms\n"
     ]
    }
   ],
   "source": [
    "from sympy import isprime\n",
    "\n",
    "diagonal_number = 1\n",
    "primes = 0\n",
    "for sidelength in count(3, 2):\n",
    "    for corner in range(4):\n",
    "        diagonal_number += sidelength - 1\n",
    "        if isprime(diagonal_number):\n",
    "            primes += 1\n",
    "\n",
    "    if primes / (sidelength * 2 - 1) < 0.1:\n",
    "        break\n",
    "\n",
    "sidelength"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p59\"></a>[Problem 59](https://projecteuler.net/problem=59)\n",
    "\n",
    "Find the key that decrypts a file.\n",
    "\n",
    "Analysis: We check all possible keys, and identify the key that finds the most common words."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "107359"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 7.15 s\n"
     ]
    }
   ],
   "source": [
    "common_words = {'the', 'and', 'be', 'of', 'that', 'have', 'for', 'it', 'not', 'on', 'with', 'you'}\n",
    "ciphertext = [int(s) for line in open(\"p/p059_cipher.txt\") for s in line.split(',')]\n",
    "\n",
    "max_words_found = 0\n",
    "for key in product(range(97, 123), repeat=3):\n",
    "    decrypted = [chr(ciphertext[i] ^ key[i % len(key)]) for i in range(len(ciphertext))]\n",
    "    text = ''.join(decrypted).split()\n",
    "    words_found = len([word for word in text if word in common_words])\n",
    "    if words_found > max_words_found:\n",
    "        max_words_found = words_found\n",
    "        best_sum = sum([ciphertext[i] ^ key[i % len(key)] for i in range(len(ciphertext))])\n",
    "\n",
    "best_sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p60\"></a>[Problem 60](https://projecteuler.net/problem=60)\n",
    "\n",
    "Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.\n",
    "\n",
    "Analysis: We add the primes recursively one at a time, so that all primes in the set concatenate with each other."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "26033"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 12.3 s\n"
     ]
    }
   ],
   "source": [
    "from sympy import sieve, isprime\n",
    "\n",
    "primes = list(sieve.primerange(2, 10000))\n",
    "\n",
    "def all_concats_are_prime(primelist, prime_index):\n",
    "    primelist = [str(primes[i]) for i in primelist]\n",
    "    p1 = str(primes[prime_index])\n",
    "    return all(isprime(int(p1 + p2)) and isprime(int(p2 + p1)) for p2 in primelist)\n",
    "\n",
    "def find_primeset(primelist):\n",
    "    if len(primelist) == 5:\n",
    "        return primelist\n",
    "\n",
    "    start = primelist[-1] if primelist else 0\n",
    "\n",
    "    for i in range(start, len(primes)):\n",
    "        if all_concats_are_prime(primelist, i):\n",
    "            result = find_primeset(primelist + [i])\n",
    "            if result:\n",
    "                return result\n",
    "\n",
    "sum([primes[p] for p in find_primeset([])])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p61\"></a>[Problem 61](https://projecteuler.net/problem=61)\n",
    "\n",
    "Find the sum of the only ordered set of six cyclic 4-digit numbers for which each polygonal type: triangle, square, pentagonal, hexagonal, heptagonal, and octagonal, is represented by a different number in the set.\n",
    "\n",
    "Analysis: Build the sets recursively. Each new addition to the set must be cyclic with the previous number, and be of a new polygonal type."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "28684"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 140 ms\n"
     ]
    }
   ],
   "source": [
    "low, high = 1000, 10000\n",
    "\n",
    "def gen(func, low, high):\n",
    "    for n in count(1):\n",
    "        if func(n) > high:\n",
    "            break\n",
    "        if func(n) >= low:\n",
    "            yield func(n)\n",
    "\n",
    "polygons = {\n",
    "    'triangle': set(gen(lambda n: n * (n + 1) // 2, low, high)),\n",
    "    'square': set(gen(lambda n: n**2, low, high)),\n",
    "    'pentagonal': set(gen(lambda n: n * (3 * n -1) // 2, low, high)),\n",
    "    'hexagonal': set(gen(lambda n: n * (2*n -1), low, high)),\n",
    "    'heptagonal': set(gen(lambda n: n * (5*n -3) // 2, low, high)),\n",
    "    'octogonal': set(gen(lambda n: n * (3*n -2), low, high)),\n",
    "}\n",
    "\n",
    "def cycle(number):\n",
    "    for i in range(10, 100):\n",
    "        yield int(str(number)[-2:] + str(i))\n",
    "    \n",
    "\n",
    "def get_chain(starting_number, remaining_polygons, number):\n",
    "    if not remaining_polygons:\n",
    "        if starting_number in set(cycle(number)):\n",
    "            return starting_number\n",
    "        return\n",
    "\n",
    "    for next_number, polygon in product(cycle(number), remaining_polygons):\n",
    "        if next_number in polygons[polygon]:\n",
    "            result = get_chain(starting_number, remaining_polygons.copy() - {polygon}, next_number)\n",
    "            if result:\n",
    "                return next_number + result\n",
    "\n",
    "for number in polygons['pentagonal']:\n",
    "    result = get_chain(number, set(polygons) - {'pentagonal'}, number)\n",
    "    if result:\n",
    "        break\n",
    "        \n",
    "result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p62\"></a>[Problem 62](https://projecteuler.net/problem=62)\n",
    "\n",
    "Find the smallest cube for which exactly five permutations of its digits are cube."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "127035954683"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 54 ms\n"
     ]
    }
   ],
   "source": [
    "d = defaultdict(list)\n",
    "for n in range(10000):\n",
    "    d[str(sorted(str(n**3)))].append(n)\n",
    "\n",
    "min(min(basenumbers)**3 for basenumbers in d.values() if len(basenumbers) == 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [Problem 63](https://projecteuler.net/problem=63)\n",
    "\n",
    "How many n-digit positive integers exist which are also an nth power?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "49"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 17 ms\n"
     ]
    }
   ],
   "source": [
    "sum(len(str(a**b)) == b for a in range(1,100) for b in range(1, 100))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p64\"></a>[Problem 64](https://projecteuler.net/problem=64)\n",
    "\n",
    "How many continued fractions for N ≤ 10000 have an odd period?\n",
    "\n",
    "Analysis: Algorithm from https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1322"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 310 ms\n"
     ]
    }
   ],
   "source": [
    "from math import floor\n",
    "\n",
    "def continued_fraction(n):\n",
    "    m = 0\n",
    "    d = 1\n",
    "    a0 = a = floor(n ** 0.5)\n",
    "    while 2 * a0 != a:\n",
    "        m =  d * a - m\n",
    "        d = (n - (m ** 2)) / d\n",
    "        a = floor((a0 + m) / d)\n",
    "        yield a\n",
    "   \n",
    "def non_squares_up_to(hi):\n",
    "    for n in range(1, hi):\n",
    "        if sqrt(n) != floor(sqrt(n)):\n",
    "            yield n\n",
    "\n",
    "sum(len(list(continued_fraction(n))) % 2 != 0 for n in non_squares_up_to(10000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p65\"></a>[Problem 65](https://projecteuler.net/problem=65)\n",
    "\n",
    "Find the sum of digits in the numerator of the 100th convergent of the continued fraction for e."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "272"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 7 ms\n"
     ]
    }
   ],
   "source": [
    "def continued_fraction(i):\n",
    "    if i % 3 == 2:\n",
    "        return i // 3 * 2 + 2\n",
    "    else:\n",
    "        return 1\n",
    "\n",
    "numerator, denominator = 2, 1\n",
    "for i in range(1, 100):\n",
    "    numerator, denominator = continued_fraction(i) * numerator + denominator, numerator\n",
    "\n",
    "sum(int(digit) for digit in str(numerator))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p66\"></a>[Problem 66](https://projecteuler.net/problem=66)\n",
    "\n",
    "Solve diophantine equations.\n",
    "\n",
    "Analysis: Method from https://en.wikipedia.org/wiki/Chakravala_method"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "661"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 46 ms\n"
     ]
    }
   ],
   "source": [
    "def chakravala(N):\n",
    "    sq = int(floor(sqrt(N)))\n",
    "    a, b, k, m = sq, 1, sq**2 - N, sq\n",
    "    while k != 1:\n",
    "        m = ((m + sq) // k) * k - m \n",
    "        a, b, k = (a*m + N*b) // abs(k), (a + b*m) // abs(k), (m**2 - N) // k\n",
    "    return a\n",
    " \n",
    "max_x, max_D = 0, 0\n",
    "for D in range(1, 1001):\n",
    "    if floor(sqrt(D)) != sqrt(D):\n",
    "        x = chakravala(D)\n",
    "        if x > max_x:\n",
    "            max_x, max_D = x, D\n",
    "max_D"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p67\"></a>[Problem 67](https://projecteuler.net/problem=67)\n",
    "\n",
    "Find the maximum sum traveling from the top of the triangle to the base.\n",
    "\n",
    "Analysis: Reuse of code from problem 18."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7273"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 22 ms\n"
     ]
    }
   ],
   "source": [
    "with open('p/p067_triangle.txt') as inp:\n",
    "    a = [[int(elem) for elem in line.split()] for line in inp]\n",
    "\n",
    "for row in reversed(range(len(a) -1)):\n",
    "    for col in range(len(a[row])):\n",
    "        a[row][col] += max(a[row+1][col], a[row+1][col +1])\n",
    "\n",
    "a[0][0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p68\"></a>[Problem 68](https://projecteuler.net/problem=68)\n",
    "\n",
    "What is the maximum 16-digit string for a \"magic\" 5-gon ring?\n",
    "\n",
    "Analysis: For each permutation, use only one of the five symmetrical configurations, and look only at permutations where all arms have equal sum."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'6531031914842725'"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 7.39 s\n"
     ]
    }
   ],
   "source": [
    "def magic_strings():\n",
    "    arms = [[0, 5, 6], [1, 6, 7], [2, 7, 8], [3, 8, 9], [4, 9, 5]]\n",
    "    for ring in permutations(range(1, 11)):\n",
    "        if all(ring[0] < ring[i] for i in range(1, 5)):\n",
    "            if len(set(sum(ring[i] for i in arms[j]) for j in range(5))) == 1:\n",
    "                s = \"\".join((str(ring[arms[i][j]]) for i in range(5) for j in range(3)))\n",
    "                if len(s) == 16:\n",
    "                    yield s\n",
    "\n",
    "max(magic_strings())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p69\"></a>[Problem 69](https://projecteuler.net/problem=69)\n",
    "\n",
    "Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.\n",
    "\n",
    "Analysis: n/φ(n) is lowest when n has the most prime factors compared to its size. This is the case when n is a primorial"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "510510"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 3 ms\n"
     ]
    }
   ],
   "source": [
    "from sympy.ntheory.generate import primorial\n",
    "\n",
    "primorial(max(takewhile(lambda n: primorial(n) <= 10**6, count(1))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p70\"></a>[Problem 70](https://projecteuler.net/problem=70)\n",
    "\n",
    "Find the value of n, 1 < n < 10^7, for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum\n",
    "\n",
    "Analysis: φ is lowest when its the product of exactly two primes. The algorithm searches through pairs of primes and saves the best pair product."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8319823"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 598 ms\n"
     ]
    }
   ],
   "source": [
    "from sympy import sieve\n",
    "\n",
    "ceiling = 10**7\n",
    "\n",
    "primes = sieve.primerange(2, int(sqrt(1.3 * int(ceiling))))\n",
    "\n",
    "def phi_is_permutation():\n",
    "    for p1, p2 in product(primes, repeat=2):\n",
    "        n = p1 * p2\n",
    "        phi = (1 - p1) * (1 - p2)\n",
    "        if n <= ceiling and sorted(str(n)) == sorted(str(phi)):\n",
    "            yield [n / phi, n]\n",
    "\n",
    "min(phi_is_permutation(), key=itemgetter(0))[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p71\"></a>[Problem 71](https://projecteuler.net/problem=71)\n",
    "\n",
    "By listing the set of reduced proper fractions for d ≤ 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "428570"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 4 ms\n"
     ]
    }
   ],
   "source": [
    "from fractions import Fraction\n",
    "\n",
    "def find_nearest_fraction(fraction, ceiling):\n",
    "    while 1:\n",
    "        new_fraction = (fraction - Fraction(1, ceiling*10)).limit_denominator(ceiling)\n",
    "        if new_fraction < fraction:\n",
    "            return new_fraction\n",
    "\n",
    "find_nearest_fraction(Fraction(3, 7), 10**6).numerator"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p72\"></a>[Problem 72](https://projecteuler.net/problem=72)\n",
    "\n",
    "How many elements would be contained in the set of reduced proper fractions for d ≤ 1,000,000?\n",
    "\n",
    "Analysis: Go through the primes in order. For each prime, update all the values of d and discount the denominators for which the fraction could be reduced by that prime."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "30396356427241"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 15.1 s\n"
     ]
    }
   ],
   "source": [
    "ceiling = 10**7\n",
    "\n",
    "d = list(range(ceiling+1))\n",
    "for n in range(2, ceiling+1):\n",
    "    if d[n] == n:\n",
    "        for k in range(n, ceiling+1, n):\n",
    "            d[k] -= d[k] // n\n",
    "sum(d) - 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p73\"></a>[Problem 73](https://projecteuler.net/problem=73)\n",
    "\n",
    "How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d ≤ 12,000?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7295372"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 4.01 s\n"
     ]
    }
   ],
   "source": [
    "from math import gcd\n",
    "\n",
    "ceiling = 12000\n",
    "\n",
    "sum(1 for denom in range(4, ceiling + 1) for num in range(denom//3 + 1, denom//2 + 1) if gcd(num, denom) == 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p74\"></a>[Problem 74](https://projecteuler.net/problem=74)\n",
    "\n",
    "How many chains, with a starting number below one million, contain exactly sixty non-repeating terms?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "402"
      ]
     },
     "execution_count": 75,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 9.02 s\n"
     ]
    }
   ],
   "source": [
    "chain_length = {\n",
    "    169: 3,\n",
    "    363601: 3,\n",
    "    1454: 3,\n",
    "    871: 2,\n",
    "    45361: 2,\n",
    "    872: 2,\n",
    "    45362: 2\n",
    "}\n",
    "\n",
    "@lru_cache(2**20)\n",
    "def get_chain(n):\n",
    "    for steps in count(0):\n",
    "        if n in chain_length:\n",
    "            return steps + chain_length[n]\n",
    "        next_n = sum(factorial(int(digit)) for digit in str(n))\n",
    "        if next_n == n:\n",
    "            return steps + 1\n",
    "        n = next_n\n",
    "\n",
    "for number in range(1, 10**6):\n",
    "    chain_length[number] = get_chain(number)\n",
    "\n",
    "sum(length == 60 for length in chain_length.values())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p75\"></a>[Problem 75](https://projecteuler.net/problem=75)\n",
    "\n",
    "Given that L is the length of the wire, for how many values of L ≤ 1,500,000 can exactly one integer sided right angle triangle be formed?\n",
    "\n",
    "Analysis: Formula from https://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "161667"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 2.82 s\n"
     ]
    }
   ],
   "source": [
    "from math import gcd\n",
    "\n",
    "ceiling = 1500000\n",
    "\n",
    "def perimeters():\n",
    "    for n in range(1, int(sqrt(ceiling))):\n",
    "        for m in range(n+1, int(sqrt(ceiling)), 2):\n",
    "            if gcd(m, n) == 1:\n",
    "                for k in count(1):\n",
    "                    perimeter = k*(m**2 - n**2 + 2*m*n + m**2 + n**2)\n",
    "                    if perimeter > ceiling:\n",
    "                        break\n",
    "                    yield perimeter\n",
    "\n",
    "sum(value == 1 for value in Counter(perimeters()).values())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p76\"></a>[Problem 76](https://projecteuler.net/problem=76)\n",
    "\n",
    "How many different ways can one hundred be written as a sum of at least two positive integers?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "190569291"
      ]
     },
     "execution_count": 77,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 47 ms\n"
     ]
    }
   ],
   "source": [
    "from sympy.functions.combinatorial.numbers import nT\n",
    "\n",
    "nT(100) -1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p77\"></a>[Problem 77](https://projecteuler.net/problem=77)\n",
    "\n",
    "What is the first value which can be written as the sum of primes in over five thousand different ways?\n",
    "\n",
    "Analysis: Reuse of code from problem 31."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "71"
      ]
     },
     "execution_count": 78,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 5 ms\n"
     ]
    }
   ],
   "source": [
    "from sympy import sieve\n",
    "\n",
    "ceiling = 100\n",
    "\n",
    "ways = [1] + [0] * ceiling\n",
    "for prime in sieve.primerange(2, ceiling+1):\n",
    "    for i in range(len(ways) - prime):\n",
    "        ways[i + prime] += ways[i]\n",
    "     \n",
    "min(i for i, number_of_ways in enumerate(ways) if number_of_ways > 5000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p78\"></a>[Problem 78](https://projecteuler.net/problem=78)\n",
    "\n",
    "Let p(n) represent the number of different ways in which n coins can be separated into piles. Find the least value of n for which p(n) is divisible by one million.\n",
    "\n",
    "Analysis: Solution from \n",
    "<https://en.wikipedia.org/wiki/Partition_(number_theory)>:  \n",
    "p(k) = p(k − 1) + p(k − 2) − p(k − 5) − p(k − 7) + p(k − 12) + p(k − 15) − p(k − 22) − ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "55374"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 7.56 s\n"
     ]
    }
   ],
   "source": [
    "from itertools import cycle\n",
    "\n",
    "partitions = [1]\n",
    "pentagonals = sorted([n*(3*n - 1)//2 for n in range(-250, 250)])\n",
    "\n",
    "for n in count(1):\n",
    "    signs = cycle([1, 1, -1, -1])\n",
    "    use_pentagonals = [p for p in pentagonals if 0 < p <= n]\n",
    "\n",
    "    number_of_partitions = sum(sign * partitions[n - p] for sign, p in zip(signs, use_pentagonals))\n",
    "    if number_of_partitions % 10**6 == 0:\n",
    "        break\n",
    "    \n",
    "    partitions.append(number_of_partitions)\n",
    "\n",
    "n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p79\"></a>[Problem 79](https://projecteuler.net/problem=79)\n",
    "\n",
    "Analyse the file so as to determine the shortest possible secret passcode of unknown length.\n",
    "\n",
    "Analysis: Sort the numbers in order of how many different numbers appear after it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'73162890'"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 10 ms\n"
     ]
    }
   ],
   "source": [
    "logins = set([line.strip() for line in open('p/p079_keylog.txt')])\n",
    "\n",
    "numbers_pressed_after = defaultdict(set)\n",
    "for login in logins:\n",
    "    numbers_pressed_after[login[0]].add(login[1])\n",
    "    numbers_pressed_after[login[0]].add(login[2])\n",
    "    numbers_pressed_after[login[1]].add(login[2])\n",
    "    numbers_pressed_after[login[2]].add('')\n",
    " \n",
    "''.join([t[1] for t in sorted([(len(v), k) for k, v in numbers_pressed_after.items()], reverse=True)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p80\"></a>[Problem 80](https://projecteuler.net/problem=80)\n",
    "\n",
    "For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all the irrational square roots."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "40886"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 18 ms\n"
     ]
    }
   ],
   "source": [
    "from decimal import Decimal, Context\n",
    "\n",
    "sum(int(digit) for n in range(2, 101) for digit in str(Decimal(n).sqrt(Context(prec=102))).replace('.', '')[:-2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p81\"></a>[Problem 81](https://projecteuler.net/problem=81)\n",
    "\n",
    "Find the minimal path sum in a matrix from the top left to the bottom right by only moving right and down."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "427337"
      ]
     },
     "execution_count": 82,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 2.51 s\n"
     ]
    }
   ],
   "source": [
    "import networkx as nx\n",
    "\n",
    "matrix = {(row, col): int(n) for row, line in enumerate(open('p/p081_matrix.txt')) for col, n in enumerate(line.split(','))}\n",
    "\n",
    "start, end = (0,-1), max(matrix)\n",
    "\n",
    "matrix[start] = 0\n",
    "\n",
    "directions = {(1,0), (0,1)}\n",
    "\n",
    "def moves(tile):\n",
    "    return {(tile[0] + move[0], tile[1] + move[1]) for move in directions} & set(matrix)\n",
    "\n",
    "G = nx.DiGraph()\n",
    "for tile in matrix:\n",
    "    for adjacent_tile in moves(tile):\n",
    "        G.add_edge(tile, adjacent_tile, weight = matrix[adjacent_tile])\n",
    "\n",
    "nx.dijkstra_path_length(G, source=start, target=end)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p82\"></a>[Problem 82](https://projecteuler.net/problem=82)\n",
    "\n",
    "Find the minimal path sum in a matrix from the left column to the right column, only moving up, down and right."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "260324"
      ]
     },
     "execution_count": 83,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 2.91 s\n"
     ]
    }
   ],
   "source": [
    "import networkx as nx\n",
    "\n",
    "matrix = {(row, col): int(n) for row, line in enumerate(open('p/p081_matrix.txt')) for col, n in enumerate(line.split(','))}\n",
    "\n",
    "nrows, ncols = max(matrix)\n",
    "\n",
    "starts = {(row, -1) for row in range(nrows)}\n",
    "ends = {(row, ncols) for row in range(nrows)}\n",
    "\n",
    "for start in starts:\n",
    "    matrix[start] = 0\n",
    "\n",
    "directions = {(0, -1), (0, 1), (-1,0), (1,0)}\n",
    "\n",
    "def moves(tile):\n",
    "    return {(tile[0] + move[0], tile[1] + move[1]) for move in directions} & set(matrix)\n",
    "\n",
    "G = nx.DiGraph()\n",
    "for tile in matrix:\n",
    "    for adjacent_tile in moves(tile) & set(matrix):\n",
    "        G.add_edge(tile, adjacent_tile, weight = matrix[adjacent_tile])\n",
    "        \n",
    "paths = nx.single_source_dijkstra_path_length(G, source=(0, -1))\n",
    "\n",
    "min(val for tile, val in paths.items() if tile in ends)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p83\"></a>[Problem 83](https://projecteuler.net/problem=83)\n",
    "\n",
    "Find the minimal path sum ain matrix from the top left to the bottom right by moving left, right, up, and down."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "425185"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 2.04 s\n"
     ]
    }
   ],
   "source": [
    "import networkx as nx\n",
    "\n",
    "matrix = {(row, col): int(n) for row, line in enumerate(open('p/p081_matrix.txt')) for col, n in enumerate(line.split(','))}\n",
    "\n",
    "start, end = (0,-1), max(matrix)\n",
    "\n",
    "matrix[start] = 0\n",
    "\n",
    "directions = {(-1,0), (0,-1), (1,0), (0,1)}\n",
    "\n",
    "def moves(tile):\n",
    "    return {(tile[0] + move[0], tile[1] + move[1]) for move in directions} & set(matrix)\n",
    "\n",
    "G = nx.DiGraph()\n",
    "for tile in matrix:\n",
    "    for adjacent_tile in moves(tile):\n",
    "        G.add_edge(tile, adjacent_tile, weight = matrix[adjacent_tile])\n",
    "\n",
    "nx.dijkstra_path_length(G, source=start, target=end)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p84\"></a>[Problem 84](https://projecteuler.net/problem=84)\n",
    "\n",
    "Find the squares that you land most often on in a game of monopoly.\n",
    "\n",
    "Analysis: We ignore the order of cards, and instead treat it as a random pick each turn. Likewise three double rolls in a row is treated as an independent event with likelihood 1/n^3."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'101516'"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 499 ms\n"
     ]
    }
   ],
   "source": [
    "\n",
    "from random import choice, randint\n",
    "\n",
    "class Tiles():\n",
    "    GO = 0\n",
    "    CC1 = 2\n",
    "    R1 = 5\n",
    "    CH1 = 7\n",
    "    JAIL = 10\n",
    "    C1 = 11\n",
    "    U1 = 12\n",
    "    R2 = 15\n",
    "    CC2 = 17\n",
    "    CH2 = 22\n",
    "    E3 = 24\n",
    "    R3 = 25\n",
    "    U2 = 28\n",
    "    G2J = 30\n",
    "    CC3 = 33\n",
    "    R4 = 35\n",
    "    CH3 = 36\n",
    "    H2 = 39\n",
    "\n",
    "dice_sides = 4\n",
    "dice = range(1, dice_sides + 1)\n",
    "community_chest = [Tiles.GO, Tiles.JAIL] + ['']*14\n",
    "\n",
    "next_R = {\n",
    "    Tiles.CH1: Tiles.R2,\n",
    "    Tiles.CH2: Tiles.R3,\n",
    "    Tiles.CH3: Tiles.R1\n",
    "}\n",
    "\n",
    "next_U = {\n",
    "    Tiles.CH1: Tiles.U1,\n",
    "    Tiles.CH2: Tiles.U2,\n",
    "    Tiles.CH3: Tiles.U1\n",
    "}\n",
    "\n",
    "chance = [Tiles.GO, Tiles.JAIL, Tiles.C1, Tiles.E3, Tiles.H2, Tiles.R1, next_R, \n",
    "          next_R, next_U, 'Go back 3 squares'] + ['']*6\n",
    "\n",
    "pos = Tiles.GO\n",
    "\n",
    "\n",
    "def get_next(pos):\n",
    "    \n",
    "    roll = (choice(dice), choice(dice))\n",
    "\n",
    "    if roll[0] == roll[1] and randint(1, dice_sides**2) == 1:\n",
    "        return Tiles.JAIL\n",
    "    \n",
    "    pos += sum(roll)\n",
    "    if pos >= 40:\n",
    "        pos -= 40\n",
    "    \n",
    "    if pos in {Tiles.CC1, Tiles.CC2, Tiles.CC3}:\n",
    "        card = choice(community_chest)\n",
    "        if type(card) is int:\n",
    "            return card\n",
    "        \n",
    "    if pos in {Tiles.CH1, Tiles.CH2, Tiles.CH3}:\n",
    "        card = choice(chance)\n",
    "        if type(card) is int:\n",
    "            return card\n",
    "        elif type(card) is dict:\n",
    "            return card[pos]\n",
    "        elif card == 'Go back 3 squares':\n",
    "            pos -= 3 \n",
    "            if pos < 0:\n",
    "                pos += 40\n",
    "    \n",
    "    if pos == Tiles.G2J:\n",
    "        return Tiles.JAIL\n",
    "    \n",
    "    return pos\n",
    "        \n",
    "c = Counter()\n",
    "pos = Tiles.GO\n",
    "for _ in range(10**5):\n",
    "    pos = get_next(pos)\n",
    "    c[pos] += 1\n",
    "\n",
    "result = c.most_common(3)\n",
    "''.join(str(item[0]) for item in result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p85\"></a>[Problem 85](https://projecteuler.net/problem=85)\n",
    "\n",
    "Although there exists no rectangular grid that contains exactly two million rectangles, find the area of the grid with the nearest solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2772"
      ]
     },
     "execution_count": 86,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 4.48 s\n"
     ]
    }
   ],
   "source": [
    "def rectangles(x, y):\n",
    "    return sum((x + 1 - a) * (y + 1 - b) for a, b in product(range(1, x+1), range(1, y+1)))\n",
    "\n",
    "prod(min(product(range(1, 100), repeat=2), key=lambda sides: abs(rectangles(*sides) - 2*10**6)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p86\"></a>[Problem 86](https://projecteuler.net/problem=86)\n",
    "\n",
    "Investigate routes in a cuboid."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1818"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 4.81 s\n"
     ]
    }
   ],
   "source": [
    "def solutions_with_largest_side_equal_to(a):\n",
    "    for bc in range(1, 2 * a + 1):\n",
    "        route = sqrt(a**2 + bc**2)\n",
    "        if route == round(route):\n",
    "            for c in range(1, bc//2 + 1):\n",
    "                b = bc - c\n",
    "                if a >= b:\n",
    "                    yield a, b, c\n",
    "\n",
    "solutions = []\n",
    "for M in count(1):\n",
    "    solutions += solutions_with_largest_side_equal_to(M)\n",
    "    if len(solutions) > 1000000:\n",
    "        break\n",
    "\n",
    "M"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p87\"></a>[Problem 87](https://projecteuler.net/problem=87)\n",
    "\n",
    "How many numbers below fifty million can be expressed as the sum of a prime square, prime cube, and prime fourth power?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1097343"
      ]
     },
     "execution_count": 88,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 819 ms\n"
     ]
    }
   ],
   "source": [
    "from sympy import sieve\n",
    "from fractions import Fraction\n",
    "\n",
    "ceiling = 5*10**7\n",
    "\n",
    "def powers(power):\n",
    "    max_root = round(pow(ceiling, Fraction(1, power))) + 1\n",
    "    for n in sieve.primerange(2, max_root):\n",
    "        yield n**power\n",
    "\n",
    "len(set(sum(triplet) for triplet in product(powers(2), powers(3), powers(4)) if sum(triplet) < ceiling))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p88\"></a>[Problem 88](https://projecteuler.net/problem=88)\n",
    "\n",
    "What is the sum of all the minimal product-sum numbers for 2≤k≤12000?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7587457"
      ]
     },
     "execution_count": 89,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 6.94 s\n"
     ]
    }
   ],
   "source": [
    "min_solutions = defaultdict(lambda: 10**9)\n",
    "ceiling = 12000\n",
    "\n",
    "def get_solutions(nfactors, nproduct, nsum):\n",
    "    k = nfactors + nproduct - nsum\n",
    "    if k > ceiling:\n",
    "        return\n",
    "    min_solutions[k] = min(min_solutions[k], nproduct)\n",
    "\n",
    "    for n in range(2, int(2*ceiling / nproduct) + 1):\n",
    "        get_solutions(nfactors+1, n*nproduct, nsum+n)\n",
    "\n",
    "get_solutions(1, 1, 1)\n",
    "\n",
    "sum(set(val for k, val in min_solutions.items() if k >= 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p89\"></a>[Problem 89](https://projecteuler.net/problem=89)\n",
    "\n",
    "Find the minimal form of roman numerals."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "743"
      ]
     },
     "execution_count": 90,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 6 ms\n"
     ]
    }
   ],
   "source": [
    "romans = [line.strip() for line in open('p/p089_roman.txt')]\n",
    "\n",
    "savedict = {'VIIII': 1, 'IIII': 2, 'LXXXX': 1, 'XXXX': 2, 'DCCCC': 1, 'CCCC': 2}\n",
    "\n",
    "sum(val for roman in romans for key, val in savedict.items() if key in roman)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p90\"></a>[Problem 90](https://projecteuler.net/problem=90)\n",
    "\n",
    "How many distinct arrangements of the two cubes allow for all of the square numbers to be displayed?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1217"
      ]
     },
     "execution_count": 91,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 448 ms\n"
     ]
    }
   ],
   "source": [
    "from itertools import chain\n",
    "\n",
    "squares = {'01', '04', '06', '16', '25', '36', '46', '64', '81'}\n",
    "numbers = [str(i) for i in range(9)] + ['6']\n",
    "\n",
    "\n",
    "def configuration_works(cube1, cube2):\n",
    "    possible_displays = {''.join(faces) for faces in chain(product(cube1, cube2), product(cube2, cube1))}\n",
    "    return squares.issubset(possible_displays)\n",
    "\n",
    "\n",
    "def get_solutions():\n",
    "    for cube1, cube2 in combinations_with_replacement(combinations(numbers, 6), 2):      \n",
    "        if configuration_works(cube1, cube2):\n",
    "            yield (cube1, cube2)\n",
    "\n",
    "len(list(get_solutions()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p91\"></a>[Problem 91](https://projecteuler.net/problem=91)\n",
    "\n",
    "How many right triangles can be formed in a 50*50 grid?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "14234"
      ]
     },
     "execution_count": 92,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 13.3 s\n"
     ]
    }
   ],
   "source": [
    "from collections import namedtuple\n",
    "\n",
    "Point = namedtuple('Point', 'x y')\n",
    "origin = Point(0,0)\n",
    "\n",
    "\n",
    "def length_of_side_squared(p1, p2):\n",
    "    return (p2.x - p1.x)**2 + (p2.y - p1.y)**2\n",
    "\n",
    "\n",
    "def right_angled_triangles(n):\n",
    "    points = {Point(x,y) for x, y in product(range(0, n+1), repeat=2)} - {origin}\n",
    "    \n",
    "    for p1, p2 in combinations(points, 2):\n",
    "        a2 = length_of_side_squared(p1, origin)\n",
    "        b2 = length_of_side_squared(p2, origin)\n",
    "        c2 = length_of_side_squared(p1, p2)\n",
    "        if a2+b2==c2 or a2+c2==b2 or c2+b2==a2:\n",
    "            yield([p1, p2, origin])\n",
    "\n",
    "len(list(right_angled_triangles(50)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p92\"></a>[Problem 92](https://projecteuler.net/problem=92)\n",
    "\n",
    "A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before. How many starting numbers below ten million will arrive at 89?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8581146"
      ]
     },
     "execution_count": 93,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 57.1 s\n"
     ]
    }
   ],
   "source": [
    "@lru_cache(2**20)\n",
    "def is89chain(n):\n",
    "    if n == 1: return False\n",
    "    if n == 89: return True\n",
    "    return is89chain(sum((int(digit)**2 for digit in str(n))))\n",
    "\n",
    "sum(is89chain(i) for i in range(2, 10**7))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p93\"></a>[Problem 93](https://projecteuler.net/problem=93)\n",
    "\n",
    "Find the set of four distinct digits, a < b < c < d, for which the longest set of consecutive positive integers, 1 to n, can be obtained, giving your answer as a string: abcd."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'1258'"
      ]
     },
     "execution_count": 94,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 364 ms\n"
     ]
    }
   ],
   "source": [
    "all_operations = [lambda x, y: x + y, \n",
    "                  lambda x, y: x*y, \n",
    "                  lambda x, y: x - y, \n",
    "                  lambda x,y: x/y]\n",
    "\n",
    "\n",
    "def targets(orig_digits):\n",
    "    for a,b,c,d in permutations(orig_digits):\n",
    "        for operations in product(all_operations, repeat=3):  \n",
    "            target = operations[0](operations[1](operations[2](a, b), c), d)\n",
    "            if target > 0 and round(target) == target:\n",
    "                yield target\n",
    "\n",
    "            target = operations[0](operations[1](a, b), operations[2](c, d))\n",
    "            if target > 0 and round(target) == target:\n",
    "                yield target\n",
    "\n",
    "                \n",
    "def consecutive_integers(integers):\n",
    "    for i, elem in enumerate(set(integers)):\n",
    "        if i+1 != elem:\n",
    "            return i\n",
    "\n",
    "result = max(combinations(range(1, 10), 4), key=lambda digits: consecutive_integers(targets(digits)))\n",
    "\n",
    "''.join(str(digit) for digit in result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p94\"></a>[Problem 94](https://projecteuler.net/problem=94)\n",
    "\n",
    "Find the sum of the perimeters of all almost equilateral triangles with integral side lengths and area and whose perimeters do not exceed one billion."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "518408346"
      ]
     },
     "execution_count": 95,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 929 ms\n"
     ]
    }
   ],
   "source": [
    "from sympy.geometry import Triangle\n",
    "from sympy.solvers.solvers import check_assumptions\n",
    "\n",
    "def seq(n):\n",
    "    if n == 0 or n == 1:\n",
    "        return 1\n",
    "    if n == 2:\n",
    "        return 5\n",
    "\n",
    "    return 3 * seq(n-1) + 3 * seq(n -2) - seq(n -3)\n",
    "\n",
    "\n",
    "def get_perimeters(ceiling):\n",
    "    for n in count(2):\n",
    "        a = seq(n)\n",
    "        if a*3 > ceiling:\n",
    "            break\n",
    "        triangle = Triangle(sss=(a, a, a+1))\n",
    "        if check_assumptions(triangle.area, integer=True):\n",
    "            yield triangle.perimeter\n",
    "        triangle = Triangle(sss=(a, a, a-1))\n",
    "        if check_assumptions(triangle.area, integer=True):\n",
    "            yield triangle.perimeter\n",
    "\n",
    "sum(get_perimeters(10**9))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p95\"></a>[Problem 95](https://projecteuler.net/problem=95)\n",
    "\n",
    "Find the smallest member of the longest amicable chain with no element exceeding one million."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "14316"
      ]
     },
     "execution_count": 96,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 11.3 s\n"
     ]
    }
   ],
   "source": [
    "from sympy import divisors\n",
    "ceiling = 10**6\n",
    "\n",
    "sumofdivisors = [1 for i in range(1, ceiling + 1)]\n",
    "for n in range(2, ceiling + 1):\n",
    "    for i in range(2*n, ceiling, n):\n",
    "        sumofdivisors[i] += n\n",
    "\n",
    "zeros = {0}\n",
    "\n",
    "longest_chain = []\n",
    "for start_n in range(10, ceiling):\n",
    "    n = start_n\n",
    "    chain = [n]\n",
    "    while 1:\n",
    "        n = sumofdivisors[n]\n",
    "\n",
    "        if n in zeros:\n",
    "            zeros |= set(chain)\n",
    "            break\n",
    "\n",
    "        if n == start_n:\n",
    "            if len(chain) > len(longest_chain):\n",
    "                longest_chain = chain\n",
    "            break\n",
    "\n",
    "        if n in chain or n > ceiling:\n",
    "            break\n",
    "\n",
    "        chain.append(n)\n",
    "\n",
    "min(longest_chain)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p96\"></a>[Problem 96](https://projecteuler.net/problem=96)\n",
    "\n",
    "Solve sudoku puzzles."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "24702"
      ]
     },
     "execution_count": 98,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 583 ms\n"
     ]
    }
   ],
   "source": [
    "from dlxsudoku.sudoku import Sudoku\n",
    "\n",
    "s = [l for l in open('p/p096_sudoku.txt').readlines() if l[0].isdigit()]\n",
    "sudokus = [Sudoku(''.join(s[i*9:(i+1)*9])) for i in range(50)]\n",
    "for sudoku in sudokus:\n",
    "    sudoku.solve()\n",
    "    \n",
    "sum(int(sudoku.to_oneliner()[:3]) for sudoku in sudokus)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p97\"></a>[Problem 97](https://projecteuler.net/problem=97)\n",
    "\n",
    "Find the last ten digits of a prime number."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8739992577"
      ]
     },
     "execution_count": 99,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 8 ms\n"
     ]
    }
   ],
   "source": [
    "(28433 * pow(2, 7830457, 10**10) + 1) % 10**10"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p98\"></a>[Problem 98](https://projecteuler.net/problem=98)\n",
    "\n",
    "Find the largest square anagram word pairs in a list of words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "18769"
      ]
     },
     "execution_count": 100,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 59.5 s\n"
     ]
    }
   ],
   "source": [
    "words = [list(word.replace('\"', '')) for word in open('p/p098_words.txt').readlines()[0].split(',')]\n",
    "\n",
    "def is_anagram(w1, w2):\n",
    "    return sorted(w1) == sorted(w2) and w1 != w2\n",
    "\n",
    "def formed_number(w, d):\n",
    "    return int(''.join([str(d[l]) for l in w]))\n",
    "\n",
    "def is_square(n):\n",
    "    return sqrt(n) == int(sqrt(n))\n",
    "\n",
    "\n",
    "def square_anagrams():\n",
    "    for w1, w2 in combinations(words, r=2):\n",
    "        if is_anagram(w1, w2):\n",
    "            for order in [order for numbers in combinations(range(10), len(w1)) for order in permutations(numbers)]:\n",
    "                d = {w1[i]: order[i] for i in range(len(w1))}\n",
    "                if d[w1[0]] != 0 and d[w2[0]] != 0:\n",
    "                    nw1, nw2 = formed_number(w1, d), formed_number(w2, d)\n",
    "                    if nw1 != nw2 and is_square(nw1) and is_square(nw2):\n",
    "                        yield(nw1)\n",
    "                        yield(nw2)\n",
    "\n",
    "max(square_anagrams())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p99\"></a>[Problem 99](https://projecteuler.net/problem=99)\n",
    "\n",
    "Determine which base and exponential pair has the greatest numerical value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "709"
      ]
     },
     "execution_count": 101,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 20 ms\n"
     ]
    }
   ],
   "source": [
    "def get_log_values():\n",
    "    for i, line in enumerate(open('p/p099_base_exp.txt')):\n",
    "        base, exponent = [int(n) for n in line.split(',')]\n",
    "        yield i+1, exponent * log(base)\n",
    "\n",
    "max(get_log_values(), key=itemgetter(1))[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"p100\"></a>[Problem 100](https://projecteuler.net/problem=100)\n",
    "\n",
    "By finding the first arrangement to contain over 10^12 = 1,000,000,000,000 discs in total, determine the number of blue discs that the box would contain.\n",
    "\n",
    "Analysis: Sequence formula from https://oeis.org/A011900"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "756872327473"
      ]
     },
     "execution_count": 102,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 1.83 s\n"
     ]
    }
   ],
   "source": [
    "from sympy import solve, Symbol\n",
    "\n",
    "def seq(n):\n",
    "    if n == 0 or n == -1:\n",
    "        return 1\n",
    "    return int(seq(n-1) * (seq(n-1) + 2) / seq(n-2))\n",
    "\n",
    "total = Symbol('total')\n",
    "\n",
    "for n in count(1):\n",
    "    blue = seq(n)\n",
    "    discs = max(solve(blue/total * (blue-1)/(total-1) -1/2, total))\n",
    "    if discs > 10**12:\n",
    "        break\n",
    "\n",
    "blue"
   ]
  }
 ],
 "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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}