A179215 -id:A179215 - cp's OEIS frontend

A000720 pi(n), the number of primes <= n. Sometimes called PrimePi(n) to distinguish it from the number 3.14159...

0, 1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 10, 10, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 17, 17, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 20, 20, 21, 21, 21, 21, 21, 21

Offset: 1

N. J. A. Sloane

Partial sums of A010051 (characteristic function of primes). - Jeremy Gardiner, Aug 13 2002
pi(n) and prime(n) are inverse functions: a(A000040(n)) = n and A000040(n) is the least number m such that A000040(a(m)) = A000040(n). A000040(a(n)) = n if (and only if) n is prime. - Jonathan Sondow, Dec 27 2004
See the additional references and links mentioned in A143227. - Jonathan Sondow, Aug 03 2008
A lower bound that gets better with larger N is that there are at least T prime numbers less than N, where the recursive function T is: T = N - N*Sum_{i=0..T(sqrt(N))} A005867(i)/A002110(i). - Ben Paul Thurston, Aug 23 2010
Number of partitions of 2n into exactly two parts with the smallest part prime. - Wesley Ivan Hurt, Jul 20 2013
Equivalent to the Riemann hypothesis: abs(a(n) - li(n)) < sqrt(n)*log(n)/(8*Pi), for n >= 2657, where li(n) is the logarithmic integral (Lowell Schoenfeld). - Ilya Gutkovskiy, Jul 05 2016
The second Hardy-Littlewood conjecture, that pi(x) + pi(y) >= pi(x + y) for integers x and y with min{x, y} >= 2, is known to hold for (x, y) sufficiently large (Udrescu 1975). - Peter Luschny, Jan 12 2021

			There are 3 primes <= 6, namely 2, 3 and 5, so pi(6) = 3.

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 870.
Tom M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, p. 8.
Raymond Ayoub, An Introduction to the Analytic Theory of Numbers, Amer. Math. Soc., 1963; p. 129.
Florian Cajori, A History of Mathematical Notations, Dover edition (2012), par. 409.
Richard Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see p. 5.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, Theorems 6, 7, 420.
G. J. O. Jameson, The Prime Number Theorem, Camb. Univ. Press, 2003. [See also the review by D. M. Bressoud (link below).]
Władysław Narkiewicz, The Development of Prime Number Theory, Springer-Verlag, 2000.
Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See pp. 132-133, 157-184.
József Sándor, Dragoslav S. Mitrinovic and Borislav Crstici, Handbook of Number Theory I, Springer Science & Business Media, 2005, Section VII.1. (For inequalities, etc.).
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Gerald Tenenbaum and Michel Mendès France, Prime Numbers and Their Distribution, AMS Providence RI, 1999.
V. Udrescu, Some remarks concerning the conjecture pi(x + y) <= pi(x) + pi(y), Rev. Roumaine Math. Pures Appl. 20 (1975), 1201-1208.

