A385665 -id:A385665 - cp's OEIS frontend

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

N. J. A. Sloane

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
Also number of 2n-bead balanced binary necklaces that are equivalent to their complements. - Andrew Howroyd, Sep 29 2017

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

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

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

Cf. A000031, A000016, A000116.
Cf. A128976.
Cf. A000010, A027750.
Cf. A385665, A000048.

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

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;

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

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

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

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
a(n) = Sum_{k=1..n} A385665(n,k) = Sum_{d|n} A000048(d). - Tilman Piesk, Jul 31 2025

A045654 Number of 2n-bead balanced binary strings, rotationally equivalent to complement.

Original entry on oeis.org

1, 2, 6, 8, 22, 32, 72, 128, 278, 512, 1056, 2048, 4168, 8192, 16512, 32768, 65814, 131072, 262656, 524288, 1049632, 2097152, 4196352, 8388608, 16781384, 33554432, 67117056, 134217728, 268451968, 536870912, 1073774592, 2147483648, 4295033110, 8589934592

Offset: 0

David W. Wilson

			From _Andrew Howroyd_, Jul 06 2025: (Start)
The a(1) = 2 length 2 balanced binary strings are: 01, 10.
The a(2) = 6 strings are: 0101, 1010, 0011, 0110, 1100, 1001.
The a(3) = 8 strings are: 010101, 101010, 000111, 001110, 011100, 111000, 110001, 100011. (End)

Andrew Howroyd, Table of n, a(n) for n = 0..1000
Tilman Piesk, Row sums of triangle derived from A385665
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions

Cf. A000984, A045653, A045655, A045656, A045663, A127804, A385665.

a:= proc(n) option remember;
      2^n+`if`(n::even and n>0, a(n/2), 0)
    end:
seq(a(n), n=0..33);  # Alois P. Heinz, Jul 01 2025

a(n)={if(n==0, 1, my(s=0); while(n%2==0, s+=2^n; n/=2); s + 2^n)} \\ Andrew Howroyd, Sep 22 2019

def A045654(n): return sum(1<<(n>>k) for k in range((~n & n-1).bit_length()+1)) if n else 1 # Chai Wah Wu, Jul 22 2024

a(0)=1, a(2n) = a(n)+2^(2n), a(2n+1) = 2^(2n+1). - Ralf Stephan, Jun 07 2003
G.f.: 1/(1-x) + sum(k>=0, t(1+2t-2t^2)/(1-t^2)/(1-2t), t=x^2^k). - Ralf Stephan, Aug 30 2003
For n >= 1, a(n) = Sum_{k=0..A007814(n)} 2^(n/2^k). - David W. Wilson, Jan 01 2012
Inverse Moebius transform of A045663. - Andrew Howroyd, Sep 15 2019
a(n) = 2*A127804(n-1) for n > 0. - Tilman Piesk, Jul 05 2025
a(n) = Sum_{k=1..n} 2 * n * A385665(n,k) / k. - Tilman Piesk, Jul 07 2025

A115118 Number of imprimitive (periodic) n-bead binary necklaces with beads of 2 colors where the colors may be swapped but turning over is not allowed.

Original entry on oeis.org

0, 0, 1, 1, 2, 1, 3, 1, 4, 2, 5, 1, 10, 1, 11, 5, 20, 1, 36, 1, 58, 11, 95, 1, 196, 4, 317, 30, 598, 1, 1153, 1, 2068, 95, 3857, 13, 7488, 1, 13799, 317, 26288, 1, 50531, 1, 95422, 1124, 182363, 1, 351764, 10, 671144, 3857, 1290874, 1, 2492820, 97, 4794104, 13799, 9256397, 1, 17923218, 1, 34636835, 49968, 67110932, 319

Offset: 0

Valery A. Liskovets, Jan 17 2006

a(p) = 1 for prime p. Presumably a(n) = A115121(n) = A066656(n)/2 for odd n.

Antti Karttunen, Table of n, a(n) for n = 0..1024

Cf. A000013, A000048, A385665.

Cf. A115121, A066656.

a[n_] := If[n == 0, 0, Sum[EulerPhi[2d] 2^(n/d) - Boole[OddQ[d]] MoebiusMu[d] 2^(n/d), {d, Divisors[n]}]/(2n)];
Array[a, 66, 0] (* Jean-François Alcover, Aug 29 2019 *)

a(n) = if (n==0, 0, (sumdiv(n, d, eulerphi(2*d) * 2^(n/d)) - sumdiv(n, d, (d%2)*(moebius(d)*2^(n/d))))/(2*n)); \\ Michel Marcus, Oct 21 2017

