cp's OEIS Frontend

A246807 Number of n-bit numbers that can be written as the concatenation of 0 or more prime numbers (everything written in base 2).

%I A246807 #41 May 31 2025 19:53:23
%S A246807 1,0,2,2,5,8,15,33,59,126,246,494,978,1971,3930,7845,15749,31527,
%T A246807 63349,126986,254880,511468,1026348,2060633,4135808,8303940,16669925,
%U A246807 33472231,67201664,134930088,270895845,543915707,1091923726,2192302476,4400938402,8835035284
%N A246807 Number of n-bit numbers that can be written as the concatenation of 0 or more prime numbers (everything written in base 2).
%C A246807 Here we only consider canonical base-2 expansions (with no leading zeros). 1 is not a prime, and neither is 0.
%e A246807 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).
%o A246807 (Python)
%o A246807 from sympy import isprime, primerange
%o A246807 from functools import lru_cache
%o A246807 @lru_cache(maxsize=None)
%o A246807 def ok(n):
%o A246807   if n%4 == 0: return False
%o A246807   if isprime(n): return True
%o A246807   b = bin(n)[2:]
%o A246807   for i in range(2, len(b)-1):
%o A246807     if b[i] != '0' and isprime(int(b[:i], 2)) and ok(int(b[i:], 2)):
%o A246807       return True
%o A246807   return False
%o A246807 def a(n):
%o A246807   return 1 if n == 0 else sum(1 for m in range(2**(n-1), 2**n) if ok(m))
%o A246807 print([a(n) for n in range(21)]) # _Michael S. Branicky_, Mar 26 2021
%Y A246807 Cf. A162145, A246806.
%K A246807 nonn,base
%O A246807 0,3
%A A246807 _Jeffrey Shallit_, Nov 16 2014
%E A246807 More terms from _Jeffrey Shallit_, Nov 25 2014
%E A246807 a(29)-a(32) from _Michael S. Branicky_, Mar 26 2021
%E A246807 a(33)-a(35) from _Jinyuan Wang_, May 31 2025