Suffix primes

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 novelty primes:

14 thoughts on “Suffix primes

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

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

  3. 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("", []))
    
    Max Prefix Prime: 357686312646216567629137
    
  4. Is 103 a suffix prime or not? If zeroes are allowed, the longest suffix prime claim is harder to establish..

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

  6. 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.

  7. 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

  8. 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);
    }

  9. 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

  10. 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


  11. 53 607427 1927313691687008616062631595723184712591552207338172661
    59 1870270 4077508027639490147990095553206762226024137866036348886452326969
    61 3680378 238089544539042409591603000630200657940967296327557776119980057913

Leave a Reply

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>