login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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.
(Formerly M0564 N0203)
161
1, 2, 3, 4, 6, 8, 14, 20, 36, 60, 108, 188, 352, 632, 1182, 2192, 4116, 7712, 14602, 27596, 52488, 99880, 190746, 364724, 699252, 1342184, 2581428, 4971068, 9587580, 18512792, 35792568, 69273668, 134219796, 260301176, 505294128, 981706832 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,2
COMMENTS
Also a(n)-1 is the number of 1's in the truth table for the lexicographically least de Bruijn cycle (Fredricksen).
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
Also, minimum cardinality of an unavoidable set of length-n binary words (Champarnaud, Hansel, Perrin). - Jeffrey Shallit, Jan 10 2019
(1/n) * Dirichlet convolution of phi(n) and 2^n, n>0. - Richard L. Ollerton, May 06 2021
From Jianing Song, Nov 13 2021: (Start)
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.
a(n) == 2 (mod 4) if and only if n = 1, 4 or n = 2*p^e with prime p == 3 (mod 4).
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)
REFERENCES
S. W. Golomb, Shift-Register Sequences, Holden-Day, San Francisco, 1967, pp. 120, 172.
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
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 7.112(a).
LINKS
Seiichi Manyama, Table of n, a(n) for n = 0..3333 (first 201 terms from T. D. Noe)
Joerg Arndt, Matters Computational (The Fxtbook), p. 151, pp. 379-383.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
J.-M. Champarnaud, G. Hansel, and D. Perrin, Unavoidable sets of constant length, Internat. J. Alg. Comput. 14 (2004), 241-251.
James East and Ron Niles, Integer polygons of given perimeter, arXiv:1710.11245 [math.CO], 2017.
S. N. Ethier and J. Lee, Parrondo games with spatial dependence, arXiv preprint arXiv:1202.2609 [math.PR], 2012.
S. N. Ethier, Counting toroidal binary arrays, arXiv preprint arXiv:1301.2352 [math.CO], 2013 and J. Int. Seq. 16 (2013) #13.4.7.
N. J. Fine, Classes of periodic sequences, Illinois J. Math., 2 (1958), 285-302.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see pages 18, 64.
H. Fredricksen, The lexicographically least de Bruijn cycle, J. Combin. Theory, 9 (1970) 1-5.
Harold Fredricksen, An algorithm for generating necklaces of beads in two colors, Discrete Mathematics, Volume 61, Issues 2-3, September 1986, Pages 181-188.
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
Juhani Karhumäki, S. Puzynina, M. Rao, and M. A. Whiteland, On cardinalities of k-abelian equivalence classes, arXiv preprint arXiv:1605.03319 [math.CO], 2016.
Abraham Lempel, On extremal factors of the de Bruijn graph, J. Combinatorial Theory Ser. B 11 1971 17--27. MR0276126 (43 #1874).
Karyn McLellan, Periodic coefficients and random Fibonacci sequences, Electronic Journal of Combinatorics, 20(4), 2013, #P32.
Johannes Mykkeltveit, A proof of Golomb's conjecture for the de Bruijn graph, J. Combinatorial Theory Ser. B 13 (1972), 40-45. MR0323629 (48 #1985).
Matthew Parker, The first 25K terms (7-Zip compressed file) [a large file]
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
Ville Salo, Universal gates with wires in a row, arXiv:1809.08050 [math.GR], 2018.
J. A. Siehler, The Finite Lamplighter Groups: A Guided Tour, College Mathematics Journal, Vol. 43, No. 3 (May 2012), pp. 203-211.
N. J. A. Sloane, On single-deletion-correcting codes, 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.
David Thomson, Musical Polygons, Mathematics Today, Vol. 57, No. 2 (April 2021), pp. 50-51.
R. C. Titsworth, Equivalence classes of periodic sequences, Illinois J. Math., 8 (1964), 266-270.
A. M. Uludag, A. Zeytin and M. Durmus, Binary Quadratic Forms as Dessins, 2012.
Eric Weisstein's World of Mathematics, Necklace
Wolfram Research, Number of necklaces
FORMULA
a(n) = (1/n)*Sum_{ d divides n } phi(d)*2^(n/d) = A053635(n)/n, where phi is A000010.
Warning: easily confused with A001037, which has a similar formula.
G.f.: 1 - Sum_{n>=1} phi(n)*log(1 - 2*x^n)/n. - Herbert Kociemba, Oct 29 2016
a(0) = 1; a(n) = (1/n) * Sum_{k=1..n} 2^gcd(n,k). - Ilya Gutkovskiy, Apr 16 2021
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
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
EXAMPLE
For n=3 and n=4 the necklaces are {000,001,011,111} and {0000,0001,0011,0101,0111,1111}.
The analogous shift register sequences are {000..., 001001..., 011011..., 111...} and {000..., 00010001..., 00110011..., 0101..., 01110111..., 111...}.
MAPLE
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) ];
MATHEMATICA
a[n_] := Sum[If[Mod[n, d] == 0, EulerPhi[d] 2^(n/d), 0], {d, 1, n}]/n
a[n_] := Fold[#1 + 2^(n/#2) EulerPhi[#2] &, 0, Divisors[n]]/n (* Ben Branman, Jan 08 2011 *)
Table[Expand[CycleIndex[CyclicGroup[n], t] /. Table[t[i]-> 2, {i, 1, n}]], {n, 0, 30}] (* Geoffrey Critzer, Mar 06 2011*)
a[0] = 1; a[n_] := DivisorSum[n, EulerPhi[#]*2^(n/#)&]/n; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 03 2016 *)
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 *)
PROG
(PARI) {A000031(n)=if(n==0, 1, sumdiv(n, d, eulerphi(d)*2^(n/d))/n)} \\ Randall L Rathbun, Jan 11 2002
(Haskell)
a000031 0 = 1
a000031 n = (`div` n) $ sum $
zipWith (*) (map a000010 divs) (map a000079 $ reverse divs)
where divs = a027750_row n
-- Reinhard Zumkeller, Mar 21 2013
(Python)
from sympy import totient, divisors
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
CROSSREFS
Column 2 of A075195.
Cf. A001037 (primitive solutions to same problem), A014580, A000016, A000013, A000029 (if turning over is allowed), A000011, A001371, A058766.
Rows sums of triangle in A047996.
Dividing by 2 gives A053634.
A008965(n) = a(n) - 1 allowing different offsets.
Cf. A008965, A053635, A052823, A100447 (bisection).
Cf. A000010.
Sequence in context: A283022 A219186 A049708 * A298072 A111023 A261751
KEYWORD
nonn,easy,nice,core
AUTHOR
EXTENSIONS
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).
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 04:26 EDT 2024. Contains 370952 sequences. (Running on oeis4.)