Primes_Proj.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Primes Proj.ipynb",
      "provenance": [],
      "collapsed_sections": [
        "1mv5AxfNh9AO",
        "UnfbNa3B29ML",
        "gpSrT21bcI0V",
        "R3FiQxp1wryT",
        "dx4jCk-nwkxx",
        "Y2bjoQN3waJw"
      ],
      "authorship_tag": "ABX9TyO6cRau1XnajR41J8TtTByf",
      "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/Primes_Proj.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",
        "**Due: Friday, April 22**\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"
      ],
      "metadata": {
        "id": "TozcFxZshHUx"
      },
      "execution_count": 156,
      "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": "code",
      "source": [
        "def fastEratos(nMax):\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": 66,
      "outputs": []
    },
    {
      "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",
        "  #print(\"runtime:\", endTime - startTime)\n",
        "  return endTime - startTime"
      ],
      "metadata": {
        "id": "MR-JhstNjHHD"
      },
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "timeEratos(1000)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "If22CYQOjs0x",
        "outputId": "afc11525-de98-44ba-bc64-7b4eea4570f1"
      },
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "0.0006604194641113281"
            ]
          },
          "metadata": {},
          "execution_count": 7
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Another way to measure the runtime for computing the primes up to n, for various n."
      ],
      "metadata": {
        "id": "v8ycDYEqkRXW"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "%time primes = fastEratos(100)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "aoYKh755j3Ud",
        "outputId": "3271f884-a56f-4b1d-9447-b582de0481f9"
      },
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "CPU times: user 61 µs, sys: 4 µs, total: 65 µs\n",
            "Wall time: 68.2 µs\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "%time primes = fastEratos(10000)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "0plmWTWAj4xG",
        "outputId": "b1616f35-72d0-41fe-f5e3-374417d1964c"
      },
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "CPU times: user 5.33 ms, sys: 0 ns, total: 5.33 ms\n",
            "Wall time: 5.53 ms\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "%time primes = fastEratos(1000000)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "rp-yXZ_Gjb5u",
        "outputId": "a94a7270-e800-4e99-ab07-596c69c926f5"
      },
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "CPU times: user 581 ms, sys: 10.8 ms, total: 592 ms\n",
            "Wall time: 597 ms\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "%time primes = fastEratos(10000000)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "eZ99yrkAj7Pe",
        "outputId": "7f876dcb-a05c-4ea3-fa67-317f1562cf93"
      },
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "CPU times: user 7.04 s, sys: 240 ms, total: 7.28 s\n",
            "Wall time: 7.37 s\n"
          ]
        }
      ]
    },
    {
      "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": [
        "nMaxVals = range(10000,200000,10000)\n",
        "runtimes = [timeEratos(n) for n in nMaxVals]  # list comprehension -- makes a list of runtime values\n",
        "#print(runtimes)"
      ],
      "metadata": {
        "id": "BszIFPEUbnwY"
      },
      "execution_count": 19,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "It would be much nicer to plot these 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(nMaxVals, runtimes, 'go') # creates the plot; syntax is plot(xvals, yvals, format)\n",
        "plt.title(\"Sieve of Eratosthenes runtimes (first attempt)\")\n",
        "plt.xlabel(\"nMax\")\n",
        "plt.ylabel(\"time (seconds)\");"
      ],
      "metadata": {
        "id": "Vped8LXyb7-w",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 295
        },
        "outputId": "7085270f-ea51-44f2-c420-b3558295d3bc"
      },
      "execution_count": 20,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ],
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYgAAAEWCAYAAAB8LwAVAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAgAElEQVR4nO3de7xcZX3v8c+XBAJB2NyixYTszVUN4kEIF4+oaASBGqIWJJhWQGqKLUc5ai0ajyIaCrVFtHCKG8EihJtUaBDagFBqDwpNQCCEi2xiQhK5hFsCBIHI7/zxPIOTyZrZM3vP7Jm99/f9es1rzzzrMr+19pr5zbPWep5HEYGZmVmlTdodgJmZdSYnCDMzK+QEYWZmhZwgzMyskBOEmZkVcoIwM7NCThAtJGmWpBvbHUc5Se+W9LCkFyR9pN3xDIakWyX9ebvjaCdJX5H0gw6I4y8knVP2+qOSVuTj7J2Slkg6uI0hdixJ4yQ9KGlCu2Op5AQxSJIOkvQLSWskPSPpNkn7AUTEvIg4tN0xVjgdODci3hAR11ZOlLRM0kv5g116nDvQN8vr++CgIk7rOU3SpYNdz3Am6WBJK8vLIuKMiGhrkpS0GfBV4NtlxX8PnJyPs19FxJ4RcesA1t0jKSSNHUR8IWm3stcb7cehVPnDJiJeBi4CTm1XTNUMeKcbSNoa+CnwGeAqYDPgPcDL7YyrH93Akn7mmR4RP+tvRZLGRsT65oQ18o3g/TUDeDAiVpWV1XOcASN6vzTiMuBuSV/JCaMzRIQfA3wAU4Hnakw/Hvh/Za/fCtwEPAM8BHw8lx8APA6MKZv3o8C9+fkmpF8XjwBPk5LRdjXe99NAX36f+cCbc/kjwGvAS8ALwLiCZZcBH6yxPbcB38lxfAvYFbglv34KmAdsk+e/pOL9vpTLjyR9eTwH3Aq8rew9/gZYBTyf99E04DDgFeDVvJ578ry3At/MMT0P3AjsULauA4Ff5Pe5Bzi4bNpglj0eWJqX+w0wq8r+Og24GrgUWAv8OfDPwLfK5jkYWFmx/78I3AusAa4ENge2zPvxtbwPXgDenN/j0rxsDxDACcAK4FngJGC/vL7nSLXH8hg/BTyQ510AdOdy5f/zkzn2xcDbq2znRcBX8/NxObYAXgQeqTyuquyX/YFF+fUTwNl53kfzukrb/K6C998f+GXevseAc4HN8rSfl8XyAnBclf1Y9TPW6H7lD5+Tc/P/8EFgWp42F/g98Lv83uXLPQy8r93faxvs23YHMJwfwNb5YLoYOBzYtmL68eQEQfqAr8gH2VjgnaQv1Cl5+iPAIWXL/hg4NT//HHA7MCl/AL8PXF4lpg/k9e6T5/1H4Odl01//oFZZvur0vD3rgf+Vt2ELYDfgkPxeE/IH8pxq6wP2yB/WQ4BNgS+RktlmwFvyPioltB5g1/z8NPIXYdm6bs37bY8cy63AmXnaxPy/OYL04T8kv54wmGXz/3Et8JY8747AnlX212mkpPaRvJ4tqC9B/DfpS2s70pf3SUXzVu4X/vBFdj4pqRxK+iK6Fnhj3q4nyV9CpF/+fcDb8v/zq8Av8rQPAXcC25CSxduAHats50Lg6IqyAHYrOg6q7JdfAn+Wp78BOLBim8bWOGb3JSX0sXn+B4BTasRStB+rfsYGsF+PJ31O/jfpGD+GlChKCedW4M8LtmM+8Nl2f6+VP3wNYhAiYi1wEOnguQBYLWm+pDcVzP5hYFlE/DAi1kfEr4B/AY7O0y8HjgWQtBXpy+nyPO0kYE5ErIxU/TwNOKrKedlZwEURcVee98vAuyT1NLBp10p6ruzx6bJpv42If8zb8FJE9EXETRHxckSsBs4G3ldj3ccA1+dlXiWdq94C+J+kX1bjgCmSNo2IZRHxSD+x/jAifh0RL5F+9e2dy/8UuCEiboiI1yLiJtIv1COasOxrwNslbRERj0VErVMpv4yIa/N6XupnW0q+FxG/jYhngOvK4qrXNyPidxFxIykZXx4RT0Y6BfRfpB8nkI6rv42IByKd4jkD2FtSN+kLfCtSrVd5nseqvN82pNpUIyr3y6vAbpJ2iIgXIuL2elcUEXdGxO35mFxG+nKvdQwWqeczVu9+hZQwzomIVyPiSlJt+I/7ieF50r7sGE4Qg5Q/OMdHxCTg7aRffucUzNoNHFD+xUv6Mv+jPP0y4GOSxgEfA+6KiOVly15TttwDpC/TokT0ZqC0HBHxAunX78QGNusjEbFN2eOCsmkrymeU9CZJV0haJWkt6bTBDjXWXRnfa3mdEyOiDziF9OF8Mq/3zf3E+njZ83WkX5+Q9tnRFfv7INIv/gEvGxEvkpLcScBjkq6X9NYa8a2oMa3RbarXE2XPXyp4Xb6d3y3bxmdItYWJEXEL6RTJeaT/RW++5lbkWVIyaUTlfjmRVJt7UNJCSR+ud0WS9pD0U0mP52PwDGofg0Xq+YzVu18BVkWuFmTLScd+LVuRTld1DCeIJoqIB0mnEN5eMHkF8J8VX7xviIjP5GXvJx1EhwOfICWM8mUPr1h289jwomDJb0kHOwCStgS2J53Xb4bK7n/PyGV7RcTWpF/fqjF/ZXwCdirFFxGXRcRBeZ4Azqqynv6sAC6p2GdbRsSZg102IhZExCGkZPMgqfZYTWXcLwLjy17/EfVrdtfLK4C/qNjOLSLiFwAR8b2I2BeYQvry/usq67k3T2/EBtsSEQ9HxLGkUzZnAVfnY7eebf4n0v9h93wMfoUNj8Ga75018hmrx8R8bJdMJh371d4f0mm8ewb4fi3hBDEIkt4q6QuSJuXXO5FOExVVj38K7CHpzyRtmh/7SXpb2TyXkc6Fvpd0DaLkfGBurvojaYKkGVXCuhw4QdLeuTZyBnBHrnq3wlaki21rJE1k4y+RJ4Bdyl5fBfyxpGmSNgW+QLrr6xeS3iLpAznu3/GHi4ml9fRIqveYvRSYLulDksZI2jzf3jhpMMvmGtOM/OX1ct7212qvbgN3A0dI2k7SH5FqTPV6AtheUlcDy9RyPvBlSXsCSOqSdHR+vp+kA/L/6EXS/6Padt5A46d0NiDpTyVNyDXK0q/o14DV+e8uVRdOx+Ba4IVcm/tMxfTKY7BoPzbyGavHG4HP5s/50aQv/xuqxEP+7GxH8XdH2zhBDM7zpDuQ7pD0Iumfex/pS28DEfE86eLWTNIvicdJv5TGlc12OemDdktEPFVW/l3SBawbJT2f3+eAooAi3Z76f0jXNx4j3WU0s8Htuk4btoO4psa83yBdEF8DXA/8pGL63wJfzVX3L0bEQ6Raxj+SLqZPJ91W+wppX5yZyx8nfci+nNdTSphPS7qrvw2IiBWki7BfIX3JrCAlr36P+X6W3QT4POl/+Azp/1X5hVTLJaRfictId05dWe+CuYZ6ObA078/+Tln0t75rSMfgFfnUzH2kGiykGzAuIJ0+Wk46TfntovWQrpO8dZDxHAYskfQC6Xifma9xrSPd+XNb3uYDC5b9IqnW/XyOuXKfngZcnJf/eJX9WPdnrE53ALuTjuW5wFER8XSe9l3S9Y1nJX0vl30CuDg66RZX0sWndsdgZsOcpNmkO/IaqRGNSJKOJ92ldFCd848j/Wh4b0Q82crYGuWGcmY2aBHR2+4Yhqtca6h1o0Pb+BSTmZkV8ikmMzMr5BqEmZkVGjHXIHbYYYfo6elpdxhmZsPKnXfe+VREFHY1PmISRE9PD4sWLWp3GGZmw4qk5dWm+RSTmZkVammCkHSYpIck9UnaaDAMSe+VdJek9ZKOKivfW9IvlUahulfSMa2M08zMNtayBCFpDKmjr8NJfbkcK2lKxWyPkrrGvayifB3wyYjYk9TC8hxJHdXLoZnZSNfKaxD7A30RsRRA0hWk7gvuL81Q6h9I0gZ9vETEr8ue/1bSk6S++Duqp0Mzs5GslaeYJrJhl74raazLaQAk7U8aTGajcQEkzZa0SNKi1atXDzhQMzPbWEdfpJa0I6lzsxNyL48biIjeiJgaEVMnTCi8S8vMrCPNWzyPnnN62OQbm9BzTg/zFs9rd0gbaeUpplWkfv5LJtHAmAR5cJLrSaM8dVQXuGZmgzFv8TxmXzebda+uA2D5muXMvm42ALP2mtXO0DbQyhrEQmB3STtL2ozU5fT8ehbM818D/Cgirm5hjGZmQ27OzXNeTw4l615dx5yb57QpomItSxB5jNuTgQWk4fuuioglkk6XdCS8PijJStK4zN+XVBrb9+OkQXOOl3R3fjQ6Lq+ZWUd6dM2jDZW3S0tbUkfEDfxhFKVS2dfKni8knXqqXO5S0qheZmYjzuSuySxfs3ED5sldk9sQTXUdfZHazGwkmjttLuM3Hb9B2fhNxzN32tw2RVTMCcLMbIjN2msWvdN76e7qRojurm56p/d21AVqGEHjQUydOjXcWZ+ZWWMk3RkRU4umuQZhZmaFnCDMzKyQE4SZmRVygjAzs0JOEGZmVsgJwszMCjlBmJlZIScIMzMr5ARhZjZMtXpMiZZ21mdmZq0xFGNKuAZhZjYMDcWYEk4QZmbD0FCMKeEEYWY2DFUbO6KZY0o4QZiZDUNDMaaEE4SZ2TA0FGNKeDwIM7NRzONBmJlZw5wgzMyskBOEmZkVcoIwM7NCThBmZlbICcLMzAo5QZiZWSEnCDMzK9TSBCHpMEkPSeqTdGrB9PdKukvSeklHVUw7TtLD+XFcK+M0M7ONtSxBSBoDnAccDkwBjpU0pWK2R4Hjgcsqlt0O+DpwALA/8HVJ27YqVjMz21graxD7A30RsTQiXgGuAGaUzxARyyLiXuC1imU/BNwUEc9ExLPATcBhLYzVzMwqtDJBTARWlL1emcuatqyk2ZIWSVq0evXqAQdqZmYbG9YXqSOiNyKmRsTUCRMmtDscM7MRpZUJYhWwU9nrSbms1cuamVkTtDJBLAR2l7SzpM2AmcD8OpddABwqadt8cfrQXGZmZkOkZQkiItYDJ5O+2B8AroqIJZJOl3QkgKT9JK0Ejga+L2lJXvYZ4JukJLMQOD2XmZnZEPGAQWZmo5gHDDIzs4Y5QZiZNWje4nn0nNPDJt/YhJ5zepi3eF67Q2qJse0OwMxsOJm3eB6zr5vNulfXAbB8zXJmXzcbgFl7zWpnaE3nGoSZWQPm3Dzn9eRQsu7Vdcy5eU6bImodJwgzswY8uubRhsqHMycIM7MGTO6a3FD5cOYEYWbWgLnT5jJ+0/EblI3fdDxzp81tU0St4wRhZtaAWXvNond6L91d3QjR3dVN7/TeEXeBGtxQzsxsVHNDOTMza5gThJmZFXKCMDOzQk4QZmZWyAnCzMwKOUGYmVkhJwgzMyvkBGFmw8Zo6Wa7U7i7bzMbFkZTN9udwjUIMxsWRlM3253CCcLMhoVmdbPt01T1c4Iws2GhGd1sl05TLV+znCBeP03lJFHMCcLMhoVmdLPt01SNcYIws2GhGd1sj6bR4JrBdzGZ2bAxa69Zg7pjaXLXZJavWV5YbhtzDcLMRo3RNBpcMzhBmNmoMZpGg2uGukaUk/RG4N3Am4GXgPuARRHxWmvDq59HlDMza9yAR5ST9H5JC4DrgcOBHYEpwFeBxZK+IWnrGssfJukhSX2STi2YPk7SlXn6HZJ6cvmmki6WtFjSA5K+XO/GmplZc/R3kfoI4NMRsdElfkljgQ8DhwD/UjB9DHBenr4SWChpfkTcXzbbicCzEbGbpJnAWcAxwNHAuIjYS9J44H5Jl0fEsoa30MzMBqRmgoiIv64xbT1wbY3F9wf6ImIpgKQrgBlAeYKYAZyWn18NnCtJQABb5iS0BfAKsLbmlpiZWVPVdZFa0uckba3kQkl3STq0n8UmAivKXq/MZYXz5ISzBtielCxeBB4DHgX+PiKeKYhrtqRFkhatXr26nk0xM7M61XsX06ciYi1wKLAt8GfAmS2LKtU+fk+6KL4z8AVJu1TOFBG9ETE1IqZOmDChheGYmY0+9SYI5b9HAJdExJKysmpWATuVvZ6UywrnyaeTuoCngU8A/x4Rr0bEk8BtQOFVdjMza416E8Sdkm4kJYgFkrYC+rvFdSGwu6SdJW0GzATmV8wzHzguPz8KuCXSfbePAh8AkLQlcCDwYJ2xmplZE9Tb1caJwN7A0ohYJ2l74IRaC0TEekknAwuAMcBFEbFE0umkNhTzgQuBSyT1Ac+Qkgiku59+KKlUU/lhRNzb6MaZmdnA1WwoJ2mfWgtHxF1Nj2iA3FDOzKxxtRrK9VeD+If8d3NgX+Be0i/6dwCLgHc1K0gzM+ssNa9BRMT7I+L9pNtN9813DO0LvJONLzibmdkIUu9F6rdExOLSi4i4D3hba0Iys5HIQ30OP/VepL5X0g+AS/PrWaTTTWZm/SoN9Vkaza001CfgnlQ7WL01iBOAJcDn8uN++rmLycysxEN9Dk911SAi4nfAd/LDzKwhHupzeKq3L6Z3S7pJ0q8lLS09Wh2cmY0M1Yb09FCfna3eU0wXAmcDBwH7lT3MzPrloT6Hp3ovUq+JiH9raSRmNmKVLkTPuXkOj655lMldk5k7ba4vUHe4eoccPZPUXcZPgJdL5W5JbWY2vA2mJXXJAflv+UqC3KGemZmNPPXexfT+VgdiZmadpd67mLoknV0avU3SP0jqanVwZmbWPvXexXQR8Dzw8fxYC/ywVUGZmVn71Zsgdo2Ir0fE0vz4BrDREKBmNnK5L6XRp94E8ZKkg0ovJL0beKk1IZlZpyn1pbR8zXKCeL0vJSeJka3eBPEZ4DxJyyQtA84FTmpZVGbWUdyX0uhUV4KIiLsj4n+QBgp6R0S8MyLuaW1oZtYsgz095L6URqd672I6Q9I2EbE2ItZK2lbSt1odnJkNXjNOD7kvpdGp3lNMh0fEc6UXEfEscERrQjKzZmrG6SH3pTQ61ZsgxkgaV3ohaQtgXI35zaxDNOP00Ky9ZtE7vZfurm6E6O7qpnd6r/tSGuHq7WpjHnCzpFLbhxOAi1sTkpk10+SuySxfs7ywvBGz9prlhDDK1HuR+izgW6RxqN8GfDMi/q6VgZlZc/j0kA1UvTUIgAeA9RHxM0njJW0VEc+3KjAzaw53tW0DVW93358GZgPbRcSuknYHzo+Iaa0OsF7u7tvMrHG1uvuu9yL1XwHvJvXBREQ8DLyxOeGZmVknqjdBvBwRr5ReSBpLGg/CzMxGqHoTxH9K+gqwhaRDgB8D1/W3kKTDJD0kqU/SqQXTx0m6Mk+/Q1JP2bR3SPqlpCWSFkvavM5YzcysCepNEKcCq4HFwF8ANwBfrbWApDHAecDhwBTgWElTKmY7EXg2InYDvgOclZcdC1wKnBQRewIHA6/WGatZx3APqDac1Tui3GvABcAFkrYDJkX/V7f3B/oiYimApCuAGcD9ZfPMAE7Lz68GzpUk4FDg3lJ/TxHxdH2bY9Y5Sl1clFoxl7q4AHwHkQ0L9fbFdKukrXNyuJOUKL7Tz2ITgRVlr1fmssJ5ImI9sAbYHtgDCEkLJN0l6UtV4ppdGuVu9erV9WyK2ZBxD6g23NV7iqkrItYCHwN+FBEHAK28xXUscBAwK//9qKSN3i8ieiNiakRMnTBhQgvDMWtcs3pA9Wkqa5d6E8RYSTuShhv9aZ3LrAJ2Kns9KZcVzpOvO3QBT5NqGz+PiKciYh3pmsc+db6vWUdoRg+oHqjH2qneBHE6sIB0TWGhpF2Ah/tZZiGwu6SdJW0GzATmV8wzHzguPz8KuCVf21gA7JVbbI8F3seG1y7MOl4zurjwaSprp3ovUv+YdGtr6fVS4E/6WWa9pJNJX/ZjgIsiYomk04FFETEfuBC4RFIf8AwpiRARz0o6m5RkArghIq5veOvM2qgZXVx4oB5rp5pdbUj6KvB/I+KZKtM/AIyPiHpPO7WMu9qwkajnnJ7Cnli7u7pZdsqyoQ/IRpxaXW30V4NYDFwn6XfAXaS2EJsDuwN7Az8DzmhirGZWZu60uRvcKgvuidWGTs0EERH/Cvxr7pzv3cCOpP6YLgVmR8RLrQ/RbPRyT6zWTnX15joc+BSTmVnjmtGbq5mZjTJOEGZmVsgJwszMCtXbF9Mekm6WdF9+/Y58C6yZmY1Q9dYgLgC+TO5yOyLuJTdqMzOzkaneBDE+Iv67omx9s4MxM7POUW+CeErSruRhRiUdBTzWsqjMzKzt6uqLCfgroBd4q6RVwG+AP21ZVGZm1nb1dta3FPigpC2BTSLi+daGZWZm7VZXgpC0DfBJoIc0NgQAEfHZlkVmZmZtVe8pphuA20md973WunDMzKxT1JsgNo+Iz7c0EjMz6yj13sV0iaRPS9pR0nalR0sjM2szjwVto129NYhXgG8Dc8i3uua/u7QiKLN2K40FXRqHoTQWNOCutm3UqLcG8QVgt4joiYid88PJwUYsjwVtVn+C6APW9TuX2QjhsaDN6j/F9CJwt6T/AF4uFfo2VxupJndNLhwLenLX5DZEY9Ye9dYgrgXmAr8A7ix7mI1Ic6fNZfym4zco81jQNtrU25L64lYHYtZJPBa0WT9jUku6KiI+Lmkxf7h76XUR8Y5WBtcIj0ltZta4WmNS91eD+Fz+++HmhmRmZp2u5jWIiCh16f2XEbG8/AH8ZevDMzOzdqn3IvUhBWWHNzMQMzPrLDVPMUn6DKmmsIuke8smbQXc1srAzMysvfqrQVwGTAfm57+lx74R0e+AQZIOk/SQpD5JpxZMHyfpyjz9Dkk9FdMnS3pB0hfr3B4zM2uSmjWIiFgDrAGObXTFksYA55FOT60EFkqaHxH3l812IvBsROwmaSZwFnBM2fSzgX9r9L3NzGzw6r0GMRD7A30RsTQiXgGuAGZUzDMDKLWxuBqYpjwakaSPkIY2XdLCGM3MrIpWJoiJwIqy1ytzWeE8EbGeVFvZXtIbgL8BvlHrDSTNlrRI0qLVq1c3LXAb/txVt9ngtTJBDMZpwHci4oVaM0VEb0RMjYipEyZMGJrIrOOVuupevmY5QbzeVbeThFljWpkgVgE7lb2elMsK55E0FugCngYOAP5O0jLgFOArkk5uYaw2grirbrPmqLc314FYCOwuaWdSIpgJfKJinvnAccAvgaOAWyL1/fGe0gySTgNeiIhzWxirjSDuqtusOVpWg8jXFE4GFgAPAFdFxBJJp0s6Ms92IemaQx/weWCjW2HNGlWtS2531W3WmJZeg4iIGyJij4jYNSLm5rKvRcT8/Px3EXF0ROwWEftHxNKCdZwWEX/fyjitswz2ArO76jZrjk69SG2jVDMuMM/aaxa903vp7upGiO6ubnqn97qrbrMG1ezuezhxd98jQ885PYUjuXV3dbPslGVDH5DZCFeru2/XIKyj+AKzWedwgrCO4gvMZp3DCcI6ii8wm3UOJwjrKL7AbNY5fJHazGwU80VqMzNrmBOEmZkVcoIwM7NCThBmZlbICcKaygP1mI0crezu20aZUj9KpbEYSv0oAb5N1WwYcg3CmsYD9ZiNLE4Q1jTuR8lsZHGCsKZxP0pmI4sThDWN+1EyG1mcIKxp3I+S2cjivpjMzEYx98VkZmYNc4Kw17mRm5mVc0M5A9zIzcw25hqEAW7kZmYbc4IwwI3czGxjThAGuJGbmW3MCcIAN3Izs405QRjgRm5mtrGWNpSTdBjwXWAM8IOIOLNi+jjgR8C+wNPAMRGxTNIhwJnAZsArwF9HxC213ssN5czMGteWhnKSxgDnAYcDU4BjJU2pmO1E4NmI2A34DnBWLn8KmB4RewHHAZe0Kk4zMyvWylNM+wN9EbE0Il4BrgBmVMwzA7g4P78amCZJEfGriPhtLl8CbJFrG2ZmNkRamSAmAivKXq/MZYXzRMR6YA2wfcU8fwLcFREvV76BpNmSFklatHr16qYFPhy5FbSZNVtHt6SWtCfptNOhRdMjohfohXQNYghD6yhuBW1mrdDKGsQqYKey15NyWeE8ksYCXaSL1UiaBFwDfDIiHmlhnMOeW0GbWSu0MkEsBHaXtLOkzYCZwPyKeeaTLkIDHAXcEhEhaRvgeuDUiLithTGOCG4FbWat0LIEka8pnAwsAB4AroqIJZJOl3Rknu1CYHtJfcDngVNz+cnAbsDXJN2dH29sVazDnVtBm1kreMCgEaDyGgSkVtBu6GZm/fGAQSOcW0GbWSu4BmFmNoq5BmFmZg1zgmiCwTZScyM3M+tEHd1QbjgYbCM1N3Izs07lGsQgDbaRmhu5mVmncoIYpME2UnMjNzPrVE4QgzTYRmpu5GZmncoJYpAGO1Snh/o0s07lBDFIg22k5kZuZtap3FDOzGwUc0M5MzNrmBOEmZkVGvUJwq2YzcyKjeqW1G7FbGZW3aiuQbgVs5lZdaM6QbgVs5lZdaM6QbgVs5lZdaM6QbgVs5lZdaM6QbgVs5lZdW5JbWY2irkltZmZNcwJwszMCjlBmJlZIScIMzMr5ARhZmaFRsxdTJJWA8vbHUc/dgCeancQdRguccLwidVxNtdwiRM6P9buiJhQNGHEJIjhQNKiareTdZLhEicMn1gdZ3MNlzhheMVayaeYzMyskBOEmZkVcoIYWr3tDqBOwyVOGD6xOs7mGi5xwvCKdQO+BmFmZoVcgzAzs0JOEGZmVsgJokGSdpL0H5Lul7RE0udy+WmSVkm6Oz+OKFvmy5L6JD0k6UNl5Yflsj5Jp5aV7yzpjlx+paTNBhjrMkmLczyLctl2km6S9HD+u20ul6Tv5fe8V9I+Zes5Ls//sKTjysr3zevvy8tqgHG+pWy/3S1praRTOmGfSrpI0pOS7isra/k+rPYeDcb5bUkP5liukbRNLu+R9FLZfj1/oPHU2uYGY235/1rSuPy6L0/vGUCcV5bFuEzS3Z2wT1smIvxo4AHsCOyTn28F/BqYApwGfLFg/inAPcA4YGfgEWBMfjwC7AJslueZkpe5CpiZn58PfGaAsS4Ddqgo+zvg1Pz8VOCs/PwI4N8AAQcCd+Ty7YCl+e+2+fm2edp/53mVlz28Cft3DPA40N0J+xR4L7APcN9Q7sNq79FgnIcCY/Pzs8ri7Cmfr2I9DcVTbZsHEGvL/9fAXwLn5+czgSsbjbNi+j8AX+uEfdqqh2sQDYqIxyLirvz8eeABYGKNRWYAVwHugX4AAAU6SURBVETEyxHxG6AP2D8/+iJiaUS8AlwBzMi/Lj4AXJ2Xvxj4SBM3YUZeZ+W6ZwA/iuR2YBtJOwIfAm6KiGci4lngJuCwPG3riLg90lH9oybFOQ14JCJqtYofsn0aET8Hnil4/1bvw2rvUXecEXFjRKzPL28HJtVaxwDjqbbNDcVaQzP/1+XbcDUwrfRrvtE483IfBy6vFfxQ7dNWcYIYhFxFfSdwRy46OVcJLyo7JTARWFG22MpcVq18e+C5sg92qXwgArhR0p2SZueyN0XEY/n548CbBhjnxPy8snywZrLhh67T9ikMzT6s9h4D9SnSr9KSnSX9StJ/SnpPWfyNxlNt2wai1f/r15fJ09fk+QfiPcATEfFwWVkn7tNBcYIYIElvAP4FOCUi1gL/BOwK7A08Rqp+tttBEbEPcDjwV5LeWz4x/6LpmPuc87niI4Ef56JO3KcbGIp9ONj3kDQHWA/My0WPAZMj4p3A54HLJG09VPFU0fH/6wrHsuEPmU7cp4PmBDEAkjYlJYd5EfETgIh4IiJ+HxGvAReQqsAAq4CdyhaflMuqlT9NqlKOrShvWESsyn+fBK7JMT1Rqq7mv08OMM5VbHjKYsBxljkcuCsinshxd9w+zYZiH1Z7j4ZIOh74MDArfwmRT9c8nZ/fSTqXv8cA46m2bQ0Zov/168vk6V15/obkZT8GXFkWf8ft02ZwgmhQPvd4IfBARJxdVl5+jvCjQOnOh/nAzHwHxc7A7qSLVguB3fMdF5uRTq3Mzx/i/wCOyssfB/zrAOLcUtJWpeekC5b35XhKd9GUr3s+8Ml8B8WBwJpc/V0AHCpp21ztPxRYkKetlXRg3iefHEicFTb4VdZp+7TMUOzDau9RN0mHAV8CjoyIdWXlEySNyc93Ie2/pQOMp9o2NxrrUPyvy7fhKOCWUtJs0AeBByPi9VNHnbhPm6La1Ws/qt7ZcBCpKngvcHd+HAFcAizO5fOBHcuWmUP6RfEQZXf65OV+nafNKSvfhfQh6COdbhk3gDh3Id3ZcQ+wpLR+0jnXm4GHgZ8B2+VyAeflWBYDU8vW9akcSx9wQln5VNIH+RHgXHLL/AHu1y1Jv+a6ysravk9JCesx4FXSueATh2IfVnuPBuPsI53LLh2npTt4/iQfE3cDdwHTBxpPrW1uMNaW/6+BzfPrvjx9l0bjzOX/DJxUMW9b92mrHu5qw8zMCvkUk5mZFXKCMDOzQk4QZmZWyAnCzMwKOUGYmVkhJwizJpH0z5LWldqf5LJzJIWkHdoZm9lAOEGYNVcfqbM1JG1C6jiuLa1gzQbLCcKsQUp9/z8g6QKlMUFulLRFnnwFcEx+fjBwG6kfpNKy1+bOE5eUOlCU1K00JsAOkjaR9F+SDh3KbTIr4gRhNjC7A+dFxJ7Ac6SWtJBa9k7IXWocS0oY5T4VEfuSWtd+VtL2kbo2P4vUYd0XgPsj4sah2AizWpwgzAbmNxFxd35+J2nAmJKfkPoGOgD4r4rlPivpHtL4DDuREg0R8QNga+Ak4IutC9usfmP7n8XMCrxc9vz3wBZlr68kJY2LI+I15TFpJB1M6ujtXRGxTtKtpP6BkDSeP/T6+Qbg+VYGb1YPJwizJouI5XkMhp9VTOoCns3J4a2k4SRLziKN17Cc1N31h4ckWLMafIrJrAUi4vsR8UhF8b8DYyU9AJxJOs2EpPcB+5HGJJ4HvCLphCEN2KyAe3M1M7NCrkGYmVkhJwgzMyvkBGFmZoWcIMzMrJAThJmZFXKCMDOzQk4QZmZW6P8DR6evoJXxjCoAAAAASUVORK5CYII=\n"
          },
          "metadata": {
            "needs_background": "light"
          }
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Sieve of Sundaram\n"
      ],
      "metadata": {
        "id": "UnfbNa3B29ML"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def sundaram(n):\n",
        "\n",
        "  m = int((n - 1)/2)\n",
        "\n",
        "  nums = list(range(1, m + 1))\n",
        "  i = 1\n",
        "\n",
        "  for i in range(1, m + 1):    \n",
        "    while (2*i + 2*i**2) <= m:      \n",
        "      j = i   \n",
        "      while (i + j + 2(i*j))  <= m:     \n",
        "        \n",
        "        w = (i + j + 2(i*j))         \n",
        "        if w in nums:\n",
        "          nums[w] = 1  \n",
        "          j += 1\n",
        "      i +=  1\n",
        "\n",
        "  if (n > 2):\n",
        "        print(2,\" \") \n",
        "\n",
        "  for i in range(1, m + 1):\n",
        "        if (nums[i] == 0):\n",
        "            print((2 * i + 1),\" \");       \n",
        "\n",
        "  primes = [2*b + 1 for b in nums]\n",
        "  return primes"
      ],
      "metadata": {
        "id": "2cnMl1Gs4MWW"
      },
      "execution_count": 119,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def SieveOfSundaram(n):\n",
        "  \n",
        "    nNew = int((n - 1) / 2);\n",
        " \n",
        " \n",
        "    marked = [0] * (nNew + 1);\n",
        " \n",
        "\n",
        "    for i in range(1, nNew + 1):\n",
        "        j = i;\n",
        "        while((i + j + 2 * i * j) <= nNew):\n",
        "            marked[i + j + 2 * i * j] = 1;\n",
        "            j += 1;\n",
        " \n",
        "    # Since 2 is a prime number\n",
        "    if (n > 2):\n",
        "        print(2, end = \" \");\n",
        " \n",
        "    # Print other primes. Remaining\n",
        "    # primes are of the form 2*i + 1\n",
        "    # such that marked[i] is false.\n",
        "    for i in range(1, nNew + 1):\n",
        "        if (marked[i] == 0):\n",
        "            print((2 * i + 1), end = \" \")"
      ],
      "metadata": {
        "id": "yjEJgQ4RRfrv"
      },
      "execution_count": 122,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "SieveOfSundaram(20)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "r5gu0WVdR_se",
        "outputId": "39a1c693-867b-43d9-e912-511854158335"
      },
      "execution_count": 123,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "2 3 5 7 11 13 17 19 "
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "m = 20\n",
        "nums = list(range(1, m + 1))\n",
        "print(nums)\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8B7OyohdNkqb",
        "outputId": "abc6fb43-4dbf-4b8b-c978-85926c56e0c7"
      },
      "execution_count": 99,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]\n"
          ]
        }
      ]
    },
    {
      "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"
      ],
      "metadata": {
        "id": "CLVAV-eeT92j"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Conjecture A.** Every even integer greater than 2 is the sum of two primes.\n",
        "\n",
        "**Conjecture B.** For every $N$, the number of nonnegative integers less than $N$ with an even number of prime factors is less than the number of nonnegative integers less than N with an odd number of prime factors. For this, prime factors are counted with *multiplicity*; e.g.,  $24 = 2^3 · 3$ has 4 prime factors, while  $588 = 22 · 3 · 7^2$ has 5 prime factors.\n",
        "\n",
        "**(Proved) 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": "Z5L4xi0BUNqq"
      }
    },
    {
      "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": [
        "#### Get a list of even numbers"
      ],
      "metadata": {
        "id": "gpSrT21bcI0V"
      }
    },
    {
      "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\n",
        "\n",
        "def evenList(nMax): \n",
        "  \n",
        "  evenList = []\n",
        "\n",
        "  for n in range(2,nMax + 1):\n",
        "      if isEven(n):\n",
        "        evenList.append(n)\n",
        "\n",
        "  return evenList"
      ],
      "metadata": {
        "id": "hU7EhH1Wb0re"
      },
      "execution_count": 398,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "evenList(20)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ItyK80TBb-9T",
        "outputId": "cb1224f0-f4c6-44a4-b25a-65ec100e0889"
      },
      "execution_count": 399,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[4, 6, 8, 10, 12, 14, 16, 18, 20]"
            ]
          },
          "metadata": {},
          "execution_count": 399
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### The real function\n",
        "\n"
      ],
      "metadata": {
        "id": "n0vE6t4Tdfe-"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# somehow this one takes an even integer and gives you the sum of two primes\n",
        "def twoPrimes(nMax):\n",
        "\n",
        "  primeList = fastEratos(nMax)\n",
        "  evenNums = evenList(nMax)\n",
        "  j = 0\n",
        "  \n",
        "  for i in range(len(evenNums)): \n",
        "    evenInt = evenNums[i]\n",
        "\n",
        "  while primeList[j] < evenInt:  \n",
        "    j += 1\n",
        "    firstPrime = primeList[j]   \n",
        "    diff = evenInt - firstPrime\n",
        "    if isPrime(diff):\n",
        "      secondPrime = diff\n",
        "      return evenInt, firstPrime, secondPrime\n",
        "  \n",
        "  else:\n",
        "    print(\"failed\")"
      ],
      "metadata": {
        "id": "1luNATErXebC"
      },
      "execution_count": 431,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "twoPrimes(1000)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "qv3FpwFihNhd",
        "outputId": "102191c9-8698-4f62-d5b9-2cb88fdb599f"
      },
      "execution_count": 433,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(1000, 3, 997)"
            ]
          },
          "metadata": {},
          "execution_count": 433
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "def test2Primes(nMax):\n",
        "\n",
        "  primeList = fastEratos(nMax)\n",
        "  evenNums = evenList(nMax)\n",
        "  j = 0\n",
        "  \n",
        "  for i in range(len(evenNums)): \n",
        "    evenInt = evenNums[i]\n",
        "\n",
        "    while primeList[j] < evenInt:    \n",
        "      firstPrime = primeList[j]   \n",
        "      diff = evenInt - firstPrime     \n",
        "      if isPrime(diff):\n",
        "        conjectureCorrect = True        \n",
        "    \n",
        "    else:\n",
        "      break\n",
        "      conjectureCorrect = False\n",
        " \n",
        "  return conjectureCorrect"
      ],
      "metadata": {
        "id": "6OWtO6K3jBXw"
      },
      "execution_count": 445,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "test2Primes(5)"
      ],
      "metadata": {
        "id": "zFtmiuNLkpAR"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "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": "code",
      "source": [
        "def testInt(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": 391,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "testInt(500,2500000)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "xZW42RU0W3fr",
        "outputId": "2eae4f04-f4ec-4b81-ffe6-3a544efde61e"
      },
      "execution_count": 394,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "found prime: 250007\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "isPrime(250007)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "timjSk-xae6I",
        "outputId": "3c42cbc6-10a7-41d9-a87b-6cd47bc9f449"
      },
      "execution_count": 395,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "True"
            ]
          },
          "metadata": {},
          "execution_count": 395
        }
      ]
    },
    {
      "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": [
        "#### Generate Odd Numbers"
      ],
      "metadata": {
        "id": "R3FiQxp1wryT"
      }
    },
    {
      "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\n",
        "\n",
        "def oddList(nMax): # test using: oddList(50)\n",
        "  \n",
        "  oddsList = []\n",
        "\n",
        "  for n in range(2,nMax + 1):\n",
        "      if isOdd(n):\n",
        "        oddsList.append(n)\n",
        "\n",
        "  return oddsList"
      ],
      "metadata": {
        "id": "xnZgBn9NbJVM"
      },
      "execution_count": 292,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "print(oddList(50))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "NmIvGTB_jlEp",
        "outputId": "5564ba45-78ac-4c6a-ebf4-d1d839f12372"
      },
      "execution_count": 293,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Generate Squares"
      ],
      "metadata": {
        "id": "dx4jCk-nwkxx"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def isSq(n):\n",
        "\n",
        "  root = math.sqrt(n)\n",
        "  \n",
        "  if root % 1 == 0:\n",
        "    return True\n",
        "  else:\n",
        "    return False\n",
        "\n",
        "def sqList(nMax): \n",
        "  \n",
        "  sqList = []\n",
        "\n",
        "  for n in range(2, nMax + 1): # start at 2 since all is greater than 1\n",
        "      if isSq(n):\n",
        "        sqList.append(n)\n",
        "  \n",
        "  return sqList"
      ],
      "metadata": {
        "id": "8caiiYvxpA-L"
      },
      "execution_count": 233,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "sqList(80)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "7L7y5CwI25bU",
        "outputId": "48f3cb06-fed1-4e8b-f2ce-98ef5cccf291"
      },
      "execution_count": 234,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[4, 9, 16, 25, 36, 49, 64]"
            ]
          },
          "metadata": {},
          "execution_count": 234
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Generate Primes"
      ],
      "metadata": {
        "id": "Y2bjoQN3waJw"
      }
    },
    {
      "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"
      ],
      "metadata": {
        "id": "WlSns3-XwWPe"
      },
      "execution_count": 416,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "## The real function"
      ],
      "metadata": {
        "id": "1fd6l2tdE3N5"
      }
    },
    {
      "cell_type": "code",
      "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.\n",
        "\n",
        "def oddPrimes(nMax):\n",
        "\n",
        "  oddsList = oddList(nMax)\n",
        "  primeList = fastEratos(nMax)\n",
        "  squares = sqList(nMax)\n",
        "    \n",
        "  for i in range(len(oddsList)): # For all odd numbers in oddsList               \n",
        "    oddNum = oddsList[i]   \n",
        "    \n",
        "    if isPrime(oddNum): # move on to next index on oddsList\n",
        "      i += 1       \n",
        "     \n",
        "     # or if it can be expressed as (prime + 2x^2)\n",
        "      \n",
        "  for j in range(len(primeList)):\n",
        "    primeNum = primeList[j]\n",
        "       \n",
        "  for k in range(len(squares)):                             \n",
        "    twSquare = 2 * squares[k]          \n",
        "                                              \n",
        "    \n",
        "    while (primeNum + twSquare != oddNum):\n",
        "      k += 1\n",
        "      j += 1     \n",
        "      \n",
        "      if primeNum + twSquare == oddNum:\n",
        "        i += 1\n",
        "      \n",
        "  \n",
        "    \n",
        "    else:\n",
        "        return oddNum\n",
        "                "
      ],
      "metadata": {
        "id": "iIeiUDTYXdb7"
      },
      "execution_count": 321,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "oddPrimes(10000)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 293
        },
        "id": "lNMzOVej5M2x",
        "outputId": "7f6e8836-32ca-4f87-f956-819be5140f1e"
      },
      "execution_count": 322,
      "outputs": [
        {
          "output_type": "error",
          "ename": "KeyboardInterrupt",
          "evalue": "ignored",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
            "\u001b[0;32m<ipython-input-322-5417d5bbf86b>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0moddPrimes\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m10000\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
            "\u001b[0;32m<ipython-input-321-649a118fcebb>\u001b[0m in \u001b[0;36moddPrimes\u001b[0;34m(nMax)\u001b[0m\n\u001b[1;32m     26\u001b[0m       \u001b[0mj\u001b[0m \u001b[0;34m+=\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     27\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 28\u001b[0;31m       \u001b[0;32mif\u001b[0m \u001b[0mprimeNum\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mtwSquare\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0moddNum\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     29\u001b[0m         \u001b[0mi\u001b[0m \u001b[0;34m+=\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     30\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
          ]
        }
      ]
    }
  ]
}