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