A392341 - OEIS

%I #64 Jun 23 2026 01:22:22

%S 0,1,3,5,9,11,17,22,28,32,42,48,60,66,74,84,100,107,125,137,149,159,

%T 181,191,211,223,243,261,289,297,327,348,368,384,408,428,464,482,506,

%U 526,566,578,620,650,678,700,746,768,810,831,863,899,951,971,1011,1041

%N Number of pairs (x, y) with 1 <= x < y <= n such that gcd(x, y) is a perfect square.

%C Counts pairs (x, y) with 1 <= x < y <= n whose greatest common divisor is a perfect square.

%H Chai Wah Wu, <a href="/A392341/b392341.txt">Table of n, a(n) for n = 1..10000</a>

%F a(n) = Sum_{1 <= x < y <= n} [floor(sqrt(gcd(x, y)))^2 == gcd(x, y)].

%F a(n) = A370905(n) - A000196(n), i.e. partial sum of A206369 - A010052. a(n) ~ (Pi^2/30) * n^2 - _Chai Wah Wu_, Jun 22 2026

%e a(1) = |{}| = 0.

%e a(2) = |{(1, 2)}| = 1.

%e a(3) = |{(1, 2), (1, 3), (2, 3)}| = 3.

%e a(4) = |{(1, 2), (1, 3), (2, 3), (1, 4), (2, 4), (3, 4)}| = 5.

%p f:= proc(n) nops(select(t -> issqr(igcd(t,n)), [$1..n-1])) end proc:

%p ListTools:-PartialSums(map(f, [$1..100])); # _Robert Israel_, Jun 16 2026

%o (Python)

%o import math

%o def A392341(n):

%o     return sum(1 for x in range(1, n+1) for y in range(x+1, n+1)

%o                if math.isqrt(g := math.gcd(x, y))**2 == g)

%o print([A392341(n) for n in range(1, 57)])

%o (Python)

%o # uses Python code in A002088

%o from math import isqrt

%o def A392341(n):

%o     c, j, j2 = -isqrt(n), 1, 0

%o     while j <= n:

%o         k = n//j

%o         m = n//k

%o         c += (-j2+(j2:=A002088(m)))*isqrt(k)

%o         j = m+1

%o     return c # _Chai Wah Wu_, Jun 22 2026

%o (PARI) a(n) = sum(x=1, n, sum(y=x+1, n, issquare(gcd(x,y)))); \\ _Michel Marcus_, Jun 10 2026

%Y Cf. A015614, A370905, A000196, A206369, A010052.

%K nonn

%O 1,3

%A _Shahin Saadati_, Jun 07 2026