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

Offset

1,3

Links

Ray Chandler, Table of n, a(n) for n = 1..125 (first 112 terms from Hiroaki Yamanouchi)

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

The 9 prime powers not exceeding 64 are 4, 8, 9, 16, 25, 27, 32, 49, 64.
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.

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 *)

Crossrefs

Cf. A007053, A029837, A036378-A036390.

Sequence in context: A129259 A077597 A183873 * A280417 A099847 A014817

Adjacent sequences: A036383 A036384 A036385 * A036387 A036388 A036389

Keyword

nonn

Author

Labos Elemer

Extensions

More terms from Labos Elemer, May 07 2001

Terms a(47) and beyond from Hiroaki Yamanouchi, Nov 15 2016

Status

approved