euler-14.ipynb

   1 {
   2  "metadata": {
   3   "name": "",
   4   "signature": "sha256:179e1a009d7b8bf549e9cff5cea48e2a90bc80b3c370cc110bc7f40a7cae7a9f"
   5  },
   6  "nbformat": 3,
   7  "nbformat_minor": 0,
   8  "worksheets": [
   9   {
  10    "cells": [
  11     {
  12      "cell_type": "markdown",
  13      "metadata": {},
  14      "source": [
  15       "# Euler 14\n",
  16       "\n",
  17       "Which starting number, under one million, produces the longest Collatz chain?"
  18      ]
  19     },
  20     {
  21      "cell_type": "code",
  22      "collapsed": false,
  23      "input": [
  24       "# We'll need this in a bit\n",
  25       "import sys\n",
  26       "sys.setrecursionlimit(1000000)"
  27      ],
  28      "language": "python",
  29      "metadata": {},
  30      "outputs": [],
  31      "prompt_number": 79
  32     },
  33     {
  34      "cell_type": "markdown",
  35      "metadata": {},
  36      "source": [
  37       "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",
  38       "\n",
  39       "For instance, given the chain:\n",
  40       "\n",
  41       "  13 \u2192 40 \u2192 20 \u2192 10 \u2192 5 \u2192 16 \u2192 8 \u2192 4 \u2192 2 \u2192 1\n",
  42       "\n",
  43       "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",
  44       "\n",
  45       "Notice that we don't care about the values found in the chain, simply how long it is."
  46      ]
  47     },
  48     {
  49      "cell_type": "code",
  50      "collapsed": false,
  51      "input": [
  52       "def collatz_length(n):\n",
  53       "    if n == 1:\n",
  54       "        return 1\n",
  55       "    elif n % 2 == 0:\n",
  56       "        return 1 + collatz_length(n // 2)\n",
  57       "    else:\n",
  58       "        return 1 + collatz_length(3 * n + 1)"
  59      ],
  60      "language": "python",
  61      "metadata": {},
  62      "outputs": [],
  63      "prompt_number": 80
  64     },
  65     {
  66      "cell_type": "markdown",
  67      "metadata": {},
  68      "source": [
  69       "## Test it works"
  70      ]
  71     },
  72     {
  73      "cell_type": "code",
  74      "collapsed": false,
  75      "input": [
  76       "collatz_length(1)"
  77      ],
  78      "language": "python",
  79      "metadata": {},
  80      "outputs": [
  81       {
  82        "metadata": {},
  83        "output_type": "pyout",
  84        "prompt_number": 81,
  85        "text": [
  86         "1"
  87        ]
  88       }
  89      ],
  90      "prompt_number": 81
  91     },
  92     {
  93      "cell_type": "code",
  94      "collapsed": false,
  95      "input": [
  96       "collatz_length(2)"
  97      ],
  98      "language": "python",
  99      "metadata": {},
 100      "outputs": [
 101       {
 102        "metadata": {},
 103        "output_type": "pyout",
 104        "prompt_number": 82,
 105        "text": [
 106         "2"
 107        ]
 108       }
 109      ],
 110      "prompt_number": 82
 111     },
 112     {
 113      "cell_type": "code",
 114      "collapsed": false,
 115      "input": [
 116       "collatz_length(3)"
 117      ],
 118      "language": "python",
 119      "metadata": {},
 120      "outputs": [
 121       {
 122        "metadata": {},
 123        "output_type": "pyout",
 124        "prompt_number": 83,
 125        "text": [
 126         "8"
 127        ]
 128       }
 129      ],
 130      "prompt_number": 83
 131     },
 132     {
 133      "cell_type": "code",
 134      "collapsed": false,
 135      "input": [
 136       "collatz_length(13)"
 137      ],
 138      "language": "python",
 139      "metadata": {},
 140      "outputs": [
 141       {
 142        "metadata": {},
 143        "output_type": "pyout",
 144        "prompt_number": 84,
 145        "text": [
 146         "10"
 147        ]
 148       }
 149      ],
 150      "prompt_number": 84
 151     },
 152     {
 153      "cell_type": "code",
 154      "collapsed": false,
 155      "input": [
 156       "for i in range(1, 10):\n",
 157       "    print(i, collatz_length(i))"
 158      ],
 159      "language": "python",
 160      "metadata": {},
 161      "outputs": [
 162       {
 163        "output_type": "stream",
 164        "stream": "stdout",
 165        "text": [
 166         "1 1\n",
 167         "2 2\n",
 168         "3 8\n",
 169         "4 3\n",
 170         "5 6\n",
 171         "6 9\n",
 172         "7 17\n",
 173         "8 4\n",
 174         "9 20\n"
 175        ]
 176       }
 177      ],
 178      "prompt_number": 85
 179     },
 180     {
 181      "cell_type": "markdown",
 182      "metadata": {},
 183      "source": [
 184       "# Performance\n",
 185       "Let's find the longest chain starting from a number <= 10,000. We'll time how long it takes."
 186      ]
 187     },
 188     {
 189      "cell_type": "code",
 190      "collapsed": false,
 191      "input": [
 192       "%%timeit\n",
 193       "longest_start = 1\n",
 194       "longest_chain = 0\n",
 195       "for i in range(1, 10001):\n",
 196       "    this_chain = collatz_length(i)\n",
 197       "    if this_chain > longest_chain:\n",
 198       "        longest_start = i\n",
 199       "        longest_chain = this_chain\n",
 200       "print(longest_start, '->', longest_chain)"
 201      ],
 202      "language": "python",
 203      "metadata": {},
 204      "outputs": [
 205       {
 206        "output_type": "stream",
 207        "stream": "stdout",
 208        "text": [
 209         "6171 -> 262\n",
 210         "6171"
 211        ]
 212       },
 213       {
 214        "output_type": "stream",
 215        "stream": "stdout",
 216        "text": [
 217         " -> 262\n",
 218         "6171"
 219        ]
 220       },
 221       {
 222        "output_type": "stream",
 223        "stream": "stdout",
 224        "text": [
 225         " -> 262\n",
 226         "6171"
 227        ]
 228       },
 229       {
 230        "output_type": "stream",
 231        "stream": "stdout",
 232        "text": [
 233         " -> 262\n",
 234         "1 loops, best of 3: 188 ms per loop\n"
 235        ]
 236       }
 237      ],
 238      "prompt_number": 86
 239     },
 240     {
 241      "cell_type": "markdown",
 242      "metadata": {},
 243      "source": [
 244       "Now try up to 1,000,000."
 245      ]
 246     },
 247     {
 248      "cell_type": "code",
 249      "collapsed": false,
 250      "input": [
 251       "%%timeit\n",
 252       "longest_start = 1\n",
 253       "longest_chain = 0\n",
 254       "for i in range(1, 1000001):\n",
 255       "    this_chain = collatz_length(i)\n",
 256       "    if this_chain > longest_chain:\n",
 257       "        longest_start = i\n",
 258       "        longest_chain = this_chain\n",
 259       "print(longest_start, '->', longest_chain)"
 260      ],
 261      "language": "python",
 262      "metadata": {},
 263      "outputs": [
 264       {
 265        "output_type": "stream",
 266        "stream": "stdout",
 267        "text": [
 268         "837799 -> 525\n",
 269         "837799"
 270        ]
 271       },
 272       {
 273        "output_type": "stream",
 274        "stream": "stdout",
 275        "text": [
 276         " -> 525\n",
 277         "837799"
 278        ]
 279       },
 280       {
 281        "output_type": "stream",
 282        "stream": "stdout",
 283        "text": [
 284         " -> 525\n",
 285         "837799"
 286        ]
 287       },
 288       {
 289        "output_type": "stream",
 290        "stream": "stdout",
 291        "text": [
 292         " -> 525\n",
 293         "1 loops, best of 3: 28.4 s per loop\n"
 294        ]
 295       }
 296      ],
 297      "prompt_number": 87
 298     },
 299     {
 300      "cell_type": "markdown",
 301      "metadata": {},
 302      "source": [
 303       "# Better performance\n",
 304       "This is slow. Can we do better?\n",
 305       "\n",
 306       "Recall the sequence starting at 13:\n",
 307       "\n",
 308       "13 \u2192 40 \u2192 20 \u2192 10 \u2192 5 \u2192 16 \u2192 8 \u2192 4 \u2192 2 \u2192 1\n",
 309       "\n",
 310       "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",
 311       "\n",
 312       "Instead, store the results in a cache and look them up if we have them."
 313      ]
 314     },
 315     {
 316      "cell_type": "code",
 317      "collapsed": false,
 318      "input": [
 319       "collatz_cache = {}\n",
 320       "\n",
 321       "def collatz_length_cache(n):\n",
 322       "    if n not in collatz_cache:\n",
 323       "        if n == 1:\n",
 324       "            collatz_cache[n] = 1\n",
 325       "        elif n % 2 == 0:\n",
 326       "            collatz_cache[n] = 1 + collatz_length_cache(n // 2)\n",
 327       "        else:\n",
 328       "            collatz_cache[n] = 1 + collatz_length_cache(3 * n + 1)\n",
 329       "    return collatz_cache[n]"
 330      ],
 331      "language": "python",
 332      "metadata": {},
 333      "outputs": [],
 334      "prompt_number": 1
 335     },
 336     {
 337      "cell_type": "code",
 338      "collapsed": false,
 339      "input": [
 340       "collatz_length_cache(9)"
 341      ],
 342      "language": "python",
 343      "metadata": {},
 344      "outputs": [
 345       {
 346        "metadata": {},
 347        "output_type": "pyout",
 348        "prompt_number": 2,
 349        "text": [
 350         "20"
 351        ]
 352       }
 353      ],
 354      "prompt_number": 2
 355     },
 356     {
 357      "cell_type": "code",
 358      "collapsed": false,
 359      "input": [
 360       "collatz_cache"
 361      ],
 362      "language": "python",
 363      "metadata": {},
 364      "outputs": [
 365       {
 366        "metadata": {},
 367        "output_type": "pyout",
 368        "prompt_number": 3,
 369        "text": [
 370         "{1: 1,\n",
 371         " 2: 2,\n",
 372         " 34: 14,\n",
 373         " 4: 3,\n",
 374         " 5: 6,\n",
 375         " 17: 13,\n",
 376         " 40: 9,\n",
 377         " 9: 20,\n",
 378         " 10: 7,\n",
 379         " 11: 15,\n",
 380         " 13: 10,\n",
 381         " 14: 18,\n",
 382         " 16: 5,\n",
 383         " 8: 4,\n",
 384         " 20: 8,\n",
 385         " 22: 16,\n",
 386         " 7: 17,\n",
 387         " 52: 12,\n",
 388         " 26: 11,\n",
 389         " 28: 19}"
 390        ]
 391       }
 392      ],
 393      "prompt_number": 3
 394     },
 395     {
 396      "cell_type": "code",
 397      "collapsed": false,
 398      "input": [
 399       "%%timeit\n",
 400       "longest_start = 1\n",
 401       "longest_chain = 0\n",
 402       "collatz_cache = {}\n",
 403       "for i in range(1, 10001):\n",
 404       "    this_chain = collatz_length_cache(i)\n",
 405       "    if this_chain > longest_chain:\n",
 406       "        longest_start = i\n",
 407       "        longest_chain = this_chain\n",
 408       "print(longest_start, '->', longest_chain)"
 409      ],
 410      "language": "python",
 411      "metadata": {},
 412      "outputs": [
 413       {
 414        "output_type": "stream",
 415        "stream": "stdout",
 416        "text": [
 417         "6171 -> 262\n",
 418         "6171 -> 262\n",
 419         "6171 -> 262\n",
 420         "6171 -> 262\n",
 421         "6171 -> 262\n",
 422         "6171 -> 262\n",
 423         "6171 -> 262\n",
 424         "6171 -> 262\n",
 425         "6171 -> 262\n",
 426         "6171 -> 262\n",
 427         "6171 -> 262\n",
 428         "6171 -> 262\n",
 429         "6171 -> 262\n",
 430         "6171 -> 262\n",
 431         "6171 -> 262\n",
 432         "6171 -> 262\n",
 433         "6171 -> 262\n",
 434         "6171 -> 262\n",
 435         "6171 -> 262\n",
 436         "6171 -> 262\n",
 437         "6171 -> 262\n",
 438         "6171 -> 262\n",
 439         "6171 -> 262\n",
 440         "6171 -> 262\n",
 441         "6171 -> 262\n",
 442         "6171"
 443        ]
 444       },
 445       {
 446        "output_type": "stream",
 447        "stream": "stdout",
 448        "text": [
 449         " -> 262\n",
 450         "6171 -> 262\n",
 451         "6171 -> 262\n",
 452         "6171 -> 262\n",
 453         "6171 -> 262\n",
 454         "6171 -> 262\n",
 455         "6171 -> 262\n",
 456         "6171 -> 262\n",
 457         "6171 -> 262\n",
 458         "6171 -> 262\n",
 459         "6171 -> 262\n",
 460         "6171 -> 262\n",
 461         "6171 -> 262\n",
 462         "6171 -> 262\n",
 463         "6171 -> 262\n",
 464         "6171 -> 262\n",
 465         "6171 -> 262\n",
 466         "6171 -> 262\n",
 467         "6171 -> 262\n",
 468         "6171 -> 262\n",
 469         "6171 -> 262\n",
 470         "6171 -> 262\n",
 471         "6171 -> 262\n",
 472         "6171 -> 262\n",
 473         "6171 -> 262\n",
 474         "6171"
 475        ]
 476       },
 477       {
 478        "output_type": "stream",
 479        "stream": "stdout",
 480        "text": [
 481         " -> 262\n",
 482         "6171 -> 262\n",
 483         "6171 -> 262\n",
 484         "6171 -> 262\n",
 485         "6171 -> 262\n",
 486         "6171 -> 262\n",
 487         "6171 -> 262\n",
 488         "6171 -> 262\n",
 489         "6171 -> 262\n",
 490         "6171 -> 262\n",
 491         "6171 -> 262\n",
 492         "6171 -> 262\n",
 493         "6171 -> 262\n",
 494         "6171 -> 262\n",
 495         "6171 -> 262\n",
 496         "6171 -> 262\n",
 497         "6171 -> 262\n",
 498         "6171 -> 262\n",
 499         "6171 -> 262\n",
 500         "6171 -> 262\n",
 501         "6171 -> 262\n",
 502         "6171 -> 262\n",
 503         "6171 -> 262\n",
 504         "6171 -> 262\n",
 505         "6171 -> 262\n",
 506         "6171"
 507        ]
 508       },
 509       {
 510        "output_type": "stream",
 511        "stream": "stdout",
 512        "text": [
 513         " -> 262\n",
 514         "6171 -> 262\n",
 515         "6171 -> 262\n",
 516         "6171 -> 262\n",
 517         "6171 -> 262\n",
 518         "6171 -> 262\n",
 519         "6171 -> 262\n",
 520         "6171 -> 262\n",
 521         "6171 -> 262\n",
 522         "6171 -> 262\n",
 523         "6171 -> 262\n",
 524         "6171 -> 262\n",
 525         "6171 -> 262\n",
 526         "6171 -> 262\n",
 527         "6171 -> 262\n",
 528         "6171 -> 262\n",
 529         "6171 -> 262\n",
 530         "6171 -> 262\n",
 531         "6171 -> 262\n",
 532         "6171 -> 262\n",
 533         "6171 -> 262\n",
 534         "6171 -> 262\n",
 535         "6171 -> 262\n",
 536         "6171 -> 262\n",
 537         "6171 -> 262\n",
 538         "6171"
 539        ]
 540       },
 541       {
 542        "output_type": "stream",
 543        "stream": "stdout",
 544        "text": [
 545         " -> 262\n",
 546         "6171 -> 262\n",
 547         "6171 -> 262\n",
 548         "6171 -> 262\n",
 549         "6171 -> 262\n",
 550         "6171 -> 262\n",
 551         "6171 -> 262\n",
 552         "6171 -> 262\n",
 553         "6171 -> 262\n",
 554         "6171 -> 262\n",
 555         "6171 -> 262\n",
 556         "6171 -> 262\n",
 557         "6171 -> 262\n",
 558         "6171 -> 262\n",
 559         "6171 -> 262\n",
 560         "6171 -> 262\n",
 561         "6171 -> 262\n",
 562         "6171 -> 262\n",
 563         "6171 -> 262\n",
 564         "6171 -> 262\n",
 565         "6171 -> 262\n",
 566         "6171 -> 262\n",
 567         "6171 -> 262\n",
 568         "6171 -> 262\n",
 569         "6171 -> 262\n",
 570         "6171"
 571        ]
 572       },
 573       {
 574        "output_type": "stream",
 575        "stream": "stdout",
 576        "text": [
 577         " -> 262\n",
 578         "6171 -> 262\n",
 579         "6171 -> 262\n",
 580         "6171 -> 262\n",
 581         "6171 -> 262\n",
 582         "6171 -> 262\n",
 583         "6171 -> 262\n",
 584         "6171 -> 262\n",
 585         "6171 -> 262\n",
 586         "6171 -> 262\n",
 587         "6171 -> 262\n",
 588         "6171 -> 262\n",
 589         "6171 -> 262\n",
 590         "6171 -> 262\n",
 591         "6171 -> 262\n",
 592         "6171 -> 262\n",
 593         "6171 -> 262\n",
 594         "6171 -> 262\n",
 595         "6171 -> 262\n",
 596         "6171 -> 262\n",
 597         "6171 -> 262\n",
 598         "6171 -> 262\n",
 599         "6171 -> 262\n",
 600         "6171 -> 262\n",
 601         "6171 -> 262\n",
 602         "6171"
 603        ]
 604       },
 605       {
 606        "output_type": "stream",
 607        "stream": "stdout",
 608        "text": [
 609         " -> 262\n",
 610         "6171 -> 262\n",
 611         "6171 -> 262\n",
 612         "6171 -> 262\n",
 613         "6171 -> 262\n",
 614         "6171 -> 262\n",
 615         "6171 -> 262\n",
 616         "6171 -> 262\n",
 617         "6171 -> 262\n",
 618         "6171 -> 262\n",
 619         "6171 -> 262\n",
 620         "6171 -> 262\n",
 621         "6171 -> 262\n",
 622         "6171 -> 262\n",
 623         "6171 -> 262\n",
 624         "6171 -> 262\n",
 625         "6171 -> 262\n",
 626         "6171 -> 262\n",
 627         "6171 -> 262\n",
 628         "6171 -> 262\n",
 629         "6171 -> 262\n",
 630         "6171 -> 262\n",
 631         "6171 -> 262\n",
 632         "6171 -> 262\n",
 633         "6171 -> 262\n",
 634         "6171"
 635        ]
 636       },
 637       {
 638        "output_type": "stream",
 639        "stream": "stdout",
 640        "text": [
 641         " -> 262\n",
 642         "6171 -> 262\n",
 643         "6171 -> 262\n",
 644         "6171 -> 262\n",
 645         "6171 -> 262\n",
 646         "6171 -> 262\n",
 647         "6171 -> 262\n",
 648         "6171 -> 262\n",
 649         "6171 -> 262\n",
 650         "6171 -> 262\n",
 651         "6171 -> 262\n",
 652         "6171 -> 262\n",
 653         "6171 -> 262\n",
 654         "6171 -> 262\n",
 655         "6171 -> 262\n",
 656         "6171 -> 262\n",
 657         "6171 -> 262\n",
 658         "6171 -> 262\n",
 659         "6171 -> 262\n",
 660         "6171 -> 262\n",
 661         "6171 -> 262\n",
 662         "6171 -> 262\n",
 663         "6171 -> 262\n",
 664         "6171 -> 262\n",
 665         "6171 -> 262\n",
 666         "6171"
 667        ]
 668       },
 669       {
 670        "output_type": "stream",
 671        "stream": "stdout",
 672        "text": [
 673         " -> 262\n",
 674         "6171 -> 262\n",
 675         "6171 -> 262\n",
 676         "6171 -> 262\n",
 677         "6171 -> 262\n",
 678         "6171 -> 262\n",
 679         "6171 -> 262\n",
 680         "6171 -> 262\n",
 681         "6171 -> 262\n",
 682         "6171 -> 262\n",
 683         "6171 -> 262\n",
 684         "6171 -> 262\n",
 685         "6171 -> 262\n",
 686         "6171 -> 262\n",
 687         "6171 -> 262\n",
 688         "6171 -> 262\n",
 689         "6171 -> 262\n",
 690         "6171 -> 262\n",
 691         "6171 -> 262\n",
 692         "6171 -> 262\n",
 693         "6171 -> 262\n",
 694         "6171 -> 262\n",
 695         "6171 -> 262\n",
 696         "6171 -> 262\n",
 697         "6171 -> 262\n",
 698         "6171"
 699        ]
 700       },
 701       {
 702        "output_type": "stream",
 703        "stream": "stdout",
 704        "text": [
 705         " -> 262\n",
 706         "6171 -> 262\n",
 707         "6171 -> 262\n",
 708         "6171 -> 262\n",
 709         "6171 -> 262\n",
 710         "6171 -> 262\n",
 711         "6171 -> 262\n",
 712         "6171 -> 262\n",
 713         "6171 -> 262\n",
 714         "6171 -> 262\n",
 715         "6171 -> 262\n",
 716         "6171 -> 262\n",
 717         "6171 -> 262\n",
 718         "6171 -> 262\n",
 719         "6171 -> 262\n",
 720         "6171 -> 262\n",
 721         "6171 -> 262\n",
 722         "6171 -> 262\n",
 723         "6171 -> 262\n",
 724         "6171 -> 262\n",
 725         "6171 -> 262\n",
 726         "6171 -> 262\n",
 727         "6171 -> 262\n",
 728         "6171 -> 262\n",
 729         "6171"
 730        ]
 731       },
 732       {
 733        "output_type": "stream",
 734        "stream": "stdout",
 735        "text": [
 736         " -> 262\n",
 737         "6171 -> 262\n",
 738         "6171 -> 262\n",
 739         "6171 -> 262\n",
 740         "6171 -> 262\n",
 741         "6171 -> 262\n",
 742         "6171 -> 262\n",
 743         "6171 -> 262\n",
 744         "6171 -> 262\n",
 745         "6171 -> 262\n",
 746         "6171 -> 262\n",
 747         "6171 -> 262\n",
 748         "6171 -> 262\n",
 749         "6171 -> 262\n",
 750         "6171 -> 262\n",
 751         "6171 -> 262\n",
 752         "6171 -> 262\n",
 753         "6171 -> 262\n",
 754         "6171 -> 262\n",
 755         "6171 -> 262\n",
 756         "6171 -> 262\n",
 757         "6171 -> 262\n",
 758         "6171 -> 262\n",
 759         "6171 -> 262\n",
 760         "6171"
 761        ]
 762       },
 763       {
 764        "output_type": "stream",
 765        "stream": "stdout",
 766        "text": [
 767         " -> 262\n",
 768         "6171 -> 262\n",
 769         "6171 -> 262\n",
 770         "6171 -> 262\n",
 771         "6171 -> 262\n",
 772         "6171 -> 262\n",
 773         "6171 -> 262\n",
 774         "6171 -> 262\n",
 775         "6171 -> 262\n",
 776         "6171 -> 262\n",
 777         "6171 -> 262\n",
 778         "6171 -> 262\n",
 779         "6171 -> 262\n",
 780         "6171 -> 262\n",
 781         "6171 -> 262\n",
 782         "6171 -> 262\n",
 783         "6171 -> 262\n",
 784         "6171 -> 262\n",
 785         "6171 -> 262\n",
 786         "6171 -> 262\n",
 787         "6171 -> 262\n",
 788         "6171 -> 262\n",
 789         "6171 -> 262\n",
 790         "6171"
 791        ]
 792       },
 793       {
 794        "output_type": "stream",
 795        "stream": "stdout",
 796        "text": [
 797         " -> 262\n",
 798         "6171 -> 262\n",
 799         "6171 -> 262\n",
 800         "6171 -> 262\n",
 801         "6171 -> 262\n",
 802         "6171 -> 262\n",
 803         "6171 -> 262\n",
 804         "6171 -> 262\n",
 805         "6171 -> 262\n",
 806         "6171 -> 262\n",
 807         "6171 -> 262\n",
 808         "6171 -> 262\n",
 809         "6171 -> 262\n",
 810         "6171 -> 262\n",
 811         "6171 -> 262\n",
 812         "6171 -> 262\n",
 813         "6171 -> 262\n",
 814         "6171 -> 262\n",
 815         "6171 -> 262\n",
 816         "6171 -> 262\n",
 817         "6171 -> 262\n",
 818         "6171 -> 262\n",
 819         "6171 -> 262\n",
 820         "6171 -> 262\n",
 821         "6171"
 822        ]
 823       },
 824       {
 825        "output_type": "stream",
 826        "stream": "stdout",
 827        "text": [
 828         " -> 262\n",
 829         "6171 -> 262\n",
 830         "6171 -> 262\n",
 831         "6171 -> 262\n",
 832         "6171 -> 262\n",
 833         "6171 -> 262\n",
 834         "6171 -> 262\n",
 835         "6171 -> 262\n",
 836         "6171 -> 262\n",
 837         "6171 -> 262\n",
 838         "6171 -> 262\n",
 839         "6171 -> 262\n",
 840         "6171 -> 262\n",
 841         "6171 -> 262\n",
 842         "6171 -> 262\n",
 843         "6171 -> 262\n",
 844         "6171 -> 262\n",
 845         "6171 -> 262\n",
 846         "6171 -> 262\n",
 847         "6171 -> 262\n",
 848         "6171 -> 262\n",
 849         "6171 -> 262\n",
 850         "6171 -> 262\n",
 851         "6171 -> 262\n",
 852         "6171"
 853        ]
 854       },
 855       {
 856        "output_type": "stream",
 857        "stream": "stdout",
 858        "text": [
 859         " -> 262\n",
 860         "6171 -> 262\n",
 861         "6171 -> 262\n",
 862         "6171 -> 262\n",
 863         "6171 -> 262\n",
 864         "6171 -> 262\n",
 865         "6171 -> 262\n",
 866         "6171 -> 262\n",
 867         "6171 -> 262\n",
 868         "6171 -> 262\n",
 869         "6171 -> 262\n",
 870         "6171 -> 262\n",
 871         "6171 -> 262\n",
 872         "6171 -> 262\n",
 873         "6171 -> 262\n",
 874         "6171 -> 262\n",
 875         "6171 -> 262\n",
 876         "6171 -> 262\n",
 877         "6171 -> 262\n",
 878         "6171 -> 262\n",
 879         "6171 -> 262\n",
 880         "6171 -> 262\n",
 881         "6171 -> 262\n",
 882         "6171 -> 262\n",
 883         "6171"
 884        ]
 885       },
 886       {
 887        "output_type": "stream",
 888        "stream": "stdout",
 889        "text": [
 890         " -> 262\n",
 891         "6171 -> 262\n",
 892         "6171 -> 262\n",
 893         "6171 -> 262\n",
 894         "6171 -> 262\n",
 895         "6171 -> 262\n",
 896         "6171 -> 262\n",
 897         "6171 -> 262\n",
 898         "6171 -> 262\n",
 899         "6171 -> 262\n",
 900         "6171 -> 262\n",
 901         "6171 -> 262\n",
 902         "6171 -> 262\n",
 903         "6171 -> 262\n",
 904         "6171 -> 262\n",
 905         "6171 -> 262\n",
 906         "6171 -> 262\n",
 907         "6171 -> 262\n",
 908         "6171 -> 262\n",
 909         "6171 -> 262\n",
 910         "6171 -> 262\n",
 911         "6171 -> 262\n",
 912         "6171 -> 262\n",
 913         "6171 -> 262\n",
 914         "6171"
 915        ]
 916       },
 917       {
 918        "output_type": "stream",
 919        "stream": "stdout",
 920        "text": [
 921         " -> 262\n",
 922         "6171 -> 262\n",
 923         "6171 -> 262\n",
 924         "6171 -> 262\n",
 925         "6171 -> 262\n",
 926         "6171 -> 262\n",
 927         "6171 -> 262\n",
 928         "6171 -> 262\n",
 929         "6171 -> 262\n",
 930         "6171 -> 262\n",
 931         "6171 -> 262\n",
 932         "6171 -> 262\n",
 933         "6171 -> 262\n",
 934         "6171 -> 262\n",
 935         "6171 -> 262\n",
 936         "6171 -> 262\n",
 937         "6171 -> 262\n",
 938         "6171 -> 262\n",
 939         "6171 -> 262\n",
 940         "100 loops, best of 3: 2.03 ms per loop\n"
 941        ]
 942       }
 943      ],
 944      "prompt_number": 4
 945     },
 946     {
 947      "cell_type": "code",
 948      "collapsed": false,
 949      "input": [
 950       "%%timeit\n",
 951       "longest_start = 1\n",
 952       "longest_chain = 0\n",
 953       "collatz_cache = {}\n",
 954       "for i in range(1, 1000001):\n",
 955       "    this_chain = collatz_length_cache(i)\n",
 956       "    if this_chain > longest_chain:\n",
 957       "        longest_start = i\n",
 958       "        longest_chain = this_chain\n",
 959       "print(longest_start, '->', longest_chain)"
 960      ],
 961      "language": "python",
 962      "metadata": {},
 963      "outputs": [
 964       {
 965        "output_type": "stream",
 966        "stream": "stdout",
 967        "text": [
 968         "837799 -> 525\n",
 969         "837799"
 970        ]
 971       },
 972       {
 973        "output_type": "stream",
 974        "stream": "stdout",
 975        "text": [
 976         " -> 525\n",
 977         "837799"
 978        ]
 979       },
 980       {
 981        "output_type": "stream",
 982        "stream": "stdout",
 983        "text": [
 984         " -> 525\n",
 985         "837799"
 986        ]
 987       },
 988       {
 989        "output_type": "stream",
 990        "stream": "stdout",
 991        "text": [
 992         " -> 525\n",
 993         "1 loops, best of 3: 250 ms per loop\n"
 994        ]
 995       }
 996      ],
 997      "prompt_number": 5
 998     },
 999     {
1000      "cell_type": "markdown",
1001      "metadata": {},
1002      "source": [
1003       "#It's so useful, it's built in\n",
1004       "Python 3.3 includes the `lru_cache` function decorator in the standard `functools` library. We can use that without faffing around with explicit caches."
1005      ]
1006     },
1007     {
1008      "cell_type": "code",
1009      "collapsed": false,
1010      "input": [
1011       "# Python 3.3 or higher:\n",
1012       "from functools import lru_cache\n",
1013       "\n",
1014       "@lru_cache(maxsize=None)\n",
1015       "def collatz_length_lru(n):\n",
1016       "    if n == 1:\n",
1017       "        return 1\n",
1018       "    elif n % 2 == 0:\n",
1019       "        return 1 + collatz_length_lru(n // 2)\n",
1020       "    else:\n",
1021       "        return 1 + collatz_length_lru(3 * n + 1)"
1022      ],
1023      "language": "python",
1024      "metadata": {},
1025      "outputs": [],
1026      "prompt_number": 6
1027     },
1028     {
1029      "cell_type": "code",
1030      "collapsed": false,
1031      "input": [
1032       "%%timeit\n",
1033       "longest_start = 1\n",
1034       "longest_chain = 0\n",
1035       "for i in range(1, 1000001):\n",
1036       "    this_chain = collatz_length_lru(i)\n",
1037       "    if this_chain > longest_chain:\n",
1038       "        longest_start = i\n",
1039       "        longest_chain = this_chain\n",
1040       "print(longest_start, '->', longest_chain)"
1041      ],
1042      "language": "python",
1043      "metadata": {},
1044      "outputs": [
1045       {
1046        "output_type": "stream",
1047        "stream": "stdout",
1048        "text": [
1049         "837799 -> 525\n",
1050         "837799"
1051        ]
1052       },
1053       {
1054        "output_type": "stream",
1055        "stream": "stdout",
1056        "text": [
1057         " -> 525\n",
1058         "837799"
1059        ]
1060       },
1061       {
1062        "output_type": "stream",
1063        "stream": "stdout",
1064        "text": [
1065         " -> 525\n",
1066         "837799"
1067        ]
1068       },
1069       {
1070        "output_type": "stream",
1071        "stream": "stdout",
1072        "text": [
1073         " -> 525\n",
1074         "1 loops, best of 3: 785 ms per loop\n"
1075        ]
1076       }
1077      ],
1078      "prompt_number": 7
1079     },
1080     {
1081      "cell_type": "code",
1082      "collapsed": false,
1083      "input": [],
1084      "language": "python",
1085      "metadata": {},
1086      "outputs": [],
1087      "prompt_number": 96
1088     }
1089    ],
1090    "metadata": {}
1091   }
1092  ]
1093 }