A089771 Largest n-digit prime containing no prime substrings, or 0 if no such prime exists.

7, 89, 991, 9949, 99469, 996649, 9999481, 99990091, 999996901, 9999988049, 99999981469, 999999946849, 9999999946009, 99999999904081, 999999999946069, 9999999999944869, 99999999999884081, 999999999999984469, 9999999999999968869, 99999999999999900049, 999999999999999944009, 9999999999999999999869

Offset: 1

Author

Amarnath Murthy, Nov 23 2003

Keywords

• base
• nonn

Comments

Conjecture: No term is zero.

Links

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

Crossrefs

Cf. A089768, A033274, A089770.

Programs

Maple

cbd:= proc(n)
  local x,L,i,flag;
  L:= convert(n,base,10);
  x:= n;
  for i from nops(L) to 1 by -1 do
    if member(L[i],{2,3,5,7}) then
      flag:= true;
      if L[i] = 3 then x:= x - 10^(i-1)- (x mod 10^(i-1)) -1 else x:= x - (x mod 10^(i-1)) - 1 fi;
      return x
    fi;
  od;
 x
end proc:
nps:= proc(n) option remember;
  if n <= 10 then not isprime(n)
  else not isprime(n) and nps(floor(n/10)) and nps(n mod 10^ilog10(n))
  fi
end proc:
npps:= proc(n) local L,i,t;
  if n <= 10 then true
  else
    if n::odd then return nps(floor(n/10)) and nps(n mod 10^ilog10(n)) fi;
    for i from 1 do
      t:= floor(n/10^i);
      if t::odd then return nps(t) and nps(t mod 10^ilog10(t))
      elif t = 0 then return true
  fi od fi
end proc:
g:= proc(n) local p,i,x;
  p:= 10^n;
  do
    p:= prevprime(p);
    x:= cbd(p);
    while x <> p do
      p:= prevprime(x+1);
      x:= cbd(p)
    od;
    if npps(p) then return p fi
  od
end proc:
g(1):= 7:
map(g, [$1..30]); # Robert Israel, Aug 30 2024

Python

from sympy import isprime
from itertools import product
def c(s): return not any(isprime(int(s[i:j])) for i in range(len(s)-1, -1, -1) for j in range(len(s), i, -1) if (i, j) != (0, len(s)))
def a(n):
    if n == 1: return 7
    return next(t for p in product("986410", repeat=n-1) for last in "91" if isprime(t:=int(s:="".join(p)+last)) and c(s))
print([a(n) for n in range(1, 23)]) # Michael S. Branicky, Aug 30 2024

Extensions

More terms from David Wasserman, Oct 12 2005

More terms from Robert Israel, Aug 30 2024