euler-014-longest-collatz-sequence-20161214.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Project Euler](https://projecteuler.net/)\n",
    "\n",
    "#### Longest Collatz sequence\n",
    "\n",
    "\n",
    "[Problem 14](https://projecteuler.net/problem=14)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following iterative sequence is defined for the set of positive integers:\n",
    "\n",
    "    n → n/2 (n is even)\n",
    "    n → 3n + 1 (n is odd)\n",
    "    \n",
    "Using the rule above and starting with 13, we generate the following sequence:\n",
    "\n",
    "    13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1\n",
    "    \n",
    "It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet ([Collatz Problem](https://en.wikipedia.org/wiki/Collatz_problem)), it is thought that all starting numbers finish at 1.\n",
    "\n",
    "Which starting number, under one million, produces the longest chain?\n",
    "\n",
    "**NOTE:** Once the chain starts the terms are allowed to go above one million."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from functools import lru_cache"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def gen_collatz(n):\n",
    "    yield n\n",
    "    while n > 1:\n",
    "        if n % 2 == 0:\n",
    "            n //= 2\n",
    "        else:\n",
    "            n = 3 * n + 1\n",
    "        yield n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[13, 40, 20, 10, 5, 16, 8, 4, 2, 1]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(gen_collatz(13))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(list(gen_collatz(13)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def foo(n):\n",
    "    max_chain_len = 0\n",
    "    max_chain_n = 0\n",
    "    for i in range(1, n):\n",
    "        if len(list(gen_collatz(i))) > max_chain_len:\n",
    "            max_chain_len = len(list(gen_collatz(i)))\n",
    "            max_chain_n = i\n",
    "    return max_chain_n, max_chain_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 50.5 s, sys: 0 ns, total: 50.5 s\n",
      "Wall time: 50.6 s\n",
      "The Collatz sequence for 837799 is 525 long.\n"
     ]
    }
   ],
   "source": [
    "n = 10**6\n",
    "%time known_good_output = foo(n)\n",
    "print('The Collatz sequence for %s is %s long.' % known_good_output)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The subchains are calculated over and over again,\n",
    "so use caching to avoid recalculating subchains.\n",
    "collatz is changed to be recursive\n",
    "to take advantage of\n",
    "[lru_cache](https://docs.python.org/3/library/functools.html#functools.lru_cache).\n",
    "\n",
    "Using cache was inspired by\n",
    "[Kristian](http://www.mathblog.dk/project-euler-14/)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "@lru_cache(maxsize=None)\n",
    "def collatz(n):\n",
    "    x = [n]\n",
    "    if n > 1:\n",
    "        if n % 2 == 0:\n",
    "            n //= 2\n",
    "        else:\n",
    "            n = 3 * n + 1\n",
    "        x.extend(collatz(n))\n",
    "    return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[13, 40, 20, 10, 5, 16, 8, 4, 2, 1]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(gen_collatz(13))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[13, 40, 20, 10, 5, 16, 8, 4, 2, 1]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "collatz(13)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def foo(n):\n",
    "    max_chain_len = 0\n",
    "    max_chain_n = 0\n",
    "    for i in range(1, n):\n",
    "        if len(collatz(i)) > max_chain_len:\n",
    "            max_chain_len = len(collatz(i))\n",
    "            max_chain_n = i\n",
    "    return max_chain_n, max_chain_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The slowest run took 6.86 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "1 loop, best of 3: 1.64 s per loop\n"
     ]
    }
   ],
   "source": [
    "n = 10**6\n",
    "%timeit foo(n)\n",
    "assert known_good_output == foo(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Only the lengths of the Collatz chains are wanted,\n",
    "not the numbers in the Collatz chains,\n",
    "so len_collatz is created to return only the lengths\n",
    "of the Collatz chains.\n",
    "len_collatz is also recursive to take advantage of lru_cache.\n",
    "\n",
    "len_collatz is faster than collatz,\n",
    "but not as general as collatz."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "@lru_cache(maxsize=None)\n",
    "def len_collatz(n):\n",
    "    len_chain = 1\n",
    "    if n > 1:\n",
    "        if n % 2 == 0:\n",
    "            n //= 2\n",
    "        else:\n",
    "            n = 3 * n + 1\n",
    "        len_chain += len(collatz(n))\n",
    "    return len_chain"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len_collatz(13)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def foo(n):\n",
    "    max_chain_len = 0\n",
    "    max_chain_n = 0\n",
    "    for i in range(1, n):\n",
    "        if len_collatz(i) > max_chain_len:\n",
    "            max_chain_len = len_collatz(i)\n",
    "            max_chain_n = i\n",
    "    return max_chain_n, max_chain_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 1.45 s per loop\n"
     ]
    }
   ],
   "source": [
    "n = 10**6\n",
    "%timeit foo(n)\n",
    "assert known_good_output == foo(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Review\n",
    "\n",
    "Cell 2 is very readable. Cell 5 has good readability.\n",
    "Together they pound through with brute force\n",
    "and produce the correct result *slowly*.\n",
    "\n",
    "Cell 7 is slightly less readable than cell 2,\n",
    "but uses caching for a big speed increase,\n",
    "especially when generating many Collatz chains.\n",
    "Cell 10 is slightly more readable than cell 5.\n",
    "Together, cells 7 and 10 are much faster than cells 2 and 5.\n",
    "\n",
    "Cell 12 has good readability, but is less general than cell 7.\n",
    "Cell 14 is more readable than cell 10.\n",
    "Together, cells 12 and 14 are faster than cells 7 and 10\n",
    "but not hugely so.\n",
    "\n",
    "# Summary\n",
    "\n",
    "If one wants only one Collatz chain,\n",
    "caching would not help,\n",
    "so use gen_collatz of cell 2 because it is most readable\n",
    "and is probably faster than collatz of cell 7\n",
    "for a single Collatz chain.\n",
    "\n",
    "collatz of cell 7 is readable, general, and fast.\n",
    "It is probably the best choice if doing work with many Collatz chains.\n",
    "\n",
    "len_collatz of cell 12 is useful only for when\n",
    "- one wants to know only the lengths of many Collatz chains\n",
    "- one wants fastest speed\n",
    "\n",
    "Otherwise collatz of cell 7's readability and generality make it a better choice.\n",
    "\n",
    "---\n",
    "\n",
    "collatz of cell 7 is probably the the best overall choice because:\n",
    "\n",
    "1. It has good readability.\n",
    "2. It is fast for making many Collatz chains.\n",
    "    - It is probably slower than gen_collatz of cell 2\n",
    "    if one is making few chains.\n",
    "    However, if one is making few chains,\n",
    "    then speed is likely not critical.\n",
    "3. It is general."
   ]
  }
 ],
 "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.4.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}