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.
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 :)
from sympy.ntheory import isprime 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("", []))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