cp's OEIS Frontend

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

%I A344574 #30 Mar 22 2025 04:40:07
%S A344574 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 A344574 130,0,105,46,120,21,181,0,153,67,189,0,262,0,213,118,231,0,337,15,
%U A344574 306,121,303,0,433,51,369,154,378,0,583,0,435,217,465
%N A344574 Number of ordered pairs (i,j) with 0 < i < j < n such that gcd(i,j,n) > 1.
%C A344574 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 A344574 a(n) >= 1 iff n is a composite > 4. - _Robert Israel_, Nov 26 2024
%H A344574 Robert Israel, <a href="/A344574/b344574.txt">Table of n, a(n) for n = 1..10000</a>
%H A344574 Paul Theo Meijer, <a href="https://core.ac.uk/display/56367757">Connectivities and diameters of circulant graphs</a>, Thesis, 1991, Simon Fraser University.
%H A344574 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CirculantGraph.html">Circulant Graph</a>
%e A344574 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 A344574 f:= proc(n) local t,i,g;
%p A344574 t:= 0:
%p A344574 for i from 1 to n-2 do
%p A344574   g:= igcd(i,n);
%p A344574   if g > 1 then t:= t + nops(select(s -> igcd(s,g) > 1, [$i+1..n-1])) fi
%p A344574 od:
%p A344574 t;
%p A344574 end proc:
%p A344574 map(f, [$1..80]); # _Robert Israel_, Nov 26 2024
%t A344574 npairs[n_]:=Module[{k=0},
%t A344574 Do[Do[
%t A344574 If[GCD[i,j,n]>1,k++]
%t A344574 ,{i,1,j-1}],{j,2,n-1}];
%t A344574 Return[k]];
%t A344574 Table[npairs[n],{n,1,60}]
%o A344574 (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 A344574 Cf. A000741, A075545, A344517.
%K A344574 nonn,easy,look
%O A344574 1,8
%A A344574 _Andres Cicuttin_, May 23 2021