OFFSET
1,8
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
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
EXAMPLE
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
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}]
PROG
(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
CROSSREFS
KEYWORD
AUTHOR
Andres Cicuttin, May 23 2021
STATUS
approved