login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A013928
Number of (positive) squarefree numbers < n.
81
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. A158819 Number of squarefree numbers <= n minus round(n/zeta(2)).
Sequence in context: A335152 A111899 A074753 * A172104 A006161 A132351
KEYWORD
nonn,easy
STATUS
approved