Created
September 25, 2017 21:37
-
-
Save mozz100/69ae347cda4b92b8996b75349c796491 to your computer and use it in GitHub Desktop.
Prime numbers
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
{ | |
"cells": [ | |
{ | |
"cell_type": "markdown", | |
"metadata": {}, | |
"source": [ | |
"### Credits\n", | |
"\n", | |
"Prime number functions from https://inventwithpython.com/hacking/chapter23.html\n", | |
"\n", | |
"Trinity Hall Prime from https://math.stackexchange.com/questions/2420488/what-is-trinity-hall-prime-number\n", | |
"\n", | |
"Prior art and inspiration from https://friendlyfieldsandopenmaps.com/2017/09/08/the-corpus-christi-prime/\n", | |
"\n", | |
"Prime number checking at https://www.alpertron.com.ar/ECM.HTM\n" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 1, | |
"metadata": { | |
"collapsed": true | |
}, | |
"outputs": [], | |
"source": [ | |
"# Primality Testing with the Rabin-Miller Algorithm\n", | |
"# http://inventwithpython.com/hacking (BSD Licensed)\n", | |
"import random\n", | |
"\n", | |
"\n", | |
"def rabinMiller(num):\n", | |
" # Returns True if num is a prime number.\n", | |
" s = num - 1\n", | |
" t = 0\n", | |
" while s % 2 == 0:\n", | |
" # keep halving s while it is even (and use t\n", | |
" # to count how many times we halve s)\n", | |
" s = s // 2\n", | |
" t += 1\n", | |
" for trials in range(5): # try to falsify num's primality 5 times\n", | |
" a = random.randrange(2, num - 1)\n", | |
" v = pow(a, s, num)\n", | |
" if v != 1: # this test does not apply if v is 1.\n", | |
" i = 0\n", | |
" while v != (num - 1):\n", | |
" if i == t - 1:\n", | |
" return False\n", | |
" else:\n", | |
" i = i + 1\n", | |
" v = (v ** 2) % num\n", | |
" return True\n", | |
"\n", | |
"def isPrime(num):\n", | |
" # Return True if num is a prime number. This function does a quicker\n", | |
" # prime number check before calling rabinMiller().\n", | |
" if (num < 2):\n", | |
" return False # 0, 1, and negative numbers are not prime\n", | |
" # About 1/3 of the time we can quickly determine if num is not prime\n", | |
" # by dividing by the first few dozen prime numbers. This is quicker\n", | |
" # than rabinMiller(), but unlike rabinMiller() is not guaranteed to\n", | |
" # prove that a number is prime.\n", | |
" lowPrimes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]\n", | |
" if num in lowPrimes:\n", | |
" return True\n", | |
" # See if any of the low prime numbers can divide num\n", | |
" for prime in lowPrimes:\n", | |
" if (num % prime == 0):\n", | |
" return False\n", | |
" # If all else fails, call rabinMiller() to determine if num is a prime.\n", | |
" return rabinMiller(num)" | |
] | |
}, | |
{ | |
"cell_type": "markdown", | |
"metadata": {}, | |
"source": [ | |
"Draw ascii with:\n", | |
"```\n", | |
">$ jp2a --height=20 -i --chars=\"18\" /Users/mozz/Desktop/angentbw.jpg --invert\n", | |
"```\n", | |
"\n", | |
"```88888888888888888888881111118888888888888888888888\n", | |
"88888888888888888881111111111118888888888888888888\n", | |
"88888888888888888111111111111111188888888888888888\n", | |
"88888888888888881111111111111111118888888888888888\n", | |
"88888888888888811111111111111111111888888888888888\n", | |
"88888888888888111111118888881111111188888888888888\n", | |
"88888888888888111118888111188881111188888888888888\n", | |
"88888888888881111188811111111888111118888888888888\n", | |
"88888888888881111888111111111188811118888888888888\n", | |
"88888888888811111188811111111888111111888888888888\n", | |
"88888888888811111118888111188881111111888888888888\n", | |
"88888888888111111111188888888111111111188888888888\n", | |
"88888888881111111111111111111111111111118888888888\n", | |
"88888888111111111111111111111111111111111188888888\n", | |
"88888111111111111111111111111111111111111111188888\n", | |
"11111111111111111111188888888111111111111111111111\n", | |
"11111111111111111118888888888881111111111111111111\n", | |
"11111111111111111888888888888888811111111111111111\n", | |
"11111111111111118888888888888888881111111111111111\n", | |
"11111111111111888888888888888888888811111111111111\n", | |
"00000000000000000000000000000000000000000000000000\n", | |
"00000000000000000000000000000000000000000000000000\n", | |
"```\n" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 3, | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
"Trying n=0\n", | |
"Trying n=100\n", | |
"Trying n=200\n", | |
"Trying n=300\n", | |
"Success\n" | |
] | |
} | |
], | |
"source": [ | |
"angent0 = 88888888888888888888881111118888888888888888888888888888888888888888811111111111188888888888888888888888888888888888811111111111111118888888888888888888888888888888881111111111111111118888888888888888888888888888888111111111111111111118888888888888888888888888888811111111888888111111118888888888888888888888888888111118888111188881111188888888888888888888888888811111888111111118881111188888888888888888888888888111188811111111118881111888888888888888888888888811111188811111111888111111888888888888888888888888111111188881111888811111118888888888888888888888811111111118888888811111111118888888888888888888881111111111111111111111111111118888888888888888881111111111111111111111111111111111888888888888811111111111111111111111111111111111111118888811111111111111111111188888888111111111111111111111111111111111111111188888888888811111111111111111111111111111111111188888888888888881111111111111111111111111111111118888888888888888881111111111111111111111111111118888888888888888888888111111111111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000\n", | |
"def angent_prime():\n", | |
" n = 0\n", | |
" while True:\n", | |
" if n % 100 == 0:\n", | |
" print(\"Trying n=%d\" % n)\n", | |
" num = angent0 + 1 + n*2\n", | |
" if isPrime(num):\n", | |
" print(\"Success\")\n", | |
" return num\n", | |
" n += 1\n", | |
"angent_result = angent_prime()" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 4, | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
"88888888888888888888881111118888888888888888888888\n", | |
"88888888888888888881111111111118888888888888888888\n", | |
"88888888888888888111111111111111188888888888888888\n", | |
"88888888888888881111111111111111118888888888888888\n", | |
"88888888888888811111111111111111111888888888888888\n", | |
"88888888888888111111118888881111111188888888888888\n", | |
"88888888888888111118888111188881111188888888888888\n", | |
"88888888888881111188811111111888111118888888888888\n", | |
"88888888888881111888111111111188811118888888888888\n", | |
"88888888888811111188811111111888111111888888888888\n", | |
"88888888888811111118888111188881111111888888888888\n", | |
"88888888888111111111188888888111111111188888888888\n", | |
"88888888881111111111111111111111111111118888888888\n", | |
"88888888111111111111111111111111111111111188888888\n", | |
"88888111111111111111111111111111111111111111188888\n", | |
"11111111111111111111188888888111111111111111111111\n", | |
"11111111111111111118888888888881111111111111111111\n", | |
"11111111111111111888888888888888811111111111111111\n", | |
"11111111111111118888888888888888881111111111111111\n", | |
"11111111111111888888888888888888888811111111111111\n", | |
"00000000000000000000000000000000000000000000000000\n", | |
"00000000000000000000000000000000000000000000000621\n", | |
"\n" | |
] | |
} | |
], | |
"source": [ | |
"# Function for pretty printing long numbers\n", | |
"def pp(num, line_len):\n", | |
" s = str(num)\n", | |
" for l in range(0,1 + len(s)//line_len):\n", | |
" print(s[line_len*l:line_len*(l+1)])\n", | |
"\n", | |
"pp(angent_result, 50)" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 5, | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
"Trying n=0\n", | |
"Trying n=100\n", | |
"Trying n=200\n", | |
"Trying n=300\n", | |
"Trying n=400\n", | |
"Trying n=500\n", | |
"Trying n=600\n", | |
"Trying n=700\n", | |
"Trying n=800\n", | |
"Trying n=900\n", | |
"Trying n=1000\n", | |
"Trying n=1100\n", | |
"Trying n=1200\n", | |
"Trying n=1300\n", | |
"Trying n=1400\n", | |
"Success\n" | |
] | |
} | |
], | |
"source": [ | |
"# Owlstone logo by a similar method. Line length 45 this time\n", | |
"owl1 = 111111111111118111111111111111111111111111111111111111111118881111111111111111111111111111111111111111111888888111111111111111111111111111111111111888111118888811111111111111111111111111111118881111111111111111111111111111111111111111188811111111111111111111111111111111111111111111111111111111111111188811111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111188888888111111111111111111118111111111188888888888888888811111111188111888111111111111111888888888888888111111188118888111111111111111111888888888888881111881118888811111111111111111111888888888888111881118888811111111111111111111188888888888811888118888881111111111111111111118888888888811888111888881111111111111111111111888888888811188111188888111111111111111111111188888888811118811111888811111111111111111111188811888811111881111188881111111111111111111111111888111111181111111888811111111111111111111111888111111111111111118881111111111111111111111881111111111111111111118811111111111111111118811111111111111111111111111111111111111111118811111111111111111111111111111111111111111188111111111111111111111111111111111111111111181111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\n", | |
"def owl_prime():\n", | |
" n = 0\n", | |
" while True:\n", | |
" if n % 100 == 0:\n", | |
" print(\"Trying n=%d\" % n)\n", | |
" num = owl1 + n*2\n", | |
" if isPrime(num):\n", | |
" print(\"Success\")\n", | |
" return num\n", | |
" n += 1\n", | |
"owl_result = owl_prime()" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 6, | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
"111111111111118111111111111111111111111111111\n", | |
"111111111111118881111111111111111111111111111\n", | |
"111111111111111888888111111111111111111111111\n", | |
"111111111111888111118888811111111111111111111\n", | |
"111111111118881111111111111111111111111111111\n", | |
"111111111188811111111111111111111111111111111\n", | |
"111111111111111111111111111111188811111111111\n", | |
"111111111111111111111111111111111111111111111\n", | |
"111111111111111111111111111111111111111111111\n", | |
"111111111111111111111111111111111111111111111\n", | |
"111111111111111111111111111111111111111111111\n", | |
"111111111111111111111111188888888111111111111\n", | |
"111111118111111111188888888888888888811111111\n", | |
"188111888111111111111111888888888888888111111\n", | |
"188118888111111111111111111888888888888881111\n", | |
"881118888811111111111111111111888888888888111\n", | |
"881118888811111111111111111111188888888888811\n", | |
"888118888881111111111111111111118888888888811\n", | |
"888111888881111111111111111111111888888888811\n", | |
"188111188888111111111111111111111188888888811\n", | |
"118811111888811111111111111111111188811888811\n", | |
"111881111188881111111111111111111111111888111\n", | |
"111181111111888811111111111111111111111888111\n", | |
"111111111111118881111111111111111111111881111\n", | |
"111111111111111118811111111111111111118811111\n", | |
"111111111111111111111111111111111111118811111\n", | |
"111111111111111111111111111111111111188111111\n", | |
"111111111111111111111111111111111111181111111\n", | |
"111111111111111111111111111111111111111111111\n", | |
"111111111111111111111111111111111111111114027\n", | |
"\n" | |
] | |
} | |
], | |
"source": [ | |
"pp(owl_result, 45)" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 7, | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
"1350\n" | |
] | |
} | |
], | |
"source": [ | |
"print(len(str(owl_result))) # TH" | |
] | |
} | |
], | |
"metadata": { | |
"kernelspec": { | |
"display_name": "Python 3", | |
"language": "python", | |
"name": "python3" | |
}, | |
"language_info": { | |
"codemirror_mode": { | |
"name": "ipython", | |
"version": 3 | |
}, | |
"file_extension": ".py", | |
"mimetype": "text/x-python", | |
"name": "python", | |
"nbconvert_exporter": "python", | |
"pygments_lexer": "ipython3", | |
"version": "3.5.1" | |
} | |
}, | |
"nbformat": 4, | |
"nbformat_minor": 2 | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment