cp's OEIS Frontend

A000031 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.

%I A000031 M0564 N0203 #226 Jul 08 2025 12:17:12
%S A000031 1,2,3,4,6,8,14,20,36,60,108,188,352,632,1182,2192,4116,7712,14602,
%T A000031 27596,52488,99880,190746,364724,699252,1342184,2581428,4971068,
%U A000031 9587580,18512792,35792568,69273668,134219796,260301176,505294128,981706832
%N A000031 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 A000031 Also a(n)-1 is the number of 1's in the truth table for the lexicographically least de Bruijn cycle (Fredricksen).
%C A000031 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 A000031 Also, minimum cardinality of an unavoidable set of length-n binary words (Champarnaud, Hansel, Perrin). - _Jeffrey Shallit_, Jan 10 2019
%C A000031 (1/n) * Dirichlet convolution of phi(n) and 2^n, n>0. - _Richard L. Ollerton_, May 06 2021
%C A000031 From _Jianing Song_, Nov 13 2021: (Start)
%C A000031 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 A000031 a(n) == 2 (mod 4) if and only if n = 1, 4 or n = 2*p^e with prime p == 3 (mod 4).
%C A000031 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 A000031 S. W. Golomb, Shift-Register Sequences, Holden-Day, San Francisco, 1967, pp. 120, 172.
%D A000031 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 A000031 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000031 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A000031 R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 7.112(a).
%H A000031 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 A000031 Nicolás Álvarez, Verónica Becher, Martín Mereb, Ivo Pajor, and Carlos Miguel Soto, <a href="https://arxiv.org/abs/2308.16257">On extremal factors of de Bruijn-like graphs</a>, arXiv:2308.16257 [math.CO], 2023. See references.
%H A000031 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, p. 151, pp. 379-383.
%H A000031 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 A000031 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 A000031 Vladimir Dotsenko and Irvin Roy Hentzel, <a href="https://arxiv.org/abs/2507.00437">On the conjecture of Kashuba and Mathieu about free Jordan algebras</a>, arXiv:2507.00437 [math.RA], 2025. See p. 14.
%H A000031 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 A000031 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 A000031 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 A000031 N. J. Fine, <a href="http://projecteuclid.org/euclid.ijm/1255381350">Classes of periodic sequences</a>, Illinois J. Math., 2 (1958), 285-302.
%H A000031 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see pages 18, 64.
%H A000031 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 A000031 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 A000031 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 A000031 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=2">Encyclopedia of Combinatorial Structures 2</a>
%H A000031 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=130">Encyclopedia of Combinatorial Structures 130</a>
%H A000031 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 A000031 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 A000031 Karyn McLellan, <a href="https://doi.org/10.37236/3204">Periodic coefficients and random Fibonacci sequences</a>, Electronic Journal of Combinatorics, 20(4), 2013, #P32.
%H A000031 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 A000031 Matthew Parker, <a href="https://oeis.org/A000031/a000031_25K.7z">The first 25K terms (7-Zip compressed file)</a> [a large file]
%H A000031 J. Riordan, <a href="/A001867/a001867.pdf">Letter to N. J. A. Sloane, Jul. 1978</a>
%H A000031 Frank Ruskey, <a href="http://combos.org/necklace">Necklaces, Lyndon words, De Bruijn sequences, etc.</a>
%H A000031 Frank Ruskey, <a href="/A000011/a000011.pdf">Necklaces, Lyndon words, De Bruijn sequences, etc.</a> [Cached copy, with permission, pdf format only]
%H A000031 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 A000031 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 A000031 N. J. A. Sloane, <a href="http://neilsloane.com/doc/dijen.txt">On single-deletion-correcting codes</a>
%H A000031 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 A000031 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 A000031 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 A000031 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 A000031 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Necklace.html">Necklace</a>
%H A000031 Wolfram Research, <a href="http://functions.wolfram.com/NumberTheoryFunctions/EulerPhi/31/08/ShowAll.html">Number of necklaces</a>
%H A000031 <a href="/index/Cor#core">Index entries for "core" sequences</a>
%H A000031 <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>
%F A000031 a(n) = (1/n)*Sum_{ d divides n } phi(d)*2^(n/d) = A053635(n)/n, where phi is A000010.
%F A000031 Warning: easily confused with A001037, which has a similar formula.
%F A000031 G.f.: 1 - Sum_{n>=1} phi(n)*log(1 - 2*x^n)/n. - _Herbert Kociemba_, Oct 29 2016
%F A000031 a(0) = 1; a(n) = (1/n) * Sum_{k=1..n} 2^gcd(n,k). - _Ilya Gutkovskiy_, Apr 16 2021
%F A000031 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 A000031 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 A000031 For n=3 and n=4 the necklaces are {000,001,011,111} and {0000,0001,0011,0101,0111,1111}.
%e A000031 The analogous shift register sequences are {000..., 001001..., 011011..., 111...} and {000..., 00010001..., 00110011..., 0101..., 01110111..., 111...}.
%p A000031 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 A000031 a[n_] := Sum[If[Mod[n, d] == 0, EulerPhi[d] 2^(n/d), 0], {d, 1, n}]/n
%t A000031 a[n_] := Fold[#1 + 2^(n/#2) EulerPhi[#2] &, 0, Divisors[n]]/n (* _Ben Branman_, Jan 08 2011 *)
%t A000031 Table[Expand[CycleIndex[CyclicGroup[n], t] /. Table[t[i]-> 2, {i, 1, n}]], {n,0, 30}] (* _Geoffrey Critzer_, Mar 06 2011*)
%t A000031 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 A000031 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 A000031 (PARI) {A000031(n)=if(n==0,1,sumdiv(n,d,eulerphi(d)*2^(n/d))/n)} \\ _Randall L Rathbun_, Jan 11 2002
%o A000031 (Haskell)
%o A000031 a000031 0 = 1
%o A000031 a000031 n = (`div` n) $ sum $
%o A000031    zipWith (*) (map a000010 divs) (map a000079 $ reverse divs)
%o A000031    where divs = a027750_row n
%o A000031 -- _Reinhard Zumkeller_, Mar 21 2013
%o A000031 (Python)
%o A000031 from sympy import totient, divisors
%o A000031 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 A000031 Column 2 of A075195.
%Y A000031 Cf. A001037 (primitive solutions to same problem), A014580, A000016, A000013, A000029 (if turning over is allowed), A000011, A001371, A058766.
%Y A000031 Rows sums of triangle in A047996.
%Y A000031 Dividing by 2 gives A053634.
%Y A000031 A008965(n) = a(n) - 1 allowing different offsets.
%Y A000031 Cf. A008965, A053635, A052823, A100447 (bisection).
%Y A000031 Cf. A000010.
%K A000031 nonn,easy,nice,core
%O A000031 0,2
%A A000031 _N. J. A. Sloane_
%E A000031 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).