%I M0564 N0203 #213 Jan 28 2024 08:03:05

%S 1,2,3,4,6,8,14,20,36,60,108,188,352,632,1182,2192,4116,7712,14602,

%T 27596,52488,99880,190746,364724,699252,1342184,2581428,4971068,

%U 9587580,18512792,35792568,69273668,134219796,260301176,505294128,981706832

%N Number of n-bead necklaces with 2 colors when turning over is not allowed; also number of output sequences from a simple n-stage cycling shift register; also number of binary irreducible polynomials whose degree divides n.

%C Also a(n)-1 is the number of 1's in the truth table for the lexicographically least de Bruijn cycle (Fredricksen).

%C In music, a(n) is the number of distinct classes of scales and chords in an n-note equal-tempered tuning system. - _Paul Cantrell_, Dec 28 2011

%C Also, minimum cardinality of an unavoidable set of length-n binary words (Champarnaud, Hansel, Perrin). - _Jeffrey Shallit_, Jan 10 2019

%C (1/n) * Dirichlet convolution of phi(n) and 2^n, n>0. - _Richard L. Ollerton_, May 06 2021

%C From _Jianing Song_, Nov 13 2021: (Start)

%C a(n) is even for n != 0, 2. Proof: write n = 2^e * s with odd s, then a(n) * s = Sum_{d|s} Sum_{k=0..e} phi((2^e*s)/(2^k*d)) * 2^(2^k*d-e) = Sum_{d|s} Sum_{k=0..e-1} phi(s/d) * 2^(2^k*d-k-1) + Sum_{d|s} phi(s/d) * 2^(2^e*d-e) == Sum_{k=0..e-1} 2^(2^k*s-k-1) + 2^(2^e*s-e) == Sum_{k=0..min{e-1,1}} 2^(2^k*s-k-1) (mod 2). a(n) is odd if and only if s = 1 and e-1 = 0, or n = 2.

%C a(n) == 2 (mod 4) if and only if n = 1, 4 or n = 2*p^e with prime p == 3 (mod 4).

%C a(n) == 4 (mod 8) if and only if n = 2^e, 3*2^e for e >= 3, or n = p^e, 4*p^e != 12 with prime p == 3 (mod 4), or n = 2s where s is an odd number such that phi(s) == 4 (mod 8). (End)

%D S. W. Golomb, Shift-Register Sequences, Holden-Day, San Francisco, 1967, pp. 120, 172.

%D May, Robert M. "Simple mathematical models with very complicated dynamics." Nature, Vol. 261, June 10, 1976, pp. 459-467; reprinted in The Theory of Chaotic Attractors, pp. 85-93. Springer, New York, NY, 2004. The sequences listed in Table 2 are A000079, A027375, A000031, A001037, A000048, A051841. - _N. J. A. Sloane_, Mar 17 2019

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 7.112(a).

%H Seiichi Manyama, <a href="/A000031/b000031.txt">Table of n, a(n) for n = 0..3333</a> (first 201 terms from T. D. Noe)

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, p. 151, pp. 379-383.

%H P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

%H J.-M. Champarnaud, G. Hansel, and D. Perrin, <a href="https://doi.org/10.1142/S0218196704001700">Unavoidable sets of constant length</a>, Internat. J. Alg. Comput. 14 (2004), 241-251.

%H James East and Ron Niles, <a href="https://arxiv.org/abs/1710.11245">Integer polygons of given perimeter</a>, arXiv:1710.11245 [math.CO], 2017.

%H S. N. Ethier and J. Lee, <a href="http://arxiv.org/abs/1202.2609">Parrondo games with spatial dependence</a>, arXiv preprint arXiv:1202.2609 [math.PR], 2012.

%H S. N. Ethier, <a href="http://arxiv.org/abs/1301.2352">Counting toroidal binary arrays</a>, arXiv preprint arXiv:1301.2352 [math.CO], 2013 and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Ethier/ethier2.html">J. Int. Seq. 16 (2013) #13.4.7</a>.

%H N. J. Fine, <a href="http://projecteuclid.org/euclid.ijm/1255381350">Classes of periodic sequences</a>, Illinois J. Math., 2 (1958), 285-302.

