A232127 Maximal number of digits that can be appended to prime(n) preserving primality at each step.

7, 7, 7, 7, 1, 6, 3, 8, 6, 6, 3, 6, 1, 5, 3, 0, 6, 5, 5, 4, 6, 1, 1, 0, 2, 4, 9, 0, 4, 0, 5, 1, 1, 5, 3, 1, 2, 1, 0, 2, 0, 4, 2, 3, 7, 5, 2, 3, 4, 3, 5, 4, 5, 0, 4, 3, 4, 5, 3, 1, 1, 5, 1, 2, 2, 0, 6, 3, 0, 4, 5, 2, 4, 5, 1, 2, 0, 0, 3, 10, 0, 3, 0, 2, 4, 0, 3, 0, 0, 6

Offset: 1

Author

M. F. Hasler and Michel Marcus, Nov 19 2013

Keywords

• nonn
• base

Comments

Consider chains (p^(0),p^(1),p^(2),...p^(L)) of primes such that p^(k-1) = floor(p^(k)/10), or otherwise said, p^(k+1) is obtained from p^(k) by appending a digit. Then a(n) is one less than the number of primes in the longest possible such chain with p^(0)=prime(n).

Examples

			a(14)=5 because for prime(14)=43, one can add at most 5 digits to the right preserving primality at each step: 439 is prime, 4391 is prime, 43913 is prime, 439133 is prime, 4391339 is prime. There is no longer chain possible starting with 43.
		

Links

• Michael S. Branicky, Table of n, a(n) for n = 1..10000
• Archimedes' Lab, What's Special About This Number?, section about 43.

Crossrefs

Cf. A232125.

Programs

PARI

{howfar(p)=my(m);forstep(d=1,9,2,d==5&&next;isprime(p*10+d)||next;m=max(1+howfar(10*p+d),m));m}

Python

from sympy import isprime, prime
def a(n):
  pn = prime(n); ftr = {pn}; ext = 0
  while len(ftr) > 0:
    r1 = set(filter(isprime, (int(str(e)+d) for d in "1379" for e in ftr)))
    ext, ftr = ext+1, r1
  return ext - 1
print([a(n) for n in range(1, 91)]) # Michael S. Branicky, Jul 07 2021

Python

# faster version for initial segment of sequence
from sympy import isprime, prime, primerange
def aupton(terms):
  alst = []
  for p in primerange(1, prime(terms)+1):
    r = {p}; e = 0
    while len(r) > 0:
      r1 = set(filter(isprime, (int(str(e)+d) for d in "1379" for e in r)))
      e, r = e+1, r1
    alst.append(e - 1)
  return alst
print(aupton(90)) # Michael S. Branicky, Jul 07 2021

Formula

a(n)=A232128(A000040(n)).

a(n) > 0 if and only if there is a prime p between 10*prime(n)+1 and 10*prime(n)+9, in which case a(n) >= 1+a(primepi(p))

a(n) = max { L in N | exists (p[0],...,p[L]) in P^(L+1) (P = the primes A000040), such that p[0] = prime(n) and for k=1,...,L : p[k-1] = floor(p[k]/10) }