%I #41 Dec 23 2020 07:42:17
%S 0,1,4,8,16,27,40,58,80,105,128,158,198,237,278,336,382,435,502,574,
%T 632,699,798,868,968,1063,1176,1262,1362,1505,1590,1732,1880,2007,
%U 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
%N Number of pairs (x,y): 1 <= x < y <= n*n, such that x*y is a square.
%H Edward Krogius, <a href="/A339026/b339026.txt">Table of n, a(n) for n = 1..1000</a>
%H Edward Krogius, <a href="/A339026/a339026.png">Illustration of 105 solutions in 100x100 grid</a>
%F a(n) = Sum_{j=2..n} phi(j) * floor(n^2/j^2).
%F a(n) = (A338894(n) - n^2)/2.
%F a(n) = A132189(n^2)/2. - _Antti Karttunen_, Nov 23 2020
%e For n = 3, we have the following solutions: (1,4), (1,9), (2,8), (4,9), therefore a(3) = 4.
%e 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.
%t Array[Sum[EulerPhi[j] Floor[(#^2)/(j^2)], {j, 2, #}] &, 59] (* _Michael De Vlieger_, Dec 11 2020 *)
%o (PARI) A339026(n) = sum(i=2,n,floor(n^2/i^2)*eulerphi(i)); \\ _Antti Karttunen_, Nov 23 2020
%Y Cf. A000010, A015614, A018805, A132188, A132189, A132345, A338894.
%K nonn
%O 1,3
%A _Edward Krogius_, Nov 19 2020