euler-012-highly-divisible-triangular-number-20150124.ipynb

{
 "metadata": {
  "name": "euler-012-highly-divisible-triangular-number-20150124"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The sequence of triangle numbers is generated by adding the natural numbers. So the 7<sup>th</sup> triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:\n",
      "\n",
      "    1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...\n",
      "\n",
      "Let us list the factors of the first seven triangle numbers:\n",
      "\n",
      "     1: 1\n",
      "     3: 1,3\n",
      "     6: 1,2,3,6\n",
      "    10: 1,2,5,10\n",
      "    15: 1,3,5,15\n",
      "    21: 1,3,7,21\n",
      "    28: 1,2,4,7,14,28\n",
      "\n",
      "We can see that 28 is the first triangle number to have over five divisors.\n",
      "\n",
      "What is the value of the first triangle number to have over five hundred divisors?"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from __future__ import print_function\n",
      "\n",
      "from euler import gen_triangular\n",
      "from euler import gen_lt\n",
      "from euler import get_factors\n",
      "from euler import product\n",
      "from euler import gen_n\n",
      "from collections import defaultdict\n",
      "from collections import Counter\n",
      "from itertools import count"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# modest hardware for 2015\n",
      "!lscpu"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Architecture:          i686\r\n",
        "CPU op-mode(s):        32-bit\r\n",
        "Byte Order:            Little Endian\r\n",
        "CPU(s):                2\r\n",
        "On-line CPU(s) list:   0,1\r\n",
        "Thread(s) per core:    1\r\n",
        "Core(s) per socket:    2\r\n",
        "Socket(s):             1\r\n",
        "Vendor ID:             GenuineIntel\r\n",
        "CPU family:            6\r\n",
        "Model:                 14\r\n",
        "Stepping:              8\r\n",
        "CPU MHz:               2000.000\r\n",
        "BogoMIPS:              3994.38\r\n",
        "Virtualization:        VT-x\r\n",
        "L1d cache:             32K\r\n",
        "L1i cache:             32K\r\n",
        "L2 cache:              2048K\r\n"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "list(gen_lt(gen_triangular(), 100))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 3,
       "text": [
        "[1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91]"
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "list(get_factors(1)), list(get_factors(72))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 4,
       "text": [
        "([], [2, 2, 2, 3, 3])"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def tabulate(x):\n",
      "    '''Returns dictionary for given collection x where\n",
      "        keys are for collection elements\n",
      "        values are count of how many times \n",
      "            the key occurs in the given collection.'''\n",
      "    f = {}\n",
      "    for i in x:\n",
      "        if i not in f:\n",
      "            f[i] = 0\n",
      "        f[i] += 1\n",
      "    return f"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 5
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "tabulate(get_factors(24)), len(tabulate(get_factors(24)))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 6,
       "text": [
        "({2: 3, 3: 1}, 2)"
       ]
      }
     ],
     "prompt_number": 6
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def foo(n):\n",
      "    for t in gen_triangular():\n",
      "        if product(map((lambda x: x+1), tabulate(get_factors(t)).values())) > n:\n",
      "            return t"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 7
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "n = 500\n",
      "%timeit foo(n)\n",
      "foo(n)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1 loops, best of 3: 87.9 ms per loop\n"
       ]
      },
      {
       "output_type": "pyout",
       "prompt_number": 8,
       "text": [
        "76576500"
       ]
      }
     ],
     "prompt_number": 8
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def tabulate(x):\n",
      "    '''Returns dictionary for given collection x where\n",
      "        keys are for collection elements\n",
      "        values are count of how many times \n",
      "            the key occurs in the given collection.'''\n",
      "    counts = defaultdict(int)\n",
      "    for i in x:\n",
      "        counts[i] += 1\n",
      "    return counts"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 9
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "n = 500\n",
      "%timeit foo(n)\n",
      "foo(n)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "10 loops, best of 3: 97.2 ms per loop\n"
       ]
      },
      {
       "output_type": "pyout",
       "prompt_number": 10,
       "text": [
        "76576500"
       ]
      }
     ],
     "prompt_number": 10
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def foo(n):\n",
      "    for t in gen_triangular():\n",
      "        if product(map((lambda x: x+1), Counter(get_factors(t)).values())) > n:\n",
      "            return t"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 11
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "n = 500\n",
      "%timeit foo(n)\n",
      "foo(n)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "10 loops, best of 3: 186 ms per loop\n"
       ]
      },
      {
       "output_type": "pyout",
       "prompt_number": 12,
       "text": [
        "76576500"
       ]
      }
     ],
     "prompt_number": 12
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def gen_triangular_main_factors():\n",
      "    for i in count(1, 2):\n",
      "        yield i, (i+1) / 2\n",
      "        yield (i+1) / 2, i+2"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 13
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "for i in gen_n(gen_triangular_main_factors(), 10):\n",
      "    print(i, product(i))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "(1, 1) 1\n",
        "(1, 3) 3\n",
        "(3, 2) 6\n",
        "(2, 5) 10\n",
        "(5, 3) 15\n",
        "(3, 7) 21\n",
        "(7, 4) 28\n",
        "(4, 9) 36\n",
        "(9, 5) 45\n",
        "(5, 11) 55\n"
       ]
      }
     ],
     "prompt_number": 14
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def tabulate(x):\n",
      "    '''Returns dictionary for given collection of collection x where\n",
      "        keys are for collection elements\n",
      "        values are count of how many times \n",
      "            the key occurs in the given collection.'''\n",
      "    f = {}\n",
      "    for y in x:\n",
      "        for i in y:\n",
      "            if i not in f:\n",
      "                f[i] = 0\n",
      "            f[i] += 1\n",
      "    return f"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 15
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def foo(n):\n",
      "    for t in gen_triangular_main_factors():\n",
      "        factors = tabulate(map(get_factors, t))\n",
      "        if product(map((lambda x: x+1), factors.values())) > n:\n",
      "            return product(t)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 16
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "n = 500\n",
      "%timeit foo(n)\n",
      "foo(n)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "10 loops, best of 3: 114 ms per loop\n"
       ]
      },
      {
       "output_type": "pyout",
       "prompt_number": 17,
       "text": [
        "76576500"
       ]
      }
     ],
     "prompt_number": 17
    }
   ],
   "metadata": {}
  }
 ]
}