%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see pages 18, 64.

%H H. Fredricksen, <a href="http://dx.doi.org/10.1016/S0021-9800(70)80050-3">The lexicographically least de Bruijn cycle</a>, J. Combin. Theory, 9 (1970) 1-5.

%H Harold Fredricksen, <a href="http://dx.doi.org/10.1016/0012-365X(86)90089-0">An algorithm for generating necklaces of beads in two colors</a>, Discrete Mathematics, Volume 61, Issues 2-3, September 1986, Pages 181-188.

%H E. N. Gilbert and J. Riordan, <a href="http://projecteuclid.org/euclid.ijm/1255631587">Symmetry types of periodic sequences</a>, Illinois J. Math., 5 (1961), 657-665.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=2">Encyclopedia of Combinatorial Structures 2</a>

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=130">Encyclopedia of Combinatorial Structures 130</a>

%H Juhani Karhumäki, S. Puzynina, M. Rao, and M. A. Whiteland, <a href="https://arxiv.org/abs/1605.03319">On cardinalities of k-abelian equivalence classes</a>, arXiv preprint arXiv:1605.03319 [math.CO], 2016.

%H Abraham Lempel, <a href="http://dx.doi.org/10.1016/0095-8956(71)90009-8">On extremal factors of the de Bruijn graph</a>, J. Combinatorial Theory Ser. B 11 1971 17--27. MR0276126 (43 #1874).

%H Karyn McLellan, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i4p32">Periodic coefficients and random Fibonacci sequences</a>, Electronic Journal of Combinatorics, 20(4), 2013, #P32.

%H Johannes Mykkeltveit, <a href="http://dx.doi.org/10.1016/0095-8956(72)90006-8">A proof of Golomb's conjecture for the de Bruijn graph</a>, J. Combinatorial Theory Ser. B 13 (1972), 40-45. MR0323629 (48 #1985).

%H Matthew Parker, <a href="https://oeis.org/A000031/a000031_25K.7z">The first 25K terms (7-Zip compressed file)</a> [a large file]

%H J. Riordan, <a href="/A001867/a001867.pdf">Letter to N. J. A. Sloane, Jul. 1978</a>

%H F. Ruskey, <a href="http://combos.org/necklace">Necklaces, Lyndon words, De Bruijn sequences, etc.</a>

%H F. Ruskey, <a href="/A000011/a000011.pdf">Necklaces, Lyndon words, De Bruijn sequences, etc.</a> [Cached copy, with permission, pdf format only]

%H Ville Salo, <a href="https://arxiv.org/abs/1809.08050">Universal gates with wires in a row</a>, arXiv:1809.08050 [math.GR], 2018.

%H J. A. Siehler, <a href="http://www.maa.org/programs/maa-awards/writing-awards/george-polya-awards/the-finite-lamplighter-groups-a-guided-tour">The Finite Lamplighter Groups: A Guided Tour</a>, College Mathematics Journal, Vol. 43, No. 3 (May 2012), pp. 203-211.

%H N. J. A. Sloane, <a href="http://neilsloane.com/doc/dijen.txt">On single-deletion-correcting codes</a>

%H N. J. A. Sloane, <a href="http://arxiv.org/abs/math/0207197">On single-deletion-correcting codes</a>, arXiv:math/0207197 [math.CO], 2002; in Codes and Designs (Columbus, OH, 2000), 273-291, Ohio State Univ. Math. Res. Inst. Publ., 10, de Gruyter, Berlin, 2002.

%H David Thomson, <a href="https://ima.org.uk/16507/musical-polygons">Musical Polygons</a>, Mathematics Today, Vol. 57, No. 2 (April 2021), pp. 50-51.

%H R. C. Titsworth, <a href="http://projecteuclid.org/euclid.ijm/1256059671">Equivalence classes of periodic sequences</a>, Illinois J. Math., 8 (1964), 266-270.

%H A. M. Uludag, A. Zeytin and M. Durmus, <a href="http://math.gsu.edu.tr/uludag/CHARKSANDDESSINS.pdf">Binary Quadratic Forms as Dessins</a>, 2012.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Necklace.html">Necklace</a>

%H Wolfram Research, <a href="http://functions.wolfram.com/NumberTheoryFunctions/EulerPhi/31/08/ShowAll.html">Number of necklaces</a>

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%H <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>

%F a(n) = (1/n)*Sum_{ d divides n } phi(d)*2^(n/d) = A053635(n)/n, where phi is A000010.

%F Warning: easily confused with A001037, which has a similar formula.

%F G.f.: 1 - Sum_{n>=1} phi(n)*log(1 - 2*x^n)/n. - _Herbert Kociemba_, Oct 29 2016

%F a(0) = 1; a(n) = (1/n) * Sum_{k=1..n} 2^gcd(n,k). - _Ilya Gutkovskiy_, Apr 16 2021

%F a(0) = 1; a(n) = (1/n)*Sum_{k=1..n} 2^(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). - _Richard L. Ollerton_, May 06 2021

%F Dirichlet g.f.: f(s+1) * (zeta(s)/zeta(s+1)), where f(s) = Sum_{n>=1} 2^n/n^s. - _Jianing Song_, Nov 13 2021

%e For n=3 and n=4 the necklaces are {000,001,011,111} and {0000,0001,0011,0101,0111,1111}.

%e The analogous shift register sequences are {000..., 001001..., 011011..., 111...} and {000..., 00010001..., 00110011..., 0101..., 01110111..., 111...}.

%p with(numtheory); A000031 := proc(n) local d,s; if n = 0 then RETURN(1); else s := 0; for d in divisors(n) do s := s+phi(d)*2^(n/d); od; RETURN(s/n); fi; end; [ seq(A000031(n), n=0..50) ];

%t a[n_] := Sum[If[Mod[n, d] == 0, EulerPhi[d] 2^(n/d), 0], {d, 1, n}]/n

%t a[n_] := Fold[#1 + 2^(n/#2) EulerPhi[#2] &, 0, Divisors[n]]/n (* _Ben Branman_, Jan 08 2011 *)

%t Table[Expand[CycleIndex[CyclicGroup[n], t] /. Table[t[i]-> 2, {i, 1, n}]], {n,0, 30}] (* _Geoffrey Critzer_, Mar 06 2011*)

%t a[0] = 1; a[n_] := DivisorSum[n, EulerPhi[#]*2^(n/#)&]/n; Table[a[n], {n, 0, 40}] (* _Jean-François Alcover_, Feb 03 2016 *)

%t mx=40; CoefficientList[Series[1-Sum[EulerPhi[i] Log[1-2*x^i]/i,{i,1,mx}],{x,0,mx}],x] (*_Herbert Kociemba_, Oct 29 2016 *)

%o (PARI) {A000031(n)=if(n==0,1,sumdiv(n,d,eulerphi(d)*2^(n/d))/n)} \\ _Randall L Rathbun_, Jan 11 2002

%o (Haskell)

%o a000031 0 = 1

%o a000031 n = (`div` n) $ sum $

%o zipWith (*) (map a000010 divs) (map a000079 $ reverse divs)

%o where divs = a027750_row n

%o -- _Reinhard Zumkeller_, Mar 21 2013

%o (Python)

%o from sympy import totient, divisors

%o def A000031(n): return sum(totient(d)*(1<<n//d) for d in divisors(n,generator=True))//n if n else 1 # _Chai Wah Wu_, Nov 16 2022

%Y Column 2 of A075195.

%Y Cf. A001037 (primitive solutions to same problem), A014580, A000016, A000013, A000029 (if turning over is allowed), A000011, A001371, A058766.

%Y Rows sums of triangle in A047996.

%Y Dividing by 2 gives A053634.

%Y A008965(n) = a(n) - 1 allowing different offsets.

%Y Cf. A008965, A053635, A052823, A100447 (bisection).

%Y Cf. A000010.

%K nonn,easy,nice,core

%O 0,2

%A _N. J. A. Sloane_

%E There is an error in Fig. M3860 in the 1995 Encyclopedia of Integer Sequences: in the third line, the formula for A000031 = M0564 should be (1/n) sum phi(d) 2^(n/d).