A070072 Number of distinct rectangles with integer sides <= n and squarefree area.
1, 2, 4, 4, 7, 9, 14, 14, 14, 17, 24, 24, 32, 37, 43, 43, 54, 54, 66, 66, 74, 83, 98, 98, 98, 108, 108, 108, 125, 133, 152, 152, 165, 178, 193, 193, 216, 231, 248, 248, 274, 285, 313, 313, 313, 331, 361, 361, 361, 361, 382, 382, 414
Offset: 1
Keywords
Examples
There are seven rectangles with sides <= 5 having a squarefree area: 1 X 1, 1 X 2, 1 X 3, 1 X 5, 2 X 3, 2 X 5 and 3 X 5, whereas 1 X 4, 2 X 2, 2 X 4, 3 X 3, 3 X 4, 4 X 4, 4 X 5 and 5 X 5 are not squarefree; therefore a(5) = 7.
Links
- Reinhard Zumkeller, Table of n, a(n) for n = 1..500
- Eric Weisstein's World of Mathematics, Squarefree.
Programs
-
Haskell
a070072 n = length [() | x <- [1..n], y <- [1..x], a008966 (x*y) == 1] -- Reinhard Zumkeller, May 26 2012
-
Magma
[&+[&+[MoebiusMu(i*j)^2:j in [1..i]]:i in [1..n]]:n in [1..53]]; // Marius A. Burtea, Oct 17 2019
Formula
a(n) = Sum_{i=1..n} Sum_{j= 1..i} mu(i*j)^2, where mu is the Moebius function (A008683). - Ridouane Oudra, Oct 17 2019
a(n) = (A118259(n) + 1)/2. - Ridouane Oudra, May 06 2025
a(n) = c * n^2 / 2 + O(n*log(n)), where c = Product_{p prime} (1 - (3*p-2)/(p^3)) (A065473). - Amiram Eldar, May 12 2025