MathUpdate tweeted this afternoon that

Any number made by removing the first n digits of 646216567629137 is still prime.

and links to sequence A012885 in the Online Encyclopedia of Integer Sequences (OEIS). The OEIS heading for the sequence is

Suffixes of 357686312646216567629137 (all primes)

which implies you can start with an even larger number, cutting off the first digit each time and producing a sequence of primes.

The following Python code verifies that this is indeed the case.

from sympy.ntheory import isprime
x = "357686312646216567629137"
while x:
print isprime(int(x))
x = x[1:]

**Update**: lucio wrote a program to show that the prime given here is the longest one with the suffix property.

def extend_prime(n, result):
for i in range(10):
nn = int(str(i) + str(n))
if nn == n: continue
if isprime(nn):
result.append(nn)
extend_prime(nn, result)
return result
print "Max Prefix Prime:", max(extend_prime("", []))

One minor suggestion: by using `range(1, 10)`

rather than `range(10)`

above, i.e. eliminating 0, the line `if nn == n: continue`

could be eliminated.

Instead of calling `max`

, you could call `len`

to find that there are 4260 suffix primes.

Here’s a list of all suffix primes created by the code above and sorting the output.

## Other special primes

Wow. Can a digit be added to 357686312646216567629137 to generator another prime, or that a terminal end of this prime suffix sequence?

No, that’s as far as you can go with this sequence. Maybe there’s another line that goes longer, but not this one.

Theres no other sequence, this one is the longest one :)

Sorry about the mess.

Here’s a nicely formatted and colored pastebin: http://pastebin.ubuntu.com/5609377/

[JDC: I edited the original comment to format correctly.]

Is 103 a suffix prime or not? If zeroes are allowed, the longest suffix prime claim is harder to establish..

It might be helpful to note we are talking about base 10 here. There are more and probably bigger suffix primes in other bases.

You expect the number of suffix primes to be finite based on the prime number theorem. If N(d) is the number of e-digit suffix primes then (very roughly) one would expect the function to behave something like N(d+1) ~ k N(d) /(d+1), where k is about 9/log(10) = (roughly 4). Don’t take this

too seriously — but it’s atleast shows that N(d) should grow for awhile and then start diminishing rapidly as d gets large enough. The back-of-the-envelope estimate for the number of digits of largest suffix prime is 10, which is off by a factor of a little more than 2, but not too bad given the crudity of the approximation.

In Haskell,

import Math.NumberTheory.Primes.Testing (isPrime)

primeSuffixList = concat $ takeWhile (not . null) $ iterate (>>= prefDigit) $ filter isPrime [1..9]

prefDigit n = [p | d > print (last primeSuffixList)

then

$ ghc -O prime-suffix.hs

$ time ./prime-suffix

Largest: 357686312646216567629137

user 0m0.328s

In Perl 6:

sub next-suffix-primes(@suffix-primes) {

(1..9 X~ @suffix-primes).grep(*.Int.is-prime);

}

`my @suffix-primes = next-suffix-primes([""]);`

while @suffix-primes {

say @suffix-primes;

@suffix-primes = next-suffix-primes(@suffix-primes);

}

Python http://pastie.org/6473850 different bases:

BASE 2 | No prefix primes

BASE 3 | Max Prefix Prime: 212 , different: 1

BASE 4 | Max Prefix Prime: 333323 , different: 5

BASE 5 | Max Prefix Prime: 222232 , different: 4

BASE 6 | Max Prefix Prime: 14141511414451435 , different: 148

BASE 7 | Max Prefix Prime: 6642623 , different: 7

BASE 8 | Max Prefix Prime: 313636165537775 , different: 144

BASE 9 | Max Prefix Prime: 4284484465 , different: 37

BASE 10 | Max Prefix Prime: 357686312646216567629137 , different: 1442

BASE 11 | Max Prefix Prime: a68822827 , different: 26

BASE 12 | Max Prefix Prime: 471a34a164259ba16b324ab8a32b7817 , different: 60026

BASE 13 | Max Prefix Prime: cc4c8c65 , different: 33

BASE 14 | Max Prefix Prime: d967ccd63388522619883a7d23 , different: 12166

BASE 15 | Max Prefix Prime: 6c6c2ce2ceeea4826e642b , different: 3266

BASE 16 | Max Prefix Prime: dbc7fba24fe6aec462abf63b3 , different: 9925

BASE 17 | Max Prefix Prime: 6c66cc4cc83 , different: 138

Oh, just found link for the code:

http://rosettacode.org/wiki/Find_largest_left_truncatable_prime_in_a_given_base

I put my three-liner, tweaked to do any base and not print/read internally, in a gist:

suffix-primes.hs

This includes a main routine to make some tables, which I found interesting. There seem to be some theorems lurking. Trivially, using P(b) for the set of suffix primes base b, if c is a factor of b then P(c) is a subset of P(b). But a lot more structure seems apparent. And what’s up with base 18?

$ ./suffix-primes --all

Base Number Largest

3 3 23

4 16 4091

5 15 7817

6 454 4836525320399

7 22 817337

8 446 14005650767869

9 108 1676456897

10 4260 357686312646216567629137

11 75 2276005673

12 170053 13092430647736190817303130065827539

13 100 812751503

14 34393 615419590422100474355767356763

15 9357 34068645705927662447286191

16 27982 1088303707153521644968345559987

17 362 13563641583101

18 14979714 571933398724668544269594979167602382822769202133808087

19 685 546207129080421139

20 3062899 1073289911449776273800623217566610940096241078373

21 59131 391461911766647707547123429659688417

22 1599447 33389741556593821170176571348673618833349516314271

23 1372 116516557991412919458949

^C

$ ./suffix-primes --prime

Base Number Largest

3 3 23

5 15 7817

7 22 817337

11 75 2276005673

13 100 812751503

17 362 13563641583101

19 685 546207129080421139

23 1372 116516557991412919458949

29 3926 4300289072819254369986567661

31 11314 645157007060845985903112107793191

37 31898 1227906370578703713220305155209183002341

41 62930 30936779512712351021129939907890870072806919

43 132356 103002723043391997634166979685453834058870099

47 196709 18846885009617750406310165885751950752131092800539

^C

53 607427 1927313691687008616062631595723184712591552207338172661

59 1870270 4077508027639490147990095553206762226024137866036348886452326969

61 3680378 238089544539042409591603000630200657940967296327557776119980057913