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,8

Links

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

Example

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.

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 *)

Prog

(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))

Crossrefs

Cf. A215417, A290175.

Sequence in context: A101941 A089313 A052998 * A344937 A354061 A318921

Adjacent sequences: A290171 A290172 A290173 * A290175 A290176 A290177

Keyword

nonn,base

Author

Felix Fröhlich, Jul 23 2017

Status

approved