a(n) = A000013(n) - A000048(n).

a(n) = Sum_{k=2..n} A385665(n,k). - Tilman Piesk, Aug 03 2025

More terms from Antti Karttunen, Oct 21 2017

A127804 a(2n) = 2^(2n), a(2n+1) = 2^(2n+1) + a(n).

Original entry on oeis.org

1, 3, 4, 11, 16, 36, 64, 139, 256, 528, 1024, 2084, 4096, 8256, 16384, 32907, 65536, 131328, 262144, 524816, 1048576, 2098176, 4194304, 8390692, 16777216, 33558528, 67108864, 134225984, 268435456, 536887296, 1073741824, 2147516555, 4294967296, 8590000128

Offset: 0

Paul Barry, Jan 29 2007

From Tilman Piesk, Jun 30 2025: (Start)
The binary expansion of a(n), with bits least to most significant, is row n of A115361.
Number of 1's in binary expansion of a(n) is A001511(n+1).
Row sums of triangle A128807.
Row sums of triangle A127803.(End)

Tilman Piesk, Table of n, a(n) for n = 0..1023 (terms 0..61 from R. J. Mathar)
Tilman Piesk, Illustrated triangles with 32 rows:
related to necklaces (similar to A385665),
binary (A115361),
signed (A127803)
Tilman Piesk, Serration of Boolean functions (Wikiversity)

Cf. A045654, A128807, A127803, A115361, A187767, A001511.

A127804 := proc(n)
    add( A127803(n,k),k=0..n) ;
end proc: # R. J. Mathar, Feb 12 2024
# second Maple program:
a:= proc(n) option remember;
      2^n+`if`(n::odd, a((n-1)/2), 0)
    end:
seq(a(n), n=0..33);  # Alois P. Heinz, Jul 01 2025

rows = 30;
A[n_, k_] := If[k <= n, If[n <= 2 k, 1/(2*2^n - 1), 0], 0];
T = Table[A[n, k], {n, 0, rows-1}, {k, 0, rows-1}] // Inverse;
a[n_] := T[[n+1]] // Total;
Table[a[n], {n, 0, rows-1}] (* Jean-François Alcover, Jul 03 2018 *)

Conjecture: a(n) = 1 + A187767(n+1). - Andrew Howroyd, Jun 02 2017
From Tilman Piesk, Jun 30 2025: (Start)
a(n) = Sum_{i=0..A001511(n+1)-1} 2^((n+1) / 2^i - 1)
     = Sum_{i=0..A001511(n+1)-1} 2^floor(n / 2^i).
a(n) = A045654(n+1) / 2. (End)

Name changed by Tilman Piesk, Jun 30 2025

A386388 a(n) is the number of complement pairs of 2n-bead balanced bicolor necklaces.

Original entry on oeis.org

0, 0, 0, 1, 3, 11, 36, 118, 395, 1337, 4598, 15986, 56270, 199854, 716132, 2584754, 9391051, 34315811, 126040590, 465062362, 1723070794, 6407806952, 23910175804, 89493721076, 335912391966, 1264105728842, 4768446886764, 18027215662284, 68291878325138

Offset: 0

Tilman Piesk, Jul 20 2025

nonn

A003239(n) is the number of 2n-bead balanced bicolor necklaces, and A000013(n) is the number of those that are self-complementary (i.e., can be rotated so that all beads change color). Their difference 2*a(n) is the number of those that are not self-complementary. a(n) is the number pairs of distinct complements.

Doubled entries: 0, 0, 0, 2, 6, 22, 72, 236, 790, 2674, 9196, 31972, 112540, 399708, 1432264, ...

			  n  | A003239(n) A000013(n) | 2*a(n)      a(n)
  0  |         1          1  |     0         0
  1  |         1          1  |     0         0
  2  |         2          2  |     0         0
  3  |         4          2  |     2         1
  4  |        10          4  |     6         3
  5  |        26          4  |    22        11
  6  |        80          8  |    72        36
  7  |       246         10  |   236       118
  8  |       810         20  |   790       395
  9  |      2704         30  |  2674      1337
 10  |      9252         56  |  9196      4598
Examples for n=4 with necklaces of length 8:
A000013(4) = 4 necklaces are self-complementary:
 00001111, 00110011, 01010101, 00101101 (compare A385665)
There are a(n) = 3 pairs of complementary necklaces:
 (00110101, 00101011), (00100111, 00011011), (00010111, 00011101)

Michael De Vlieger, Table of n, a(n) for n = 0..1670

Cf. A000013, A003239, A385665.

