A013928 Number of (positive) squarefree numbers < n.

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

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

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
(Python)
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

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

Henri Lifchitz

Status

approved