Daniel Forgues, Table of n, pi(n) for n = 1..100000 (first 20000 terms from N. J. A. Sloane; see below for links with 823852 terms (Verma) and more (Caldwell))
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Christian Axler, Über die Primzahl-Zählfunktion, die n-te Primzahl und verallgemeinerte Ramanujan-Primzahlen, Ph.D. thesis 2013, in German, English summary.
Paul T. Bateman and Harold G. Diamond, A Hundred Years of Prime Numbers, Amer. Math. Month., Vol. 103, No. 9 (Nov. 1996), pp. 729-741, MAA Washington DC.
Steve Bennett, The role of Riemann's zeta function in the analytic proof of the Prime Number Theorem, 2004.
Claudio Bonanno and Mirko S. Mega, Toward a dynamical model for prime numbers, Chaos, Solitons & Fractals, Vol. 20, No. 1 (2004), pp. 107-118; arXiv preprint, arXiv:cond-mat/0309251, 2003.
David M. Bressoud, Review of "The Prime Number Theorem" by G. J. O. Jameson, MAA Reviews, 2005. - from _N. J. A. Sloane_, Dec 29 2018
D. M. Bressoud and Stan Wagon, Computational Number Theory: Basic Algorithms, Springer/Key, 2000 (with a Mathematica package for computational number theory).
Ben Brubaker, The Prime Number Theorem.
C. K. Caldwell, The Prime Glossary: Prime number theorem.
W. W. L. Chen, Distribution of Prime Numbers.
Jean-Marie de Koninck and Aleksandar Ivić, Topics in Arithmetical Functions: Asymptotic Formulae for Sums of Reciprocals of Arithmetical Functions and Related Fields, Amsterdam, Netherlands: North-Holland, 1980. See Chapter 9, p. 231.
Marc Deléglise, Computation of large values of pi(x), 1996.
Pierre Dusart, Autour de la fonction qui compte le nombre de nombres premiers, Thèse, Université de Limoges, France (1998).
Pierre Dusart, The k-th prime is greater than k(ln k + ln ln k-1) for k>=2, Mathematics of Computation, Vo. 68, No. 225 (1999), pp. 411-415.
Encyclopedia Britannica, The Prime Number Theorem [web.archive.org's copy of a no longer available personal copy of the Encyclopedia's article]
R. Gray and J. D. Mitchell, Largest subsemigroups of the full transformation monoid, Discrete Math., 308 (2008), 4801-4810.
G. H. Hardy and J. E. Littlewood, Contributions to the theory of the Riemann zeta-function and the theory of the distribution of primes, Acta Mathematica, Vol. 41 (1916), pp. 119-196.
G. H. Hardy and J. E. Littlewood, Some problems of 'Partitio numerorum'; III: On the expression of a number as a sum of primes, Acta Math., Vol. 44, No. 1 (1923), pp. 1-70.
Mehdi Hassani, Approximation of pi(x) by Psi(x), J. Inequ. Pure Appl. Math., Vol. 7, No. 1 (2006), Article #7.
Y.-C. Kim, Note on the Prime Number Theorem, arXiv:math/0502062 [math.NT], 2005.
Tzanio V. Kolev, On the number of Prime Numbers less than a Given Quantity, 2000.
Angel V. Kumchev, The Distribution of Prime Numbers, 2005.
J. C. Lagarias, V. S. Miller and A. M. Odlyzko, Computing pi(x): The Meissel-Lehmer method, Math. Comp., Vol. 44, No. 170 (1985), pp. 537-560.
Jeffrey C. Lagarias and Andrew M. Odlyzko, Computing pi(x): An analytic method, Journal of Algorithms, Vol. 8, No. 2 (1987), pp. 173-191; alternative link.
John Lorch, The Distribution of Primes, B.S. Undergraduate Mathematics Exchange, Vol. 3, No. 1 (Fall 2005).
Nathan McKenzie, Computing the Prime Counting Function with Linnik's Identity, personal blog, March 24, 2011.
Murat Baris Paksoy, Derived Ramanujan primes: R'_n, arXiv:1210.6991 [math.NT], 2012.
Bent E. Petersen, Prime Number Theorem, Seminar Lecture Note, 1996; version 2002-05-14.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Omar E. Pol, Determinacion geometrica de los numeros primos y perfectos, personal website, 2001 (?); Illustration of initial terms: Divisors and pi(x).
Bernhard Riemann, On the Number of Prime Numbers, 1859, last page (various transcripts)
J. Barkley Rosser, Explicit Bounds for Some Functions of Prime Numbers, American Journal of Mathematics, Vol. 63, No. 1 (1941), pp. 211-232.
J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Ill. Journ. Math. 6 (1962) 64-94.
J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers (scan of some key pages from an ancient annotated photocopy).
Sebastian Martin Ruiz and Jonathan Sondow, Formulas for pi(n) and the n-th prime, arXiv:math/0210312 [math.NT], 2002, 2014.
Jeffrey Shallit, Bibliography on calculation of pi(x).
Jonathan Sondow, Ramanujan Primes and Bertrand's Postulate, The American Mathematical Monthly, Vol. 116, No. 7 (2009), pp. 630-635; arXiv preprint, arXiv:0907.5232 [math.NT], 2009-2010.
Igor Turkanov, The prime counting function, arXiv:1603.02914 [math.NT], 2016.
Gaurav Verma and Srujan Sapkal, Table of n, pi(n) for n = 1..823852.
Matthew R. Watkins, The distribution of Prime Numbers.
Matthew R. Watkins, The prime number theorem (some references).
Eric Weisstein's World of Mathematics, Prime Counting Function.
Wikipedia, Prime number theorem.
Wikipedia, Prime-counting function.
C. P. Willans, On formulae for the nth prime, Math. Gazette 48 (1964), 413-415.
Marek Wolf, Applications of Statistical Mechanics in Number Theory, Physica A, vol. 274, no. 2, 1999, pp. 149-157; 1999 preprint.
Wolfram Research, First 50 values of pi(n).
Index entries for "core" sequences

Cf. A048989, A000040, A132090, A137588, A139328, A104272, A143223, A143224, A143225, A143226, A143227.
Cf. A143538, A036234, A033844, A034387, A034386, A179215, A010051, A212210-A212213, A233824, A056171, A304483.
Closely related:
A099802: Number of primes <= 2n.
A060715: Number of primes between n and 2n (exclusive).
A035250: Number of primes between n and 2n (inclusive).
A038107: Number of primes < n^2.
A014085: Number of primes between n^2 and (n+1)^2.
A007053: Number of primes <= 2^n.
A036378: Number of primes p between powers of 2, 2^n < p <= 2^(n+1).
A006880: Number of primes < 10^n.
A006879: Number of primes with n digits.
A033270: Number of odd primes <= n.
A065855: Number of composites <= n.
For lists of large values of a(n) see, e.g., A005669(n) = a(A002386(n)), A214935(n) = a(A205827(n)).
Related sequences:
Primes (p) and composites (c): A000040, A002808, A065855.
Primes between p(n) and 2*p(n): A063124, A070046; between c(n) and 2*c(n): A376761; between n and 2*n: A035250, A060715, A077463, A108954.
Composites between p(n) and 2*p(n): A246514; between c(n) and 2*c(n): A376760; between n and 2*n: A075084, A307912, A307989, A376759.

a000720 n = a000720_list !! (n-1)
a000720_list = scanl1 (+) a010051_list  -- Reinhard Zumkeller, Sep 15 2011

