login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000013 Definition (1): Number of n-bead binary necklaces with beads of 2 colors where the colors may be swapped but turning over is not allowed.
(Formerly M0313 N0115)
28
1, 1, 2, 2, 4, 4, 8, 10, 20, 30, 56, 94, 180, 316, 596, 1096, 2068, 3856, 7316, 13798, 26272, 49940, 95420, 182362, 349716, 671092, 1290872, 2485534, 4794088, 9256396, 17896832, 34636834, 67110932, 130150588, 252648992, 490853416 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Definition (2): Equivalently, number of different output sequences from an n-stage pure cycling shift register when 2 sequences are considered the same if one is the complement of the other.

Definition (3): Also number of different output sequences from an n-stage pure cycling shift register constrained so contents have even weight.

Definition (4): Also number of output sequences from (n-1)-stage shift register which feeds back the mod 2 sum of the contents of the register.

The equivalence of definitions (1) and (2) follows at once from the definitions.

If u is an output sequence of type (2) then its derivative is of type (3) - so (2) and (3) count the same things.

If we have a shift register of type (4), append a new cell which contains the mod 2 sum of the contents to get a shift register of type (3). So (3) and (4) count the same things.

If n is even, a(n) = A000116(n/2). If 2^(n+1)-1 is prime, then a(n) = A128976(n+1), the number of cycles in the digraph of the Lucas-Lehmer operator LL(x)=x^2-2 acting on Z/(2^(n+1)-1). - M. F. Hasler, May 19 2007

REFERENCES

S. W. Golomb, Shift-Register Sequences, Holden-Day, San Francisco, 1967, p. 172.

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

LINKS

T. D. Noe and Seiichi Manyama, Table of n, a(n) for n = 0..3334 (first 201 terms from T. D. Noe)

Joerg Arndt, Matters Computational (The Fxtbook), p.151, p.408

H. Bottomley, Initial terms of A000011 and A000013

N. J. Fine, Classes of periodic sequences, Illinois J. Math., 2 (1958), 285-302.

E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.

Karyn McLellan, Periodic coefficients and random Fibonacci sequences, Electronic Journal of Combinatorics, 20(4), 2013, #P32.

F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.

N. J. A. Sloane, On single-deletion-correcting codes

N. J. A. Sloane, On single-deletion-correcting codes, in Codes and Designs (Columbus, OH, 2000), 273-291, Ohio State Univ. Math. Res. Inst. Publ., 10, de Gruyter, Berlin, 2002.

N. J. A. Sloane, Maple code for this and related sequences

Index entries for sequences related to necklaces

FORMULA

a(n) = Sum_{ d divides n } (phi(2d)*2^(n/d))/(2n) for n>0. - Michael Somos, Oct 20 1999

G.f.: 1-Sum_{i>=1} phi(2*i)*log(1-2*x^i)/(2*i). - Herbert Kociemba, Nov 01 2016

EXAMPLE

G.f. = 1 + x + 2*x^2 + 2*x^3 + 4*x^4 + 4*x^5 + 8*x^6 + 10*x^7 + 20*x^8 + ...

MAPLE

with(numtheory): A000013 := proc(n) local s, d; if n = 0 then RETURN(1) else s := 0; for d in divisors(n) do s := s+(phi(2*d)*2^(n/d))/(2*n); od; RETURN(s); fi; end;

MATHEMATICA

a[n_] := Fold[ #1 + EulerPhi[2#2]2^(n/#2)/(2n) &, 0, Divisors[n]]

a[ n_] := If[ n < 1, Boole[n == 0], DivisorSum[ n, EulerPhi[2 #] 2^(n/#) &] / (2 n)]; (* Michael Somos, Dec 19 2014 *)

mx=40; CoefficientList[Series[1-Sum[EulerPhi[2i] Log[1-2*x^i]/(2i), {i, 1, mx}], {x, 0, mx}], x] (* Herbert Kociemba, Nov 01 2016 *)

PROG

(PARI) {a(n) = if( n<1, n==0, sumdiv(n, k, eulerphi(2*k) * 2^(n/k)) / (2*n))}; /* Michael Somos, Oct 20 1999 */

(Haskell)

a000013 0 = 1

a000013 n = sum (zipWith (*)

   (map (a000010 . (* 2)) ds) (map (2 ^) $ reverse ds)) `div` (2 * n)

   where ds = a027750_row n

-- Reinhard Zumkeller, Jul 08 2013

CROSSREFS

Cf. A000031, A000016, A000116.

Cf. A128976.

Cf. A000010, A027750.

Sequence in context: A000011 A187213 A022476 * A064484 A063776 A276063

Adjacent sequences:  A000010 A000011 A000012 * A000014 A000015 A000016

KEYWORD

nonn,nice,easy

AUTHOR

N. J. A. Sloane

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified March 25 13:36 EDT 2017. Contains 284081 sequences.