A122121 -id:A122121 - cp's OEIS frontend

A145540 Number of numbers removed in each step of Eratosthenes's sieve for 10^4.

4999, 1666, 666, 380, 207, 159, 110, 94, 76, 59, 56, 46, 41, 37, 33, 27, 23, 21, 17, 15, 12, 9, 8, 6, 3

Offset: 1

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

Number of steps in Eratosthenes's sieve for 10^n is A122121(n).

Number of primes less than 10^4 is 10^4 - (sum all of numbers in this sequence) - 1 = A006880(4).

A145540:=Array([seq(0,j=1..25)]): lim:=10^4: p:=Array([seq(ithprime(j),j=1..25)]): for n from 4 to lim do if(isprime(n))then n:=n+1: fi: for k from 1 to 25 do if(n mod p[k] = 0)then A145540[k]:=A145540[k]+1: break: fi: od: od: seq(A145540[j],j=1..25); # Nathaniel Johnston, Jun 23 2011

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 = 4; kk = PrimePi[Sqrt[10^nn]]; t3 = f3[10^nn, kk] (* Bob Hanlon (hanlonr(AT)cox.net) *)

A060967 Number of squared primes <= 2^n.

Original entry on oeis.org

0, 0, 1, 1, 2, 3, 4, 5, 6, 8, 11, 14, 18, 24, 31, 42, 54, 72, 97, 128, 172, 229, 309, 418, 564, 760, 1028, 1393, 1900, 2585, 3512, 4792, 6542, 8952, 12251, 16777, 23000, 31579, 43390, 59631, 82025, 112957, 155611, 214516, 295947, 408493, 564163, 779638

Offset: 0

Labos Elemer, May 09 2001

nonn

			For n = 8, the squared primes not exceeding 2^8 = 256 are 4, 9, 25, 49, 121, 169, so a(8) = 6.

Amiram Eldar, Table of n, a(n) for n = 0..150 (terms 0..63 from Harry J. Smith, terms 64..112 from Hiroaki Yamanouchi, terms 113..125 from Ray Chandler)
Index entries for sequences related to numbers of primes in various ranges.

Cf. A000720, A001248, A007053, A017910, A036386, A060969, A060970, A060971, A122121.

