Russian Doll Prime Numbers

Russian Doll Prime Numbers

As a child, weren’t you in wonder of Russian Dolls, and where you learnt how the dolls fitted into each other? I bet you still pass a Russian Doll at a market, and remember the time you played with them, and perhaps even think about buying one.

And so where else can we find Russian Dolls? Well, within prime numbers we have a similar concept — known as truncatable primes — and where we can peal numbers off from the left or right, and still reveal a prime number.

A left-truncatable prime (or Russian Doll prime) is defined as a prime number, that when we take away the leading left digit successively, it still reveals a prime number. For example, 197 is a left-truncable prime as 197, 97 and 7 are primes, but 311 is not left-truncatable prime as 331 is a prime, 31 is a prime, but 1 is not a prime. A right-truncatable prime is defined as a prime number which, when taking away the end right digit successively, reveals numbers which are prime. 379 is an example of a right-truncatable prime, since 379, 37, and 3 are all prime.

A value of 5,555 reveals the following [here]:

Maximum prime:  5531

Left-truncatable primes:
[2, 3, 5, 7, 13, 17, 23, 37, 43, 47, 53, 67, 73, 83, 97, 113, 137, 167, 173, 197, 223, 283, 313, 317, 337, 347, 353, 367, 373, 383, 397, 443, 467, 523, 547, 613, 617, 643, 647, 653, 673, 683, 743, 773, 797, 823, 853, 883, 937, 947, 953, 967, 983, 997, 1223, 1283, 1367, 1373, 1523, 1613, 1823, 1997, 2113, 2137, 2347, 2383, 2467, 2617, 2647, 2683, 2797, 2953, 3137, 3167, 3313, 3347, 3373, 3467, 3547, 3613, 3617, 3643, 3673, 3797, 3823, 3853, 3947, 3967, 4283, 4337, 4373, 4397, 4523, 4547, 4643, 4673, 4937, 4967, 5113, 5167, 5197, 5347, 5443]

Right-truncatable primes:
[2, 3, 5, 7, 23, 29, 31, 37, 53, 59, 71, 73, 79, 233, 239, 293, 311, 313, 317, 373, 379, 593, 599, 719, 733, 739, 797, 2333, 2339, 2393, 2399, 2939, 3119, 3137, 3733, 3739, 3793, 3797]

Left- and Right-truncatable primes:
[2, 3, 5, 7, 23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797]

The numbers that are left- and right-trucated primes are known as two-sided primes and are: { 2, 3, 5, 7, 23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797}.

The following outlines some sample code [here]:

from sympy import sieve
import sys

n=4201

if (len(sys.argv)>1):
 n=int(sys.argv[1])

if (n>10000): sys.Exit(1)

truncateleft=[]
truncateright=[]

primelist = [str(x) for x in list(sieve.primerange(1, n))]
primeset = set(primelist)

for n in primelist:
  alltruncs = set(n[i:] for i in range(len(n)))
  if alltruncs.issubset(primeset):
    truncateleft.append(int(n))

print ("Maximum prime: ",n)

print ("\nLeft-truncatable primes:")
print (truncateleft)

for n in primelist:
  alltruncs = set(n[:i+1] for i in range(len(n)))
  if alltruncs.issubset(primeset):
    truncateright.append(int(n))

print ("\nRight-truncatable primes:")
print (truncateright)

print ("\nLeft- and Right-truncatable primes:")

res = set(truncateleft).intersection(set(truncateright))
print (sorted(res, key=int))

And here is the running code:

Oh, you have gotta love Russian Dolls, Python, and prime numbers!