{ "metadata": { "name": "", "signature": "sha256:179e1a009d7b8bf549e9cff5cea48e2a90bc80b3c370cc110bc7f40a7cae7a9f" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Euler 14\n", "\n", "Which starting number, under one million, produces the longest Collatz chain?" ] }, { "cell_type": "code", "collapsed": false, "input": [ "# We'll need this in a bit\n", "import sys\n", "sys.setrecursionlimit(1000000)" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 79 }, { "cell_type": "markdown", "metadata": {}, "source": [ "This is the obvious implementation of the problem: the length of the chain is one more than the length of the chain from the next number. \n", "\n", "For instance, given the chain:\n", "\n", " 13 \u2192 40 \u2192 20 \u2192 10 \u2192 5 \u2192 16 \u2192 8 \u2192 4 \u2192 2 \u2192 1\n", "\n", "we know that the length of chain starting at 13 is one more than the length of chain starting at 40, which is one more than the length of the chain starting at 20, ...\n", "\n", "Notice that we don't care about the values found in the chain, simply how long it is." ] }, { "cell_type": "code", "collapsed": false, "input": [ "def collatz_length(n):\n", " if n == 1:\n", " return 1\n", " elif n % 2 == 0:\n", " return 1 + collatz_length(n // 2)\n", " else:\n", " return 1 + collatz_length(3 * n + 1)" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 80 }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Test it works" ] }, { "cell_type": "code", "collapsed": false, "input": [ "collatz_length(1)" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 81, "text": [ "1" ] } ], "prompt_number": 81 }, { "cell_type": "code", "collapsed": false, "input": [ "collatz_length(2)" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 82, "text": [ "2" ] } ], "prompt_number": 82 }, { "cell_type": "code", "collapsed": false, "input": [ "collatz_length(3)" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 83, "text": [ "8" ] } ], "prompt_number": 83 }, { "cell_type": "code", "collapsed": false, "input": [ "collatz_length(13)" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 84, "text": [ "10" ] } ], "prompt_number": 84 }, { "cell_type": "code", "collapsed": false, "input": [ "for i in range(1, 10):\n", " print(i, collatz_length(i))" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "1 1\n", "2 2\n", "3 8\n", "4 3\n", "5 6\n", "6 9\n", "7 17\n", "8 4\n", "9 20\n" ] } ], "prompt_number": 85 }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Performance\n", "Let's find the longest chain starting from a number <= 10,000. We'll time how long it takes." ] }, { "cell_type": "code", "collapsed": false, "input": [ "%%timeit\n", "longest_start = 1\n", "longest_chain = 0\n", "for i in range(1, 10001):\n", " this_chain = collatz_length(i)\n", " if this_chain > longest_chain:\n", " longest_start = i\n", " longest_chain = this_chain\n", "print(longest_start, '->', longest_chain)" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "6171 -> 262\n", "6171" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " -> 262\n", "6171" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " -> 262\n", "6171" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " -> 262\n", "1 loops, best of 3: 188 ms per loop\n" ] } ], "prompt_number": 86 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now try up to 1,000,000." ] }, { "cell_type": "code", "collapsed": false, "input": [ "%%timeit\n", "longest_start = 1\n", "longest_chain = 0\n", "for i in range(1, 1000001):\n", " this_chain = collatz_length(i)\n", " if this_chain > longest_chain:\n", " longest_start = i\n", " longest_chain = this_chain\n", "print(longest_start, '->', longest_chain)" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "837799 -> 525\n", "837799" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " -> 525\n", "837799" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " -> 525\n", "837799" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " -> 525\n", "1 loops, best of 3: 28.4 s per loop\n" ] } ], "prompt_number": 87 }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Better performance\n", "This is slow. Can we do better?\n", "\n", "Recall the sequence starting at 13:\n", "\n", "13 \u2192 40 \u2192 20 \u2192 10 \u2192 5 \u2192 16 \u2192 8 \u2192 4 \u2192 2 \u2192 1\n", "\n", "If we're finding the Collatz chain lengths for all numbers up to 13, we've just calculated the Collatz chain length of 10. We don't need to recalculate it. \n", "\n", "Instead, store the results in a cache and look them up if we have them." ] }, { "cell_type": "code", "collapsed": false, "input": [ "collatz_cache = {}\n", "\n", "def collatz_length_cache(n):\n", " if n not in collatz_cache:\n", " if n == 1:\n", " collatz_cache[n] = 1\n", " elif n % 2 == 0:\n", " collatz_cache[n] = 1 + collatz_length_cache(n // 2)\n", " else:\n", " collatz_cache[n] = 1 + collatz_length_cache(3 * n + 1)\n", " return collatz_cache[n]" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 1 }, { "cell_type": "code", "collapsed": false, "input": [ "collatz_length_cache(9)" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 2, "text": [ "20" ] } ], "prompt_number": 2 }, { "cell_type": "code", "collapsed": false, "input": [ "collatz_cache" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 3, "text": [ "{1: 1,\n", " 2: 2,\n", " 34: 14,\n", " 4: 3,\n", " 5: 6,\n", " 17: 13,\n", " 40: 9,\n", " 9: 20,\n", " 10: 7,\n", " 11: 15,\n", " 13: 10,\n", " 14: 18,\n", " 16: 5,\n", " 8: 4,\n", " 20: 8,\n", " 22: 16,\n", " 7: 17,\n", " 52: 12,\n", " 26: 11,\n", " 28: 19}" ] } ], "prompt_number": 3 }, { "cell_type": "code", "collapsed": false, "input": [ "%%timeit\n", "longest_start = 1\n", "longest_chain = 0\n", "collatz_cache = {}\n", "for i in range(1, 10001):\n", " this_chain = collatz_length_cache(i)\n", " if this_chain > longest_chain:\n", " longest_start = i\n", " longest_chain = this_chain\n", "print(longest_start, '->', longest_chain)" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "6171 -> 262\n", "100 loops, best of 3: 2.03 ms per loop\n" ] } ], "prompt_number": 4 }, { "cell_type": "code", "collapsed": false, "input": [ "%%timeit\n", "longest_start = 1\n", "longest_chain = 0\n", "collatz_cache = {}\n", "for i in range(1, 1000001):\n", " this_chain = collatz_length_cache(i)\n", " if this_chain > longest_chain:\n", " longest_start = i\n", " longest_chain = this_chain\n", "print(longest_start, '->', longest_chain)" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "837799 -> 525\n", "837799" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " -> 525\n", "837799" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " -> 525\n", "837799" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " -> 525\n", "1 loops, best of 3: 250 ms per loop\n" ] } ], "prompt_number": 5 }, { "cell_type": "markdown", "metadata": {}, "source": [ "#It's so useful, it's built in\n", "Python 3.3 includes the `lru_cache` function decorator in the standard `functools` library. We can use that without faffing around with explicit caches." ] }, { "cell_type": "code", "collapsed": false, "input": [ "# Python 3.3 or higher:\n", "from functools import lru_cache\n", "\n", "@lru_cache(maxsize=None)\n", "def collatz_length_lru(n):\n", " if n == 1:\n", " return 1\n", " elif n % 2 == 0:\n", " return 1 + collatz_length_lru(n // 2)\n", " else:\n", " return 1 + collatz_length_lru(3 * n + 1)" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 6 }, { "cell_type": "code", "collapsed": false, "input": [ "%%timeit\n", "longest_start = 1\n", "longest_chain = 0\n", "for i in range(1, 1000001):\n", " this_chain = collatz_length_lru(i)\n", " if this_chain > longest_chain:\n", " longest_start = i\n", " longest_chain = this_chain\n", "print(longest_start, '->', longest_chain)" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "837799 -> 525\n", "837799" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " -> 525\n", "837799" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " -> 525\n", "837799" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " -> 525\n", "1 loops, best of 3: 785 ms per loop\n" ] } ], "prompt_number": 7 }, { "cell_type": "code", "collapsed": false, "input": [], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 96 } ], "metadata": {} } ] }