[ #PrimesUpTo(n): n in [1..200] ];  // Bruno Berselli, Jul 06 2011

with(numtheory); A000720 := pi; [ seq(A000720(i),i=1..50) ];

A000720[n_] := PrimePi[n]; Table[ A000720[n], {n, 1, 100} ]
Array[ PrimePi[ # ]&, 100 ]
Accumulate[Table[Boole[PrimeQ[n]],{n,100}]] (* Harvey P. Dale, Jan 17 2015 *)

A000720=vector(100,n,omega(n!)) \\ For illustration only; better use A000720=primepi

vector(300,j,primepi(j)) \\ Joerg Arndt, May 09 2008

from sympy import primepi
for n in range(1,100): print(primepi(n), end=', ') # Stefano Spezia, Nov 30 2018

[prime_pi(n) for n in range(1, 79)]  # Zerinvary Lajos, Jun 06 2009

The prime number theorem gives the asymptotic expression a(n) ~ n/log(n).
For x > 1, pi(x) < (x / log x) * (1 + 3/(2 log x)). For x >= 59, pi(x) > (x / log x) * (1 + 1/(2 log x)). [Rosser and Schoenfeld]
For x >= 355991, pi(x) < (x / log(x)) * (1 + 1/log(x) + 2.51/(log(x))^2 ). For x >= 599, pi(x) > (x / log(x)) * (1 + 1/log(x)). [Dusart]
For x >= 55, x/(log(x) + 2) < pi(x) < x/(log(x) - 4). [Rosser]
For n > 1, A138194(n) <= a(n) <= A138195(n) (Tschebyscheff, 1850). - Reinhard Zumkeller, Mar 04 2008
For n >= 33, a(n) = 1 + Sum_{j=3..n} ((j-2)! - j*floor((j-2)!/j)) (Hardy and Wright); for n >= 1, a(n) = n - 1 + Sum_{j=2..n} (floor((2 - Sum_{i=1..j} (floor(j/i)-floor((j-1)/i)))/j)) (Ruiz and Sondow 2000). - Benoit Cloitre, Aug 31 2003
a(n) = A001221(A000142(n)). - Benoit Cloitre, Jun 03 2005
G.f.: Sum_{p prime} x^p/(1-x) = b(x)/(1-x), where b(x) is the g.f. for A010051. - Franklin T. Adams-Watters, Jun 15 2006
a(n) = A036234(n) - 1. - Jaroslav Krizek, Mar 23 2009
From Enrique Pérez Herrero, Jul 12 2010: (Start)
a(n) = Sum_{i=2..n} floor((i+1)/A000203(i)).
a(n) = Sum_{i=2..n} floor(A000010(n)/(i-1)).
a(n) = Sum_{i=2..n} floor(2/A000005(n)). (End)
Let pf(n) denote the set of prime factors of an integer n. Then a(n) = card(pf(n!/floor(n/2)!)). - Peter Luschny, Mar 13 2011
a(n) = -Sum_{p <= n} mu(p). - Wesley Ivan Hurt, Jan 04 2013
a(n) = (1/2)*Sum_{p <= n} (mu(p)*d(p)*sigma(p)*phi(p)) + sum_{p <= n} p^2. - Wesley Ivan Hurt, Jan 04 2013
a(1) = 0 and then, for all k >= 1, repeat k A001223(k) times. - Jean-Christophe Hervé, Oct 29 2013
a(n) = n/(log(n) - 1 - Sum_{k=1..m} A233824(k)/log(n)^k + O(1/log(n)^{m+1})) for m > 0. - Jonathan Sondow, Dec 19 2013
a(n) = A001221(A003418(n)). - Eric Desbiaux, May 01 2014
a(n) = Sum_{j=2..n} H(-sin^2 (Pi*(Gamma(j)+1)/j)) where H(x) is the Heaviside step function, taking H(0)=1. - Keshav Raghavan, Jun 18 2016
a(A014076(n)) = (1/2) * (A014076(n) + 1) - n + 1. - Christopher Heiling, Mar 03 2017
From Steven Foster Clark, Sep 25 2018: (Start)
a(n) = Sum_{m=1..n} A143519(m) * floor(n/m).
a(n) = Sum_{m=1..n} A001221(m) * A002321(floor(n/m)) where A002321() is the Mertens function.
a(n) = Sum_{m=1..n} |A143519(m)| * A002819(floor(n/m)) where A002819() is the Liouville Lambda summatory function and |x| is the absolute value of x.
a(n) = Sum_{m=1..n} A137851(m)/m * H(floor(n/m)) where H(n) = Sum_{m=1..n} 1/m is the harmonic number function.
a(n) = Sum_{m=1..log_2(n)} A008683(m) * A025528(floor(n^(1/m))) where A008683() is the Moebius mu function and A025528() is the prime-power counting function.
(End)
Sum_{k=2..n} 1/a(k) ~ (1/2) * log(n)^2 + O(log(n)) (de Koninck and Ivić, 1980). - Amiram Eldar, Mar 08 2021
a(n) ~ 1/(n^(1/n)-1). - Thomas Ordowski, Jan 30 2023
a(n) = Sum_{j=2..n} floor(((j - 1)! + 1)/j - floor((j - 1)!/j)) [Mináč, unpublished] (see Ribenboim, pp. 132-133). - Stefano Spezia, Apr 13 2025
a(n) = n - 1 - Sum_{k=2..floor(log_2(n))} pi_k(n), where pi_k(n) is the number of k-almost primes <= n. - Daniel Suteu, Aug 27 2025

Additional links contributed by Lekraj Beedassy, Dec 23 2003

Edited by M. F. Hasler, Apr 27 2018 and (links recovered) Dec 21 2018

A025487 Least integer of each prime signature A124832; also products of primorial numbers A002110.

Original entry on oeis.org

1, 2, 4, 6, 8, 12, 16, 24, 30, 32, 36, 48, 60, 64, 72, 96, 120, 128, 144, 180, 192, 210, 216, 240, 256, 288, 360, 384, 420, 432, 480, 512, 576, 720, 768, 840, 864, 900, 960, 1024, 1080, 1152, 1260, 1296, 1440, 1536, 1680, 1728, 1800, 1920, 2048, 2160, 2304, 2310

Offset: 1

David W. Wilson

All numbers of the form 2^k1*3^k2*...*p_n^k_n, where k1 >= k2 >= ... >= k_n, sorted.
A111059 is a subsequence. - Reinhard Zumkeller, Jul 05 2010
Choie et al. (2007) call these "Hardy-Ramanujan integers". - Jean-François Alcover, Aug 14 2014
The exponents k1, k2, ... can be read off Abramowitz & Stegun p. 831, column labeled "pi".
For all such sequences b for which it holds that b(n) = b(A046523(n)), the sequence which gives the indices of records in b is a subsequence of this sequence. For example, A002182 which gives the indices of records for A000005, A002110 which gives them for A001221 and A000079 which gives them for A001222. - Antti Karttunen, Jan 18 2019
The prime signature corresponding to a(n) is given in row n of A124832. - M. F. Hasler, Jul 17 2019

			The first few terms are 1, 2, 2^2, 2*3, 2^3, 2^2*3, 2^4, 2^3*3, 2*3*5, ...

Franklin T. Adams-Watters, Table of n, a(n) for n = 1..10001 (first 291 terms from Will Nicholes)
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972.
Kevin Broughan, Equivalents of the Riemann Hypothesis, Vol. 1: Arithmetic Equivalents, Cambridge University Press, 2017. See section 8.2, "Hardy-Ramanujan Numbers".
YoungJu Choie, Nicolas Lichiardopol, Pieter Moree and Patrick Solé, On Robin's criterion for the Riemann hypothesis, Journal de théorie des nombres de Bordeaux, Vol. 19, No. 2 (2007), pp. 357-372. See section 5, p. 367.
Asaf Cohen Antonir and Asaf Shapira, An Elementary Proof of a Theorem of Hardy and Ramanujan (2022). arXiv:2207.09410 [math.NT]
Michael De Vlieger, Relations of A025487 to A002110, A002182, and A002201.
Steven R. Finch, Errata and Addenda to Mathematical Constants, arXiv:2001.00578 [math.HO], 2020, pp. 9-10.
G. H. Hardy and S. Ramanujan, Asymptotic formulae for the distribution of integers of various types, Proc. London Math. Soc, Ser. 2, Vol. 16 (1917), pp. 112-132. Also published in the book Collected Papers of Srinivasa Ramanujan, Chelsea, 1962, pages 245-261.
Jeffery Kline, On the eigenstructure of sparse matrices related to the prime number theorem, Linear Algebra and its Applications (2020) Vol. 584, 409-430.
L. B. Richmond, Asymptotic results for partitions (I) and the distribution of certain integers, Journal of Number Theory, Vol. 8, No. 4 (1976), pp. 372-389. See page 388.

Subsequence of A055932, A191743, and A324583.
Cf. A025488, A051282, A036041, A051466, A061394, A124832, A161360, A166469, A181815, A181817, A283980, A306802, A322584, A322585 (characteristic function), A329897, A329898, A329899, A329900, A329904, A330683.
Cf. A085089, A101296 (left inverses).
Equals range of values taken by A046523.
Cf. A178799 (first differences), A247451 (squarefree kernel), A146288 (number of divisors).
Subsequences of this sequence include: A000079, A000142, A000400, A001013, A001813, A002110, A002182, A005179, A006939, A025527, A056836, A061742, A064350, A066120, A087980, A097212, A097213, A111059, A119840, A119845, A126098, A129912, A140999, A166338, A166470, A166472, A166473, A166475, A167448, A168262, A168263, A168264, A179215, A181555, A181804, A181806, A181809, A181818, A181822, A181823, A181824, A181825, A181826, A181827, A182763, A182862, A182863, A212170, A220264, A220423, A250269, A250270, A260633, A266047, A284456, A300357, A304938, A329894, A330687; also A037019 and A330681 (when sorted), possibly also A289132.
Rearrangements of this sequence include A036035, A059901, A063008, A077569, A085988, A086141, A087443, A108951, A181821, A181822, A322827, A329886, A329887.
Cf. also array A124832 (row n = prime signature of a(n)) and A304886, A307056.

import Data.Set (singleton, fromList, deleteFindMin, union)
a025487 n = a025487_list !! (n-1)
a025487_list = 1 : h [b] (singleton b) bs where
   (_ : b : bs) = a002110_list
   h cs s xs'@(x:xs)
     | m <= x    = m : h (m:cs) (s' `union` fromList (map (* m) cs)) xs'
     | otherwise = x : h (x:cs) (s  `union` fromList (map (* x) (x:cs))) xs
     where (m, s') = deleteFindMin s
-- Reinhard Zumkeller, Apr 06 2013

isA025487 := proc(n)
    local pset,omega ;
    pset := sort(convert(numtheory[factorset](n),list)) ;
    omega := nops(pset) ;
    if op(-1,pset) <> ithprime(omega) then
        return false;
    end if;
    for i from 1 to omega-1 do
        if padic[ordp](n,ithprime(i)) < padic[ordp](n,ithprime(i+1)) then
            return false;
        end if;
    end do:
    true ;
end proc:
A025487 := proc(n)
    option remember ;
    local a;
    if n = 1 then
        1 ;
    else
        for a from procname(n-1)+1 do
            if isA025487(a) then
                return a;
            end if;
        end do:
    end if;
end proc:
seq(A025487(n),n=1..100) ; # R. J. Mathar, May 25 2017

PrimeExponents[n_] := Last /@ FactorInteger[n]; lpe = {}; ln = {1}; Do[pe = Sort@PrimeExponents@n; If[ FreeQ[lpe, pe], AppendTo[lpe, pe]; AppendTo[ln, n]], {n, 2, 2350}]; ln (* Robert G. Wilson v, Aug 14 2004 *)
(* Second program: generate all terms m <= A002110(n): *)
f[n_] := {{1}}~Join~
  Block[{lim = Product[Prime@ i, {i, n}],
   ww = NestList[Append[#, 1] &, {1}, n - 1], dec},
   dec[x_] := Apply[Times, MapIndexed[Prime[First@ #2]^#1 &, x]];
   Map[Block[{w = #, k = 1},
      Sort@ Prepend[If[Length@ # == 0, #, #[[1]]],
        Product[Prime@ i, {i, Length@ w}] ] &@ Reap[
         Do[
          If[# < lim,
             Sow[#]; k = 1,
             If[k >= Length@ w, Break[], k++]] &@ dec@ Set[w,
             If[k == 1,
               MapAt[# + 1 &, w, k],
               PadLeft[#, Length@ w, First@ #] &@
                 Drop[MapAt[# + Boole[i > 1] &, w, k], k - 1] ]],
           {i, Infinity}] ][[-1]]
] &, ww]]; Sort[Join @@ f@ 13] (* Michael De Vlieger, May 19 2018 *)

isA025487(n)=my(k=valuation(n,2),t);n>>=k;forprime(p=3,default(primelimit),t=valuation(n,p);if(t>k,return(0),k=t);if(k,n/=p^k,return(n==1))) \\ Charles R Greathouse IV, Jun 10 2011

factfollow(n)={local(fm, np, n2);
  fm=factor(n); np=matsize(fm)[1];
  if(np==0,return([2]));
  n2=n*nextprime(fm[np,1]+1);
  if(np==1||fm[np,2]Franklin T. Adams-Watters, Dec 01 2011 */

is(n) = {if(n==1, return(1)); my(f = factor(n));  f[#f~, 1] == prime(#f~) && vecsort(f[, 2],,4) == f[, 2]} \\ David A. Corneth, Feb 14 2019

upto(Nmax)=vecsort(concat(vector(logint(Nmax,2),n,select(t->t<=Nmax,if(n>1,[factorback(primes(#p),Vecrev(p)) || p<-partitions(n)],[1,2]))))) \\ M. F. Hasler, Jul 17 2019

\\ For fast generation of large number of terms, use this program:
A283980(n) = {my(f=factor(n)); prod(i=1, #f~, my(p=f[i, 1], e=f[i, 2]); if(p==2, 6, nextprime(p+1))^e)}; \\ From A283980
A025487list(e) = { my(lista = List([1, 2]), i=2, u = 2^e, t); while(lista[i] != u, if(2*lista[i] <= u, listput(lista,2*lista[i]); t = A283980(lista[i]); if(t <= u, listput(lista,t))); i++); vecsort(Vec(lista)); }; \\ Returns a list of terms up to the term 2^e.
v025487 = A025487list(101);
A025487(n) = v025487[n];
for(n=1,#v025487,print1(A025487(n), ", ")); \\ Antti Karttunen, Dec 24 2019

def sharp_primorial(n): return sloane.A002110(prime_pi(n))
N = 2310
nmax = 2^floor(log(N,2))
sorted([j for j in (prod(sharp_primorial(t[0])^t[1] for k, t in enumerate(factor(n))) for n in (1..nmax)) if j <= N])
# Giuseppe Coppoletta, Jan 26 2015

What can be said about the asymptotic behavior of this sequence? - Franklin T. Adams-Watters, Jan 06 2010
Hardy & Ramanujan prove that there are exp((2 Pi + o(1))/sqrt(3) * sqrt(log x/log log x)) members of this sequence up to x. - Charles R Greathouse IV, Dec 05 2012
From Antti Karttunen, Jan 18 & Dec 24 2019: (Start)
A085089(a(n)) = n.
A101296(a(n)) = n [which is the first occurrence of n in A101296, and thus also a record.]
A001221(a(n)) = A061395(a(n)) = A061394(n).
A007814(a(n)) = A051903(a(n)) = A051282(n).
a(A101296(n)) = A046523(n).
a(A306802(n)) = A002182(n).
a(n) = A108951(A181815(n)) = A329900(A181817(n)).
If A181815(n) is odd, a(n) = A283980(a(A329904(n))), otherwise a(n) = 2*a(A329904(n)).
(End)
Sum_{n>=1} 1/a(n) = Product_{n>=1} 1/(1 - 1/A002110(n)) = A161360. - Amiram Eldar, Oct 20 2020

Offset corrected by Matthew Vandermast, Oct 19 2008

Minor correction by Charles R Greathouse IV, Sep 03 2010

A008966 a(n) = 1 if n is squarefree, otherwise 0.

Original entry on oeis.org

1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0

Offset: 1

N. J. A. Sloane

a(n) depends only on prime signature of n (cf. A025487). So a(24) = a(375) since 24 = 2^3*3 and 375 = 3*5^3 both have prime signature (3, 1).

The infinite lower triangular matrix with A008966 on the main diagonal and the rest zeros is the square of triangle A143255. - Gary W. Adamson, Aug 02 2008

Daniel Forgues, Table of n, a(n) for n = 1..100000
Eric Weisstein's World of Mathematics, Moebius Function
Index entries for characteristic functions
Index entries for sequences computed from exponents in factorization of n

Cf. A005117, A008836 (Dirichlet inverse), A013928 (partial sums).
Cf. A179211, A179212, A179213, A179214, A179215.
Cf. A020639, A073576, A087188.
Cf. A124010, A212793, A085357, A156552.
Parity of A002033.
Cf. A047999, A036987
Cf. A082020 (Dgf at s=2), A157289 (Dgf at s=3), A157290 (Dgf at s=4).

a008966 = abs . a008683
-- Reinhard Zumkeller, Dec 13 2015, Dec 15 2014, May 27 2012, Jan 25 2012

Magma
```
[ Abs(MoebiusMu(n)) : n in [1..100]];
```

A008966 := proc(n) if numtheory[issqrfree](n) then 1 ; else 0 ; end if; end proc: # R. J. Mathar, Mar 14 2011

A008966[n_] := Abs[MoebiusMu[n]]; Table[A008966[n], {n, 100}] (* Enrique Pérez Herrero, Apr 15 2010 *)
Table[If[SquareFreeQ[n],1,0],{n,100}] (* or *) Boole[SquareFreeQ/@ Range[ 100]] (* Harvey P. Dale, Feb 28 2015 *)

MuPAD
```
func(abs(numlib::moebius(n)), n):
```
PARI
```
a(n)=if(n<1,0,direuler(p=2,n,1+X))[n]
```

a(n)=issquarefree(n) \\ Michel Marcus, Feb 22 2015

from sympy import factorint
def A008966(n): return int(max(factorint(n).values(),default=1)==1) # Chai Wah Wu, Apr 05 2023

Dirichlet g.f.: zeta(s)/zeta(2s).
a(n) = abs(mu(n)), where mu is the Moebius function (A008683).
a(n) = 0^(bigomega(n) - omega(n)), where bigomega(n) and omega(n) are the numbers of prime factors of n with and without repetition (A001222, A001221, A046660). - Reinhard Zumkeller, Apr 05 2003
Multiplicative with p^e -> 0^(e - 1), p prime and e > 0. - Reinhard Zumkeller, Jul 15 2003
a(n) = 0^(A046951(n) - 1). - Reinhard Zumkeller, May 20 2007
a(n) = 1 - A107078(n). - Reinhard Zumkeller, Oct 03 2008
a(n) = floor(rad(n)/n), where rad() is A007947. - Enrique Pérez Herrero, Nov 13 2009
A175046(n) = a(n)*A073311(n). - Reinhard Zumkeller, Apr 05 2010
a(n) = floor(A000005(n^2)/A007425(n)). - Enrique Pérez Herrero, Apr 15 2010
a(A005117(n)) = 1; a(A013929(n)) = 0; a(n) = A013928(n + 1) - A013928(n). - Reinhard Zumkeller, Jul 05 2010
a(n) * A112526(n) = A063524(n). - Reinhard Zumkeller, Sep 16 2011
a(n) = mu(n) * lambda(n) = A008836(n) * A008683(n). - Enrique Pérez Herrero, Nov 29 2013
a(n) = Sum_{d|n} 2^omega(d)*mu(n/d). - Geoffrey Critzer, Feb 22 2015
a(n) = A085357(A156552(n)). - Antti Karttunen, Mar 06 2017
Limit_{n->oo} (1/n)*Sum_{j=1..n} a(j) = 6/Pi^2. - Andres Cicuttin, Aug 13 2017
a(1) = 1; a(n) = -Sum_{d|n, d < n} (-1)^bigomega(n/d) * a(d). - Ilya Gutkovskiy, Mar 10 2021

Deleted an unclear comment. - N. J. A. Sloane, May 30 2021

A034386 Primorial numbers (second definition): n# = product of primes <= n.

Original entry on oeis.org

1, 1, 2, 6, 6, 30, 30, 210, 210, 210, 210, 2310, 2310, 30030, 30030, 30030, 30030, 510510, 510510, 9699690, 9699690, 9699690, 9699690, 223092870, 223092870, 223092870, 223092870, 223092870, 223092870, 6469693230, 6469693230, 200560490130, 200560490130

Offset: 0

N. J. A. Sloane

Squarefree kernel of both n! and lcm(1, 2, 3, ..., n).
a(n) = lcm(core(1), core(2), core(3), ..., core(n)) where core(x) denotes the squarefree part of x, the smallest integer such that x*core(x) is a square. - Benoit Cloitre, May 31 2002
The sequence can also be obtained by taking a(1) = 1 and then multiplying the previous term by n if n is coprime to the previous term a(n-1) and taking a(n) = a(n-1) otherwise. - Amarnath Murthy, Oct 30 2002; corrected by Franklin T. Adams-Watters, Dec 13 2006

			a(5) = a(6) = 2*3*5 = 30;
a(7) = 2*3*5*7 = 210.

Steven R. Finch, Mathematical Constants, Cambridge, 2003, Section 1.3, p. 14, "n?".
József Sándor, Dragoslav S. Mitrinovic, Borislav Crstici, Handbook of Number Theory I, Springer Science & Business Media, 2005, Section VII.35, p. 268.

Alois P. Heinz, Table of n, a(n) for n = 0..2370 (first 401 terms from T. D. Noe)
Jens Askgaard, On the additive period length of the Sprague-Grundy function of certain Nim-like games, arXiv:1902.06299 [math.CO], 2019.
Klaus Dohmen and Martin Trinks, An Abstraction of Whitney's Broken Circuit Theorem, arXiv:1404.5480 [math.CO], 2014.
Romeo Meštrović, Euclid's theorem on the infinitude of primes: a historical survey of its proofs (300 BC--2012) and another new proof, arXiv:1202.3670 [math.HO], 2012. - From _N. J. A. Sloane_, Jun 13 2012
J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math., Vol. 6, No. 1 (1962), 64-94.
Eric Weisstein's World of Mathematics, Primorial.

Cf. A002110, A057872, A249270.
Cf. A073838, A034387. - Reinhard Zumkeller, Jul 05 2010
The following fractions are all related to each other: Sum 1/n: A001008/A002805, Sum 1/prime(n): A024451/A002110 and A106830/A034386, Sum 1/nonprime(n): A282511/A282512, Sum 1/composite(n): A250133/A296358.

[n eq 0 select 1 else LCM(PrimesInInterval(1, n)) : n in [0..50]]; // G. C. Greubel, Jul 21 2023

A034386 := n -> mul(k,k=select(isprime,[$1..n])); # Peter Luschny, Jun 19 2009
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1,
      `if`(isprime(n), n, 1)*a(n-1))
    end:
seq(a(n), n=0..36);  # Alois P. Heinz, Nov 26 2020

q[x_]:=Apply[Times,Table[Prime[w],{w,1,PrimePi[x]}]]; Table[q[w],{w,1,30}]
With[{pr=FoldList[Times,1,Prime[Range[20]]]},Table[pr[[PrimePi[n]+1]],{n,0,40}]] (* Harvey P. Dale, Apr 05 2012 *)
Table[ResourceFunction["Primorial"][i], {i,1,40}] (* Navvye Anand, May 22 2024 *)

a(n)=my(v=primes(primepi(n)));prod(i=1,#v,v[i]) \\ Charles R Greathouse IV, Jun 15 2011

a(n)=lcm(primes([2,n])) \\ Jeppe Stig Nielsen, Mar 10 2019

from sympy import primorial
def A034386(n): return 1 if n == 0 else primorial(n,nth=False) # Chai Wah Wu, Jan 11 2022

def sharp_primorial(n): return sloane.A002110(prime_pi(n))
[sharp_primorial(n) for n in (0..30)] # Giuseppe Coppoletta, Jan 26 2015

a(n) = n# = A002110(A000720(n)) = A007947(A003418(n)) = A007947(A000142(n)).
Asymptotic expression for a(n): exp((1 + o(1)) * n) where o(1) is the "little o" notation. - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 08 2001
For n > 0, log(a(n)) < 1.01624*n. [Rosser and Schoenfeld, 1962; Sándor et al., 2005] - N. J. A. Sloane, Apr 04 2017
a(n) <= A179215(n). - Reinhard Zumkeller, Jul 05 2010
a(n) = lcm(A006530(n), a(n-1)). - Jon Maiga, Nov 10 2018
Sum_{n>=0} 1/a(n) = A249270. - Amiram Eldar, Nov 08 2020

Offset changed and initial term added by Arkadiusz Wesolowski, Jun 04 2011

A013928 Number of (positive) squarefree numbers < n.

Original entry on oeis.org

0, 1, 2, 3, 3, 4, 5, 6, 6, 6, 7, 8, 8, 9, 10, 11, 11, 12, 12, 13, 13, 14, 15, 16, 16, 16, 17, 17, 17, 18, 19, 20, 20, 21, 22, 23, 23, 24, 25, 26, 26, 27, 28, 29, 29, 29, 30, 31, 31, 31, 31, 32, 32, 33, 33, 34, 34, 35, 36, 37, 37, 38, 39, 39, 39, 40, 41, 42, 42, 43, 44, 45, 45, 46, 47, 47, 47, 48, 49, 50, 50, 50, 51

Offset: 1

Henri Lifchitz

For n >= 1 define an n X n (0, 1) matrix A by A[i, j] = 1 if gcd(i, j) = 1, A[i, j] = 0 if gcd(i, j) > 1 for 1 <= i,j <= n . The rank of A is a(n + 1). Asymptotic expression for a(n) is a(n) ~ n * 6 / Pi^2. - Sharon Sela (sharonsela(AT)hotmail.com), May 06 2002
a(n) = Sum_{k=1..n-1} A008966(k). - Reinhard Zumkeller, Jul 05 2010
For all n >= 1, a(n)/n >= a(176)/176 = 53/88, and the equality occurs only for n=176 (see K. Rogers link). - Michel Marcus, Dec 16 2012 [Thus the Schnirelmann density of the squarefree numbers is 53/88. - Charles R Greathouse IV, Feb 02 2016]
Cohen, Dress, & El Marraki prove that |a(n) - 6n/Pi^2| < 0.02767*sqrt(n) for n >= 438653. - Charles R Greathouse IV, Feb 02 2016

			a(10) = 6 because there are 6 squarefree numbers up to 10: 1, 2, 3, 5, 6, 7.
a(11) = 7 because there are 7 squarefree numbers up to 11: the numbers listed above for 10, plus 10 itself.
a(13) = 8 because the 12 X 12 matrix described in the first comment by Sharon Sela has rank 8. Rows 2,4,8 (the powers of two) are identical, rows 3,9 (the powers of three) are identical, and rows 6 and 12 (same prime factors) are identical. - _Geoffrey Critzer_, Dec 07 2014
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
1, 0, 1, 0, 1, 0, 1, 0, 1, 0  1, 0, ...
1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, ...
1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...
1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, ...
1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, ...
1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, ...
1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...
1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, ...
1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, ...
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, ...
1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, ...
.                                   .
.                                    .
.                                     .

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fifth edition (1979), Clarendon Press, pp. 269-270.
E. Landau, Über den Zusammenhang einiger neuer Sätze der analytischen Zahlentheorie, Wiener Sitzungberichte, Math. Klasse 115 (1906), pp. 589-632. Cited in Sándor, Mitrinović, & Crstici.
József Sándor, Dragoslav S. Mitrinovic, and Borislav Crstici, Handbook of Number Theory I. Springer, 2005. Section VI.18.

Daniel Forgues, Table of n, a(n) for n = 1..100000 (first 1000 terms from T. D. Noe)
Henri Cohen, Francois Dress, and Mahomed El Marraki, Explicit estimates for summatory functions linked to the Möbius μ-function, Funct. Approx. Comment. Math. 37:1 (2007), pp. 51-63.
G. H. Hardy and S. Ramanujan, The normal number of prime factors of a number n, Q. J. Math., 48 (1917), pp. 76-92.
L. Moser and R. A. MacLeod, The error term for the squarefree integers, Canad. Math. Bull. vol. 9, no. 3, (1966).
K. Rogers, The Schnirelmann density of the squarefree integers, Proc. Amer. Math. Soc. 15 (1964), pp. 515-516.
A. M. Vaidya, On the order of the error function of the square free numbers, Proc. Nat. Inst. Sci. India Part A 32 (1966), pp. 196-201.
Eric Weisstein's World of Mathematics, Squarefree.

One less than A107079.
Cf. A005117, A002321, A057627, A179211, A000720, A081239, A066779, A179215, A284584.
Cf. A158819 Number of squarefree numbers <= n minus round(n/zeta(2)).

a013928 n = a013928_list !! (n-1)
a013928_list = scanl (+) 0 $ map a008966 [1..]
-- Reinhard Zumkeller, Aug 03 2012

ListTools:-PartialSums([0,seq(numtheory:-mobius(i)^2,i=1..100)]); # Robert Israel, Dec 11 2014

Accumulate[Table[Abs[MoebiusMu[n]], {n, 0, 79}]] (* Alonso del Arte, Oct 07 2012 *)
Accumulate[Table[If[SquareFreeQ[n],1,0],{n,0,80}]] (* Harvey P. Dale, Mar 06 2019 *)

a(n)=sum(i=1,n-1,if(issquarefree(i),1,0)) \\ Lifchitz

a(n)=n--;sum(k=1,sqrtint(n),moebius(k)*(n\k^2)) \\ Benoit Cloitre, Oct 25 2009

a(n)=n--; my(s); forfactored(k=1,sqrtint(n), s += n\k[1]^2*moebius(k)); s \\ Charles R Greathouse IV, Nov 05 2017

a(n)=n--; my(s); forsquarefree(k=1, sqrtint(n), s += n\k[1]^2*moebius(k)); s \\ Charles R Greathouse IV, Jan 08 2018

from sympy.ntheory.factor_  import core
def a(n): return sum ([1 for i in range(1, n) if core(i) == i]) # Indranil Ghosh, Apr 16 2017

from math import isqrt
from sympy import mobius
def A013928(n): return sum(mobius(k)*((n-1)//k**2) for k in range(1,isqrt(n-1)+1)) # Chai Wah Wu, Jan 03 2024

a(n) = Sum_{k = 1..n-1} mu(k)^2. - Vladeta Jovovic, May 18 2001
a(n) = Sum_{d = 1..floor(sqrt(n - 1))} mu(d)*floor((n - 1)/d^2) where mu(d) is the Moebius function (A008683). - Vladeta Jovovic, Apr 06 2001
Asymptotic formula (with error term): a(n) = Sum_{k = 1..n-1} mu(k)^2 = Sum_{k = 1..n-1} |mu(k)| = 6*n/Pi^2 + O(sqrt(n)). - Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Jul 20 2002
a(n) = Sum_{k = 0..n} if(k <= n-1, mu(n - k) mod 2, else 0; a(n + 1) = Sum_{k = 0..n} mu(n - k + 1) mod 2. - Paul Barry, May 10 2005
a(n + 1) = Sum_{k = 0..n} abs(mu(n - k + 1)). - Paul Barry, Jul 20 2005
a(n) = Sum_{k = 1..floor(sqrt(n))} mu(k)*floor(n/k^2). - Benoit Cloitre, Oct 25 2009
Landau proved that a(n) = 6*n/Pi^2 + o(sqrt(n)). - Charles R Greathouse IV, Feb 02 2016
Vaidya proved that a(n) = 6*n/Pi^2 + O(n^k) for any k > 2/5 on the Riemann hypothesis. - Charles R Greathouse IV, Feb 02 2016
a(n) = A107079(n)-1. - Antti Karttunen, Oct 07 2016
G.f.: Sum_{k>=1} mu(k)^2*x^(k+1)/(1 - x). - Ilya Gutkovskiy, Feb 06 2017
a(n+1) = n - A057627(n) - Antti Karttunen, Apr 17 2017

cp's OEIS Frontend

A000720 pi(n), the number of primes <= n. Sometimes called PrimePi(n) to distinguish it from the number 3.14159...

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Sage

Formula

Extensions

A025487 Least integer of each prime signature A124832; also products of primorial numbers A002110.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

PARI

PARI

Sage

Formula

Extensions

A008966 a(n) = 1 if n is squarefree, otherwise 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

MuPAD

PARI

PARI

Python

Formula

Extensions

A034386 Primorial numbers (second definition): n# = product of primes <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Python

SageMath

Formula

Extensions

A013928 Number of (positive) squarefree numbers < n.

Views