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

Author

Reinhard Zumkeller, Apr 21 2002

Keywords

• nonn

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.

Crossrefs

Cf. A005117, A065473, A070073.

Cf. A008966, A008683, A118259.

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