4 "signature": "sha256:910fd3bd845f28d453d531005afb4e6d3ce4f040aa35835ad49dbb76f9e611fa"
12 "cell_type": "markdown",
17 "Which starting number, under one million, produces the longest Collatz chain?"
24 "# We'll need this in a bit\n",
26 "sys.setrecursionlimit(1000000)"
34 "cell_type": "markdown",
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",
39 "For instance, given the chain:\n",
41 " 13 \u2192 40 \u2192 20 \u2192 10 \u2192 5 \u2192 16 \u2192 8 \u2192 4 \u2192 2 \u2192 1\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",
45 "Notice that we don't care about the values found in the chain, simply how long it is."
52 "def collatz_length(n):\n",
55 " elif n % 2 == 0:\n",
56 " return 1 + collatz_length(n // 2)\n",
58 " return 1 + collatz_length(3 * n + 1)"
66 "cell_type": "markdown",
83 "output_type": "pyout",
103 "output_type": "pyout",
118 "language": "python",
123 "output_type": "pyout",
138 "language": "python",
143 "output_type": "pyout",
156 "for i in range(1, 10):\n",
157 " print(i, collatz_length(i))"
159 "language": "python",
163 "output_type": "stream",
181 "cell_type": "markdown",
185 "Let's find the longest chain starting from a number <= 10,000. We'll time how long it takes."
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)"
202 "language": "python",
206 "output_type": "stream",
214 "output_type": "stream",
222 "output_type": "stream",
230 "output_type": "stream",
234 "1 loops, best of 3: 188 ms per loop\n"
241 "cell_type": "markdown",
244 "Now try up to 1,000,000."
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)"
261 "language": "python",
265 "output_type": "stream",
273 "output_type": "stream",
281 "output_type": "stream",
289 "output_type": "stream",
293 "1 loops, best of 3: 28.4 s per loop\n"
300 "cell_type": "markdown",
303 "# Better performance\n",
304 "This is slow. Can we do better?\n",
306 "Recall the sequence starting at 13:\n",
308 "13 \u2192 40 \u2192 20 \u2192 10 \u2192 5 \u2192 16 \u2192 8 \u2192 4 \u2192 2 \u2192 1\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",
312 "Instead, store the results in a cache and look them up if we have them."
319 "collatz_cache = {}\n",
321 "def collatz_length_cache(n):\n",
322 " if n not in collatz_cache:\n",
324 " collatz_cache[n] = 1\n",
325 " elif n % 2 == 0:\n",
326 " collatz_cache[n] = 1 + collatz_length_cache(n // 2)\n",
328 " collatz_cache[n] = 1 + collatz_length_cache(3 * n + 1)\n",
329 " return collatz_cache[n]"
331 "language": "python",
340 "collatz_length_cache(9)"
342 "language": "python",
347 "output_type": "pyout",
362 "language": "python",
367 "output_type": "pyout",
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)"
410 "language": "python",
414 "output_type": "stream",
446 "output_type": "stream",
478 "output_type": "stream",
510 "output_type": "stream",
542 "output_type": "stream",
574 "output_type": "stream",
606 "output_type": "stream",
638 "output_type": "stream",
670 "output_type": "stream",
702 "output_type": "stream",
734 "output_type": "stream",
766 "output_type": "stream",
798 "output_type": "stream",
830 "output_type": "stream",
862 "output_type": "stream",
894 "output_type": "stream",
926 "output_type": "stream",
940 "100 loops, best of 3: 2.03 ms per loop\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)"
961 "language": "python",
965 "output_type": "stream",
973 "output_type": "stream",
981 "output_type": "stream",
989 "output_type": "stream",
993 "1 loops, best of 3: 248 ms per loop\n"
1000 "cell_type": "markdown",
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."
1008 "cell_type": "code",
1011 "# Python 3.3 or higher:\n",
1012 "from functools import lru_cache\n",
1014 "@lru_cache(maxsize=None)\n",
1015 "def collatz_length_lru(n):\n",
1018 " elif n % 2 == 0:\n",
1019 " return 1 + collatz_length_lru(n // 2)\n",
1021 " return 1 + collatz_length_lru(3 * n + 1)"
1023 "language": "python",
1029 "cell_type": "code",
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)"
1042 "language": "python",
1046 "output_type": "stream",
1054 "output_type": "stream",
1062 "output_type": "stream",
1070 "output_type": "stream",
1074 "1 loops, best of 3: 851 ms per loop\n"
1081 "cell_type": "code",
1084 "language": "python",