Revis_PrimesProject_.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Revis_PrimesProject .ipynb",
      "provenance": [],
      "collapsed_sections": [
        "1mv5AxfNh9AO",
        "UnfbNa3B29ML",
        "U-NPlImJQp08",
        "BIR0F0-nOekx",
        "gpSrT21bcI0V",
        "uRyNjFTWNvqE",
        "Bitf-WMwNTgw",
        "SxzDf6J-NiFn",
        "YFmcjfX4bkIb",
        "E41QrAKW9Gcx",
        "ABBo28kZB3LJ",
        "NSalKh6lD073",
        "V6KTbYFLgF3u",
        "dx4jCk-nwkxx"
      ],
      "authorship_tag": "ABX9TyMXG5SkWf3Gc2nMoPeOoaxI",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/cw805/MATH-242/blob/main/Revis_PrimesProject_.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1sz37RJiHzE2"
      },
      "source": [
        "# **Primes Project**\n",
        "\n",
        "Math 242 - Modern Computational Mathematics\n",
        "\n",
        "\n",
        "**Claire Wu** \n",
        "\n",
        "**Due: Friday, April 22**\n",
        "\n",
        "\n",
        "This project has two parts, both involving prime numbers.\n",
        "\n",
        "**Part 1**: Implement the Sieve of Sundaram and compare it with the Sieve of Eratosthenes. The Sieve\n",
        "of Sundaram algorithm is found on page 138 in Computational Mathematics, chapter 4. Compare the runtime required for computing lists of primes with each sieve method. You should measure the runtime of each sieve for computing the primes up to n, for various n. Then make a plot that shows your results (n on the horizontal axis, runtimes on the vertical axis).\n",
        "\n",
        "\n",
        "**Part 2**: Investigate at least two (three for a score of Excellent) of the following conjectures about primes. For each, either provide computational evidence in support of the conjecture, or find a counterexample showing that the conjecture is false.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "To receive a grade of Excellent, your notebook should further exhibit the following:\n",
        "- You investigate three of the above conjectures. For each, you either find evidence in support\n",
        "of the conjecture or a counterexample that disproves it.\n",
        "- Computational methodology demonstrates mastery of the computational techniques that we\n",
        "have studied in this course.\n",
        "- Exposition is clear and precise, thoroughly explaining your methodology and reasoning. Any assumptions necessary for the estimates are reasonable and clearly stated.\n",
        "- The work may extend beyond the project requirements in a creative or insightful direction.\n"
      ],
      "metadata": {
        "id": "9Mq2lNkTcgyN"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Preliminary Code\n",
        "First import modules:"
      ],
      "metadata": {
        "id": "7pJ0mfrRhfHy"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "import math   # for sqrt and other math functions\n",
        "import time   # for runtime analysis\n",
        "import matplotlib.pyplot as plt  # for plotting\n",
        "import sympy\n",
        "import numpy as np"
      ],
      "metadata": {
        "id": "TozcFxZshHUx"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# **Part 1 - Sieve of Sundaram vs. Eratosthenes (Ch.4 p.138 )**\n",
        "Compare the runtime required for computing lists of primes with each sieve method. You should \n",
        "\n",
        "- measure the runtime of each sieve for computing the primes up to n, for various n. \n",
        "\n",
        "- Then make a plot that shows your results (n on the horizontal axis, runtimes on the vertical axis)."
      ],
      "metadata": {
        "id": "JrlbngtZgZ0k"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## **Sieve of Eratosthenes**\n",
        "\n",
        "We will implement the *fastEroatos()* function that we've been working with in class. The function will simply replace composite numbers with zero. The nonzero numbers that remain will be our list of primes."
      ],
      "metadata": {
        "id": "1mv5AxfNh9AO"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Implementat fastEratos"
      ],
      "metadata": {
        "id": "vlRvysghqbmV"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def fastEratos(nMax):\n",
        "  \n",
        "  # start with a list 2, 3, 4, ..., nMax\n",
        "  nums = list(range(2,nMax+1))\n",
        "\n",
        "  # compute the sqare root of nMax\n",
        "  nroot = math.sqrt(nMax)\n",
        "\n",
        "  i = 0 # index of smallest item in nums\n",
        "  while nums[i] <= nroot:\n",
        "\n",
        "    if nums[i] > 0:   # then nums[i] is prime, so set all of its multiples to zero\n",
        "      j = i + nums[i]   # this index of twice the prime nums[i]\n",
        "      while j < len(nums):\n",
        "        nums[j] = 0\n",
        "        j += nums[i]    # go to the next multiple of the prime nums[i]\n",
        "\n",
        "    i += 1  # go to the next smallest item in nums\n",
        "\n",
        "  # all nonzero numbers that remain in our list are prime\n",
        "  primes = [n for n in nums if n != 0]\n",
        "  return primes"
      ],
      "metadata": {
        "id": "E3-J5gH4ioE4"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Now we can generate a list of primes from fastEratos:"
      ],
      "metadata": {
        "id": "9zOSiBHgTOTP"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "fastEratos(50)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "qZwIHDn_m8Xn",
        "outputId": "f3c9051b-cac6-42f8-aa60-1178f1942c89"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]"
            ]
          },
          "metadata": {},
          "execution_count": 99
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Runtime of fastEratos"
      ],
      "metadata": {
        "id": "w3F6BUAlmw-8"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Now measure the runtime of this implementation. This is the function that will measure and return the runtime of fastEratos(nMax)."
      ],
      "metadata": {
        "id": "dsNho4YpjJh4"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def timeEratos(nMax):\n",
        "  startTime = time.time()\n",
        "  fastEratos(nMax)\n",
        "  endTime = time.time()\n",
        "  return endTime - startTime"
      ],
      "metadata": {
        "id": "MR-JhstNjHHD"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "timeEratos(10000)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "If22CYQOjs0x",
        "outputId": "bd6d7947-5ba8-43bb-9b82-90ddbda8801c"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "0.009406805038452148"
            ]
          },
          "metadata": {},
          "execution_count": 102
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Plotting Runtime of fastEratos"
      ],
      "metadata": {
        "id": "vVW2_OkDqJ3F"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Now we will make a list of the `nMax` values that we will test, and then we will measure the runtimes and store them in a list. "
      ],
      "metadata": {
        "id": "2KLiBXazbSs_"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "erastosMaxVals = range(10000,100000,5000)\n",
        "runtimes = [timeEratos(n) for n in erastosMaxVals]  # list comprehension -- makes a list of runtime values"
      ],
      "metadata": {
        "id": "BszIFPEUbnwY"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "With a list of nMax values, we can now plot the runtimes! For plotting in Python, we will use the `matplotlib.pyplot` module, which we imported above. "
      ],
      "metadata": {
        "id": "8Qc0Vbm1brw1"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "plt.plot(erastosMaxVals, runtimes, 'go') # creates the plot; syntax is plot(xvals, yvals, format)\n",
        "plt.title(\"Sieve of Eratosthenes runtimes\")\n",
        "plt.xlabel(\"nMax\")\n",
        "plt.ylabel(\"time (seconds)\");"
      ],
      "metadata": {
        "id": "Vped8LXyb7-w",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 295
        },
        "outputId": "ba9d0d18-06a6-4638-90c0-dad7714a8414"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ],
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAY4AAAEWCAYAAABxMXBSAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAgAElEQVR4nO3df5xcVX3/8deb/CLhxwIhWkjILkgUA2kRVsCvWJEIBkoaWrGEpoJIiYh8S+uPNhhtgTYU+kOihYe6/FCMC0FToYtKAwapVUvKBoEQEF1CNj9EWULYAOFX5NM/7pkwmczuzk1mdmd338/H4z7m3nPPPXPu3dn5zL3n3nMUEZiZmVVqt4GugJmZDS4OHGZmlosDh5mZ5eLAYWZmuThwmJlZLg4cZmaWiwOH9UnSHEl3DXQ9ikl6t6RfSnpB0ukDXZ9dIeleSX8+0PUYSJI+K+n6ga6HVcaBwwCQdLykn0rqlvSspJ9IeidARLRGxMkDXccSlwPXRMSeEXF76UpJayS9lAJLYbpmZ98slff+XapxVs6lkr65q+UMZpJOkLS+OC0iroiIYR08B5ORA10BG3iS9ga+C3wc+BYwGngP8MpA1qsPjcCqPvLMjIgf9FWQpJERsbU61Rr6fLzMZxwG8FaAiLglIn4bES9FxF0R8TCApI9I+nEhs6TDJN2dzkwel/QnKf1YSb+WNKIo7x9JKpSzm6R5kp6QtFHStyTt11OlJJ0vqSO9T5ukA1P6E8AhwB3pTGJMnp1N+/MTSVdL2ghcKuktku5J9XpGUqukfVL+RcDkovf765T+h5JWSXouXW56e9F7/I2kDZKeT8douqQZwGeBM1M5DxVVqzHV6XlJd0nav6is49LZ4HOSHpJ0QtG6eyX9/U5u+xFJq9N2T0qa08PxulTSEknflLQZ+Iikr0v6h6I8251FpDO0T0t6OJ3F3ippd0l7AHcCBxadCR5YfCYmqUlSSDpX0jpJmyRdIOmdqbznSs8eJX1U0mMp71JJjSld6e/8tKTNklZKOqLPD4n1LiI8DfMJ2BvYCNwEnALsW7L+I8CP0/wewDrgXLIz1ncAzwBT0/ongJOKtv02MC/NXwzcB0wCxgBfBW7poU4npnKPSnn/DfhR0fo1wPt72ace16f92Qr8/7QPY4FDgZPSe00AfgQs7Kk8smD7YtpmFPDXQAfZ2drb0jE6MOVtAt6S5i8FvllSn3vTcXtrqsu9wJVp3cT0tzmV7IfeSWl5wq5sm/6Om4G3pbwHAIf3cLwuBV4DTk/ljAW+DvxDUZ4TgPUlx+t/gQOB/YDHgAvK5S09Lul4BfAVYHfgZOBl4HbgTWm/ngbem/LPSsf+7env+Tngp2ndB4AVwD6AUp4DBvp/brBPPuMwImIzcDzZP+t1QFf6hf/mMtlPA9ZExNciYmtE/Az4d+BDaf0twFkAkvYi+9K6Ja27AJgfEesj4hWyL4szJJW7ZDoHuDEiHkh5LwHeJakpx67dnn6dFqbzi9b9KiL+Le3DSxHRERF3R8QrEdEFfAF4by9lnwl8L23zGvAvZF+o/w/4LVkAmippVESsiYgn+qjr1yLiFxHxEtnlwiNT+p8B34+I70fE6xFxN9BOdlx3ddvXgSMkjY2IpyKit0t//xMRt6dyXupjXwq+FBG/iohngTuK6lWpv4+IlyPiLrIgfUtEPB0RG4D/JvvRAtnn6h8j4rHILqFdARyZzjpeA/YCDgOU8jyVsx5WwoHDAEj/UB+JiEnAEWS/FBeWydoIHFv8hUz2Jf87af3NwB+ny0d/DDwQEZ1F295WtN1jZF+y5QLUgUBhOyLiBbJfyxNz7NbpEbFP0XRd0bp1xRklvVnS4nR5aTPwTWB/elZav9dTmRMjogP4S7LA+HQq98A+6vrrovktwJ5pvhH4UMnxPp7sDGGnt42IF8mC3wXAU5K+J+mwXuq3rpd1efepUr8pmn+pzHLxfn6xaB+fJTu7mBgR9wDXANeS/S1alLXp2S5w4LAdRMTPyS5FlLsWvA74r5Iv5D0j4uNp20fJvlBPAf6ULJAUb3tKyba7p1+QpX5F9oUAQLo2Ph4ol3dnlHYLfUVKmxYRe5P9Wlcv+UvrJ+CgQv0i4uaIOD7lCeCqHsrpyzpgUckx2yMirtzVbSNiaUScRBaEfk52ttmT0nq/CIwrWv4dKlftLrnXAR8r2c+xEfFTgIj4UkQcDUwlu6T3mSq//7DjwGGFxu5PSZqUlg8iu9x0X5ns3wXeKunDkkal6Z3FDcNkweJi4PfJ2jgKvgIsKGq4nCBpVg/VugU4V9KR6ezlCmB5RKzZhV3tzV7AC0C3pIns+OXyG7IG+YJvAX+grNF7FPApsrvQfirpbZJOTPV+mezX8etF5TRJqvR/75vATEkfkDQiNTCfUPhb7ey26QxrVgrIr6R9f7334rbzIHCqpP0k/Q7ZGValfgOMl9SQY5vefAW4RNLhAJIaJH0ozb9T2U0bo8iC3cvk208rw4HDAJ4HjgWWS3qRLGA8QvZluJ2IeJ6ssXI22a/uX5P9mi6+s+kWsvaBeyLimaL0LwJtwF2Snk/vc2y5CkV2G+3nydpPngLekt4zj8JdUIXptl7yXkbWEN8NfA/4Tsn6fwQ+ly6HfDoiHic7K/k3skb8mWS3/75KdiyuTOm/JmvQvSSVUwikGyU90NcORMQ6ssbfzwJdZL+uP0MF/7t9bLsb8Emyv+GzZH+vj/dVZpFFwENkjeB3AbdWumE6o70FWJ2OZ1+X8foq7zayz+DidJnxEbIzXshu/LgO2ER2JrwR+OddeT/LGosGug5mZjaI+IzDzMxyceAwM7NcHDjMzCwXBw4zM8tlWHRyuP/++0dTU9NAV8PMbFBZsWLFMxExoTR9WASOpqYm2tvbB7oaZmaDiqTOcum+VGVmZrk4cJiZWS4OHGZmlosDh5mZ5VLTwCFphrLRzzokzSuzfoyykcE6JC0vHWtB0uTUx9Cni9LWpFG8HpTkFm8zs35Ws8ChbPjQa8k6G5sKnCVpakm284BNEXEocDVvdD1d8AWyYSZLvS8ijoyI5ipX28xs0Gtd2UrTwiZ2u2w3mhY20bqytarl1/KM4xigIyJWpx5DF5P11FlsFtlwpQBLgOlpXAMknQ48CfQ2KpmZmRVpXdnK3Dvm0tndSRB0dncy9465VQ0etQwcE9l+1LD17Dh627Y8acjHbrJ++vcE/oasq+tSQdYt9wpJc6teazOzQWz+svlseW3LdmlbXtvC/GXzq/Ye9foA4KXA1RHxQjoBKXZ8RGyQ9Cbgbkk/j4gflWZKQWUuwOTJk2tdXzOzurC2e22u9J1RyzOODWRDaRZMYsdhP7flkTQSaCAbaOVY4J8krSEbWeyzki4CKAwzGhFPA7eRXRLbQUS0RERzRDRPmLDDE/NmZkPS5IbyP5R7St8ZtQwc9wNTJB0saTTZ6G1tJXnagHPS/BlkI8ZFRLwnIpoioglYCFwREddI2kPSXrBtDOqTyUb7MjMzYMH0BYwbNW67tHGjxrFg+oKqvUfNLlVFxNZ0lrAUGAHcGBGrJF0OtEdEG3ADsEhSB9nwlX0NDfpm4LZ0+WokcHNE/Get9sHMbLCZM20OkLV1rO1ey+SGySyYvmBbejUMi6Fjm5ubw50cmpnlI2lFucce/OS4mZnl4sBhZma5OHCYmVkuDhxmZpaLA4eZmeXiwGFmZrk4cJiZWS4OHGZmlosDh5mZ5eLAYWZWJ2o9AFO11Gu36mZmw0phAKbCWBqFAZiAqvYzVQ0+4zAzqwP9MQBTtThwmJnVgf4YgKlaHDjMzOpAfwzAVC0OHGZmdaA/BmCqFgcOM7M6MGfaHFpmttDY0IgQjQ2NtMxsqbuGcfBATmZm1gMP5GRmVkY1np0YLM9fVEtNA4ekGZIel9QhaV6Z9WMk3ZrWL5fUVLJ+sqQXJH260jLNzCpVeHais7uTILY9O5Hni78aZQw2NQsckkYA1wKnAFOBsyRNLcl2HrApIg4FrgauKln/BeDOnGWamVWkGs9ODKbnL6qllmccxwAdEbE6Il4FFgOzSvLMAm5K80uA6ZIEIOl04ElgVc4yzcwqUo1nJwbT8xfVUsvAMRFYV7S8PqWVzRMRW4FuYLykPYG/AS7biTLNzCpSjWcnBtPzF9VSr43jlwJXR8QLO1uApLmS2iW1d3V1Va9mZjZkVOPZicH0/EW11LKTww3AQUXLk1JauTzrJY0EGoCNwLHAGZL+CdgHeF3Sy8CKCsoEICJagBbIbsfd5b0xsyGn8IzE/GXzWdu9lskNk1kwfUGuZyeqUcZgU7PnOFIg+AUwnezL/X7gTyNiVVGeTwDTIuICSbOBP46IPykp51LghYj4l0rKLMfPcZiZ5dfTcxw1O+OIiK2SLgKWAiOAGyNilaTLgfaIaANuABZJ6gCeBWbvTJm12gczM9uRnxw3M7Oy/OS4mZlVhQOHmZnl4sBhZma5OHCYmVkuDhxmZpaLA4eZmeXiwGFmZrk4cJiZWS4OHGZmlosDh5mZ5eLAYWYVGW7jalvPatmtupkNEYVxtQtDpBbG1QaGdPfhVp7POMysT8NxXG3rmQOHmfVpOI6rbT1z4DCzPg3HcbWtZw4cZtan4TiutvXMgcPM+jRn2hxaZrbQ2NCIEI0NjbTMbHHD+DDlEQDNzKysARkBUNIMSY9L6pA0r8z6MZJuTeuXS2pK6cdIejBND0n6o6Jt1khamdY5GpiZ9bOaPcchaQRwLXASsB64X1JbRDxalO08YFNEHCppNnAVcCbwCNAcEVslHQA8JOmOiNiatntfRDxTq7qbmVnPannGcQzQERGrI+JVYDEwqyTPLOCmNL8EmC5JEbGlKEjsDgz962lmZoNELQPHRGBd0fL6lFY2TwoU3cB4AEnHSloFrAQuKAokAdwlaYWkuT29uaS5ktoltXd1dVVlh8zMrI7vqoqI5RFxOPBO4BJJu6dVx0fEUcApwCck/X4P27dERHNENE+YMKGfam1m/cV9Zw2cWgaODcBBRcuTUlrZPJJGAg3AxuIMEfEY8AJwRFrekF6fBm4juyRmZsNIoe+szu5OgtjWd5aDR/+oZeC4H5gi6WBJo4HZQFtJnjbgnDR/BnBPRETaZiSApEbgMGCNpD0k7ZXS9wBOJmtIN7NhxH1nDaya3VWV7oi6CFgKjABujIhVki4H2iOiDbgBWCSpA3iWLLgAHA/Mk/Qa8DpwYUQ8I+kQ4DZJhbrfHBH/Wat9MLP65L6zBlZNu1WPiO8D3y9J+9ui+ZeBD5XZbhGwqEz6auD3ql9TMxtMJjdMprO7s2y61V7dNo6bmfXEfWcNLAcOMxt03HfWwHJfVWbWr1pXtjJ/2XzWdq9lcsNkFkxf4C/8OtVTX1UeOtbM+o2HoB0afKnKzPqNb6MdGio645D0JuDdwIHAS2TPTrRHxOs1rJuZDTG+jXZo6PWMQ9L7JC0FvkfWxccBwFTgc8BKSZdJ2rv21TSzocBD0A4NfZ1xnAqcHxE7/BxIT3afRtZt+r/XoG5mNsQsmL5guzYO8G20g1GvgSMiPtPLuq3A7VWvkZkNWYUGcN9VNbhVdDuupIuBrwHPA9cD7wDmRcRdta1edfh2XDOz/HZ16NiPRsRmsk4F9wU+DFxZxfqZmdkgUWngUHo9FVgUEauK0szMbBipNHCskHQXWeBYmro29624ZmbDUKVPjp8HHAmsjogtksYD59auWmZmVq96DRySjipJOiSNhWFmZsNUX2cc/5pedweOBh4ma9v4XaAdeFftqmZmZvWo1zaOiHhfRLwPeAo4OiKaI+JosttxS8cPNzOzYaDSxvG3RcTKwkJEPAK8vTZVMjOzelZp4HhY0vWSTkjTdWSXrXolaYakxyV1SJpXZv0YSbem9cslNaX0YyQ9mKaHJP1RpWWamVltVRo4zgVWARen6VH6uKtK0gjgWrLOEacCZ0maWpLtPGBTRBwKXA1cldIfAZoj4khgBvBVSSMrLNPMzGqoottxI+Jlsi/2q3OUfQzQERGrASQtBmaRBZ2CWcClaX4JcI0kRURxh/27A4V+USop08zMaqiiMw5J75Z0t6RfSFpdmPrYbCKwrmh5fUormyd1mtgNjE/veaykVcBK4IK0vpIyC3WeK6ldUntXV1clu2lmZhWo9AHAG4C/AlYAv61ddd4QEcuBwyW9HbhJ0p05t28BWiDr5LAGVTQzG5YqDRzdEZHri5vsdt2DipYnseMtvIU869P4Hg3AxuIMEfGYpBeAIyos08zMaqjSxvEfSvpnSe+SdFRh6mOb+4Epkg6WNBqYDbSV5GkDzknzZwD3RESkbUYCSGoEDgPWVFimmZnVUKVnHMem1+J+2QM4sacNImKrpIuApcAI4MaIWCXpcrLxytvILoEtktQBPEsWCACOB+ZJeo2sM8ULI+IZgHJlVrgPZmZWBRUN5DTYeSAnM7P8dmkgJ0kNkr5QuEtJ0r9Kaqh+Nc3MrN5V2sZxI9mwsX+Sps1kQ8mamdkwU2ngeEtE/F1ErE7TZcAhtayYmVVH68pWmhY2sdtlu9G0sInWla0DXSUb5CoNHC9JOr6wIOndwEu1qZKZVUvrylbm3jGXzu5OgqCzu5O5d8x18LBdUmng+DhwraQ1ktYA1wAX1KxWZlYV85fNZ8trW7ZL2/LaFuYvmz9ANbKhoNK+qh4Efk/S3ml5c01rZWZVsbZ7ba50s0pUelfVFZL2iYjNEbFZ0r6S/qHWlTOzXTO5YXKudLNKVHqp6pSIeK6wEBGbgFNrUyUzq5YF0xcwbtS47dLGjRrHgukLBqhGNhRUGjhGSBpTWJA0FhjTS34zqwNzps2hZWYLjQ2NCNHY0EjLzBbmTJsz0FWzQazSLkdagWWSCs9unAvcVJsqmVk1zZk2x4HCqqrSxvGrJD0EvD8l/X1ELK1dtczMrF5VesYB8BiwNSJ+IGmcpL0i4vlaVczMzOpTpXdVnU82tOtXU9JE4PZaVcrMzOpXpY3jnwDeTdZHFRHxS+BNtaqUmZnVr0oDxysR8WphIQ2yNPT7Yzczsx1UGjj+S9JngbGSTgK+DdxRu2qZmVm9qjRwzAO6gJXAx4DvA5+rVaXMzKx+VXo77uvAdcB1kvYDJsVwGDrQzMx2UOldVfdK2jsFjRVkAeTqCrabIelxSR2S5pVZP0bSrWn9cklNKf0kSSskrUyvJxZtc28q88E0uZHehiSPo2H1qtLnOBpS54Z/DnwjIv5O0sO9bSBpBHAtcBKwHrhfUltEPFqU7TxgU0QcKmk2cBVwJvAMMDMifiXpCGAp2S3ABXMiwoOI25BVGEej0CV6YRwNwE+B24CrtI1jpKQDyIaN/W6F2xwDdKQRA18FFgOzSvLM4o2uS5YA0yUpIn4WEb9K6avIGuXdN5YNGx5Hw+pZpYHjcrJf/R0Rcb+kQ4Bf9rHNRGBd0fJ6tj9r2C5PRGwFuoHxJXk+CDwQEa8UpX0tXab6vCSVe3NJcyW1S2rv6urqo6pm9cXjaFg9qyhwRMS3I+J3I+LCtLw6Ij5Y26qBpMPJLl99rCh5TkRMA96Tpg/3UOeWiGiOiOYJEybUuqpmVeVxNKye9Ro4JH0uNYj3tP5ESaf1sHoDcFDR8qSUVjZPeqiwAdiYlicBtwFnR8QThQ0iYkN6fR64meySmNmQ4nE0rJ711Ti+ErhD0svAA2TPcuwOTAGOBH4AXNHDtvcDUyQdTBYgZgN/WpKnDTgH+B/gDOCeiAhJ+wDfA+ZFxE8KmVNw2ScinpE0Cjgt1cFsSCk0gM9fNp+13WuZ3DCZBdMXuGHc6oIqeRxD0hSyvqoOAF4i6yn3RxHxUh/bnQosBEYAN0bEAkmXA+0R0SZpd2AR8A7gWWB2RKyW9DngErZvRzkZeBH4ETAqlfkD4JMR8dve6tHc3Bzt7b4Jy8wsD0krIqJ5h/Th8ByfA4eZWX49BY5K76oyMzMDHDjMzCwnBw4zM8ul0r6q3ippmaRH0vLvpgZsMzMbZio947iO7C6n1wAi4mGy22vNzGyYqTRwjIuI/y1J21rtypiZWf2rNHA8I+ktpOFiJZ0BPFWzWpmZWd2qtFv1TwAtwGGSNgBPAn9Ws1qZmVndqnQEwNXA+yXtAeyW+okyM7NhqKLAkfqOOhtoIhubA4CI+Iua1cxskGpd2eo+pmxIq/RS1feB+8g6PXy9dtUxG9w8cp8NB5UGjt0j4pM1rYnZENDbyH0OHDZUVHpX1SJJ50s6QNJ+hammNTMbhDxynw0HlQaOV4F/Jhs3Y0Wa3N2sWQmP3GfDQaWB41PAoRHRFBEHp+mQWlbMbDDyyH02HFQaODqALX3mMhvm5kybQ8vMFhobGhGisaGRlpktbt+wIaXSxvEXgQcl/RB4pZDo23HNdjRn2hwHChvSKg0ct6fJzMyGuUqfHL9pZwqXNAP4Itn44NdHxJUl68cA3wCOBjYCZ0bEGkknAVcCo8ka5j8TEfekbY4Gvg6MJXu+5OIYDuPfmpnViV7bOCR9K72ulPRw6dTHtiOAa4FTgKnAWZKmlmQ7D9gUEYcCVwNXpfRngJkRMQ04B1hUtM2XgfOBKWmaUcF+mplZlfR1xnFxej1tJ8o+BuhI/VwhaTEwC3i0KM8s4NI0vwS4RpIi4mdFeVYBY9PZyX7A3hFxXyrzG8DpwJ07UT8zM9sJvZ5xRESh6/QLI6KzeAIu7KPsicC6ouX1Ka1snojYCnQD40vyfBB4ICJeSfnX91EmAJLmSmqX1N7V1dVHVc3MrFKV3o57Upm0U6pZkXIkHU52+epjebeNiJaIaI6I5gkTJlS/cjbktK5spWlhE7tdthtNC5toXdk60FUyq0u9XqqS9HGyM4tDSto09gJ+0kfZG4CDipYnpbRyedZLGgk0kDWSI2kScBtwdkQ8UZR/Uh9lmuXmzgnNKtfXGcfNwEygLb0WpqMjoq+BnO4Hpkg6WNJosjHK20rytJE1fgOcAdwTEZG6cf8eMC8itgWodOlss6TjlPXtfjbwH33tpFlfeuuc0My21+sZR0R0k7U7nJW34IjYKukiYCnZ7bg3RsQqSZcD7RHRBtxA1oFiB/AsWXABuAg4FPhbSX+b0k6OiKfJzoC+TnY77p24YdyqwJ0TmlVOw+ERiObm5mhvd5+M1rOmhU10dnfukN7Y0Miav1zT/xUyqwOSVkREc2l6pY3jZnWrGo3a7pzQrHIOHDaoFRq1O7s7CWJbo3be4OHOCc0q50tVNqj5EpNZ7fhSlQ1JbtQ2638OHDaoecQ9s/7nwGGDmhu1zfqfA4cNam7UNut/bhw3M7Oy3DhuZmZV4cBhZma5OHCYmVkuDhxmZpaLA4eZmeXiwGFmZrk4cJiZWS4OHGZmlosDh5mZ5eLAYWZmudQ0cEiaIelxSR2S5pVZP0bSrWn9cklNKX28pB9KekHSNSXb3JvKfDBNb6rlPljtVGPkPjPrfyNrVbCkEcC1wEnAeuB+SW0R8WhRtvOATRFxqKTZwFXAmcDLwOeBI9JUak5EuPOpQawwct+W17YAbBu5D3AHhWZ1rpZnHMcAHRGxOiJeBRYDs0ryzAJuSvNLgOmSFBEvRsSPyQKIDUHzl83fFjQKtry2hfnL5g9QjcysUrUMHBOBdUXL61Na2TwRsRXoBsZXUPbX0mWqz0tSuQyS5kpql9Te1dWVv/ZWUx65z2zwGoyN43MiYhrwnjR9uFymiGiJiOaIaJ4wYUK/VtD65pH7zAavWgaODcBBRcuTUlrZPJJGAg3Axt4KjYgN6fV54GayS2I2yHjkPrPBq5aB435giqSDJY0GZgNtJXnagHPS/BnAPdHLyFKSRkraP82PAk4DHql6za3mPHKf2eBV0xEAJZ0KLARGADdGxAJJlwPtEdEmaXdgEfAO4FlgdkSsTtuuAfYGRgPPAScDncCPgFGpzB8An4yI3/ZWD48AaGaWX08jAHroWDMzK8tDx5qZWVU4cJiZWS4OHGZmlosDh+0U9zNlNnzVrK8qG7rcz5TZ8OYzDsvN/UyZDW8OHJab+5kyG94cOCw39zNlNrw5cFhu7mfKbHhz4LDc3M+U2fDmLkfMzKwsdzliZmZV4cBhZma5OHCYmVkuDhxmZpaLA8cw4z6mzGxXua+qYcR9TJlZNfiMYxhxH1NmVg01DRySZkh6XFKHpHll1o+RdGtav1xSU0ofL+mHkl6QdE3JNkdLWpm2+ZIk1XIfhhL3MWVm1VCzwCFpBHAtcAowFThL0tSSbOcBmyLiUOBq4KqU/jLweeDTZYr+MnA+MCVNM6pf+6HJfUyZWTXU8ozjGKAjIlZHxKvAYmBWSZ5ZwE1pfgkwXZIi4sWI+DFZANlG0gHA3hFxX2SPvH8DOL2G+zCkuI8pM6uGWgaOicC6ouX1Ka1snojYCnQD4/soc30fZQIgaa6kdkntXV1dOas+NLmPKTOrhiF7V1VEtAAtkPVVNcDVqRtzps1xoDCzXVLLM44NwEFFy5NSWtk8kkYCDcDGPsqc1EeZZmZWQ7UMHPcDUyQdLGk0MBtoK8nTBpyT5s8A7oleuuuNiKeAzZKOS3dTnQ38R/WrbmZmPanZpaqI2CrpImApMAK4MSJWSbocaI+INuAGYJGkDuBZsuACgKQ1wN7AaEmnAydHxKPAhcDXgbHAnWkyM7N+4vE4BonWla3MXzaftd1rmdwwmQXTF7itwsxqyuNxDJBq9A1V6Cqks7uTILZ1FeJ+psxsIDhw9KCevvDdVYiZ1RMHjjLq7QvfXYWYWT1x4Cij3r7w3VWImdUTB44y6u0L312FmFk9ceAoo96+8N1ViJnVkyHb5ciuWDB9wXYDHsHOf+EDVbmN1l2FmFm98HMcPfBzE2Y23PX0HIcDh5mZleUHAM3MrCocOMzMLBcHDjMzy8WBw8zMcnHgMDOzXIbFXVWSuoDOga5HlewPPDPQlahTPja98/HpnY/PjhojYkJp4rAIHEOJpPZyt8eZj01ffHx65+NTOV+qMjOzXBw4zMwsFweOwadloCtQx3xseufj0zsfnwq5jcPMzHLxGYeZmeXiwGFmZrk4cAwASQdJ+qGkRyWtknRxSt9P0t2Sfple903pkvQlSR2SHpZ0VFFZ54n76xoAAAVTSURBVKT8v5R0TlH60ZJWpm2+JEn9v6c7T9IIST+T9N20fLCk5Wl/bpU0OqWPScsdaX1TURmXpPTHJX2gKH1GSuuQNK+/921XSdpH0hJJP5f0mKR3+bPzBkl/lf6vHpF0i6Td/fmpsojw1M8TcABwVJrfC/gFMBX4J2BeSp8HXJXmTwXuBAQcByxP6fsBq9Prvml+37Tuf1NepW1PGej9znmMPgncDHw3LX8LmJ3mvwJ8PM1fCHwlzc8Gbk3zU4GHgDHAwcATwIg0PQEcAoxOeaYO9P7mPDY3AX+e5kcD+/izs+3YTASeBMYWfW4+4s9PdSefcQyAiHgqIh5I888Dj5F94GeRfSmQXk9P87OAb0TmPmAfSQcAHwDujohnI2ITcDcwI63bOyLui+y/4BtFZdU9SZOAPwCuT8sCTgSWpCylx6ZwzJYA01P+WcDiiHglIp4EOoBj0tQREasj4lVgcco7KEhqAH4fuAEgIl6NiOfwZ6fYSGCspJHAOOAp/PmpKgeOAZZOjd8BLAfeHBFPpVW/Bt6c5icC64o2W5/SektfXyZ9sFgI/DXweloeDzwXEVvTcvH+bDsGaX13yp/3mA0WBwNdwNfSpbzrJe2BPzsARMQG4F+AtWQBoxtYgT8/VeXAMYAk7Qn8O/CXEbG5eF36tTfs7pWWdBrwdESsGOi61KmRwFHAlyPiHcCLZJemthmunx2A1LYziyzAHgjsAcwY0EoNQQ4cA0TSKLKg0RoR30nJv0mXCkivT6f0DcBBRZtPSmm9pU8qkz4YvBv4Q0lryC4DnAh8kewSy8iUp3h/th2DtL4B2Ej+YzZYrAfWR8TytLyELJD4s5N5P/BkRHRFxGvAd8g+U/78VJEDxwBI11BvAB6LiC8UrWoDCne3nAP8R1H62ekOmeOA7nRZYilwsqR90y+tk4Glad1mScel9zq7qKy6FhGXRMSkiGgia6y8JyLmAD8EzkjZSo9N4ZidkfJHSp+d7po5GJhC1uh7PzAl3WUzOr1HWz/sWlVExK+BdZLelpKmA4/iz07BWuA4SeNS/QvHx5+fahro1vnhOAHHk11KeBh4ME2nkl1bXQb8EvgBsF/KL+Basrs5VgLNRWV9lKzhrgM4tyi9GXgkbXMNqZeAwTQBJ/DGXVWHkP3jdgDfBsak9N3Tckdaf0jR9vPT/j9O0Z1B6Vj/Iq2bP9D7uRPH5UigPX1+bie7K8qfnTfqfxnw87QPi8jujPLnp4qTuxwxM7NcfKnKzMxyceAwM7NcHDjMzCwXBw4zM8vFgcPMzHJx4DCrMUlfl7RF0l5FaQslhaT9B7JuZjvDgcOsf3SQOsOTtBvZE/HD7oljGxocOMyqRFJTGh/jujQexF2SxqbVi4Ez0/wJwE+ArUXb3i5pRdpubkprTGNl7C9pN0n/Lenk/twns3IcOMyqawpwbUQcDjwHfDCl/wKYkLr3OIsskBT7aEQcTfbU9l9IGh8RncBVwJeBTwGPRsRd/bETZr1x4DCrricj4sE0vwJoKlr3HbK+jY4F/rtku7+Q9BBwH1knelMAIuJ6YG/gAuDTtau2WeVG9p3FzHJ4pWj+t8DYouVbyYLJTRHxemFEVkknkPXq+q6I2CLpXrI+lJA0jjd6q90TeL6WlTerhAOHWT+JiE5J88k6ISzWAGxKQeMwsmFbC64CWoFO4DrgtH6prFkvfKnKrB9FxFcj4omS5P8ERkp6DLiS7HIVkt4LvJNs/PBW4FVJ5/Zrhc3KcO+4ZmaWi884zMwsFwcOMzPLxYHDzMxyceAwM7NcHDjMzCwXBw4zM8vFgcPMzHL5PzGJr4gOGkx/AAAAAElFTkSuQmCC\n"
          },
          "metadata": {
            "needs_background": "light"
          }
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## **Sieve of Sundaram**\n",
        "\n",
        "Now, we will repeat the same steps for the Sieve of Sundaram "
      ],
      "metadata": {
        "id": "UnfbNa3B29ML"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### First, implement the Sieve of Sundaram sudo code:"
      ],
      "metadata": {
        "id": "R3p6FL0fr11i"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def sundaram(n):\n",
        "\n",
        "  m = int((n - 1)/2)\n",
        "  nums = list(range(1, m + 1))\n",
        "  i = 1    \n",
        "  \n",
        "  while (2*i + 2*(i**2)) <= m: \n",
        "    j = i             \n",
        "    w = (i + j + 2* i * j)\n",
        "    while w  <= m:                   \n",
        "      if w in nums:\n",
        "        nums.remove(w)\n",
        "      j += 1\n",
        "      w = (i + j + 2* i * j) # recalculate since j changed\n",
        "         \n",
        "    i += 1    \n",
        "\n",
        "  primes = [(2*b + 1) for b in nums]\n",
        "  return primes"
      ],
      "metadata": {
        "id": "2cnMl1Gs4MWW"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Test the function and print out the first primes up to 50:"
      ],
      "metadata": {
        "id": "3Ck3-Kb1Zara"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "sundaram(50)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "pKK8YsJjYqxv",
        "outputId": "752b459e-b5ba-4f18-821b-36951e0f80e3"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]"
            ]
          },
          "metadata": {},
          "execution_count": 148
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Note that this algorithm excludes \"2\" as a prime number, but we could always add it on manually if that's necessary."
      ],
      "metadata": {
        "id": "5ymqIO9aVT4Z"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Runtime of Sundaram"
      ],
      "metadata": {
        "id": "QxEbWdwFp1yW"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def timeSundaram(Max):\n",
        "  startTime = time.time()\n",
        "  sundaram(Max)\n",
        "  endTime = time.time()\n",
        "  return endTime - startTime"
      ],
      "metadata": {
        "id": "5Oxud1h3p4sL"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "timeSundaram(10000)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "A-_P_ZOVp94h",
        "outputId": "9c622e01-efda-4fa1-d538-ad147235eb19"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "0.2920386791229248"
            ]
          },
          "metadata": {},
          "execution_count": 150
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Plotting runtime of Sundaram"
      ],
      "metadata": {
        "id": "UQFN_qcMq04Y"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "SundaramMaxVals = range(10000,100000,5000)\n",
        "runtimes = [timeSundaram(n) for n in SundaramMaxVals]  "
      ],
      "metadata": {
        "id": "4180-F-mq7Am"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "plt.plot(SundaramMaxVals, runtimes, 'go') \n",
        "plt.title(\"Sieve of Sundaram runtimes\")\n",
        "plt.xlabel(\"nMax\")\n",
        "plt.ylabel(\"time (seconds)\");"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 295
        },
        "id": "cUstxAECrFEZ",
        "outputId": "ed2cfa43-b62c-4b63-87da-4592e55b977a"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ],
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX4AAAEWCAYAAABhffzLAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAeMklEQVR4nO3dfZwcVZ3v8c83hKcIDMGMGB4yA4iyKBpkFHiJigRZYMkFleWCuYroOq4PV9jV9aKzd1dc4+ruotHViwyCoA7PIgIvVsAsPt4lOsFIgChEyAS4gQxChkAQEvjdP+p0aCbzUD3p6p6e+r5fr3pN16mqrl9VOr+uPnXqHEUEZmZWHtOaHYCZmTWWE7+ZWck48ZuZlYwTv5lZyTjxm5mVjBO/mVnJOPEbAJIWSLq52XFUk/QmSfdKelLSSU2OZZWko5sZQzNJukvSkc2Ow+rDib9EJB0h6f9KGpL0mKRfSnoDQET0RcQxzY5xmM8BX4+InSLi2uELxzoemzhJF0v6fHVZRLw6In7SpJCszqY3OwBrDEm7ADcAHwauBLYD3gw808y4xtEB3DXSglY5HknTI2LTVN2ftaiI8FSCCegC1o2x/H3AL6rmDwBuAR4Dfg+cksoPBR4Gtqla9x3AHen1NOBs4A/AH8mS8m5j7PeDwMq0n+uAPVL5H4DngaeBJ4HtazyezwLfq5rvBAKYnuZ/AvwT8EtgPXAzMKtq/fcAA+kYeoBVwNFp2RuB/wLWAWuArwPbVW0bwEeBe4H7U9lXgQeAJ4ClwJuHxXoV8L0Uy3LglcCngbVpu2PGONZVwP8C7iD74pueYnhF1ToXA59Pr48EHgQ+kd5/DXBGWtYNbASeTef9+qp9HD2ReIE24MK0n4eAz5M+P8ArgJ8CQ8CjwBXN/r9ShslVPeVxD/CcpEskHSdp5mgrSnoJWdK/FHgZcCrwfyQdGBFLgKeAo6o2eXdaF+B/AicBbwX2AB4HvjHKfo4C/hk4BZhNlmgvB4iI/YDVwPzIqnqGX8nnPp4xvBs4Ix3jdsAnU1wHAueRJf89gJcCe1Vt9xzwN8As4HBgHvCRYe99EtmX5IFp/tfAXGA3snN1laQdqtafD3wXmAn8BriJ7Et0T7Iqr/PHOZbTgL8Ado18V/wvJ0vIewIfAL4haWZE9AJ9wL+k8z5/lO1rifdiYBNZkj8YOAb4q7Tsn8i+dGeSneN/zxG7bSUn/pKIiCeAI8iuBC8ABiVdJ2n3EVY/AVgVEd+OiE0R8Rvg+8BfpuWXkSUaJO0MHJ/KAP4a6ImIB1Oy/ixwsqSRqhUXABdFxO1p3U8Dh0vqrPPxjObbEXFPRDxN9stkbio/GbghIn6W4vrfZL8+KvteGhG3pXOziizJvXXYe/9zRDyW3puI+F5E/DFtcy6wPfCqqvV/HhE3paR9FdAOfDEiNpJ9GXZK2nWMY/laRDxQ2V8OG4HPRcTGiLiR7Or+VeNsUy1XvOnf43jgrIh4KiLWAl8hu5ioxNFB9kvvTxHxixpisAly4i+RiFgREe+LiL2A15BdzS4aYdUO4FBJ6yoTWZJ+eVp+KfBOSdsD7wRuj4iBqm1/ULXdCrIr5JES8h5kV/mV+J4kq1rZs87HM5qHq15vAHaqiuuBqv08leICQNIrJd0g6WFJTwBfILv6r/ZA9YykT0pakW5EryO72q7e5pGq108Dj0bEc1XzVMU3kgfGWDaSPw77ZVB9/HnkjbcD2BZYU/WZOJ/sVxbApwABv0oth95f43HYBDjxl1RE/I7sJ/hrRlj8APDTiNi1atopIj6ctr2bLGEfx4ureSrbHjds2x0i4qER9vP/yBIDsLmK6aVk9cBbezxPATOqVnn58G3GsAbYuyquGSmuivOA3wH7R8QuwGfIkteLQqra/s1kCe4UYGZE7EpWpz18m60xvJvdDUz8+OvZZe8DZPcdZlV9HnaJiFcDRMTDEfHBiNgD+BBZleIr6rh/G4ETf0lIOkDSJyTtleb3JquuuW2E1W8AXinpPZK2TdMbJP1Z1TqXAmcCbyH7qV/xTWChpI60n3ZJJ44S1mXAGZLmpl8PXwCWpOqTrT2eZcBbJM2R1EZWjZTX1cAJqbnodmR11tX/V3Ymu0n7pKQDyFoWjWVnsjruQWC6pH8AdqkhnolYBrxb0jaSjmXLqqixPALsW48gImINWR3+uZJ2kTRN0n6S3gog6S8r/4Zk94OCqmo1K4YTf3msJ7vZuETSU2QJ8k6ylh0vEhHryW7AnUp2Vf4w8CWyeumKy8iSyX9GxKNV5V8la51zs6T1aT+HjhRQRPyYrP78+2RX2fvxQt3vVh1PRNwCXEHW0mUp2ZdZLhFxF1mrnEtTXI+TtYKp+CTZL531ZPcXrhjnLW8CfkR2Q3oA+BO1V83U6kyyG7CVarotnoMYw4XAgalqppbtRvNespvnd5Ody6vJbuYDvIHs3/BJss/NmRFxXx32aWNQhAdiMTMrE1/xm5mVjBO/mVnJOPGbmZWME7+ZWcm0RCdts2bNis7OzmaHYWbWUpYuXfpoRLQPL2+JxN/Z2Ul/f3+zwzAzaymSBkYqd1WPmVnJOPGbmZWME7+ZWck48ZuZlYwTv5lZyTjxm5lNQn3L++hc1Mm0c6bRuaiTvuV9dXvvlmjOaWZWJn3L++i+vpsNGzcAMDA0QPf13QAsOGjBVr+/r/jNzCaZnsU9m5N+xYaNG+hZ3FOX93fiNzObZFYPra6pvFZO/GZmk8yctjk1ldfKid/MbJJZOG8hM7ad8aKyGdvOYOG8hXV5fyd+M7NJZsFBC+id30tHWwdCdLR10Du/ty43dqFFhl7s6uoKd9JmZlYbSUsjomt4ua/4zcxKxonfzKxknPjNzErGid/MrGSc+M3MSsaJ38ysZJz4zcxKxonfzKxknPjNzErGid/MrGSc+M3M6qjIkbPqpbDEL2kHSb+S9FtJd0k6J5XvI2mJpJWSrpC0XVExmJk1UmXkrIGhAYLYPHLWZEv+RV7xPwMcFRGvA+YCx0o6DPgS8JWIeAXwOPCBAmMwM2uYokfOqpfCEn9knkyz26YpgKOAq1P5JcBJRcVgZtZIRY+cVS+F1vFL2kbSMmAtcAvwB2BdRGxKqzwI7FlkDGZmjVL0yFn1Umjij4jnImIusBfwRuCAvNtK6pbUL6l/cHCwsBjNzOql6JGz6qUhrXoiYh1wK3A4sKuk6WnRXsBDo2zTGxFdEdHV3t7eiDDNzLZK0SNn1cv08VeZGEntwMaIWCdpR+DtZDd2bwVOBi4HTgd+WFQMZmaNtuCgBZMu0Q9XWOIHZgOXSNqG7JfFlRFxg6S7gcslfR74DXBhgTGYmdkwhSX+iLgDOHiE8vvI6vvNzKwJ/OSumVnJOPGbmZWME7+ZWck48ZuZlYwTv5lZyTjxm5mVjBO/mVnJOPGbmZWME7+ZWck48ZuZlYwTv5lZyTjxm5mVjBO/mVnJOPGbmZWME7+ZWck48ZuZAX3L++hc1Mm0c6bRuaiTvuV9zQ6pMEWOwGVm1hL6lvfRfX03GzZuAGBgaIDu67sBJv0wihPhK34zK72exT2bk37Fho0b6Fnc06SIiuXEb2alt3podU3lrc6J38xKb07bnJrKW50Tv5mV3sJ5C5mx7YwXlc3YdgYL5y1sUkTFKizxS9pb0q2S7pZ0l6QzU/lnJT0kaVmaji8qBjOzPBYctIDe+b10tHUgREdbB73ze6fkjV0ARUQxbyzNBmZHxO2SdgaWAicBpwBPRsS/5X2vrq6u6O/vLyROM7OpStLSiOgaXl5Yc86IWAOsSa/XS1oB7FnU/szMLJ+G1PFL6gQOBpakoo9JukPSRZJmNiIGMzPLFJ74Je0EfB84KyKeAM4D9gPmkv0iOHeU7bol9UvqHxwcLDpMM7PSKDTxS9qWLOn3RcQ1ABHxSEQ8FxHPAxcAbxxp24jojYiuiOhqb28vMkwzs1IpslWPgAuBFRHx5ary2VWrvQO4s6gYzMxsS0X21fMm4D3AcknLUtlngNMkzQUCWAV8qMAYzMxsmCJb9fwC0AiLbixqn2ZmNj4/uWtmVjJO/GZmJePEb2ZWMk78ZtbSyjRyVr14BC4za1llGzmrXnzFb2Ytq2wjZ9WLE7+ZtayyjZxVL078ZtayyjZyVr048ZtZyyrbyFn1kuvmrqSXkXXBsAfwNFn/Ov2pozUzs6ao3MDtWdzD6qHVzGmbw8J5C31jdxxjjsAl6W3A2cBuwG+AtcAOwCvJula+Gjg3dbdcGI/AZWZWu4mOwHU88MGI2OJOiaTpwAnA28m6XjYzsxYwZuKPiL8bY9km4Nq6R2RmZoXKdXNX0pmSdlHmQkm3Szqm6ODMzKz+8rbqeX+qxz8GmEnWz/4XC4vKzMwKkzfxV/rVPx74bkTcxch97ZuZ2SSXN/EvlXQzWeK/SdLOgJtympm1oLydtH0AmAvcFxEbJL0UOKO4sMzMrChjJn5Jrx9WtG82hrqZmbWq8a74z01/dwAOAe4gq9t/LdAPHF5caGZmVoQx6/gj4m0R8TZgDXBIRHRFxCHAwcBDjQjQzMzqK+/N3VdFxPLKTETcCfzZWBtI2lvSrZLulnSXpDNT+W6SbpF0b/o7c+Lhm1mr8shZzZM38d8h6VuSjkzTBWTVPmPZBHwiIg4EDgM+KulAsr5/FkfE/sDiNG9mJVIZOWtgaIAgNo+c5eTfGHkT/xnAXcCZabqbcVr1RMSaiLg9vV4PrAD2BE4ELkmrXQKcVHvYZtbKPHJWc+VqzhkRfwK+kqaaSeokuy+wBNg9ItakRQ8Du0/kPc2sdXnkrObK21fPm1J9/D2S7qtMObfdiaz3zrOGd98cWZ/QI/YLLalbUr+k/sHBwTy7MrMW4ZGzmitvVc+FwJeBI4A3VE1jkrQtWdLvi4hrUvEjkman5bPJ+vjfQkT0plZEXe3t7TnDNLNW4JGzmitv4h+KiP+IiLUR8cfKNNYGyp70uhBYERFfrlp0HXB6en068MOaozazlrbgoAX0zu+lo60DITraOuid3+uRsxpkzBG4Nq8kfRHYBrgGeKZSXrl5O8o2RwA/B5bzQr8+nyGr578SmAMMAKdExGNj7d8jcJmZ1W6iI3BVHJr+Vr9BAEeNtkFE/ILRe/Ccl3O/ZmZWZ3lb9byt6EDMzKwx8rbqaZP05UorG0nnSmorOjgzM6u/vDd3LwLWA6ek6Qng20UFZWZmxclbx79fRLyrav4cScuKCMjMzIqV94r/6dRKB8ge6AKeLiYkMzMrUt4r/g8Dl1TV6z8OvK+QiMzMrFB5W/UsA14naZc0/8Q4m5iZ2SSVt1XPFyTtGhFPRMQTkmZK+nzRwZmZWf3lreM/LiLWVWYi4nHg+GJCMjOzIuVN/NtI2r4yI2lHYPsx1jezKcojZ7W+vDd3+4DFkipt98/ghcFUzKwkKiNnVQZRqYycBbiDtRaSq5M2AEnHAken2Vsi4qbCohrGnbSZTQ6dizoZGBrYoryjrYNVZ61qfEA2pq3tpA2yoRM3RcSPJc2QtHMaUtHMSsIjZ00NeVv1fBC4Gjg/Fe0JXFtUUGY2OXnkrKkh783djwJvIuujh4i4F3hZUUGZ2eTkkbOmhryJ/5mIeLYyI2k6o4yVa2ZTl0fOmhry1vH/VNJngB0lvR34CHB9cWGZ2WS14KAFTvQtLu8V/9nAINkwih8CbgT+vqigzMysOHn76nkeuAC4QNJuwF6Rtx2omZlNKnlb9fxE0i4p6S8l+wL4SrGhmZlZEfJW9bSlHjnfCXwnIg7FA6abmbWkvIl/uqTZZMMu3pBnA0kXSVor6c6qss9KekjSsjS5ozczswbLm/g/B9wErIyIX0vaF7h3nG0uBo4dofwrETE3TTfmD9XMzOoh783dq4CrqubvA941+hYQET+T1Lk1wZmZWf2NecUv6e/TDd3Rlh8l6YQa9/kxSXekqqCZNW5rZmZbabyqnuXA9ZIWS/pXSZ+S9A+SvitpOTAfWFLD/s4D9gPmAmuAc0dbUVK3pH5J/YODgzXswsxG4n70rSJXt8yS9ifrq2c28DRZT50/i4inx9muE7ghIl5Ty7Lh3C2z2dYZ3o8+ZH3suLuFqW2rumVOnbKNdzM3TxCzI2JNmn0HcOdY65tZffQs7nlR0gfYsHEDPYt7nPhLqJb++Gsi6TLgSGCWpAeBfwSOlDSXrIO3VWTdP5hZwdyPvlUrLPFHxGkjFF9Y1P7MbHRz2uaMOHKW+9Evp7zt+M2shbkffauWt6+eV6aWPXem+ddKcu+cZi3C/ehbtbyten4K/B1wfkQcnMruzNMipx7cqsfMrHajterJW9UzIyJ+Naxs09aHZWZmjZY38T8qaT/ScIuSTiZ7AMvMzFpM3lY9HwV6gQMkPQTcD/yPwqIyM7PC5H2A6z7gaEkvAaZFxPpiwzIzs6LkSvySdgXeC3SS9c0PQER8vLDIzMysEHmrem4EbiPrtO354sIxM7Oi5U38O0TE3xYaiZmNqG95Hz2Le1g9tJo5bXNYOG+h29/bVsmb+L8r6YNkwy4+UymMiMcKicrMgC171RwYGqD7+m4AJ3+bsLzNOZ8F/hX4L2BpmvxElVnBxupV02yi8l7xfwJ4RUQ8WmQwZvZi7lXTipD3in8lsGHctcysrkbrPdO9atrWyJv4nwKWSTpf0tcqU5GBmZl71bRi5K3quTZNZtZAlRu4btVj9ZSrd85mc++cZma1m9CYu5KujIhTJC0nddBWLSJeW8cYzcysAcar6jkz/T2h6EDMzKwxxry5GxGVrpc/EhED1RPwkeLDMzOzesvbquftI5QdV89AzMysMcar4/8w2ZX9vpLuqFq0M/DLIgMzM7NijHfFfykwH7gu/a1Mh0TEmAOxSLpI0trKAO2pbDdJt0i6N/2duZXxm01afcv76FzUybRzptG5qJO+5X3NDskMGL+OfygiVkXEacPq+PN0znYxcOywsrOBxRGxP7A4zZtNOZXO1QaGBghic+dqTv42GeSt469ZRPwMGP4FcSJwSXp9CXBSUfs3ayZ3rmaTWWGJfxS7V7UUehjYfbQVJXVL6pfUPzg42JjozOrEnavZZNboxL9ZZI8Mj/rYcET0RkRXRHS1t7c3MDKzrefO1Wwya3Tif0TSbID0d22D92/WEO5czSazRif+64DT0+vTgR82eP9mDbHgoAX0zu+lo60DITraOuid3+vO1WxSKKyTNkmXAUcCs4BHgH8k6+HzSmAOMACckqeFkDtpMzOr3YQ6adsaEXHaKIvmFbVPMzMbX9Nu7pqZWXM48ZuZlYwTv9kw7mrBprrC6vjNWlGlq4XKU7eVrhYAt8ixKcNX/GZV3NWClYETv1kVd7VgZeDEb1bFXS1YGTjxm1VxVwtWBk78ZlXc1YKVQWFdNtSTu2wwM6vdaF02+IrfzKxknPjNzErGid+mDD9xa5aPn9y1KcFP3Jrl5yt+mxL8xK1Zfk78NiX4iVuz/Jz4bUrwE7dm+Tnx25TgJ27N8nPitynBT9ya5ecnd83Mpig/uWtmZkCTEr+kVZKWS1omyZfy5oevzBqomQ9wvS0iHm3i/m2S8MNXZo3lqh5rOj98ZdZYzUr8Adwsaamk7pFWkNQtqV9S/+DgYIPDs0byw1dmjdWsxH9ERLweOA74qKS3DF8hInojoisiutrb2xsfoTWMH74ya6ymJP6IeCj9XQv8AHhjM+KwycEPX5k1VsMTv6SXSNq58ho4Briz0XHY5OGHr8waqxmtenYHfiCpsv9LI+JHTYjD6qBveR89i3tYPbSaOW1zWDhv4YQS9oKDFjjRmzVIwxN/RNwHvK7R+7X6czNMs9bk5pw2YW6GadaanPhtwtwM06w1OfHbhLkZpllrcuK3CXMzTLPW5MRvE+ZmmGatyf3xl1S9mmGa2eQ1Wn/8zeyd05rEzTDNys1VPSXkZphm5ebEX0JuhmlWbk78LaYeI1W5GaZZuTnxt5BK3fzA0ABBbK6brzX5uxmmWbk58beQetXNuxmmWbm5VU8LqWfdvHvDNCsvX/G3ENfNm1k9OPE3SD1uyrpu3szqwYm/Aep1U9Z182ZWD+6yoQE6F3UyMDSwRXlHWwerzlrV+IDMrBRG67LBV/zjqEcVjR+YMrPJxIl/DPWqovFNWTObTKZs4q/HlXq92s37pqyZTSZTMvHX60q9XlU0vilrZpNJU27uSjoW+CqwDfCtiPjiWOvXenO3XjdTfVPWzFrZpLm5K2kb4BvAccCBwGmSDqznPup1pe4qGjObippR1fNGYGVE3BcRzwKXAyfWcwf1upnqKhozm4qa0VfPnsADVfMPAocOX0lSN9ANMGdObQl74byFLxphCiZ+pe4+bcxsqpm0N3cjojciuiKiq729vaZtfaVuZja6ZlzxPwTsXTW/VyqrK1+pm5mNrBlX/L8G9pe0j6TtgFOB65oQh5lZKTX8ij8iNkn6GHATWXPOiyLirkbHYWZWVk0ZiCUibgRubMa+zczKbtLe3DUzs2I48ZuZlUxL9McvaRDYsu+E1jQLeLTZQUxiPj+j87kZm8/PljoiYov28C2R+KcSSf0j9Z1hGZ+f0fncjM3nJz9X9ZiZlYwTv5lZyTjxN15vswOY5Hx+RudzMzafn5xcx29mVjK+4jczKxknfjOzknHinwBJe0u6VdLdku6SdGYq303SLZLuTX9npnJJ+pqklZLukPT6qvc6Pa1/r6TTq8oPkbQ8bfM1SWr8kU6cpG0k/UbSDWl+H0lL0vFckTroQ9L2aX5lWt5Z9R6fTuW/l/TnVeXHprKVks5u9LFtLUm7Srpa0u8krZB0uD87L5D0N+n/1Z2SLpO0gz8/dRYRnmqcgNnA69PrnYF7yIaR/Bfg7FR+NvCl9Pp44D8AAYcBS1L5bsB96e/M9HpmWvartK7Stsc1+7hrPEd/C1wK3JDmrwROTa+/CXw4vf4I8M30+lTgivT6QOC3wPbAPsAfyDr12ya93hfYLq1zYLOPt8ZzcwnwV+n1dsCu/uxsPjd7AvcDO1Z9bt7nz099J1/xT0BErImI29Pr9cAKsg/siWT/qUl/T0qvTwS+E5nbgF0lzQb+HLglIh6LiMeBW4Bj07JdIuK2yD7F36l6r0lP0l7AXwDfSvMCjgKuTqsMPzeVc3Y1MC+tfyJweUQ8ExH3AyvJhu0sfOjOIklqA94CXAgQEc9GxDr82ak2HdhR0nRgBrAGf37qyol/K6WflgcDS4DdI2JNWvQwsHt6PdJwk3uOU/7gCOWtYhHwKeD5NP9SYF1EbErz1cez+Ryk5UNp/VrPWavYBxgEvp2qwr4l6SX4swNARDwE/BuwmizhDwFL8eenrpz4t4KknYDvA2dFxBPVy9LVVunayko6AVgbEUubHcskNR14PXBeRBwMPEVWtbNZWT87AOnexolkX5B7AC8Bjm1qUFOQE/8ESdqWLOn3RcQ1qfiR9FOb9HdtKh9tuMmxyvcaobwVvAn4b5JWkf2MPgr4KlkVRWX8h+rj2XwO0vI24I/Ufs5axYPAgxGxJM1fTfZF4M9O5mjg/ogYjIiNwDVknyl/furIiX8CUh3ihcCKiPhy1aLrgErritOBH1aVvze10DgMGEo/628CjpE0M13pHAPclJY9IemwtK/3Vr3XpBYRn46IvSKik+xm239GxALgVuDktNrwc1M5Zyen9SOVn5pabewD7E9207Klh+6MiIeBByS9KhXNA+7Gn52K1cBhkmak+Cvnx5+femr23eVWnIAjyH6K3wEsS9PxZHWLi4F7gR8Du6X1BXyDrDXBcqCr6r3eT3bjaSVwRlV5F3Bn2ubrpKesW2kCjuSFVj37kv3HWwlcBWyfyndI8yvT8n2rtu9Jx/97qlqmpHN9T1rW0+zjnMB5mQv0p8/PtWStcvzZeSH+c4DfpWP4LlnLHH9+6ji5ywYzs5JxVY+ZWck48ZuZlYwTv5lZyTjxm5mVjBO/mVnJOPGb5SDpYkkbJO1cVbZIUkia1czYzGrlxG+W30pSh16SppE9lVy6pz6t9Tnxm1WR1Jn6yL8g9Ql/s6Qd0+LLgf+eXh8J/BLYVLXttZKWpu26U1lH6i9/lqRpkn4u6ZhGHpPZcE78ZlvaH/hGRLwaWAe8K5XfA7SnLhJOI/siqPb+iDiE7MnZj0t6aUQMAF8CzgM+AdwdETc34iDMRuPEb7al+yNiWXq9FOisWnYNWf8uhwI/H7bdxyX9FriNrCOw/QEi4lvALsBfA58sLmyzfKaPv4pZ6TxT9fo5YMeq+SvIvgwuiYjnK6MaSjqSrGfJwyNig6SfkPUjg6QZvNBj5k7A+iKDNxuPE79ZDSJiQFIPWUdq1dqAx1PSP4Bs6MOKLwF9wABwAXBCQ4I1G4WresxqFBHnR8QfhhX/CJguaQXwRbLqHiS9FXgD2Ri6fcCzks5oaMBmw7h3TjOzkvEVv5lZyTjxm5mVjBO/mVnJOPGbmZWME7+ZWck48ZuZlYwTv5lZyfx/EmQH5EBWRnYAAAAASUVORK5CYII=\n"
          },
          "metadata": {
            "needs_background": "light"
          }
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### **Comparing runtimes:**\n",
        "\n",
        "In short, the ***Sieve of Eratosthenes is much faster than the Sieve of Sundaram.*** For up to 10,000 n values, the runtimes are:\n",
        "\n",
        "**Sieve of Eratosthenes:** 0.0094 sec\n",
        "\n",
        "**Sieve of Sundaram:** 0.2920 sec\n",
        "\n",
        "\n",
        "Furthermore, from looking at the plots, we plotted the same intervals for both algorithms. The sieve of Eratosthenes' max time is around 0.045 seconds while Sundaram's max time is over 30 seconds."
      ],
      "metadata": {
        "id": "hqiro95LX4pM"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "# **Part 2: Investigate the following conjectures about primes.**\n",
        "For each, either provide computational evidence in support of the conjecture, or find a counterexample showing that the conjecture is false.\n",
        "\n",
        "**Conjecture A.** Every even integer greater than 2 is the sum of two primes.\n",
        "\n",
        "**Conjecture C.** For every positive integer n, there exists at least one prime between $n^2$ and $(n + 1)^2$\n",
        "\n",
        "**Conjecture D**. All odd numbers greater than 1 are either prime, or can be expressed as the sum of a prime and twice a square."
      ],
      "metadata": {
        "id": "CLVAV-eeT92j"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Set up some lists for Part 2"
      ],
      "metadata": {
        "id": "U-NPlImJQp08"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### **isPrime** function"
      ],
      "metadata": {
        "id": "wpD2is1sOTFB"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def isPrime(n):   # test: isPrime(13)\n",
        "  if n < 2:\n",
        "    return False\n",
        "  \n",
        "  # compute the largest integer less than or equal to the square root of n\n",
        "  rootn = math.floor(math.sqrt(n))\n",
        "\n",
        "  # check for divisors of n\n",
        "  for i in range(2, rootn+1):\n",
        "    if n % i == 0:\n",
        "      # if i divides n, then n is not prime\n",
        "      return False\n",
        "  \n",
        "  return True\n",
        "\n"
      ],
      "metadata": {
        "id": "OhNGZgXEOTFC"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "### **isOdd** and **oddsList** and faster odd"
      ],
      "metadata": {
        "id": "BIR0F0-nOekx"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def isOdd(n): # test using : isOdd(50)\n",
        "\n",
        "  #while n > 1:\n",
        "    if n % 2 == 0:\n",
        "      return False\n",
        "    else:\n",
        "      return True"
      ],
      "metadata": {
        "id": "aaLtKKjwOekz"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "OddsList = list(range(1,20, 2))"
      ],
      "metadata": {
        "id": "gpa2lSsfOek_"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "### **isEven** and evenList"
      ],
      "metadata": {
        "id": "uRyNjFTWNvqE"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def isEven(n): \n",
        "\n",
        "  while n > 2: # specificed: even integers greater than 2\n",
        "    if n % 2 == 0:\n",
        "      return True\n",
        "    else:\n",
        "      return False"
      ],
      "metadata": {
        "id": "hU7EhH1Wb0re"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "evenList= list(range(2,1000,2))\n",
        "# %time evens2 = list(range(2,1000,2))"
      ],
      "metadata": {
        "id": "63EIaEZhNcyn"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "## **Conjecture A.** Every even integer greater than 2 is the sum of two primes"
      ],
      "metadata": {
        "id": "YFmcjfX4bkIb"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Basic Plan for Conjecture A function:\n",
        "\n",
        "**-input:** integers up to *evenMax*\n",
        "\n",
        "**-iterate:** over list of even numbers, \n",
        "\n",
        "for each even number: \n",
        "\n",
        "**-Set** :\n",
        " - num = evenNums [ i ]\n",
        " - firstPrime = primeList [ p ]\n",
        " - diff = *num*  - *firstPrime*,\n",
        "\n",
        "**-Test** if remainder is in primeList\n",
        "\n",
        "- if yes, **Trues += 1**, **move on** to the next even integer\n",
        "\n",
        "**Output:** Trues:123"
      ],
      "metadata": {
        "id": "BdK-XFyHnC1C"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Function with print statements"
      ],
      "metadata": {
        "id": "w5evus-VHpQi"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Sometimes when you can't go through all the nested loops very clearly in your head, it's useful to have a function that simply have a bunch of print statements. This will help make sure that the steps are functioning properly (as it should) for each step."
      ],
      "metadata": {
        "id": "B9oCQbR5i75s"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def printIterateEven(evenMax):\n",
        "\n",
        "  primeList = fastEratos(500000)\n",
        "  evenNums = list(range(4, evenMax + 1,2)) # start loop at 4 so even numbers > 2\n",
        "  Trues = 0\n",
        "\n",
        "  i = 0\n",
        "  for i in range(len(evenNums)): \n",
        "    number = evenNums[i]    \n",
        "    \n",
        "    for p in range(len(primeList)):\n",
        "      \n",
        "      print(\"( prime:\",primeList[p],\", index:\",p,\")\" ) # print out the prime and its index\n",
        "      \n",
        "      if primeList[p] <= number // 2 :\n",
        "          \n",
        "        firstPrime = primeList[p]\n",
        "        diff = number - firstPrime\n",
        "                  \n",
        "        if diff in primeList :            \n",
        "          Trues += 1\n",
        "          print(\"[even number:\", number,\", 1st Prime:\",firstPrime, \", 2nd Prime:\", diff, \"]\") # print out integer, the prime, and its index\n",
        "          break\n",
        "                 \n",
        "  print(\"True count:\", Trues)"
      ],
      "metadata": {
        "id": "Z4uTIa4Lm9jV"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "printIterateEven(10)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "7xzE2iZXjgQy",
        "outputId": "aea33afd-0a8b-45a2-b477-ce5484f396be"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "( prime: 2 , index: 0 )\n",
            "[even number: 4 , 1st Prime: 2 , 2nd Prime: 2 ]\n",
            "( prime: 2 , index: 0 )\n",
            "( prime: 3 , index: 1 )\n",
            "[even number: 6 , 1st Prime: 3 , 2nd Prime: 3 ]\n",
            "( prime: 2 , index: 0 )\n",
            "( prime: 3 , index: 1 )\n",
            "[even number: 8 , 1st Prime: 3 , 2nd Prime: 5 ]\n",
            "( prime: 2 , index: 0 )\n",
            "( prime: 3 , index: 1 )\n",
            "[even number: 10 , 1st Prime: 3 , 2nd Prime: 7 ]\n",
            "True count: 4\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Now we can make that into our main function!"
      ],
      "metadata": {
        "id": "VoE3VzozHfxI"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def iterateEven(evenMax):\n",
        "\n",
        "  primeList = fastEratos(500000)\n",
        "  evenNums = list(range(4, evenMax + 1,2)) \n",
        "  Trues = 0\n",
        "\n",
        "  i = 0\n",
        "  for i in range(len(evenNums)): \n",
        "    number = evenNums[i]\n",
        "       \n",
        "    for p in range(len(primeList)):\n",
        "           \n",
        "      if primeList[p] <= number // 2 :\n",
        "          \n",
        "        firstPrime = primeList[p]\n",
        "        diff = number - firstPrime\n",
        "                  \n",
        "        if diff in primeList :            \n",
        "          Trues += 1\n",
        "          break\n",
        "                 \n",
        "  return Trues"
      ],
      "metadata": {
        "id": "-exPTMX3jcRz"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "iterateEven(10000)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "q0Yip6wMCpzP",
        "outputId": "9eba37f3-2a33-43b9-fd73-cca6d39dc888"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "4999"
            ]
          },
          "metadata": {},
          "execution_count": 219
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### **It seems our computational evidence is in support of Conjecture A!**\n",
        "\n",
        "We tested up to 10000 integers, which includes 5000 even integers, but we have to subtract by one for excluding the number 2. We should expect 4999 true counts for the conjecture to hold and we did!"
      ],
      "metadata": {
        "id": "wXFpNzcVFyBb"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## **Conjecture C.** For every positive integer n, there exists at least one prime between $n^2$ and $(n + 1)^2$"
      ],
      "metadata": {
        "id": "_ix-kEUQaoYh"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Basic Plan for Conjecture C function:\n",
        "\n",
        "**-input:** numRange (positive integers), nMax  (list of primes)\n",
        "\n",
        "**-iterate:** over list of positive integers, \n",
        "\n",
        "for every integer in nums\n",
        "for every prime in primeList\n",
        "\n",
        "**-Set** :\n",
        " - interval = ($n^2$ and $(n + 1)^2$)\n",
        " \n",
        "\n",
        "**-Test** if a prime number is found in the interval\n",
        "\n",
        "- if yes, **Trues += 1**, **break** from the loop since we only need at least one prime in the interval\n",
        "- if not, **Falses += 1**\n",
        "\n",
        "**Output:** Trues:000, Falses: 000"
      ],
      "metadata": {
        "id": "0rN446xvJ1UP"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "I started building the function by writing a couple of more simple functions to better understand how each part works so I know where my parameters are at all times when we get to the main function."
      ],
      "metadata": {
        "id": "zcwwv7TZJawm"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### **First**: we write a function that takes an integer n and find if a prime number exists in the interval ($n^2$ and $(n + 1)^2$). If a prime is found, print out the first one that is found. If not, function returns false"
      ],
      "metadata": {
        "id": "LY9tfQ8WIKwQ"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def returnPrime(n, nMax):\n",
        "\n",
        "  primeList = fastEratos(nMax)\n",
        "  interval = range(n**2, (n+1)**2)   \n",
        "  \n",
        "  for i in range(len(primeList)):\n",
        "    i += 1\n",
        "    if primeList[i] in interval:\n",
        "      print(\"found prime:\", primeList[i])\n",
        "      break # since we only need at least 1, report the first prime found and exit the loop\n",
        "  else:\n",
        "    return False"
      ],
      "metadata": {
        "id": "TtFaAr7YXdqt"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "returnPrime(500,2500000)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "xZW42RU0W3fr",
        "outputId": "a6cc7679-3103-45af-eb9b-e29402d74eb2"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "found prime: 250007\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### **2nd**: simply switch out the print statement to \"return True\""
      ],
      "metadata": {
        "id": "yw1vtEOIJDzq"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def testInterval(n, nMax):\n",
        "\n",
        "  primeList = fastEratos(nMax)\n",
        "  interval = range(n**2, (n+1)**2)   \n",
        "  \n",
        "  for i in range(len(primeList)):\n",
        "    i += 1\n",
        "    if primeList[i] in interval:\n",
        "      return True\n",
        "      break \n",
        "  else:\n",
        "    return False\n"
      ],
      "metadata": {
        "id": "ECCknbT-53Of"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "testInterval(200,300000)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "r1P7rVxR7ENv",
        "outputId": "62af76cc-b6b5-439f-a30e-bbdb176b655b"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "True"
            ]
          },
          "metadata": {},
          "execution_count": 24
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### **Final version -**\n",
        "\n",
        " write a function that takes the number of integers n to test the conjectrue (numRange), and a big list of prime numbers to search from (nMax). The function will return the number of n's where at least one prime is found and number of n's where no prime is found. If the function returns a false, the conjecture would be false. However, my function doesn't return the integer that is the counterexample"
      ],
      "metadata": {
        "id": "D8tpgaw2M-bM"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def countTrues(numRange, nMax):\n",
        "   \n",
        "  primeList = fastEratos(nMax)\n",
        "  nums = range(1, numRange)   \n",
        "  Trues = 0\n",
        "  Falses = 0\n",
        "  \n",
        "  for n in range(len(nums)): # for every integer in nums\n",
        "    \n",
        "    n += 1\n",
        "    interval = range(n**2, (n+1)**2)\n",
        "\n",
        "    for i in range(len(primeList)):\n",
        "      i += 1\n",
        "      if primeList[i] in interval: # if a prime number is found in the interval\n",
        "        Trues += 1     # add one to Trues\n",
        "        break          # since we only need to prove at at least one prime exists, go to the next n\n",
        "  \n",
        "    else:\n",
        "      Falses += 1 # if no prime numbers found, add one to Falses\n",
        "    \n",
        "  return Trues, Falses"
      ],
      "metadata": {
        "id": "cuFRh2KX7aGU"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "countTrues(1000,100000000)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "CR-rkwV9A2kn",
        "outputId": "7b27c114-2144-4397-a91d-4cce49917036"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(999, 0)"
            ]
          },
          "metadata": {},
          "execution_count": 26
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### **Computational evidence is in support of Conjecture C!**\n",
        "\n",
        "We tested 999 integers (1000 excluding zero) and for each n, there is at least one prime found (I tried to increase the number of integer's to test, but even with 5000 integers the session would crash).\n",
        "\n",
        "\n"
      ],
      "metadata": {
        "id": "YEYDSz9KwXAx"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## **Conjecture D**. All odd numbers greater than 1 are either prime, or can be expressed as the sum of a prime and twice a square."
      ],
      "metadata": {
        "id": "qJPla2WfbIMw"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Basic Plan for Conjecture D function:\n",
        "\n",
        "**-input:** nMax  (Odd integers up to nMax)\n",
        "\n",
        "**-iterate over:** non-prime odd integers, numbers that are \"twice a square\"\n",
        "\n",
        "for every non-prime odd integers\n",
        "for every twice a Square\n",
        "\n",
        "**- if twice a square < odd integer:** (we don't want negative remainders)\n",
        "\n",
        "**-Set** :\n",
        " - num = oddNotPrimes [ i ]\n",
        " - twiceSq = twiceSqs [ j ]\n",
        " - diff =  num - twiceSq\n",
        " \n",
        "**-Test:** if diff is in primeList\n",
        "\n",
        "- if yes, **found += 1**, **break**\n",
        "- if not, **notFound += 1**, print out the number that is now a counterexample\n",
        "\n",
        "**Output:** counterexample found: 0000,  (True count,  False count)\n"
      ],
      "metadata": {
        "id": "bkAKDSP4L_XV"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "This conjecture has many components. We already have functions that generate lists of primes & odd numbers, and whether or not a number if prime or odd. Now, let's write a function that determines whether an interger is **\"twice a square\"** and generate a list from that"
      ],
      "metadata": {
        "id": "PquEI3RRGCpj"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### **isTwiceSq(n)** and twiceSqList"
      ],
      "metadata": {
        "id": "dx4jCk-nwkxx"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def isTwiceSq(n):\n",
        " \n",
        "  square = n /2\n",
        "  root = math.sqrt(square)\n",
        "  \n",
        "  if root % 1 == 0:\n",
        "    return True\n",
        "  else:\n",
        "    return False\n",
        "\n",
        "def twiceSqList(nMax): \n",
        "  \n",
        "  twiceSqList = []\n",
        "\n",
        "  for n in range(1, nMax + 1): # start at 2 since all is greater than 1\n",
        "      if isTwiceSq(n):\n",
        "        twiceSqList.append(n)\n",
        "  \n",
        "  return twiceSqList"
      ],
      "metadata": {
        "id": "8caiiYvxpA-L"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "twiceSqList(200)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "7L7y5CwI25bU",
        "outputId": "de5ac766-9074-40a2-b2fb-a81493d924a4"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[2, 8, 18, 32, 50, 72, 98, 128, 162, 200]"
            ]
          },
          "metadata": {},
          "execution_count": 30
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Now, the conjecture states that all odd numbers greater than 1 are either prime, or can be expressed as the sum of a prime and twice a square. We can easily eliminate the odd numbers that are also prime and focus on the ones that must have an expression as sum of a prime and twice a square for the conjecture to hold."
      ],
      "metadata": {
        "id": "ILRVDCMPHQpL"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### **OddNotPrime**"
      ],
      "metadata": {
        "id": "JZ3XO-RnErwu"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def oddNotPrime(nMax):\n",
        "\n",
        "  oddsList = list(range(3, nMax, 2))\n",
        "  primeList = fastEratos(10000) \n",
        "  oddNotPrimes = []\n",
        "\n",
        "  for i in range(len(oddsList)):\n",
        "    odd = oddsList[i] \n",
        "    i += 1\n",
        "    if isPrime(odd) == False:\n",
        "      oddNotPrimes.append(odd)\n",
        "\n",
        "  return oddNotPrimes"
      ],
      "metadata": {
        "id": "v5Du2RNnqIYz"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "oddNotPrime(50)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "eI25EU2ZrTYP",
        "outputId": "29209d15-e369-4bf3-a608-88341da4574b"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[9, 15, 21, 25, 27, 33, 35, 39, 45, 49]"
            ]
          },
          "metadata": {},
          "execution_count": 223
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### **main function**"
      ],
      "metadata": {
        "id": "HisnDdHLEwxc"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def twiceSquarePrime(nMax):\n",
        "\n",
        "  oddNotPrimes = oddNotPrime(nMax)\n",
        "  twiceSqs = twiceSqList(100000) # set it manually so there won't be 3 different user input max values\n",
        "  primeList = fastEratos(100000) # also set manually\n",
        "  found = 0\n",
        "  notFound = 0\n",
        "\n",
        "  for i in range(len(oddNotPrimes)):\n",
        "    num = oddNotPrimes[i]\n",
        "                  \n",
        "    for j in range(len(twiceSqs)): \n",
        "      twiceSq = twiceSqs[j]\n",
        "      \n",
        "      if twiceSq < num:\n",
        "      \n",
        "        twiceSq = twiceSqs[j]\n",
        "        diff =  num - twiceSq\n",
        "\n",
        "        if diff in primeList:     \n",
        "          found += 1      \n",
        "          break                        \n",
        "        \n",
        "      else:\n",
        "        notFound += 1\n",
        "        print(\"counterexample found:\", num)\n",
        "        break\n",
        "     \n",
        "                \n",
        "  return found, notFound"
      ],
      "metadata": {
        "id": "BAyaWvHwjNkA"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "twiceSquarePrime(10000)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "qYtsaHhOoDtR",
        "outputId": "7de3fb33-c23a-4b26-f3d7-6d73d749abf8"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "counterexample found: 5777\n",
            "counterexample found: 5993\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(3769, 2)"
            ]
          },
          "metadata": {},
          "execution_count": 225
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### According to the algorithm, there are in fact **2 counterexamples: 5777 and 5993** that shows that the **conjecture is false!**"
      ],
      "metadata": {
        "id": "Sb0YolhyPJmh"
      }
    }
  ]
}