login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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 A052531

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 18 15:25 EDT 2021. Contains 343995 sequences. (Running on oeis4.)