Table[ PrimePi[ Floor[ 2^(g/2)//N ] ], {g, 1, 75} ]

a(n) = { primepi(sqrtint(2^n)) } \\ Harry J. Smith, Jul 15 2009

a(2*n) = A007053(n). - Amiram Eldar, Jul 10 2024

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

a(0) prepended by Harry J. Smith, Jul 15 2009

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

A145583 a(n) = number of numbers removed in the n-th step of Eratosthenes's sieve for 10^2.

Original entry on oeis.org

49, 16, 6, 3

Offset: 1

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

Number of steps in Eratosthenes's sieve for 10^n is A122121(n).

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

Cf. A006880, A122121, A145532, A145533, A145534, A145535, A145536, A145537, A145538, A145539, A145540, 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 = 2; kk = PrimePi[Sqrt[10^nn]]; t3 = f3[10^nn, kk] (*Bob Hanlon (hanlonr(AT)cox.net) *)

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

A132153 Largest prime <= square root of 10^n.

Original entry on oeis.org

3, 7, 31, 97, 313, 997, 3137, 9973, 31607, 99991, 316223, 999983, 3162277, 9999991, 31622743, 99999989, 316227731, 999999937, 3162277633, 9999999967, 31622776589, 99999999977, 316227766003, 999999999989, 3162277660153, 9999999999971, 31622776601657

Offset: 1

Anthony C Robin, Nov 01 2007

nonn

To check if an (n+1)-digit number is prime, a(n) is the largest prime which one needs to check is not a factor of the (n+1)-th digit number. For example, to check that a general four-digit number is not prime, we need to test its divisibility by all the primes up to and including 97.

Charles R Greathouse IV, Table of n, a(n) for n = 1..2000

Cf. A017934, A131581, A136582, A175733, A175734.

Cf. A000040, A122121, A003618.

Table[NextPrime[Sqrt[10^n],-1],{n,27}] (* James C. McMahon, Mar 04 2025 *)

a(n)=precprime(sqrtint(10^n)) \\ Charles R Greathouse IV, Aug 18 2011

from sympy import prevprime, integer_nthroot
def a(n): return prevprime(integer_nthroot(10**n, 2)[0]+1)
print([a(n) for n in range(1, 28)]) # Michael S. Branicky, Dec 23 2021

a(n) = A000040(A122121(n)). a(2n) = A003618(n). - R. J. Mathar, Nov 06 2007 [Corrected by Jaroslav Krizek, Jul 12 2010]

a(n) = sqrt(A175734(n)). - Jaroslav Krizek, Aug 24 2010

More terms from N. J. A. Sloane, Jan 05 2008

A145538 Number of numbers removed in each step of Eratosthenes's sieve for 10^5.

Original entry on oeis.org

49999, 16666, 6666, 3808, 2077, 1597, 1127, 949, 741, 555, 499, 405, 358, 335, 305, 274, 248, 242, 219, 203, 199, 184, 175, 165, 148, 141, 137, 131, 128, 124, 108, 104, 97, 95, 87, 86, 79, 75, 70, 67, 62, 60, 57, 54, 52, 50, 45, 39, 37, 35, 32, 29, 28, 25, 23, 20

Offset: 1

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

Number of steps in Eratosthenes's sieve for 10^n is A122121(n).
Number of primes less than 10^5 equals 10^5 - A065894(5) (sum of all numbers in this sequence) - 1 = A006880(5).
a(n) is the number of composite numbers m <= 10^5 whose least prime factor (A020639(m)) is prime(n).

Nathaniel Johnston, Table of n, a(n) for n = 1..65 (full sequence)

Cf. A006880, A122121, A145532-A145540.

Cf. A065894, A020639.

A145538:=Array([seq(0,j=1..65)]): lim:=10^5: p:=Array([seq(ithprime(j),j=1..65)]): for n from 4 to lim do if(isprime(n))then n:=n+1: fi: for k from 1 to 65 do if(n mod p[k] = 0)then A145538[k]:=A145538[k]+1: break: fi: od: od: seq(A145538[j],j=1..65); # Nathaniel Johnston, Jun 23 2011

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 = 5; kk = PrimePi[Sqrt[10^nn]]; t3 = f3[10^nn, kk] (* Bob Hanlon (hanlonr(AT)cox.net) *)

Edited by Rick L. Shepherd, Mar 02 2013

A036351 Number of numbers <= 10^n that are products of two distinct primes.

Original entry on oeis.org

2, 30, 288, 2600, 23313, 209867, 1903878, 17426029, 160785135, 1493766851, 13959963049, 131125938680, 1237087821006, 11715901643501, 111329815346924, 1061057287065814, 10139482896634686, 97123037634329553, 932300026078297246, 8966605849186166511, 86389956292394285653, 833671466547121873095, 8056846659972421004731

Offset: 1

Shyam Sunder Gupta

nonn

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

Cf. A066265.

Cf. A036352, A122121.

f[n_] := Sum[ PrimePi[n/Prime[i]] - i, {i, PrimePi[ Sqrt[ n]] }]; Table[ f[10^n], {n, 14}] (* Robert G. Wilson v, Feb 07 2012 and modified Dec 28 2016 *)

a(n)=my(s);forprime(p=2,sqrt(10^n),s+=primepi(10^n\p)); s-binomial(primepi(sqrt(10^n))+1,2) \\ Charles R Greathouse IV, Apr 23 2012

from math import isqrt
from sympy import primepi, primerange
def A036351(n): return -(t:=primepi(s:=isqrt(m:=10**n)))-(t*(t-1)>>1)+sum(primepi(m//k) for k in primerange(1, s+1)) # Chai Wah Wu, Aug 15 2024

a(n) = (1/2)*(pi(10^(n/2)) + Sum_{i=1..pi(10^n)} pi((10^n-1)/P_i)) -1 = Sum_{i=1..pi(sqrt(10^n))} (pi((10^n-1)/P_i) -1) - binomial(pi(sqrt(10^n)), 2). - Robert G. Wilson v, May 19 2005

a(n) = A036352(n) - A122121(n). - Robert G. Wilson v, Feb 07 2012

a(14) from Robert G. Wilson v, May 19 2005
a(15)-a(16) from Donovan Johnson, Oct 16 2010
Corrected a(15) and a(16) by Henri Lifchitz, Nov 11 2012
a(17)-a(19) from Henri Lifchitz, Nov 11 2012
a(20)-a(21) from Henri Lifchitz, Jul 03 2015
a(22)-a(23) from Henri Lifchitz, Nov 09 2024

A145539 Number of numbers removed in each step of Eratosthenes's sieve for 10^6.

Original entry on oeis.org

499999, 166666, 66666, 38094, 20778, 15983, 11283, 9502, 7434, 5646, 5098, 4136, 3617, 3356, 2982, 2575, 2261, 2143, 1910, 1775, 1700, 1553, 1460, 1354, 1244, 1195, 1171, 1130, 1109, 1074, 964, 937, 898, 886, 832, 820, 794, 763, 745, 719, 697, 689, 654

Offset: 1

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

Number of steps in Eratosthenes's sieve for 10^n is A122121(n).
Number of primes less than 10^6 equals 10^6 - A065894(6) (sum of all numbers in this sequence) - 1 = A006880(6).
a(n) is the number of composite numbers m <= 10^6 whose least prime factor (A020639(m)) is prime(n). - Rick L. Shepherd, Mar 02 2013

Nathaniel Johnston, Table of n, a(n) for n = 1..168 (full sequence)

Cf. A006880, A122121, A145532-A145540.

Cf. A065894, A020639.

A145539:=Array([seq(0,j=1..168)]): lim:=10^6: p:=Array([seq(ithprime(j),j=1..168)]): for n from 4 to lim do if(isprime(n))then n:=n+1: fi: for k from 1 to 168 do if(n mod p[k] = 0)then A145539[k]:=A145539[k]+1: break: fi: od: od: seq(A145539[j],j=1..168); # Nathaniel Johnston, Jun 23 2011

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[10^nn]]; t3 = f3[10^nn, kk] (* Bob Hanlon (hanlonr(AT)cox.net) *)

A292785 Number of odd squarefree semiprimes < 10^n.

Original entry on oeis.org

0, 16, 194, 1932, 18181, 168330, 1555366, 14424896, 134429269, 1258812629, 11840308472, 111817802539, 1059796159358, 10076977878935, 96091981692305, 918679869869451, 8803388128870716, 84537081067757934, 813340036390023775, 7838825925395981969, 75669246174605279757

Offset: 1

Hugo Pfoertner, Oct 10 2017

nonn

			a(2)=16 because there are 16 squarefree odd semiprimes < 10^2: 15=3*5, 21=3*7, 33=3*11, 35=5*7, 39=3*13, 51=3*17, 55=5*11, 57=3*19, 65=5*13, 69=3*23, 77=7*11, 85=5*17, 87=3*29, 91=7*13, 93=3*31, 95=5*19.

Cf. A046388, A066265, A122121, A220262.

-1 + Accumulate@ Table[Count[Range[10^n + 1, 10^(n + 1) - 1, 2], ?(And[ SquareFreeQ@ #, PrimeNu[#] == 2] &)], {n, 0, 5}] (* _Michael De Vlieger, Oct 10 2017 *)

from math import isqrt
from sympy import primepi, primerange
def A292785(n): return int((-(t:=primepi(s:=isqrt(m:=10**n)))*(t+1)>>1)+1+sum(primepi(m//k) for k in primerange(3, s+1))) if n>1 else 0 # Chai Wah Wu, Oct 17 2024

a(n) = A066265(n) - A122121(n) - A220262(n) + 1 for n > 1.

a(21) from Jinyuan Wang, Jul 30 2021

cp's OEIS Frontend

A145540 Number of numbers removed in each step of Eratosthenes's sieve for 10^4.

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Mathematica

A060967 Number of squared primes <= 2^n.

Views

Author

Keywords

Examples

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

A145583 a(n) = number of numbers removed in the n-th step of Eratosthenes's sieve for 10^2.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A132153 Largest prime <= square root of 10^n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A145538 Number of numbers removed in each step of Eratosthenes's sieve for 10^5.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A036351 Number of numbers <= 10^n that are products of two distinct primes.

Views

Author

Keywords

Links

Crossrefs