A138904 -id:A138904 - cp's OEIS frontend

A302291 a(n) is the period of the binary expansion of n.

1, 1, 2, 1, 3, 3, 3, 1, 4, 4, 2, 4, 4, 4, 4, 1, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 1, 6, 6, 6, 6, 3, 6, 6, 6, 6, 6, 2, 6, 6, 3, 6, 6, 6, 6, 6, 6, 6, 6, 3, 6, 6, 6, 6, 6, 6, 6, 6, 1, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7

Offset: 0

Rémy Sigrist, Apr 04 2018

Zero is assumed to be represented as 0; otherwise, leading zeros are ignored.

See A302295 for the variant where leading zeros are allowed.

			The first terms, alongside the binary expansion of n with periodic part in parentheses, are:
  n  a(n)    bin(n)
  -- ----    ------
   0    1    (0)
   1    1    (1)
   2    2    (10)
   3    1    (1)(1)
   4    3    (100)
   5    3    (101)
   6    3    (110)
   7    1    (1)(1)(1)
   8    4    (1000)
   9    4    (1001)
  10    2    (10)(10)
  11    4    (1011)
  12    4    (1100)
  13    4    (1101)
  14    4    (1110)
  15    1    (1)(1)(1)(1)
  16    5    (10000)
  17    5    (10001)
  18    5    (10010)
  19    5    (10011)
  20    5    (10100)

Rémy Sigrist, Table of n, a(n) for n = 0..10000
Index entries for sequences related to binary expansion of n

Aperiodic compositions are counted by A000740.
Aperiodic binary words are counted by A027375.
The orderless period of prime indices is A052409.
Numbers whose binary expansion is periodic are A121016.
Periodic compositions are counted by A178472.
Numbers whose prime signature is aperiodic are A329139.
Compositions by number of distinct rotations are A333941.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Necklaces are A065609.
- Sum is A070939.
- Runs are counted by A124767.
- Rotational symmetries are counted by A138904.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Lyndon compositions are A275692.
- Co-Lyndon compositions are A326774.
- Aperiodic compositions are A328594.
- Rotational period is A333632.
- Co-necklaces are A333764.
- Reversed necklaces are A333943.
Cf. A000031, A001037, A008965, A019536, A020330, A211100, A302295, A328595, A328596, A329312, A329313, A329326.

Table[If[n==0,1,Length[Union[Array[RotateRight[IntegerDigits[n,2],#]&,IntegerLength[n,2]]]]],{n,0,50}] (* Gus Wiseman, Apr 19 2020 *)

a(n) = my (l=max(1, #binary(n))); fordiv (l, w, if (#Set(digits(n, 2^w))<=1, return (w)))

a(n) = A070939(n) / A138904(n).
a(2^n) = n + 1 for any n >= 0.
a(2^n - 1) = 1 for any n >= 0.
a(A020330(n)) = a(n) for any n > 0.

A333939 Number of multisets of compositions that can be shuffled together to obtain the k-th composition in standard order.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 4, 2, 5, 4, 5, 1, 2, 2, 4, 2, 4, 5, 7, 2, 5, 4, 10, 4, 10, 7, 7, 1, 2, 2, 4, 2, 5, 5, 7, 2, 5, 3, 9, 5, 13, 11, 12, 2, 5, 5, 10, 5, 11, 13, 18, 4, 10, 9, 20, 7, 18, 12, 11, 1, 2, 2, 4, 2, 5, 5, 7, 2, 4, 4, 11, 5, 14, 11, 12, 2

Offset: 0

Gus Wiseman, Apr 15 2020

nonn

Number of ways to deal out the k-th composition in standard order to form a multiset of hands.

A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The dealings for n = 1, 3, 7, 11, 13, 23, 43:
  (1)  (11)    (111)      (211)      (121)      (2111)        (2211)
       (1)(1)  (1)(11)    (1)(21)    (1)(12)    (11)(21)      (11)(22)
               (1)(1)(1)  (2)(11)    (1)(21)    (1)(211)      (1)(221)
                          (1)(1)(2)  (2)(11)    (2)(111)      (21)(21)
                                     (1)(1)(2)  (1)(1)(21)    (2)(211)
                                                (1)(2)(11)    (1)(1)(22)
                                                (1)(1)(1)(2)  (1)(2)(21)
                                                              (2)(2)(11)
                                                              (1)(1)(2)(2)

Multisets of compositions are counted by A034691.
Combinatory separations of normal multisets are counted by A269134.
Dealings with total sum n are counted by A292884.
Length of co-Lyndon factorization of binary expansion is A329312.
Length of Lyndon factorization of reversed binary expansion is A329313.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Necklaces are A065609.
- Sum is A070939.
- Runs are counted by A124767.
- Rotational symmetries are counted by A138904.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Lyndon words are A275692.
- Co-Lyndon words are A326774.
- Aperiodic compositions are A328594.
- Length of Lyndon factorization is A329312.
- Distinct rotations are counted by A333632.
- Co-Lyndon factorizations are counted by A333765.
- Lyndon factorizations are counted by A333940.
- Length of co-Lyndon factorization is A334029.
- Combinatory separations are A334030.
Cf. A000031, A000740, A001037, A008965, A027375, A059966, A060223, A211100, A328595, A328596, A333764, A333943.

nn=100;
comps[0]:={{}};comps[n_]:=Join@@Table[Prepend[#,i]&/@comps[n-i],{i,n}];
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
dealings[q_]:=Union[Function[ptn,Sort[q[[#]]&/@ptn]]/@sps[Range[Length[q]]]];
Table[Length[dealings[stc[n]]],{n,0,nn}]

For n > 0, Sum_{k = 2^(n-1)..2^n-1} a(k) = A292884(n).

A333941 Triangle read by rows where T(n,k) is the number of compositions of n with rotational period k.

Original entry on oeis.org

1, 0, 1, 0, 2, 0, 0, 2, 2, 0, 0, 3, 2, 3, 0, 0, 2, 4, 6, 4, 0, 0, 4, 6, 9, 8, 5, 0, 0, 2, 6, 15, 20, 15, 6, 0, 0, 4, 8, 24, 32, 35, 18, 7, 0, 0, 3, 10, 27, 56, 70, 54, 28, 8, 0, 0, 4, 12, 42, 84, 125, 120, 84, 32, 9, 0, 0, 2, 10, 45, 120, 210, 252, 210, 120, 45, 10, 0

Offset: 0

Gus Wiseman, Apr 16 2020

A composition of n is a finite sequence of positive integers summing to n.

			Triangle begins:
   1
   0   1
   0   2   0
   0   2   2   0
   0   3   2   3   0
   0   2   4   6   4   0
   0   4   6   9   8   5   0
   0   2   6  15  20  15   6   0
   0   4   8  24  32  35  18   7   0
   0   3  10  27  56  70  54  28   8   0
   0   4  12  42  84 125 120  84  32   9   0
   0   2  10  45 120 210 252 210 120  45  10   0
   0   6  18  66 168 335 450 462 320 162  50  11   0
Row n = 6 counts the following compositions (empty columns indicated by dots):
  .  (6)       (15)    (114)  (1113)  (11112)  .
     (33)      (24)    (123)  (1122)  (11121)
     (222)     (42)    (132)  (1131)  (11211)
     (111111)  (51)    (141)  (1221)  (12111)
               (1212)  (213)  (1311)  (21111)
               (2121)  (231)  (2112)
                       (312)  (2211)
                       (321)  (3111)
                       (411)

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)

Column k = 1 is A000005.
Row sums are A011782.
Diagonal T(2n,n) is A045630(n).
The strict version is A072574.
A version counting runs is A238279.
Column k = n - 1 is A254667.
Aperiodic compositions are counted by A000740.
Aperiodic binary words are counted by A027375.
The orderless period of prime indices is A052409.
Numbers whose binary expansion is periodic are A121016.
Periodic compositions are counted by A178472.
Period of binary expansion is A302291.
Numbers whose prime signature is aperiodic are A329139.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Necklaces are A065609.
- Sum is A070939.
- Rotational symmetries are counted by A138904.
- Constant compositions are A272919.
- Lyndon compositions are A275692.
- Co-Lyndon compositions are A326774.
- Aperiodic compositions are A328594.
- Rotational period is A333632.
- Co-necklaces are A333764.
- Reversed necklaces are A333943.
Cf. A000031, A001037, A008965, A019536, A211100, A291166, A328595, A328596, A329312, A329313, A329326.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Function[c,Length[Union[Array[RotateRight[c,#]&,Length[c]]]]==k]]],{n,0,10},{k,0,n}]

T(n,k)=if(n==0, k==0, sumdiv(n, m, sumdiv(gcd(k,m), d, moebius(d)*binomial(m/d-1, k/d-1)))) \\ Andrew Howroyd, Jan 19 2023

T(n,k) = Sum_{m|n} Sum_{d|gcd(k,m)} mu(d)*binomial(m/d-1, k/d-1) for n > 0. - Andrew Howroyd, Jan 19 2023

A136441 Number of rotational symmetries in the binary expansion of a number with 0 appended to the front.

Original entry on oeis.org

2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 0

Max Sills, Apr 03 2008

			a(0) = 2 because 00 has two rotational symmetries; a(21) = 3 because 010101 has 3 rotational symmetries.

Gary Doran, Table of n, a(n) for n = 0..100

Cf. A138904.

A138954 Number of complement symmetries in the rotations of the binary expansion of a number.

Original entry on oeis.org

0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 0

Max Sills, Apr 03 2008

It seems that the number of complement rotational symmetries is nonzero iff #0 = #1 in the binary expansion of a number.

The above statement is true in only one direction. It is clearly necessary for the number of 1 bits to equal the number of 0 bits. However, this is not sufficient. The first counterexample is n = 37 with binary expansion 100101 and complement 011010. Values of n for which a(n) is nonzero are therefore a proper subset of A031443. - Andrew Howroyd, Jan 12 2020

			a(2) = 1 because 2 has binary expansion 10 and the complement shows up once in rotations;
a(10) = 2 because 10 has binary expansion 1010 and its complement shows up twice in rotations.

Andrew Howroyd, Table of n, a(n) for n = 0..1023

Cf. A031443, A138904.

a(n)={my(s=0); if(n, my(b=logint(n,2)+1); if(2*hammingweight(n)==b, my(w=2^b-1-n); for(i=2, b, w=if(w%2, w+2^b, w)\2; if(w==n, s++)))); s} \\ Andrew Howroyd, Jan 12 2020

Missing a(8) inserted and terms a(21) and beyond from Andrew Howroyd, Jan 12 2020

A137323 a(n) = sum(d divides n, 2^(n/d-1) - 1 ), omitting d=1 and d=n.

Original entry on oeis.org

0, 0, 0, 1, 0, 4, 0, 8, 3, 16, 0, 42, 0, 64, 18, 135, 0, 290, 0, 534, 66, 1024, 0, 2216, 15, 4096, 258, 8262, 0, 16944, 0, 32902, 1026, 65536, 78, 133415, 0, 262144, 4098, 524948, 0, 1056864, 0, 2098182, 16656, 4194304, 0, 8423590, 63, 16777742

Offset: 1

Max Sills, Apr 06 2008

Previous name was: Characteristic value of numbers used to compute number of binary expansions of a certain length that have a given number of rotational symmetries.
Sequence is useful in counting binary expansions of length l with r rotational symmetries (we only consider r>1), where r has to be a proper divisor not equal to 1.
We discount numbers with l symmetry, because we know this only occurs once, at (2^l) - 1.
For example, consider binary expansions of length 8. We know that for any number the possible symmetries are the proper divisors of 8 not equal to 1; (2, 4).
So if we would like to find the number of expansions of length 8 that have 2 rotational symmetries, it is [2^(8/2 -1) -1] - a(8/2) = 7 - 1 = 6.
In general it appears that the formula for r rotational-symmetric numbers of expansion length l is the following: [2^(l/r -1) -1] - a(l/r).

			a(6) = 4 because 6 has (2,3) as proper divisors not equal to one. Plugging these values into the formula we get [2^(6/2 -1)-1] + [2^(6/3 -1) -1] = 3 + 1 = 4.
For p prime, a(p) = 0.

John B. Fraleigh, A first course in abstract algebra, Pearson Education, 2003.

Seiichi Manyama, Table of n, a(n) for n = 1..6645

Cf. A138904.

a[1] = 0; a[n_] := Sum[2^(n/d - 1) - 1, {d, Divisors[n][[2 ;; -2]]}];
Array[a, 50] (* Jean-François Alcover, Nov 12 2017 *)

a(n) = sumdiv(n, d, if ((d==1) || (d==n), 0, 2^((n/d -1)) -1)); \\ Michel Marcus, Aug 13 2013

a(n) = sum(d divides n, 2^(n/d-1) - 1 ), omitting d=1 and d=n.

Corrected, extended, and new name by Michel Marcus, Aug 13 2013

cp's OEIS Frontend

A302291 a(n) is the period of the binary expansion of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A333939 Number of multisets of compositions that can be shuffled together to obtain the k-th composition in standard order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A333941 Triangle read by rows where T(n,k) is the number of compositions of n with rotational period k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A136441 Number of rotational symmetries in the binary expansion of a number with 0 appended to the front.

Views

Author

Keywords

Examples

Links

Crossrefs

A138954 Number of complement symmetries in the rotations of the binary expansion of a number.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A137323 a(n) = sum(d divides n, 2^(n/d-1) - 1 ), omitting d=1 and d=n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions