A380788 Numbers with a prime number of binary digits.

2, 3, 4, 5, 6, 7, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106

Offset: 1

Author

Michael S. Branicky, Feb 03 2025

Keywords

• nonn
• base
• easy

Examples

			4 is a term since its binary representation has 3 bits, a prime.
64 is a term since its binary representation has 7 bits, a prime.
		

Links

• Michael S. Branicky, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A272441, A053738.

Programs

Mathematica

Select[Range[200], PrimeQ[BitLength[#]] &] (* Paolo Xausa, Feb 03 2025 *)

Python

from sympy import isprime
def ok(n): return isprime(n.bit_length())
print([k for k in range(150) if ok(k)])

Python

# faster for initial segment of sequence
from itertools import islice
from sympy import isprime, nextprime
def agen(): # generator of terms
    d = 2
    while True:
        yield from (i for i in range(2**(d-1), 2**d))
        d = nextprime(d)
print(list(islice(agen(), 65)))

Python

from sympy import primerange
def A380788(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = kmax >> 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return n+x-sum(min(x,(1<Chai Wah Wu, Feb 03 2025