A013928 - OEIS

%I #105 Aug 04 2024 06:40:05

%S 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 17,17,18,19,20,20,21,22,23,23,24,25,26,26,27,28,29,29,29,30,31,31,31,

%U 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

%N Number of (positive) squarefree numbers < n.

%C 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 a(n) = Sum_{k=1..n-1} A008966(k). - _Reinhard Zumkeller_, Jul 05 2010

%C 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 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 G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fifth edition (1979), Clarendon Press, pp. 269-270.

%D 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 József Sándor, Dragoslav S. Mitrinovic, and Borislav Crstici, Handbook of Number Theory I. Springer, 2005. Section VI.18.

%H 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 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 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 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 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 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Squarefree.html">Squarefree</a>.

%F a(n) = Sum_{k = 1..n-1} mu(k)^2. - _Vladeta Jovovic_, May 18 2001

%F 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 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 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 a(n + 1) = Sum_{k = 0..n} abs(mu(n - k + 1)). - _Paul Barry_, Jul 20 2005

%F a(n) = Sum_{k = 1..floor(sqrt(n))} mu(k)*floor(n/k^2). - _Benoit Cloitre_, Oct 25 2009

%F Landau proved that a(n) = 6*n/Pi^2 + o(sqrt(n)). - _Charles R Greathouse IV_, Feb 02 2016

%F 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 a(n) = A107079(n)-1. - _Antti Karttunen_, Oct 07 2016

%F G.f.: Sum_{k>=1} mu(k)^2*x^(k+1)/(1 - x). - _Ilya Gutkovskiy_, Feb 06 2017

%F a(n+1) = n - A057627(n) - _Antti Karttunen_, Apr 17 2017

%e a(10) = 6 because there are 6 squarefree numbers up to 10: 1, 2, 3, 5, 6, 7.

%e a(11) = 7 because there are 7 squarefree numbers up to 11: the numbers listed above for 10, plus 10 itself.

%e 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 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

%e 1, 0, 1, 0, 1, 0, 1, 0, 1, 0  1, 0, ...

%e 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, ...

%e 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...

%e 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, ...

%e 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, ...

%e 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, ...

%e 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...

%e 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, ...

%e 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, ...

%e 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, ...

%e 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, ...

%e .                                   .

%e .                                    .

%e .                                     .

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

%t Accumulate[Table[Abs[MoebiusMu[n]], {n, 0, 79}]] (* _Alonso del Arte_, Oct 07 2012 *)

%t Accumulate[Table[If[SquareFreeQ[n],1,0],{n,0,80}]] (* _Harvey P. Dale_, Mar 06 2019 *)

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

%o (PARI) a(n)=n--;sum(k=1,sqrtint(n),moebius(k)*(n\k^2)) \\ _Benoit Cloitre_, Oct 25 2009

%o (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 (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 (Haskell)

%o a013928 n = a013928_list !! (n-1)

%o a013928_list = scanl (+) 0 $ map a008966 [1..]

%o -- _Reinhard Zumkeller_, Aug 03 2012

%o (Python)

%o from sympy.ntheory.factor_  import core

%o def a(n): return sum ([1 for i in range(1, n) if core(i) == i]) # _Indranil Ghosh_, Apr 16 2017

%o (Python)

%o from math import isqrt

%o from sympy import mobius

%o 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 One less than A107079.

%Y Cf. A005117, A002321, A057627, A179211, A000720, A081239, A066779, A179215, A284584.

%Y Cf. A158819 Number of squarefree numbers <= n minus round(n/zeta(2)).

%K nonn,easy

%O 1,3

%A _Henri Lifchitz_