|
|
A013928
|
|
Number of (positive) squarefree numbers < n.
|
|
70
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
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
|
Eric Weisstein's World of Mathematics, Squarefree.
|
|
FORMULA
|
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
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
|
|
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..]
(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
|
Cf. A158819 Number of squarefree numbers <= n minus round(n/zeta(2)).
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|