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

0, 1, 3, 5, 9, 11, 17, 22, 28, 32, 42, 48, 60, 66, 74, 84, 100, 107, 125, 137, 149, 159, 181, 191, 211, 223, 243, 261, 289, 297, 327, 348, 368, 384, 408, 428, 464, 482, 506, 526, 566, 578, 620, 650, 678, 700, 746, 768, 810, 831, 863, 899, 951, 971, 1011, 1041

Offset

1,3

Comments

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

Links

Chai Wah Wu, Table of n, a(n) for n = 1..10000

Formula

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

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

Example

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

Maple

f:= proc(n) nops(select(t -> issqr(igcd(t, n)), [$1..n-1])) end proc:
ListTools:-PartialSums(map(f, [$1..100])); # Robert Israel, Jun 16 2026

Prog

(Python)
import math
def A392341(n):
    return sum(1 for x in range(1, n+1) for y in range(x+1, n+1)
               if math.isqrt(g := math.gcd(x, y))**2 == g)
print([A392341(n) for n in range(1, 57)])
(Python)
# uses Python code in A002088
from math import isqrt
def A392341(n):
    c, j, j2 = -isqrt(n), 1, 0
    while j <= n:
        k = n//j
        m = n//k
        c += (-j2+(j2:=A002088(m)))*isqrt(k)
        j = m+1
    return c # Chai Wah Wu, Jun 22 2026
(PARI) a(n) = sum(x=1, n, sum(y=x+1, n, issquare(gcd(x, y)))); \\ Michel Marcus, Jun 10 2026

Crossrefs

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

Sequence in context: A225523 A007952 A145819 * A317827 A296768 A302596

Adjacent sequences: A392338 A392339 A392340 * A392342 A392343 A392344

Keyword

nonn,new

Author

Shahin Saadati, Jun 07 2026

Status

approved