login
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.
4
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
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
Sequence in context: A101941 A089313 A052998 * A344937 A354061 A318921
KEYWORD
nonn,base
AUTHOR
Felix Fröhlich, Jul 23 2017
STATUS
approved