Skip to content

Instantly share code, notes, and snippets.

@Llibyddap
Created August 4, 2018 03:02
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Llibyddap/eac914829c21a8aaae14110c8d9fea7f to your computer and use it in GitHub Desktop.
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.
# 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
'''
@Llibyddap
Copy link
Author

Future modifications...

a) Try multithreading on prime calculations
b) Try multiprocessor on prime calculations

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment