Reducing Prime

Otherwise known as left-truncating primes with every suffix prime and no digit are zero. Here is the whole sequence. It was proven that 357686312646216567629137 is the last number of the sequence in 1999. Cool that math understandable to me is still being done in my lifetime. Although I’d bet that the actual proof is beyond my pay grade.

Here’s a recursive python program to print out a list of these numbers under 1 million. Unfortunately it doesn’t work on the number in question, my prime checker isn’t efficient enough.

from math import sqrt
#function to check to see if a number is prime
def prime(n):
    for i in xrange(2,int(sqrt(n))+1):
        if (n%i == 0):
            return False
        return True

#recursive function to check to see if a number continues to be prime
#as the left digit gets taken away
def reducingprime(n):
    #Stopping condition
    if n == 0:
        return True
    else:
        string_n = str(n)
        if n < 10:
            return prime(n)

        #check recursive step only if second digit isn't 0
        elif string_n[1]!='0' and prime(n):
            #this takes away the left digit
            next = n % (10**((len(str(n))-1)))
            return reducingprime(next)
        else:
            return False


for a in xrange(2,1000000):
    if reducingprime(a):
        while a > 0:
            print a," ",
            a = a%(10**((len(str(a))-1)))
        print " "

Leave a Reply

Your email address will not be published. Required fields are marked *