A060967 -id:A060967 - cp's OEIS frontend

A007053 Number of primes <= 2^n.

0, 1, 2, 4, 6, 11, 18, 31, 54, 97, 172, 309, 564, 1028, 1900, 3512, 6542, 12251, 23000, 43390, 82025, 155611, 295947, 564163, 1077871, 2063689, 3957809, 7603553, 14630843, 28192750, 54400028, 105097565, 203280221, 393615806, 762939111, 1480206279, 2874398515, 5586502348, 10866266172, 21151907950, 41203088796, 80316571436, 156661034233, 305761713237, 597116381732, 1166746786182, 2280998753949, 4461632979717, 8731188863470, 17094432576778, 33483379603407, 65612899915304, 128625503610475

Offset: 0

N. J. A. Sloane, Mira Bernstein, Robert G. Wilson v, S. W. Golomb

Conjecture: The number 4 is the only perfect power in this sequence. In other words, it is impossible to have a(n) = x^m for some integers n > 3, m > 1 and x > 1. - Zhi-Wei Sun, Sep 30 2015

			pi(2^3)=4 since first 4 primes are 2,3,5,7 all <= 2^3 = 8.

Jens Franke et al., pi(10^24), Posting to the Number Theory Mailing List, Jul 29 2010.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

David Baugh, Table of n, a(n) for n = 0..92 (terms n = 87..92 found using Kim Walisch's primecount program, terms n = 0..86 from Charles R Greathouse IV and Douglas B. Staple, [a(0)-a(75) from Tomás Oliveira e Silva, a(76)-a(77) from Jens Franke et al., Jul 29 2010, a(78)-a(80) from Jens Franke et al. on the Riemann Hypothesis, verified unconditionally by Douglas B. Staple, and a(81)-a(86) from Douglas B. Staple])
Andrew R. Booker, The Nth Prime Page
S. W. Golomb, Letter to N. J. A. Sloane, Jul. 1991
Thomas R. Nicely, Some Results of Computational Research in Prime Numbers
Thomas R. Nicely, Some Results of Computational Research in Prime Numbers [Local copy, pdf only]
Tomás Oliveira e Silva, Tables of values of pi(x) and of pi2(x)
Tomás Oliveira e Silva, Computing pi(x): the combinatorial method, Revista Do Detua, Vol. 4, No 6, March 2006.
Douglas B. Staple, The combinatorial algorithm for computing pi(x), arXiv:1503.01839 [math.NT], 2015.
Index entries for sequences related to numbers of primes in various ranges

Cf. A006880, A036378.

Table[PrimePi[2^n], {n, 0, 46}] (* Robert G. Wilson v *)

a(n) = primepi(1<John W. Nicholson, May 16 2011

a(n) = A060967(2n). - R. J. Mathar, Sep 15 2012

More terms from Jud McCranie
Extended to n = 52 by Warren D. Smith, Dec 11 2000, computed with Meissel-Lehmer-Legendre inclusion exclusion formula code he wrote back in 1985, recently re-run.
Extended to n = 86 by Douglas B. Staple, Dec 18 2014

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

Original entry on oeis.org

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

Labos Elemer

nonn

			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.

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.

Cf. A000720, A007053, A029837, A036378-A036390, A060967, A060969, A060970, A060971, A122121, A246547.

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

from sympy import primepi, integer_nthroot
def A036386(n):
    m = 1<Chai Wah Wu, Jan 23 2025

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.

More terms from Labos Elemer, May 07 2001

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

A145592 a(n)=number of numbers removed in each step of Eratosthenes's sieve for 2^14.

Original entry on oeis.org

8191, 2730, 1091, 623, 340, 260, 182, 154, 121, 94, 89, 74, 66, 62, 55, 48, 43, 39, 35, 31, 28, 25, 23, 19, 15, 12, 11, 9, 7, 5, 1

Offset: 1

Artur Jasinski with assistance from Bob Hanlon (hanlonr(AT)cox.net), Oct 14 2008

Number of steps in Eratosthenes's sieve for 2^n is A060967(n).

Number of primes less than 2^14 is equal to 2^14 - (sum all of numbers in this sequence) - 1 = A007053(14).

Cf. A006880, A122121, A145532-A145540, A145583-A145592.

f3[k_Integer?Positive, i_Integer?Positive] := Module[{f, m, r, p}, p = Transpose[{r = Range[2, i], Prime[r]}];f[x_] := Catch[Fold[If[Mod[x, #2[[2]]] == 0, Throw[m[ #2[[1]]] = m[ #2[[1]]] + 1], #1] &, If[Mod[x, 2] == 0, Throw[m[1] = m[1] + 1]], p]]; Table[m[n] = -1, {n, i}]; f /@ Range[k]; Table[m[n], {n, i}]];nn = 14; kk = PrimePi[Sqrt[2^nn]]; t3 = f3[2^nn, kk] (* Bob Hanlon (hanlonr(AT)cox.net) *)

A060969 Number of cubes of primes <= 2^n.

Original entry on oeis.org

0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 8, 9, 11, 12, 15, 18, 22, 26, 31, 37, 46, 54, 66, 79, 97, 117, 141, 172, 209, 257, 309, 376, 457, 564, 687, 842, 1028, 1266, 1549, 1900, 2327, 2861, 3512, 4323, 5320, 6542, 8072, 9936, 12251, 15104, 18640, 23000, 28428

Offset: 0

Labos Elemer, May 09 2001

nonn

			For n = 10, the cubes of primes not exceeding 2^10 = 1024 are 8, 27, 125, 343, so a(10) = 4.

Cf. A000720, A007053, A017979, A030078, A036386, A060967, A060970, A060971.

Table[ PrimePi[ Floor[ 2^(g/3)//N ] ], {g, 0, 90} ]

a(3*n) = A007053(n). - Chai Wah Wu, Jan 23 2025

a(n) = A000720(A017979(n)). - Amiram Eldar, Mar 22 2025

Missing a(0)=0 inserted by Sean A. Irvine, Jan 09 2023

A060970 Number of fourth powers of primes <= 2^n.

Original entry on oeis.org

0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 5, 6, 6, 8, 8, 9, 11, 12, 14, 16, 18, 21, 24, 28, 31, 36, 42, 47, 54, 62, 72, 82, 97, 111, 128, 149, 172, 199, 229, 268, 309, 360, 418, 481, 564, 651, 760, 886, 1028, 1201, 1393, 1629, 1900, 2211, 2585, 3010, 3512, 4104, 4792

Offset: 0

Labos Elemer, May 09 2001

nonn

			For n = 12, the 4th powers of prime not exceeding 2^12 = 4096 are 16, 81, 625, 2401, so a(12) = 4.

Cf. A000720, A007053, A018048, A030514, A036386, A060967, A060969, A060971.

Table[ PrimePi[ Floor[ 2^(g/4)//N ] ], {g, 0, 100} ]

a(4*n) = A007053(n). - Chai Wah Wu, Jan 23 2025

a(n) = A000720(A018048(n)). - Amiram Eldar, Mar 22 2025

Missing a(0)=0 inserted by Sean A. Irvine, Jan 09 2023

A060971 Number of fifth powers of primes <= 2^n.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 6, 6, 7, 8, 9, 9, 11, 11, 13, 15, 16, 18, 21, 23, 25, 29, 31, 34, 39, 44, 47, 54, 62, 68, 76, 86, 97, 107, 122, 137, 154, 172, 193, 217, 244, 275, 309, 349, 393, 442, 499, 564, 635, 712, 807, 914, 1028, 1163, 1315, 1482

Offset: 0

Labos Elemer, May 09 2001

nonn

			For n = 10: the 5th powers of primes not exceeding 2^10 = 1024 are 32 and 243, so a(10) = 2.

Cf. A000720, A007053, A018117, A036386, A050997, A060967, A060969, A060970.

Table[ PrimePi[ Floor[ 2^(g/5)//N ] ], {g, 0, 150} ]

a(5*n) = A007053(n). - Chai Wah Wu, Jan 23 2025

a(n) = A000720(A018117(n)). - Amiram Eldar, Mar 22 2025

Missing a(0)=0 inserted by Sean A. Irvine, Jan 09 2023

A146168 Number of odd squarefree semiprimes (A046388) < 2^n.

Original entry on oeis.org

0, 0, 0, 1, 2, 8, 20, 46, 96, 197, 404, 798, 1599, 3134, 6169, 12093, 23640, 46199, 90180, 176198, 343927, 671783, 1312304, 2564485, 5012807, 9803883, 19181677, 37545265, 73524262, 144038812, 282313035, 553557959, 1085860455, 2130904274, 4183364732, 8215861037

Offset: 1

Washington Bomfim, Oct 27 2008

nonn

			a(5) = 2. The odd squarefree semiprimes less than 2^5 are 15 and 21. The formula gives 10 - pi(5) - pi(2^4) + 1 = 2.

Amiram Eldar, Table of n, a(n) for n = 1..57 (calculated using the b-files at A060967, A007053 and A125527)

Cf. A046388, A001358 (semiprimes), A000720 (pi(n), the number of primes <= n), A007053 (number of primes <= 2^n), A060967, A125527 (number of semiprimes <= 2^n).

Table[lim=2^n; Sum[PrimePi[lim/p]-PrimePi[p], {p, Prime[Range[2,PrimePi[Sqrt[lim]]]]}], {n,20}]

a(n) = A125527(n) - A060967(n) - A007053(n-1) + 1, for n > 1.

a(34) onwards from Amiram Eldar, Sep 05 2024

A145522 a(n) is such that A145521(n) = A053810(a(n)).

Original entry on oeis.org

1, 3, 2, 6, 5, 4, 10, 23, 12, 7, 39, 9, 97, 24, 164, 484, 2759, 5044, 109, 32334, 114605, 216960, 8, 14, 252, 785135, 5503557, 28, 39222428, 75703838, 548300521, 1496, 2063337476, 4008153424, 29523940595, 3858, 112174606866, 834662735468, 11, 12216544412251

Offset: 1

Leroy Quet, Oct 12 2008

nonn

This sequence is a permutation of the positive integers. It is its own inverse permutation.

			The primes raised to prime exponents form the sequence, when the terms are arranged in numerical order, 4,8,9,25,27,32,49,121,125,128,...(sequence A053810). The 10th term is 128, which is 2^7. So the 10th term of sequence A145521 is 7^2 = 49. 49 is the 7th term of A053810. So a(10) = 7 and a(7) = 10.

Cf. A053810, A145521, A000720, A060967.

lista(nn) = {my(c, m); for(k=1, nn, if(isprime(isprimepower(k, &p)), c=0; m=bigomega(k)^p; forprime(q=2, sqrtint(m), c+=primepi(logint(m, q))); print1(c, ", "))); } \\ Jinyuan Wang, Feb 25 2020

from itertools import count
from sympy import integer_nthroot, isprime, primepi
def A145522(n):
    total = 0
    for p in count(2):
        if 2**p > A145521(n): break
        if isprime(p): total += primepi(integer_nthroot(A145521(n), p)[0])
    return total # Jason Yuen, Jan 31 2024

from math import prod
from sympy import primepi, integer_nthroot, primerange, factorint
def A145522(n):
    def f(x): return int(n+x-sum(primepi(integer_nthroot(x, p)[0]) for p in primerange(x.bit_length())))
    m, k = n, f(n)
    while m != k:
        m, k = k, f(k)
    a = prod(e**p for p,e in factorint(m).items())
    return sum(primepi(integer_nthroot(a, p)[0]) for p in primerange(a.bit_length())) # Chai Wah Wu, Aug 10 2024

a(n) = Sum_{primes p, 2^p <= A145521(n)} A000720(floor(A145521(n)^(1/p))).

Also, if A145521(n) = 2^k then a(n) = A060967(k) + Sum_{primes p, 3 <= p <= k} A000720(floor(2^(k/p))). - Jason Yuen, Jan 31 2024

a(11)-a(28) from Ray Chandler, Nov 01 2008
a(29)-a(32) from Jinyuan Wang, Feb 25 2020
a(33)-a(39) from Jason Yuen, Jan 31 2024
a(40) from Chai Wah Wu, Aug 10 2024

A145584 a(n) = number of numbers removed in step n of Eratosthenes's sieve for 2^6.

Original entry on oeis.org

31, 10, 3, 1

Offset: 1

Artur Jasinski with assistance from Bob Hanlon (hanlonr(AT)cox.net), Oct 14 2008

Number of steps in Eratosthenes's sieve for 2^n is A060967(n).

Number of primes less than 2^6 is equal to 2^6 - (sum all of numbers in this sequence) - 1 = A007053(6).

Cf. A006880, A122121.
Cf. A145532, A145533, A145534, A145535, A145536, A145537, A145538, A145539, A145540.
Cf. A145583, A145584, A145585, A145586, A145587, A145588, A145589, A145590, A145591, A145592.

f3[k_Integer?Positive, i_Integer?Positive] := Module[{f, m, r, p}, p = Transpose[{r = Range[2, i], Prime[r]}];f[x_] := Catch[Fold[If[Mod[x, #2[[2]]] == 0, Throw[m[ #2[[1]]] = m[ #2[[1]]] + 1], #1] &, If[Mod[x, 2] == 0, Throw[m[1] = m[1] + 1]], p]]; Table[m[n] = -1, {n, i}]; f /@ Range[k]; Table[m[n], {n, i}]];nn = 6; kk = PrimePi[Sqrt[2^nn]]; t3 = f3[2^nn, kk] (* Bob Hanlon (hanlonr(AT)cox.net) *)

A145585 a(n) = number of numbers removed in each step of Eratosthenes's sieve for 2^7.

Original entry on oeis.org

63, 20, 8, 4, 1

Offset: 1

Artur Jasinski with assistance from Bob Hanlon (hanlonr(AT)cox.net), Oct 14 2008

Number of steps in Eratosthenes's sieve for 2^n is A060967(n).

Number of primes less than 2^7 is equal to 2^7 - (sum all of numbers in this sequence) - 1 = A007053(7).

Cf. A006880, A122121, A145532-A145540, A145583-A145592.

f3[k_Integer?Positive, i_Integer?Positive] := Module[{f, m, r, p}, p = Transpose[{r = Range[2, i], Prime[r]}];f[x_] := Catch[Fold[If[Mod[x, #2[[2]]] == 0, Throw[m[ #2[[1]]] = m[ #2[[1]]] + 1], #1] &, If[Mod[x, 2] == 0, Throw[m[1] = m[1] + 1]], p]]; Table[m[n] = -1, {n, i}]; f /@ Range[k]; Table[m[n], {n, i}]];nn = 7; kk = PrimePi[Sqrt[2^nn]]; t3 = f3[2^nn, kk] (* Bob Hanlon (hanlonr(AT)cox.net) *)

cp's OEIS Frontend

A007053 Number of primes <= 2^n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A145592 a(n)=number of numbers removed in each step of Eratosthenes's sieve for 2^14.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A060969 Number of cubes of primes <= 2^n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A060970 Number of fourth powers of primes <= 2^n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A060971 Number of fifth powers of primes <= 2^n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A146168 Number of odd squarefree semiprimes (A046388) < 2^n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A145522 a(n) is such that A145521(n) = A053810(a(n)).