Last active
July 21, 2022 18:52
-
-
Save kargaranamir/4b855644bdd999da1c9390c54f080b7d to your computer and use it in GitHub Desktop.
even_2prime_conjecture.ipynb
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{ | |
"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