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.
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, 954444608, 1857283156, 3616828364
Offset: 0
Examples
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 + ...
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
- Seiichi Manyama, Table of n, a(n) for n = 0..3334 (first 201 terms from T. D. Noe)
- Nicolás Álvarez, Victória Becher, Martín Mereb, Ivo Pajor, and Carlos Miguel Soto, On extremal factors of de Bruijn-like graphs, Univ. Buenos Aires (Argentina 2023). See also arXiv:2308.16257 [math.CO], 2023. See references.
- Joerg Arndt, Matters Computational (The Fxtbook), p. 151, p. 408.
- Raghav Bhutani and Frederick Saia, Replacement dynamics of binary quadratic forms, arXiv:2508.05816 [math.NT], 2025. See p. 6.
- Henry Bottomley, Initial terms of A000011 and A000013
- Zachary E. Chin and Isaac L. Chuang, The quantum trajectory sensing problem and its solution, arXiv:2410.00893 [quant-ph], 2024. See p. 19.
- 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.
- Darij Grinberg and Peter Mao, Necklaces over a group with identity product, arXiv:2405.08937 [math.CO], 2024. See pp. 15, 22.
- Karyn McLellan, Periodic coefficients and random Fibonacci sequences, Electronic Journal of Combinatorics, 20(4), 2013, #P32.
- Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
- Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
- N. J. A. Sloane, On single-deletion-correcting codes
- 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.
- N. J. A. Sloane, Maple code for this and related sequences
- Index entries for sequences related to necklaces
Programs
-
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
-
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 *)
-
PARI
{a(n) = if( n<1, n==0, sumdiv(n, k, eulerphi(2*k) * 2^(n/k)) / (2*n))}; /* Michael Somos, Oct 20 1999 */ -
Python
from sympy import divisors, totient def a(n): return 1 if n<1 else sum([totient(2*d)*2**(n//d) for d in divisors(n)])//(2*n) # Indranil Ghosh, Apr 28 2017
Formula
a(n) = Sum_{ d divides n } (phi(2*d)*2^(n/d))/(2*n) 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
From Richard L. Ollerton, May 11 2021: (Start)
For n >= 1:
a(n) = (1/(2*n))*Sum_{k=1..n} phi(2*gcd(n,k))*2^(n/gcd(n,k))/phi(n/gcd(n,k)), where phi = A000010.
a(n) = (1/(2*n))*Sum_{k=1..n} phi(2*n/gcd(n,k))*2^gcd(n,k)/phi(n/gcd(n,k)). (End)
a(n) ~ 2^(n-1)/n. - Cedric Lorand, Apr 24 2022
Comments