HW_Primes_II_CW.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "HW_Primes II_CW",
      "provenance": [],
      "collapsed_sections": [],
      "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/HW_Primes_II_CW.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 II Practice Problem\n",
        "\n",
        "**Learning Goals:** Gain proficiency with Python coding. Explore simple patterns in prime numbers.\n",
        "\n",
        "**Your task:** Complete the practice problem below.\n",
        "\n",
        "**Due:** Friday, April 15, at 5:00pm. Do the following to submit your work.\n",
        "\n",
        "1. Click on *Share* in the upper right corner of this window. Make sure your notebook is viewable by Prof. Wright and the course grader(s).\n",
        "2. In the *Get link*, click *Copy link*.\n",
        "3. Go to the [Primes II](https://mdl.stolaf.edu/mod/assign/view.php?id=189548) assignment on Moodle. Paste the link to your notebook in the text field for the assignment submission. This will allow Prof. Wright or either of the course graders to view your Colab notebook.\n",
        "\n",
        "**Grading:** This problem will be graded on a Satisfactory/Unsatisfactory scale. If you use Python code to correctly find the answer to the question below you will receive a Satisfactory grade.\n",
        "\n",
        "**Need help?** Review the notes from class and Python documentation links on the course web site. If you still need help, email Prof. Wright. Don't forget there are also evening help sessions &mdash; the help session schedule is at the top of the course website.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Problem: primes modulo 4\n",
        "\n",
        "Let $p$ be an odd prime, and consider the remainder when $p$ is divided by $4$. This remainder must be either $1$ or $3$. If the remainder is $1$, we say that $p$ is **congruent to $1$ modulo $4$**. If the remainder is $3$, we say that $p$ is **congruent to $3$ modulo $4$**.\n",
        "\n",
        "For any positive integer $M$, we can count the number of primes less than or equal to $M$ that are congruent to $1$ or to $3$ modulo $4$. For example, if $M = 20$, then the primes less than or equal to $M$ include exactly three that are congruent to $1$ modulo $4$ (that is, the primes $5$, $13$, and $17$) and exactly four that are congruent to $3$ modulo $4$ (that is, the primes $3$, $7$, $11$, and $19$).\n",
        "\n",
        "**Your task is to find the smallest positive integer $M$ such that the set of primes less than or equal to $M$ contains *more* primes congruent to $1$ modulo $4$ than congruent to $3$ modulo $4$.**\n",
        "\n",
        "(*Hint*: the correct answer is less than $100,000$.)"
      ],
      "metadata": {
        "id": "N7X8PLavhIq9"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "import math"
      ],
      "metadata": {
        "id": "1oNhVYtspaRg"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def primeModulo(nMax):\n",
        "\n",
        "  primeList = fastEratos(nMax)\n",
        "  count1 = 0\n",
        "  count2 = 0\n",
        "  \n",
        "  for i in range(len(primeList)):    \n",
        "    if primeList[i] % 4 == 1:\n",
        "      count1 += 1\n",
        "    elif primeList[i] % 4 == 3:\n",
        "      count2 += 1\n",
        "    if count1 > count2:\n",
        "      return primeList[i]     "
      ],
      "metadata": {
        "id": "j3j3eYMcofF5"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "primeModulo(100000)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Bw1bvkV4q-kx",
        "outputId": "8bb52af3-f4f5-4284-dad1-3ea367224c9d"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "26861"
            ]
          },
          "metadata": {},
          "execution_count": 152
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### **The smallest positive integer  𝑀 = 26861**"
      ],
      "metadata": {
        "id": "VvhQ7vf4k2sJ"
      }
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "DB3XW9wNgvZd"
      },
      "outputs": [],
      "source": [
        "# First I wrote a more simple function that returns the counts\n",
        "def printPrimeModulo(minInt):\n",
        "\n",
        "  primeList = fastEratos(minInt)\n",
        "  count1 = 0\n",
        "  count2 = 0\n",
        "  \n",
        "  for p in primeList:    \n",
        "    if p % 4 == 1:\n",
        "      count1 += 1\n",
        "    elif p % 4 == 3:\n",
        "      count2 += 1\n",
        "  print(\"congruent to 1 modulo 4:\", count1, \"congruent to 3 modulo 4:\", count2)  "
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "printPrimeModulo(26861)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "jlBx5HPyl2_B",
        "outputId": "ddcb4770-beb5-4de2-b277-2bffdde9ee45"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "congruent to 1 modulo 4: 1473 congruent to 3 modulo 4: 1472\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# Find list of prime \n",
        "def fastEratos(nMax):\n",
        "\n",
        "  nums = list(range(2,nMax+1))\n",
        "  nroot = math.sqrt(nMax)\n",
        "\n",
        "  i = 0 \n",
        "  while nums[i] <= nroot:\n",
        "    if nums[i] > 0:  \n",
        "      j = i + nums[i]\n",
        "      while j < len(nums):\n",
        "        nums[j] = 0\n",
        "        j += nums[i]    \n",
        "\n",
        "    i += 1  \n",
        "\n",
        "  primes = [n for n in nums if n != 0]\n",
        "  return primes"
      ],
      "metadata": {
        "id": "ICifzcsCpYMi"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "fastEratos(50)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "l-RCx4T6pf1n",
        "outputId": "8bfcdaa1-31b2-4fa1-d6e9-c5191c26ff98"
      },
      "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": 145
        }
      ]
    }
  ]
}