A036386 - OEIS

A036386

Number of prime powers (p^2, p^3, ...) <= 2^n.

0, 1, 2, 4, 7, 9, 13, 16, 20, 26, 31, 40, 50, 61, 78, 93, 119, 150, 189, 242, 310, 400, 525, 684, 900, 1190, 1581, 2117, 2836, 3807, 5136, 6948, 9425, 12811, 17437, 23788, 32517, 44512, 60971, 83640, 114899, 157948, 217336, 299360, 412635, 569193, 785753, 1085319, 1500140, 2074794, 2870849, 3974425, 5504966

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

LINKS

Amiram Eldar, Table of n, a(n) for n = 1..150 (terms 1..112 from Hiroaki Yamanouchi, terms 113..125 from Ray Chandler)

Index entries for sequences related to numbers of primes in various ranges.

FORMULA

a(n) = Sum_{j=2..n+1} pi(floor(2^(n/j))). The summation starts with squares (j=2); for arbitrary range (=y), the y^(1/j) argument has to be used.

EXAMPLE

For n = 6, there are 9 prime powers not exceeding 2^6 = 64: 4, 8, 9, 16, 25, 27, 32, 49, 64, so a(6) = 9.

For n = 25, a(25) = 900, pi(5792) + pi(322) + pi(76) + pi(32) + pi(17) + pi(11) + pi(8) + pi(6) + pi(5) + pi(4) + pi(4) + pi(3) + pi(3) + pi(3) + pi(2) + pi(2) + pi(2) + pi(2) + pi(2) + pi(2) + pi(2) + pi(2) + pi(2) + pi(2) + pi(1) = 760 + 66 + 21 + 11 + 7 + 5 + 4 + 3 + 3 + 2 + 2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 0 = 900.

MATHEMATICA

f[n_] := Length@ Union@ Flatten@ Table[ Prime[j]^k, {k, 2, n + 1}, {j, PrimePi[2^(n/k)]}]; Array[f, 46] (* Robert G. Wilson v, Jul 08 2011 *)

PROG

(Python)

from sympy import primepi, integer_nthroot

def A036386(n):

m = 1<<n

return sum(primepi(integer_nthroot(m, j)[0]) for j in range(2, n+2)) # Chai Wah Wu, Jan 23 2025

CROSSREFS