The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A013928 Number of (positive) squarefree numbers < n. 60
 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,3 COMMENTS 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 REFERENCES 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. LINKS T. D. Noe and 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. FORMULA 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 EXAMPLE 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, ... .                                   . .                                    . .                                     . MAPLE ListTools:-PartialSums([0, seq(numtheory:-mobius(i)^2, i=1..100)]); # Robert Israel, Dec 11 2014 MATHEMATICA 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 *) PROG (PARI) a(n)=sum(i=1, n-1, if(issquarefree(i), 1, 0)) \\ Lifchitz (PARI) a(n)=n--; sum(k=1, sqrtint(n), moebius(k)*(n\k^2)) \\ Benoit Cloitre, Oct 25 2009 (PARI) 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 (PARI) 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 (Haskell) a013928 n = a013928_list !! (n-1) a013928_list = scanl (+) 0 \$ map a008966 [1..] -- Reinhard Zumkeller, Aug 03 2012 (Python) 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 CROSSREFS 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)). Sequence in context: A335152 A111899 A074753 * A172104 A006161 A132351 Adjacent sequences:  A013925 A013926 A013927 * A013929 A013930 A013931 KEYWORD nonn,easy AUTHOR STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified July 26 10:21 EDT 2021. Contains 346294 sequences. (Running on oeis4.)