Skip to content

Instantly share code, notes, and snippets.

@kargaranamir

kargaranamir/even_2prime_conjecture.ipynb

Last active July 21, 2022 18:52
Show Gist options
  • Save kargaranamir/4b855644bdd999da1c9390c54f080b7d to your computer and use it in GitHub Desktop.
Save kargaranamir/4b855644bdd999da1c9390c54f080b7d to your computer and use it in GitHub Desktop.
Download ZIP
even_2prime_conjecture.ipynb
Display the source blob
Display the rendered blob
Raw
even_2prime_conjecture.ipynb
{
"nbformat": 4,
"nbformat_minor": 0,
"metadata": {
"colab": {
"name": "even_2prime_conjecture.ipynb",
"provenance": [],
"authorship_tag": "ABX9TyM09WOKFw3FqvptGKS21Jfs",
"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/gist/kargaranamir/4b855644bdd999da1c9390c54f080b7d/even_2prime_conjecture.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
]
},
{
"cell_type": "markdown",
"source": [
"# Conjecture\n",
"If $n$ is an even number ($n \\neq 2$), find two prime numbers $p$ and $q$ that sum to $n$, i.e. $p + q = n$\n",
"\n",
"Input: $n$\n",
"\n",
"Output: $[p, q]$\n"
],
"metadata": {
"id": "jdhB28Ydh5On"
}
},
{
"cell_type": "markdown",
"source": [
"## Discussion and Solution\n",
"Since $n$ is even and not $2$, the primes should be odd, so $p, q >2$ or both equals $2$ in case of $n=4$.\n",
"\n",
"#### First thinking: \n",
"\n",
"- It's a good idea to check just $\\frac{n}{2}$ numbers since there are $\\frac{n}{2}$ odd numbers less than $n$.\n",
"- In order to determine if a number, such as $k$, is a prime number, we must check the range from $2$ to $\\sqrt{k}$.\n",
"\n",
"#### Method:\n",
"- To find all prime numbers below $n$, we can check the odd numbers and for each of them, such as $k$, then we check the range from $2$ to $\\sqrt{k}$.\n",
"- Our next step is to determine if $p$, which is an odd number less than $n$, and $n - p$ is in the prime list or not.\n",
"\n",
"\n",
"#### Important Note!!\n",
"- We do not need to check all $\\frac{n}{2}$ numbers as we already checked $n - p$ when we checked $p$, so we just need to check $\\frac{n}{4}$ iterations. So, the odds range between $n-1$ and $n/2$."
],
"metadata": {
"id": "WS3LKOd3jLOX"
}
},
{
"cell_type": "markdown",
"source": [
"### Import Library"
],
"metadata": {
"id": "Vu76e7nXh00-"
}
},
{
"cell_type": "code",
"source": [
"from math import sqrt # Sqrt function \n",
"import time # Count the time it takes for code to run"
],
"metadata": {
"id": "4fNID_PFZlpQ"
},
"execution_count": null,
"outputs": []
},
{
"cell_type": "markdown",
"source": [
"`find_primes`: Checking the odds and making a prime list below $n$. In order to determine if a number, such as $k$, is a prime number, we must check the range from $2$ to $\\sqrt{k}$.\n",
" \n"
],
"metadata": {
"id": "FM4UM3zlrkT-"
}
},
{
"cell_type": "code",
"source": [
"def find_primes(n):\n",
"\n",
" # n is even and not 2\n",
" primes = [i%2 for i in range(0, n+1)]\n",
" primes[0] = 0\n",
" primes[1] = 0\n",
" primes[2] = 1\n",
"\n",
" # iterate only on odd numbers and check until sqrt of that number\n",
" for p in range(n, 2, -1):\n",
" # only odds\n",
" if primes[p] == 1:\n",
" i = 2\n",
" # check till sqrt\n",
" while i < int(sqrt(p)+1)+1:\n",
" # break if there is a devisor\n",
" if p % i == 0:\n",
" primes[p] = 0\n",
" break\n",
" else:\n",
" i = i + 1\n",
" return primes"
],
"metadata": {
"id": "xpbrs3_7htrk"
},
"execution_count": null,
"outputs": []
},
{
"cell_type": "markdown",
"source": [
"Gets the prime numbers below $n$ and checks if both $n-p$ and $p$ are prime. Potential $p$ is an odd between $n-1$ and $n/2$"
],
"metadata": {
"id": "3ZkzFANKr_Q_"
}
},
{
"cell_type": "code",
"source": [
"# returns first match\n",
"def find_pairs(n):\n",
" if n == 2 or n%2==1:\n",
" return [None, None]\n",
"\n",
" if n == 4:\n",
" return [2, 2]\n",
"\n",
" else:\n",
" primes = find_primes(n)\n",
"\n",
" # iterate only on odds \n",
" for i in range(n - 1, int(n/2) -1, -2):\n",
" # return when you first the find match\n",
" if (primes[i]==1 and primes[n-i]==1):\n",
" return i, n - i"
],
"metadata": {
"id": "n7fJeUNwhwQx"
},
"execution_count": null,
"outputs": []
},
{
"cell_type": "code",
"source": [
"# returns all of matches\n",
"\n",
"def find_all_pairs(n):\n",
" all_pairs = []\n",
" if n == 2 or n%2==1:\n",
" return [[None, None]]\n",
"\n",
" elif n == 4:\n",
" return [[2, 2]]\n",
"\n",
" else:\n",
" primes = find_primes(n)\n",
"\n",
" # iterate only on odds \n",
" for i in range(n - 1, int(n/2) -1, -2):\n",
" \n",
" \n",
" if (primes[i]==1 and primes[n-i]==1):\n",
" all_pairs.append([i, n - i])\n",
"\n",
" # return all of matches\n",
" return all_pairs"
],
"metadata": {
"id": "gKDz9ttPoQrQ"
},
"execution_count": null,
"outputs": []
},
{
"cell_type": "markdown",
"source": [
"## Test "
],
"metadata": {
"id": "uQz9YYE1hyCD"
}
},
{
"cell_type": "markdown",
"source": [
"### `find_pairs` Test"
],
"metadata": {
"id": "-ZHwhmi4o2HV"
}
},
{
"cell_type": "code",
"source": [
"start = time.time()\n",
"result = find_pairs(6)\n",
"print(f\"{time.time()-start} s\")\n",
"print(result)"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "gtj1ybXra91V",
"outputId": "4a769037-019b-4761-ce1d-61491b366493"
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"0.0001456737518310547 s\n",
"(3, 3)\n"
]
}
]
},
{
"cell_type": "code",
"source": [
"start = time.time()\n",
"result = find_pairs(28)\n",
"print(f\"{time.time()-start} s\")\n",
"print(result)"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "Dc2hwr-UhWrX",
"outputId": "e21a7831-473a-4862-fb0f-2342b6958d08"
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"0.00015735626220703125 s\n",
"(23, 5)\n"
]
}
]
},
{
"cell_type": "code",
"source": [
"start = time.time()\n",
"result = find_pairs(98)\n",
"print(f\"{time.time()-start} s\")\n",
"print(result)"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "pDWimC6jhmJW",
"outputId": "65d801da-a078-41ca-ba2c-e81144d52611"
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"0.0005142688751220703 s\n",
"(79, 19)\n"
]
}
]
},
{
"cell_type": "markdown",
"source": [
"### `find_all_pairs` Test"
],
"metadata": {
"id": "3Q2RzexIo6IE"
}
},
{
"cell_type": "code",
"source": [
"start = time.time()\n",
"result = find_all_pairs(6)\n",
"print(f\"{time.time()-start} s\")\n",
"print(result)"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "tk35766upEru",
"outputId": "e624e5a9-e9d1-4499-cbad-995e9ccef8e8"
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"0.00013828277587890625 s\n",
"[[3, 3]]\n"
]
}
]
},
{
"cell_type": "code",
"source": [
"\n",
"start = time.time()\n",
"result = find_all_pairs(28)\n",
"print(f\"{time.time()-start} s\")\n",
"print(result)"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "VU0U3B-BpGI2",
"outputId": "690a213f-ef96-4fe7-e354-8be9bd703cee"
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"0.00016355514526367188 s\n",
"[[23, 5], [17, 11]]\n"
]
}
]
},
{
"cell_type": "code",
"source": [
"start = time.time()\n",
"result = find_all_pairs(98)\n",
"print(f\"{time.time()-start} s\")\n",
"print(result)"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "pwiJlL7ZpO4s",
"outputId": "69d8fd7c-d7dc-4e28-eb38-b1950284072d"
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"0.0003993511199951172 s\n",
"[[79, 19], [67, 31], [61, 37]]\n"
]
}
]
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment