login
A096235
Number of n-bit base-2 deletable primes.
34
0, 2, 2, 2, 3, 6, 6, 11, 18, 31, 49, 87, 155, 253, 427, 781, 1473, 2703, 5094, 9592, 18376, 35100, 67183, 129119, 249489, 482224, 930633, 1803598, 3502353, 6813094, 13271996, 25892906, 50583039
OFFSET
1,2
COMMENTS
A prime p is a base-b deletable prime if when written in base b it has the property that removing some digit leaves either the empty string or another deletable prime. However, in base 2 we adopt the convention that 2 = 10 and 3 = 11 are deletable.
Deleting a digit cannot leave any leading zeros in the new string. For example, deleting the 2 in 2003 to obtain 003 is not allowed.
EXAMPLE
d base-2 d-digit deletable primes
2 2=10, 3=11
3 5=101, 7=111
4 11=1011, 13=1101
5 19=10011, 23=10111, 29=11101
6 37=100101, 43=101011, 47=101111, 53=110101, 59=111011, 61=111101
7 73=1001001, 79=1001111, 83=1010011, 101=1100101, 107=1101011, 109=1101101
MATHEMATICA
a = {0, 2}; d = {2, 3};
For[n = 3, n <= 15, n++,
p = Select[Range[2^(n - 1), 2^n - 1], PrimeQ[#] &];
ct = 0;
For[i = 1, i <= Length[p], i++,
c = IntegerDigits[p[[i]], 2];
For[j = 1, j <= n, j++,
t = Delete[c, j];
If[t[[1]] == 0, Continue[]];
If[MemberQ[d, FromDigits[t, 2]], AppendTo[d, p[[i]]]; ct++;
Break[]]]];
AppendTo[a, ct]];
a (* Robert Price, Nov 11 2018 *)
PROG
(Python)
from sympy import isprime
def ok(n, prevset):
if not isprime(n): return False
b = bin(n)[2:]
bi = (b[:i]+b[i+1:] for i in range(len(b)))
return any(t[0] != '0' and int(t, 2) in prevset for t in bi)
def afind(terms):
s, snxt = {2, 3}, set()
print("0, ", len(s), end=", ")
for n in range(3, terms+1):
for i in range(2**(n-1), 2**n):
if ok(i, s):
snxt.add(i)
s, snxt = snxt, set()
print(len(s), end=", ")
afind(20) # Michael S. Branicky, Jan 14 2022
CROSSREFS
KEYWORD
nonn,base,more
AUTHOR
Michael Kleber, Feb 28 2003
EXTENSIONS
a(19)-a(30) from Ryan Propper, Jul 18 2005
a(31)-a(33) from Michael S. Branicky, Jan 14 2022
STATUS
approved