A290174 Maximal number of zeros that can be inserted one-by-one between the digits of prime(n) such that the number resulting from each step remains prime.

0, 0, 0, 0, 1, 1, 1, 3, 0, 0, 0, 1, 2, 0, 0, 2, 2, 1, 2, 4, 0, 1, 0, 2, 4, 0, 0, 0, 2, 4, 0, 7, 3, 2, 3, 3, 0, 1, 2, 0, 2, 1, 3, 2, 1, 0, 2, 2, 1, 4, 0, 1, 0, 0, 0, 3, 1, 0, 2, 4, 1, 4, 0, 2, 0, 0, 1, 3, 1, 1, 0, 0, 5, 0, 1, 3, 4, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1

Offset: 1

Author

Felix Fröhlich, Jul 23 2017

Keywords

• nonn
• base

Examples

			For n = 1..4, a(n) = 0, because it is not possible to insert a 0 into the decimal expansions of 2, 3, 5, and 7 such that the resulting number is prime.
For n = 9: prime(9) = 23 and 203 is composite, so a(9) = 0.
For n = 32: prime(32) = 131 and the seven numbers 1301, 13001, 103001, 1003001, 10003001, 100030001, 1000030001 are all prime. It is not possible to insert a 0 into 1000030001 such that the resulting number is again prime and no other choice of insertions starting at 131 yields a longer sequence of primes, so a(32) = 7.
		

Links

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

Crossrefs

Cf. A215417, A290175.

Programs

Maple

f:= proc(n) local B,cands, T,m,count;
  B:= convert(ithprime(n),base,10);
  m:= nops(B)-1;
  T:= {[0$m]};
  for count from 0 do
    cands:= map(t -> seq(t + [0$k, 1$(m-k)],k=0..m-1), T);
    T:= select(t -> isprime(B[1]+add(10^(i+t[i])*B[i+1],i=1..m)), cands);
    if T = {} then return count fi
  od
end proc:
map(f, [$1..100]); # Robert Israel, Aug 04 2017

Mathematica

ins[n_] := Block[{L={}, p=10, a, b, v}, While[p <= n, a = Floor[n/p]; b = Mod[n, p]; v = 10*p*a + b; If[b >= p/10 && PrimeQ[v], AppendTo[L, v]]; p *= 10]; L]; a[n_] := Block[{p = Prime@n, k=0, w}, w = {p}; While[w != {}, w = Flatten[ins /@ w]; k++]; k-1]; Array[a, 87] (* Giovanni Resta, Jul 24 2017 *)

PARI

insertzero(num, pos) = 10*(num-num%10^pos)+(num%10^pos)
zeroprimevec_num(n) = my(w=[]); for(k=1, #Str(n)-1, my(x=insertzero(n, k)); if(ispseudoprime(x), w=concat(w, [x]))); vecsort(w, , 8)
zeroprimevec_vec(v) = my(w=[]); for(k=1, #v, w=concat(w, zeroprimevec_num(v[k]))); vecsort(w, , 8)
a(n) = my(i=0, p=prime(n), v=zeroprimevec_num(p)); while(1, if(#v==0, return(i), i++); v=zeroprimevec_vec(v))