a[0]=0;a[n_]:=( Sum[ EulerPhi[n/k]*Binomial[2k, k]/(2n), {k, Divisors[n]}]- Fold[ #1 + EulerPhi[2#2]2^(n/#2)/(2n) &, 0, Divisors[n]])/2;Array[a,29,0] (* James C. McMahon, Jul 30 2025 *)

a(n) = (A003239(n) - A000013(n)) / 2.

A385666 Triangle read by rows: T(n,k) is the number of 2n-bead balanced binary necklaces with period length 2n/k.

Original entry on oeis.org

1, 1, 1, 3, 0, 1, 8, 1, 0, 1, 25, 0, 0, 0, 1, 75, 3, 1, 0, 0, 1, 245, 0, 0, 0, 0, 0, 1, 800, 8, 0, 1, 0, 0, 0, 1, 2700, 0, 3, 0, 0, 0, 0, 0, 1, 9225, 25, 0, 0, 1, 0, 0, 0, 0, 1, 32065, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 112632, 75, 8, 3, 0, 1, 0, 0, 0, 0, 0, 1, 400023

Offset: 1

Tilman Piesk, Jul 16 2025

There are A003239(n) balanced binary necklaces of length 2n. (Central numbers of A047996.)
T(n,k) is the number of those that can be rotated into themselves in k different ways (at least 1 for the trivial rotation).
A022553(n) necklaces (corresponding to Lyndon words) have only the trivial rotation.
All columns have the same positive entries, each preceded by k-1 zeros.
Compare triangle A385665, which counts only self-complementary balanced binary necklaces.

			Triangle begins:
         k     1   2  3  4  5  6  7  8  9 10 11 12 13 14 15 16    A003239(n)
  n
  1            1   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .            1
  2            1   1  .  .  .  .  .  .  .  .  .  .  .  .  .  .            2
  3            3   .  1  .  .  .  .  .  .  .  .  .  .  .  .  .            4
  4            8   1  .  1  .  .  .  .  .  .  .  .  .  .  .  .           10
  5           25   .  .  .  1  .  .  .  .  .  .  .  .  .  .  .           26
  6           75   3  1  .  .  1  .  .  .  .  .  .  .  .  .  .           80
  7          245   .  .  .  .  .  1  .  .  .  .  .  .  .  .  .          246
  8          800   8  .  1  .  .  .  1  .  .  .  .  .  .  .  .          810
  9         2700   .  3  .  .  .  .  .  1  .  .  .  .  .  .  .         2704
 10         9225  25  .  .  1  .  .  .  .  1  .  .  .  .  .  .         9252
 11        32065   .  .  .  .  .  .  .  .  .  1  .  .  .  .  .        32066
 12       112632  75  8  3  .  1  .  .  .  .  .  1  .  .  .  .       112720
 13       400023   .  .  .  .  .  .  .  .  .  .  .  1  .  .  .       400024
 14      1432613 245  .  .  .  .  1  .  .  .  .  .  .  1  .  .      1432860
 15      5170575   . 25  .  3  .  .  .  .  .  .  .  .  .  1  .      5170604
 16     18783360 800  .  8  .  .  .  1  .  .  .  .  .  .  .  1     18784170
Examples for n=4 with necklaces of length 8:
T(4, 1) = 8 necklaces have k=1 rotation, i.e. rotating 0 places:
 00001111, 00010111, 00011011, 00011101, 00100111, 00101011, 00101101, 00110101
T(4, 2) = 1 necklace has k=2 rotations:
 00110011 can be rotated onto itself by rotating 0 or 4 places.
T(4, 4) = 1 necklace has k=4 rotations:
 01010101 can be rotated onto itself by rotating 0, 2, 4 or 6 places.

Tilman Piesk, Rows 1..32, flattened
Tilman Piesk, Triangle T(n,k)*2*n/k with row sums 2n choose n
Tilman Piesk, List of imprimitive necklaces for n=1...15
Tilman Piesk, List of primitive necklaces for n=1...8

Cf. A022553, A003239, A385665.

T(n,k) = A022553(n/k) iff n divisible by k, otherwise 0.

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A045654 Number of 2n-bead balanced binary strings, rotationally equivalent to complement.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

PARI

Python

Formula

A115118 Number of imprimitive (periodic) n-bead binary necklaces with beads of 2 colors where the colors may be swapped but turning over is not allowed.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A127804 a(2n) = 2^(2n), a(2n+1) = 2^(2n+1) + a(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A386388 a(n) is the number of complement pairs of 2n-bead balanced bicolor necklaces.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A385666 Triangle read by rows: T(n,k) is the number of 2n-bead balanced binary necklaces with period length 2n/k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula