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, 47, 48, 49, 50, 50, 50, 51
Offset: 1
Examples
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, ... . . . . . .
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.
Crossrefs
Programs
-
Haskell
a013928 n = a013928_list !! (n-1) a013928_list = scanl (+) 0 $ map a008966 [1..] -- Reinhard Zumkeller, Aug 03 2012
-
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 *) -
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
-
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
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
Comments