%I #22 Aug 06 2024 06:32:51
%S 1,2,2,4,3,8,4,12,8,20,8,48,14,48,44,88,36,192,60,336,200,416,188,
%T 1344,424,1400,944,3104,1182,8768,2192,8784,6768,16460,11144,46848,
%U 14602,58288,44424,138432,52488,355200,99880,432576,351712,762608,364724,2151936,798960
%N Number of circulant graphs on n vertices up to Cayley isomorphism.
%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. For squarefree n this is the only way that two circulant graphs can be isomorphic (See A049287).
%H Andrew Howroyd, <a href="/A285620/b285620.txt">Table of n, a(n) for n = 1..200</a>
%H V. A. Liskovets and R. Poeschel, <a href="https://citeseerx.ist.psu.edu/pdf/b76573e0c2df2ff117cef015809e232a3747f585">On the enumeration of circulant graphs of prime-power and squarefree orders.</a>
%t IsLeastPoint[s_, f_] := Module[{t = f[s]}, While[t > s, t=f[t]]; Boole[s == t]];
%t c[n_, k_] := Sum[IsLeastPoint[u, Abs[Mod[#*k + Quotient[n, 2], n] - Quotient[n, 2]]&], {u, 1, n/2}];
%t a[n_] := If[n < 3, n, Sum[If[GCD[k, n] == 1, 2^c[n, k], 0]*2/EulerPhi[n], {k, 1, n/2}]];
%t Array[a, 50] (* _Jean-François Alcover_, Jun 12 2017, translated from PARI *)
%o (PARI)
%o IsLeastPoint(s,f)={my(t=f(s)); while(t>s,t=f(t));s==t}
%o C(n,k)=sum(u=1,n/2,IsLeastPoint(u,v->abs((v*k+n\2)%n-n\2)));
%o a(n)=if(n<3, n, sum(k=1, n/2, if (gcd(k, n)==1, 2^C(n,k),0))*2/eulerphi(n));
%Y Cf. A049287, A056391 (circulant digraphs), A049297, A038782.
%K nonn
%O 1,2
%A _Andrew Howroyd_, Apr 22 2017