euler-029-distinct-powers-20130801.ipynb

{
 "metadata": {
  "name": "euler-029-distinct-powers-20130801"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Consider all integer combinations of a<sup>b</sup> for 2 \u2264 a \u2264 5 and 2 \u2264 b \u2264 5:  \n",
      "\n",
      "> 2<sup>2</sup>=4, 2<sup>3</sup>=8, 2<sup>4</sup>=16, 2<sup>5</sup>=32  \n",
      "> 3<sup>2</sup>=9, 3<sup>3</sup>=27, 3<sup>4</sup>=81, 3<sup>5</sup>=243  \n",
      "> 4<sup>2</sup>=16, 4<sup>3</sup>=64, 4<sup>4</sup>=256, 4<sup>5</sup>=1024  \n",
      "> 5<sup>2</sup>=25, 5<sup>3</sup>=125, 5<sup>4</sup>=625, 5<sup>5</sup>=3125  \n",
      "\n",
      "If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:\n",
      "4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125\n",
      "How many distinct terms are in the sequence generated by a<sup>b</sup> for 2 \u2264 a \u2264 100 and 2 \u2264 b \u2264 100?"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from euler import canonical_decomposition, canonical_decomposition2, get_factors, get_factors2"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "canonical_decomposition(12)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 2,
       "text": [
        "{2: 2, 3: 1}"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "canonical_decomposition2(12)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 3,
       "text": [
        "{2: 2, 3: 1}"
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "get_factors(12)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 4,
       "text": [
        "[2, 2, 3]"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "tuple(sorted(get_factors(12) * 5))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 5,
       "text": [
        "(2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3)"
       ]
      }
     ],
     "prompt_number": 5
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def foo(n):\n",
      "    dn = set([])\n",
      "    for a in range(2, n + 1):\n",
      "        af = get_factors(a)\n",
      "        for b in range(2, n + 1):\n",
      "            dn.add(tuple(sorted(af * b)))\n",
      "    return len(dn)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 6
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "n = 100\n",
      "%timeit foo(n)\n",
      "foo(n)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1 loops, best of 3: 232 ms per loop\n"
       ]
      },
      {
       "output_type": "pyout",
       "prompt_number": 7,
       "text": [
        "9183"
       ]
      }
     ],
     "prompt_number": 7
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def foo(n):\n",
      "    return len(set([a ** b for a in range(2, n + 1) for b in range(2, n + 1)]))          "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 8
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "n = 100\n",
      "%timeit foo(n)\n",
      "foo(n)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "10 loops, best of 3: 25.5 ms per loop\n"
       ]
      },
      {
       "output_type": "pyout",
       "prompt_number": 9,
       "text": [
        "9183"
       ]
      }
     ],
     "prompt_number": 9
    }
   ],
   "metadata": {}
  }
 ]
}