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

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.

Links

Table of n, a(n) for n=0..32.

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

Cf. A162145, A246806.

Sequence in context: A042982 A340249 A006367 * A077902 A005834 A367717

Adjacent sequences: A246804 A246805 A246806 * A246808 A246809 A246810

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