Created
August 4, 2018 03:02
-
-
Save Llibyddap/eac914829c21a8aaae14110c8d9fea7f to your computer and use it in GitHub Desktop.
Based on this youtube video... https://youtu.be/azL5ehbw_24. Which deals with left truncating 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
# Title: left_trunc_prime.py | |
# Description: This is a generator of left truncating prime numbers. Each | |
# number in the 'all_primes' list will have the property of | |
# being a prime number after the left most digit is truncated. | |
# For example, the prime number 137 is such a left truncating | |
# prime. If you truncate the 1, the number 37 is also a prime | |
# number, if you truncate the 3, the number 7 is a prime | |
# number. | |
# | |
# If run successfully, the result should be a list of 1,442 | |
# endpoints (largest base numbers that cannot have another | |
# digit added to the left and still meet the defintion of a | |
# left truncating prime). The largest endpoint should be | |
# 357,686,312,646,216,567,629,137. | |
# | |
# The program was run using single core processor, single | |
# threading on a 3.2GHz Intel Core i5 Mac. During the run | |
# time, the single core processor ran >95%. Results are | |
# appended at the end. | |
# Author: Bill Armstrong | |
# Date: July 29, 2018 | |
# Version: 1.0 | |
# Usage: python left_trunc_prime.py | |
# Notes: | |
# Python_version: 3.6.4 | |
#################################################################################### | |
import math | |
import time | |
def is_prime(num): | |
if(num==1): | |
return False | |
if(num==2): | |
return True | |
if(num%2==0): | |
return False | |
i = 3 | |
while(i<math.sqrt(num)+1): | |
if num%i==0: | |
return False | |
i += 2 | |
return True | |
primes = [2, 3, 5, 7] | |
endpoints = [] | |
all_primes = [] | |
num = [1, 2, 3, 4, 5, 6, 7, 8, 9] | |
t = time.time() | |
while len(primes)>0: | |
ep = True | |
base = primes.pop(0) | |
all_primes.append(base) | |
for leftnum in num: | |
test_num = int(str(leftnum) + str(base)) | |
if is_prime(test_num): | |
print("prime found: ", test_num) | |
primes.append(test_num) | |
all_primes.append(test_num) | |
ep = False | |
if ep: | |
endpoints.append(base) | |
print("endpoint found: ", base, " Total endpoints: ", | |
len(endpoints), " Total primes left to check: ", len(primes)) | |
print ("*** COMPLETE ***") | |
print ("Found", len(endpoints), "endpoints.") | |
print ("With a total of", len(all_primes), | |
"prime numbers that have the Left Trunc property.") | |
print ("The largest Left Trunc prime was: ", endpoints[-1]) | |
print ("Total processing time was", (time.time()- t), ".") | |
# Terminal Output of lines 54 - 58 | |
''' | |
*** COMPLETE *** | |
Found 1442 endpoints. | |
With a total of 8516 prime numbers that have the Left Trunc property. | |
The largest Left Trunc prime was: 357686312646216567629137 | |
Total processing time was 440014.46286058426 . | |
Largest left truc number: 357,686,312,646,216,567,629,137 | |
Total time: 5 days, 2 hours, 13 minutes, 34.46286058425903 seconds | |
The last 5 endpoints: | |
endpoint found: 315396334245663786197 Total endpoints: 1437 Total primes left to check: 5 | |
endpoint found: 666276812967623946997 Total endpoints: 1438 Total primes left to check: 4 | |
prime found: 96686312646216567629137 | |
prime found: 57686312646216567629137 | |
prime found: 95918918997653319693967 | |
endpoint found: 9918918997653319693967 Total endpoints: 1439 Total primes left to check: 3 | |
endpoint found: 96686312646216567629137 Total endpoints: 1440 Total primes left to check: 2 | |
prime found: 357686312646216567629137 | |
endpoint found: 95918918997653319693967 Total endpoints: 1441 Total primes left to check: 1 | |
endpoint found: 357686312646216567629137 Total endpoints: 1442 Total primes left to check: 0 | |
''' |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Future modifications...
a) Try multithreading on prime calculations
b) Try multiprocessor on prime calculations