%I #40 Jun 21 2020 06:00:21
%S 2,4,24,64,512,1728,13312,32768,373248,1310720,10903552,35831808,
%T 287965184,1240465408,10319560704,26843545600,331895275520,
%U 1253826625536,10690521726976,34359738368000,347727917481984,1307761908383744,11445236333019136,30814043149172736
%N Number of Hamiltonian cycles in the 3-ary de Bruijn graph.
%C The 3-ary de Bruijn graph is the graph with 3*n nodes {0..3*n-1} and edges from each i to 3*i (mod 3*n), 3*i+1 (mod 3*n), and 3*i+2 (mod 3*n).
%C Correctness of a(n) = A094678(n)*2^(n-1) for all n>1 follows from S. H. Chan et al. below, together with the BEST theorem. [_Dmitrii Pasechnik_, Dec 07 2014]
%H Swee Hong Chan, Henk D. L. Hollmann, Dmitrii V. Pasechnik, <a href="http://arxiv.org/abs/1405.0113">Sandpile groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields</a>, arXiv:1405.0113 [math.CO], (1-May-2014).
%H Swee Hong Chan, Henk D. L. Hollmann, Dmitrii V. Pasechnik, <a href="http://dx.doi.org/10.1016/j.jalgebra.2014.08.029">Sandpile groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields</a>, Journal of Algebra (2015), pp. 268-295.
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/BEST_theorem">BEST Theorem</a> [_Dmitrii Pasechnik_, Dec 07 2014]
%F a(n) = A094678(n)*2^(n-1) for n > 1. [_Joerg Arndt_, Dec 07 2014, amended by _Georg Fischer_, Jun 21 2020]
%t p = 3; numNormalp[n_] := Module[{r, i, pp = 1}, Do[r = MultiplicativeOrder[p, d]; i = EulerPhi[d]/r; pp *= (1 - 1/p^r)^i, {d, Divisors[n]}]; Return[pp]];
%t a[n_] := Module[{t = 1, q = n, pp}, While[0 == Mod[q, p], q /= p; t += 1]; pp = numNormalp[q]; pp *= p^n/n; Return[pp*2^(n - 1)]];
%t Array[a, 30] (* _Jean-François Alcover_, Jul 22 2018, after _Joerg Arndt_ *)
%o (PARI) a(n)=if(n==1,return(2));my(r,i,t=3^n/n<<(n-1));fordiv(n/3^valuation(n,3), d, r=znorder(Mod(3,d)); i=eulerphi(d)/r; t*=(1-1/3^r)^i);t \\ See comments. _Charles R Greathouse IV_, Jan 03 2013
%Y Cf. A003474, A094678.
%Y Cf. A003473, A027362.
%K nonn
%O 1,1
%A _Joerg Arndt_, Jul 03 2011
%E More terms from _Dmitrii Pasechnik_, Dec 07 2014