A374403 Number of n-bit primes.

0, 2, 2, 2, 5, 7, 13, 23, 43, 75, 137, 255, 464, 872, 1612, 3030, 5709, 10749, 20390, 38635, 73586, 140336, 268216, 513708, 985818, 1894120, 3645744, 7027290, 13561907, 26207278, 50697537, 98182656, 190335585, 369323305, 717267168, 1394192236, 2712103833, 5279763824

Offset: 1

Author

Jon E. Schoenfield, Jul 07 2024

Keywords

• nonn

Comments

Number of primes whose binary expansion is n digits long.

a(n) is the number of primes in the half-open interval [2^(n-1), 2^n).

First differences of A185192.

See A007053 for additional information.

Examples

			a(1) = 0 because neither 0 nor 1 is a prime.
a(2) = 2 because the 2-bit primes are 10_2 = 2 and 11_2 = 3.
a(4) = 2 because the 4-bit primes are 1011_2 = 11 and 1101_2 = 13.
		

Crossrefs

Essentially the same as A036378 and A162145.

Cf. A185192 (partial sums).

Cf. A000720, A007053.

Programs

Mathematica

a[n_]:=Sum[Boole[PrimeQ[i]],{i,2^(n-1),2^n-1}]; Array[a,38] (* Stefano Spezia, Jul 07 2024 *)

Formula

a(n) = A162145(n) for n >= 2. - Amiram Eldar, Jul 08 2024