{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "We'll use [memoization](https://en.wikipedia.org/wiki/Memoization) to cache results for odd numbers. We don't cache even numbers since there's a separate loop that divides even numbers by 2 until we have an odd number. By storing only half of the numbers we also halve the amount of memory needed." ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "837799" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "cache = {}\n", "def total_stopping_time(n):\n", " t = n\n", " c = 0\n", " while True:\n", " while t % 2 == 0:\n", " t //= 2\n", " c += 1\n", " if t == 1:\n", " break\n", " if cache.get(t):\n", " c += cache.get(t)\n", " break\n", " t = (3*t + 1)\n", " c += 1\n", " \n", " if n % 2 != 0:\n", " cache[n] = c\n", " return c\n", "\n", "max_n = 0\n", "max_length = 0\n", "for n in range(1, 1_000_000):\n", " length = total_stopping_time(n)\n", " if length > max_length:\n", " max_length = length\n", " max_n = n\n", "max_n" ] } ], "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.7.4" }, "title": "Longest Collatz sequence" }, "nbformat": 4, "nbformat_minor": 2 }