OFFSET
0,3
COMMENTS
Here we only consider canonical base-2 expansions (with no leading zeros). 1 is not a prime, and neither is 0.
EXAMPLE
For n = 5 the 8 solutions counted include the primes {17,19,23,29,31} between 16 and 31, and also the numbers 21 (10.101), 22 (101.10), and 30 (111.10).
PROG
(Python)
from sympy import isprime, primerange
from functools import lru_cache
@lru_cache(maxsize=None)
def ok(n):
if n%4 == 0: return False
if isprime(n): return True
b = bin(n)[2:]
for i in range(2, len(b)-1):
if b[i] != '0' and isprime(int(b[:i], 2)) and ok(int(b[i:], 2)):
return True
return False
def a(n):
return 1 if n == 0 else sum(1 for m in range(2**(n-1), 2**n) if ok(m))
print([a(n) for n in range(21)]) # Michael S. Branicky, Mar 26 2021
CROSSREFS
KEYWORD
nonn,base,more
AUTHOR
Jeffrey Shallit, Nov 16 2014
EXTENSIONS
More terms from Jeffrey Shallit, Nov 25 2014
a(29)-a(32) from Michael S. Branicky, Mar 26 2021
STATUS
approved