login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A246807
Number of n-bit numbers that can be written as the concatenation of 0 or more prime numbers (everything written in base 2).
1
1, 0, 2, 2, 5, 8, 15, 33, 59, 126, 246, 494, 978, 1971, 3930, 7845, 15749, 31527, 63349, 126986, 254880, 511468, 1026348, 2060633, 4135808, 8303940, 16669925, 33472231, 67201664, 134930088, 270895845, 543915707, 1091923726
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
Sequence in context: A340249 A377628 A006367 * A077902 A005834 A367717
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