A373041 2*a(n) is the number of triangles with integer sides (x, y, n), x < y < n, and gcd(x, y, n) = 1.

1, 2, 3, 4, 6, 7, 10, 10, 15, 15, 20, 20, 28, 24, 36, 32, 42, 40, 55, 44, 65, 57, 72, 66, 91, 68, 105, 88, 110, 100, 132, 102, 153, 126, 156, 136, 190, 138, 210, 170, 204, 187, 253, 184, 273, 215, 272, 240, 325, 234, 340, 276, 342, 301, 406, 280, 435, 345, 414, 368, 480

Offset: 5

Author

Andrés Sancho and Hugo Pfoertner, May 21 2024

Keywords

• nonn

Comments

Offset 5 is chosen to exclude the only count not divisible by 2, which represents the triangle with sides (2,3,4).

Links

• David A. Corneth, Table of n, a(n) for n = 5..10000

Crossrefs

Cf. A023022, A123323, A373051.

Programs

PARI

a(n) = {if(isprime(n), n\=2; return(n*(n-1)/2)); my(res = 0, g, sn = vecprod(factor(n)[,1])); for(b = (n + 3)\2, n-1, g = gcd(b, sn); if(g == 1, res+=(2*b - n - 1);, my(d, e); d = divisors(g); for(i = 1, #d, e = (-1)^(omega(d[i])); t = ((b-1)\d[i])*e; t-= ((n-b)\d[i])*e; res+=t))); res>>1} \\ David A. Corneth, May 22 2024

Formula

a(n) = (A373051(n) - A373051(n-1))/2 for n >= 5.

a(n) = (A123323(n) - 3*A023022(n))/2 for n >= 5.