Graphing the Collatz Conjecture

3n_plus_1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "# How to graph the Collatz Conjecture in Python (3n+1)\r\n",
    "The Collatz Conjecture is a really cool Mathematical problem, sometimes also referred to as the 3n+1 problem\r\n",
    "\r\n",
    "## How it works\r\n",
    "- We pick a starting whole number, this can be any whole number of our choice\r\n",
    "- We evaluate 2 rules:\r\n",
    "    - If the number is even, then we multiply by 3 and add 1 to get the next number (3n + 1)\r\n",
    "    - If the number is odd, then we simply divide it in half (n / 2)"
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Getting the necessary libraries\r\n",
    "To graph the conjecture, we use the x-axis as the index of numbers or iterations that we go through; sort of like each step\r\n",
    "\r\n",
    "The y-axis will be the resultant number when applying our rules\r\n",
    "\r\n",
    "\r\n",
    "In order for us to do this however, we need a graphing library\r\n",
    "\r\n",
    "MatPlotLib is widely used and has good documentation and is also very easy to use, therefore that's what we will be using\r\n",
    "\r\n",
    "\r\n",
    "If you do not have MatPlotLib, you can install using \"pip\"\r\n",
    "\r\n",
    "Here is the command for Windows:\r\n",
    "```\r\n",
    "pip install matplotlib\r\n",
    "```"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "import matplotlib.pyplot as plt"
   ],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Getting user input\r\n",
    "\r\n",
    "Now lets get our starting number as an input from the user.\r\n",
    "\r\n",
    "We will also check if the input given is a numeric value, otherwise we will terminate the program to avoid throwing errors."
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "start_number = input(\"Input a starting number: \")\r\n",
    "\r\n",
    "if start_number.isnumeric():\r\n",
    "    start_number = int(start_number)\r\n",
    "else:\r\n",
    "    quit()"
   ],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "The `string.isnumeric()` method will return true if the string passed to it is a number.\r\n",
    "\r\n",
    "In the case that it is a numeric value, we convert it to the starting number using the `int()` method\r\n",
    "\r\n",
    "We will also define a constant for the max number of iterations we carry out because this conjecture can get pretty crazy sometimes."
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "MAX_ITERATIONS = 200"
   ],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Avoid getting stuck in an infinite loop\r\n",
    "\r\n",
    "The Collatz Conjecture has a unique pattern where it will loop through 4, 2, and 1 over and over again.\r\n",
    "\r\n",
    "This means that we have reached the end of our graphing calculation, so we want to make sure that we do not repeat ourselves or get stuck in this loop.\r\n",
    "\r\n",
    "We can do this by defining an array that shows the pattern and then comparing it in our yet-to-come `for` loop."
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "new_number = start_number\r\n",
    "repeat_pattern = [4, 2, 1]\r\n",
    "test_pattern = []"
   ],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "`new_number` will be the next number in the sequence. We will initialize it with the starting number.\r\n",
    "\r\n",
    "`repeat_pattern` is an array/list that tell our program what to look out for\r\n",
    "\r\n",
    "`test_pattern` is the array/list that we will use in our loop to check if we match the repeat_pattern and therefore halt further calculations.\r\n",
    "\r\n",
    "## Starting the loop\r\n",
    "\r\n",
    "First let's plot the beginning point on our graph using `plt.plot(x,y)`"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "plt.plot(0, start_number)"
   ],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "Now lets make the loop.\r\n",
    "\r\n",
    "Here's our checklist of things to do:\r\n",
    "- Save the previous number so we can check for the infinite loop\r\n",
    "- Check whether the number is odd or even\r\n",
    "- Apply the correct rule to odd or even numbers\r\n",
    "- Set that to `new_number`\r\n",
    "- Check whether the new number is in the repeat pattern\r\n",
    "- If so, append it to `test_pattern`\r\n",
    "- Check if `test_pattern` has reached a length of 3 and then compare with repeat pattern\r\n",
    "- If it matches the repeat pattern, break the `for` loop\r\n",
    "- Otherwise, clear `test_pattern`\r\n",
    "- Plot the number using its index"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "for i in range(MAX_ITERATIONS):\r\n",
    "    prev_number = new_number\r\n",
    "    if new_number % 2 == 0:\r\n",
    "        new_number /= 2\r\n",
    "    else:\r\n",
    "        new_number = (3 * new_number) + 1\r\n",
    "    \r\n",
    "    if new_number in repeat_pattern:\r\n",
    "        test_pattern.append(new_number)\r\n",
    "    if len(test_pattern) >= 3:\r\n",
    "        if test_pattern == repeat_pattern:\r\n",
    "            break\r\n",
    "        else:\r\n",
    "            test_pattern.clear()\r\n",
    "    \r\n",
    "    plt.plot((i-1, i), (prev_number, new_number))"
   ],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Displaying the graph\r\n",
    "\r\n",
    "This is actually really simple, we just need to use `plt.show()` and MatPlotLib will take care of the rest!"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "plt.show()"
   ],
   "outputs": [],
   "metadata": {}
  }
 ],
 "metadata": {
  "orig_nbformat": 4,
  "language_info": {
   "name": "python",
   "version": "3.9.6",
   "mimetype": "text/x-python",
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "pygments_lexer": "ipython3",
   "nbconvert_exporter": "python",
   "file_extension": ".py"
  },
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3.9.6 64-bit"
  },
  "interpreter": {
   "hash": "674a4eb853ef3b8ee2c8318a5f62f960f9c782f62ac23f0329d0e827277c513e"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}

requirements.txt

matplotlib==3.4.2