cp's OEIS Frontend

A013928 Number of (positive) squarefree numbers < n.

%I A013928 #108 Jul 15 2025 15:38:32
%S A013928 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,
%T A013928 17,17,18,19,20,20,21,22,23,23,24,25,26,26,27,28,29,29,29,30,31,31,31,
%U A013928 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
%N A013928 Number of (positive) squarefree numbers < n.
%C A013928 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
%C A013928 a(n) = Sum_{k=1..n-1} A008966(k). - _Reinhard Zumkeller_, Jul 05 2010
%C A013928 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]
%C A013928 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
%D A013928 G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fifth edition (1979), Clarendon Press, pp. 269-270.
%D A013928 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.
%D A013928 József Sándor, Dragoslav S. Mitrinovic, and Borislav Crstici, Handbook of Number Theory I. Springer, 2005. Section VI.18.
%H A013928 Daniel Forgues, <a href="/A013928/b013928.txt">Table of n, a(n) for n = 1..100000</a> (first 1000 terms from T. D. Noe)
%H A013928 Henri Cohen, Francois Dress, and Mahomed El Marraki, <a href="https://doi.org/10.7169/facm/1229618741">Explicit estimates for summatory functions linked to the Möbius μ-function</a>, Funct. Approx. Comment. Math. 37:1 (2007), pp. 51-63.
%H A013928 G. H. Hardy and S. Ramanujan, <a href="http://ramanujan.sirinudi.org/Volumes/published/ram35.html">The normal number of prime factors of a number n</a>, Q. J. Math., 48 (1917), pp. 76-92.
%H A013928 L. Moser and R. A. MacLeod, <a href="http://cms.math.ca/10.4153/CMB-1966-039-4">The error term for the squarefree integers</a>, Canad. Math. Bull. vol. 9, no. 3, (1966).
%H A013928 K. Rogers, <a href="http://dx.doi.org/10.1090/S0002-9939-1964-0163893-X">The Schnirelmann density of the squarefree integers</a>, Proc. Amer. Math. Soc. 15 (1964), pp. 515-516.
%H A013928 A. M. Vaidya, <a href="http://www.new1.dli.ernet.in/data1/upload/insa/INSA_1/20005abb_196.pdf">On the order of the error function of the square free numbers</a>, Proc. Nat. Inst. Sci. India Part A 32 (1966), pp. 196-201.
%H A013928 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Squarefree.html">Squarefree</a>.
%F A013928 a(n) = Sum_{k = 1..n-1} mu(k)^2. - _Vladeta Jovovic_, May 18 2001
%F A013928 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
%F A013928 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
%F A013928 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
%F A013928 a(n + 1) = Sum_{k = 0..n} abs(mu(n - k + 1)). - _Paul Barry_, Jul 20 2005
%F A013928 a(n) = Sum_{k = 1..floor(sqrt(n))} mu(k)*floor(n/k^2). - _Benoit Cloitre_, Oct 25 2009
%F A013928 Landau proved that a(n) = 6*n/Pi^2 + o(sqrt(n)). - _Charles R Greathouse IV_, Feb 02 2016
%F A013928 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
%F A013928 a(n) = A107079(n)-1. - _Antti Karttunen_, Oct 07 2016
%F A013928 G.f.: Sum_{k>=1} mu(k)^2*x^(k+1)/(1 - x). - _Ilya Gutkovskiy_, Feb 06 2017
%F A013928 a(n+1) = n - A057627(n) - _Antti Karttunen_, Apr 17 2017
%e A013928 a(10) = 6 because there are 6 squarefree numbers up to 10: 1, 2, 3, 5, 6, 7.
%e A013928 a(11) = 7 because there are 7 squarefree numbers up to 11: the numbers listed above for 10, plus 10 itself.
%e A013928 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
%e A013928 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
%e A013928 1, 0, 1, 0, 1, 0, 1, 0, 1, 0  1, 0, ...
%e A013928 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, ...
%e A013928 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...
%e A013928 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, ...
%e A013928 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, ...
%e A013928 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, ...
%e A013928 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...
%e A013928 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, ...
%e A013928 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, ...
%e A013928 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, ...
%e A013928 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, ...
%e A013928 .                                   .
%e A013928 .                                    .
%e A013928 .                                     .
%p A013928 ListTools:-PartialSums([0,seq(numtheory:-mobius(i)^2,i=1..100)]); # _Robert Israel_, Dec 11 2014
%t A013928 Accumulate[Table[Abs[MoebiusMu[n]], {n, 0, 79}]] (* _Alonso del Arte_, Oct 07 2012 *)
%t A013928 Accumulate[Table[If[SquareFreeQ[n],1,0],{n,0,80}]] (* _Harvey P. Dale_, Mar 06 2019 *)
%o A013928 (PARI) a(n)=sum(i=1,n-1,if(issquarefree(i),1,0)) \\ Lifchitz
%o A013928 (PARI) a(n)=n--;sum(k=1,sqrtint(n),moebius(k)*(n\k^2)) \\ _Benoit Cloitre_, Oct 25 2009
%o A013928 (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
%o A013928 (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
%o A013928 (Haskell)
%o A013928 a013928 n = a013928_list !! (n-1)
%o A013928 a013928_list = scanl (+) 0 $ map a008966 [1..]
%o A013928 -- _Reinhard Zumkeller_, Aug 03 2012
%o A013928 (Python)
%o A013928 from sympy.ntheory.factor_  import core
%o A013928 def a(n): return sum ([1 for i in range(1, n) if core(i) == i]) # _Indranil Ghosh_, Apr 16 2017
%o A013928 (Python)
%o A013928 from math import isqrt
%o A013928 from sympy import mobius
%o A013928 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
%Y A013928 One less than A107079.
%Y A013928 Cf. A005117, A002321, A057627, A179211, A000720, A081239, A066779, A179215, A284584.
%Y A013928 Cf. A158819 Number of squarefree numbers <= n minus round(n/zeta(2)).
%K A013928 nonn,easy
%O A013928 1,3
%A A013928 _Henri Lifchitz_