357686312646216567629137 and Friends

Many people close to FWPhys are aware of, in possession of, or about to possess, our first STEM merchandise, the Left Truncatable Prime Pencil. Printed on it is the largest base-10 number that remains prime as you remove digits from the left side by means of sharpening the pencil.

US$3 a pair.

It’s common knowledge and there’s a Wikipedia page dedicated to it. No matter, I wish to post my own code used to generate it. There’s no algorithmic elegance, just a regular tree search.

####################

Base = 10

####################
import numpy as np
import math

import time

# Fast
def Prime(n):
    if n == 0 or n == 1:
        return False
    
    elif n % 2 == 0 and n > 2: 
        return False
    
    return all(n % i for i in range(3, int(math.sqrt(n)) + 1, 2))


NumberLibrary = []

# Initialization
Dig = 0

# Start the tree by finding the prime first digits
for i in range(Base):
    
    if Prime(i):
        NumberLibrary.append(i)

# Iterative tree search
Primality = True

while Primality:
    
    Timestart = time.time()

    Dig += 1
    print(f'Searching and testing digit #{Dig+1}')
    
    Multiplier = Base ** Dig

    NewNumberLibrary = []
    for n in NumberLibrary:
    
        for i in range(1,Base):
            NewNum = n + i * Multiplier
            if Prime(NewNum):
                NewNumberLibrary.append(NewNum)
                
                
    if NewNumberLibrary == []:
        Primality = False;
        print(f'Failed! Time taken: {time.time()-Timestart:.3g} s.')
        print(f"Largest left truncatable prime length is {Dig}")
        
        
    else:
        
        NumberLibrary = NewNumberLibrary
        for k in NumberLibrary:
            if Base != 10:
                print(f"{np.base_repr(k,base = Base)} (base {Base}) = {k} (base 10)")
            if Base == 10:
                print(k)
                
        print(f"{len(NumberLibrary)} candidate(s) found. Time taken: {time.time()-Timestart:.3g} s.")
            
        print("\n")
        
       

And just for fun, here are some lesser left-truncatable primes in other base systems.

BaseNumbersValue in Base 10
321223
4321223
233323
333323
3691
3067
4091
52222327817
6141415114144514354836525320399
76642623817337
831363616553777514005650767869
92486266212
4284484465
2462868287
988642271
1676456897
977306389
10357686312646216567629137
11CPU Meltdown
12CPU Meltdown

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.