A344574 Number of ordered pairs (i,j) with 0 < i < j < n such that gcd(i,j,n) > 1.

0, 0, 0, 0, 0, 1, 0, 3, 1, 6, 0, 13, 0, 15, 7, 21, 0, 37, 0, 39, 16, 45, 0, 73, 6, 66, 28, 81, 0, 130, 0, 105, 46, 120, 21, 181, 0, 153, 67, 189, 0, 262, 0, 213, 118, 231, 0, 337, 15, 306, 121, 303, 0, 433, 51, 369, 154, 378, 0, 583, 0, 435, 217, 465

Offset: 1

Author

Andres Cicuttin, May 23 2021

Keywords

• nonn
• easy
• look

Comments

A 4-regular circulant graph of order n, C(n,i,j), is connected if and only if gcd(n,i,j) = 1, where 0 < i < j < n.

a(n) >= 1 iff n is a composite > 4. - Robert Israel, Nov 26 2024

Examples

			a(8) = 3 via (i, j, n) in {(2, 4, 8), (2, 6, 8), (4, 6, 8)} and that's three such tuples. - _David A. Corneth_, Nov 27 2024
		

Links

• Robert Israel, Table of n, a(n) for n = 1..10000
• Paul Theo Meijer, Connectivities and diameters of circulant graphs, Thesis, 1991, Simon Fraser University.
• Eric Weisstein's World of Mathematics, Circulant Graph

Crossrefs

Cf. A000741, A075545, A344517.

Programs

Maple

f:= proc(n) local t,i,g;
t:= 0:
for i from 1 to n-2 do
  g:= igcd(i,n);
  if g > 1 then t:= t + nops(select(s -> igcd(s,g) > 1, [$i+1..n-1])) fi
od:
t;
end proc:
map(f, [$1..80]); # Robert Israel, Nov 26 2024

Mathematica

npairs[n_]:=Module[{k=0},
Do[Do[
If[GCD[i,j,n]>1,k++]
,{i,1,j-1}],{j,2,n-1}];
Return[k]];
Table[npairs[n],{n,1,60}]

PARI

a(n) = {my(res = 0, d = divisors(factorback(factor(n)[,1]))); for(i = 2, #d, res+= moebius(d[i])*binomial((n-1)\d[i], 2)); -res} \\ David A. Corneth, Nov 27 2024