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, 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, 2192302476, 4400938402, 8835035284

Offset: 0

Author

Jeffrey Shallit, Nov 16 2014

Keywords

• nonn
• base

Comments

Here we only consider canonical base-2 expansions (with no leading zeros). 1 is not a prime, and neither is 0.

Examples

			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).
		

Crossrefs

Cf. A162145, A246806.

Programs

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

Extensions

More terms from Jeffrey Shallit, Nov 25 2014

a(29)-a(32) from Michael S. Branicky, Mar 26 2021

a(33)-a(35) from Jinyuan Wang, May 31 2025