A232128 Maximal number of digits that can be appended to n such that each step yields a prime.

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

Offset: 1

Author

M. F. Hasler, Nov 19 2013

Keywords

• nonn
• base

Comments

The digits are to be appended one by one as to form a chain of L = a(n) primes [p^(1),...,p^(L)], such that p^(k-1)=floor(p^(k)/10), k=1,...,L, starting from the initial value p^(0) = n which is not required to be a prime. (See A232127 for the variant restricted to prime "starting values".)

See A232129 for the largest prime obtained when starting with n.

Examples

			a(1)=9 because "1" can be extended with at most 9 digits to the right such that each extension is prime; the least one of the possible 1+9 digit primes is 1979339333, the largest one is given in A232129.
		

Links

• Robert Israel, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A232125, A232127, A232129.

Programs

Maple

f:= proc(n) local V,k;
      V:= select(isprime, [seq(10*n+k, k=[1,3,7,9])]);
      if V = [] then 0 else 1 + max(map(procname,V)) fi
end proc:
map(f, [$1..100]); # Robert Israel, Oct 16 2020

PARI

a(n)=my(m,r=[0,n]);forstep(d=1,9,2,d==5&&next;isprime(n*10+d)||next;m=[1,0]+howfar(10*n+d);m[1]>r[1]&&r=m);r \\ Note: this returns the list [a(n), minimal longest prime]

Python

from sympy import isprime, nextprime
def a(n):
    while True:
        extends, reach, maxp = -1, {n}, 0
        while len(reach) > 0:
            candidates = (int(str(e)+d) for d in "1379" for e in reach)
            reach1 = set(filter(isprime, candidates))
            extends, reach, maxp = extends+1, reach1, max({maxp}|reach1)
        return extends
print([a(n) for n in range(1, 92)]) # Michael S. Branicky, Sep 07 2021

Formula

If a(n) > 0, then there is some prime p in the range 10n+1,...,10n+9 such that a(p)=a(n)-1. If a(n)=0, then there is no prime in that range.