A339026 Number of pairs (x,y): 1 <= x < y <= n*n, such that x*y is a square.

0, 1, 4, 8, 16, 27, 40, 58, 80, 105, 128, 158, 198, 237, 278, 336, 382, 435, 502, 574, 632, 699, 798, 868, 968, 1063, 1176, 1262, 1362, 1505, 1590, 1732, 1880, 2007, 2150, 2272, 2434, 2567, 2746, 2930, 3062, 3265, 3444, 3654, 3832, 4035, 4284, 4454, 4668, 4875, 5142, 5364, 5590, 5889, 6078, 6336, 6614, 6881, 7166

Offset: 1

Author

Edward Krogius, Nov 19 2020

Keywords

• nonn

Examples

			For n = 3, we have the following solutions: (1,4), (1,9), (2,8), (4,9), therefore a(3) = 4.
For n = 4, we have the following solutions: (1,4), (1,9), (1,16), (2,8), (3,12), (4,9), (4,16), (9,16), therefore a(4) = 8.
		

Links

• Edward Krogius, Table of n, a(n) for n = 1..1000
• Edward Krogius, Illustration of 105 solutions in 100x100 grid

Crossrefs

Cf. A000010, A015614, A018805, A132188, A132189, A132345, A338894.

Programs

Mathematica

Array[Sum[EulerPhi[j] Floor[(#^2)/(j^2)], {j, 2, #}] &, 59] (* Michael De Vlieger, Dec 11 2020 *)

PARI

A339026(n) = sum(i=2,n,floor(n^2/i^2)*eulerphi(i)); \\ Antti Karttunen, Nov 23 2020

Formula

a(n) = Sum_{j=2..n} phi(j) * floor(n^2/j^2).

a(n) = (A338894(n) - n^2)/2.

a(n) = A132189(n^2)/2. - Antti Karttunen, Nov 23 2020