OFFSET
1,1
COMMENTS
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).
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]
LINKS
Swee Hong Chan, Henk D. L. Hollmann, Dmitrii V. Pasechnik, Sandpile groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields, arXiv:1405.0113 [math.CO], (1-May-2014).
Swee Hong Chan, Henk D. L. Hollmann, Dmitrii V. Pasechnik, Sandpile groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields, Journal of Algebra (2015), pp. 268-295.
Wikipedia, BEST Theorem [Dmitrii Pasechnik, Dec 07 2014]
FORMULA
a(n) = A094678(n)*2^(n-1) for n > 1. [Joerg Arndt, Dec 07 2014, amended by Georg Fischer, Jun 21 2020]
MATHEMATICA
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]];
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)]];
Array[a, 30] (* Jean-François Alcover, Jul 22 2018, after Joerg Arndt *)
PROG
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
Joerg Arndt, Jul 03 2011
EXTENSIONS
More terms from Dmitrii Pasechnik, Dec 07 2014
STATUS
approved