A344574 - OEIS

%I #25 Nov 27 2024 06:18:41

%S 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,

%T 130,0,105,46,120,21,181,0,153,67,189,0,262,0,213,118,231,0,337,15,

%U 306,121,303,0,433,51,369,154,378,0,583,0,435,217,465

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

%C 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.

%C a(n) >= 1 iff n is a composite > 4. - _Robert Israel_, Nov 26 2024

%H Robert Israel, <a href="/A344574/b344574.txt">Table of n, a(n) for n = 1..10000</a>

%H Paul Theo Meijer, <a href="https://core.ac.uk/display/56367757">Connectivities and diameters of circulant graphs</a>, Thesis, 1991, Simon Fraser University.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CirculantGraph.html">Circulant Graph</a>

%e 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

%p f:= proc(n) local t,i,g;

%p t:= 0:

%p for i from 1 to n-2 do

%p   g:= igcd(i,n);

%p   if g > 1 then t:= t + nops(select(s -> igcd(s,g) > 1, [$i+1..n-1])) fi

%p od:

%p t;

%p end proc:

%p map(f, [$1..80]); # _Robert Israel_, Nov 26 2024

%t npairs[n_]:=Module[{k=0},

%t Do[Do[

%t If[GCD[i,j,n]>1,k++]

%t ,{i,1,j-1}],{j,2,n-1}];

%t Return[k]];

%t Table[npairs[n],{n,1,60}]

%o (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

%Y Cf. A000741, A075545, A344517.

%K nonn,easy,look

%O 1,8

%A _Andres Cicuttin_, May 23 2021