%I #26 Jan 10 2020 05:31:16
%S 1,1,2,2,3,5,6,10,17,21,26,70,63,125,290,314,411,1121,1098,2558,5005,
%T 5909,8054,23210,26589,44301,88826,134554,170823,598805,478318,908194,
%U 2155345,2690421,5382190,10809394,10761723,21523445,48449998,72956830,87169619
%N Number of oriented circulant graphs of order n up to Cayley isomorphism.
%C This sequence may be incorrect, but for the moment I don't think so. (Even if wrong it could represent something else.) In particular, this sequence should agree with A060966 for all squarefree n. For nonsquarefree n this sequence is allowed to be greater.
%C An oriented graph is a directed graph in which there is at most one edge between any two vertices. (A directed graph can have one in each direction.)
%C Two circulant graphs are Cayley isomorphic if there is a d, which is necessarily prime to n, that transforms through multiplication modulo n the step values of one graph into those of the other.
%C Ideally this sequence should be to A060966 as A056391 is to A049297.
%H Andrew Howroyd, <a href="/A283189/b283189.txt">Table of n, a(n) for n = 1..500</a>
%e Case n=8:
%e Only 1, 3, 5, 7 are prime to 8.
%e Multiplication module 8 is described by the following multiplication table.
%e 1 2 3 4 5 6 7 => (1)(2)(3)[4](5)(6)(7) => 6 => 3^3 => 27
%e 3 6 1 4 7 2 5 => (1 3)[2 6][4](5 7) => 2 => 3^1 => 3
%e 5 2 7 4 1 6 3 => (1 5)(2)(3 7)[4](6) => 4 => 3^2 => 9
%e 7 6 5 4 3 2 1 => [1 7][2 6][3 5][4] => 0 => 3^0 => 1
%e Each row of the multiplication table can be viewed as a permutation and together these form a commutative group on 4 elements. In this case the group is isomorphic to the cyclic group C_4. Each permutation can be represented in cycle notation. However, only those cycles that do not include both a value and its negative can be used to form symmetrical solutions. In the above calculation, square brackets have been used to denote excluded cycles. Each remaining pair introduces a factor of 3 corresponding to no edge, or an edge in one of two directions. Putting everything together with Burnsides's lemma gives a(8) = (27 + 3 + 9 + 1)/4 = 10.
%e The corresponding step sets (one from each equivalence class) are:
%e {}, {1}, {2}, {1,2}, {1,-2}, {1,3}, {1,-3}, {1,2,3}, {1,2,-3}, {1,-2,-3}.
%t IsLeastPoint[s_, r_, f_] := Module[{t}, t = f[s]; While[t > s && t != r, t = f[t]]; t == s && t != r];
%t c[n_, k_] := Sum[Boole@ IsLeastPoint[u, n-u, Mod[# k, n]&], {u, 1, n-1}]/2;
%t a[n_] := Sum[If[GCD[n, k] == 1, 3^c[n, k], 0], {k, 1, n}]/EulerPhi[n];
%t a /@ Range[1, 41] (* _Jean-François Alcover_, Sep 21 2019, from PARI *)
%o (PARI)
%o IsLeastPoint(s,r,f)={my(t=f(s)); while(t>s&&t<>r,t=f(t));t==s&&t<>r}
%o C(n,k)=sum(u=1,n-1,IsLeastPoint(u,n-u,v->v*k%n))/2;
%o a(n)=sum(k=1, n, if (gcd(n,k)==1, 3^C(n,k),0))/eulerphi(n);
%Y Cf. A060966, A056391, A049297.
%K nonn
%O 1,3
%A _Andrew Howroyd_, Apr 30 2017