cp's OEIS Frontend

A138904 Number of rotational symmetries in the binary expansion of a number.

%I A138904 #15 Apr 20 2020 00:28:02
%S A138904 1,1,1,2,1,1,1,3,1,1,2,1,1,1,1,4,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,5,1,1,
%T A138904 1,1,2,1,1,1,1,1,3,1,1,2,1,1,1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,6,1,1,1,1,
%U A138904 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
%N A138904 Number of rotational symmetries in the binary expansion of a number.
%C A138904 Mersenne numbers of form (2^n - 1) have n rotational symmetries.
%C A138904 For prime length binary expansions these are the only nontrivial symmetries.
%C A138904 For composite length expansions it seems that when the number of symmetries is nontrivial it is equal to a factor of the length. We're working on an explicit formula.
%C A138904 Discovered in the context of random circulant matrices, examining if there's a correlation between degrees of freedom and number of symmetries in the first row.
%C A138904 When combined with A138954, these two sequences should give a full account of the number of redundant rows in a circulant square matrix with at most two distinct values, where a(n) is the encoding of the first row of the matrix into binary such that value a = 1 and value b = 0.
%C A138904 Discovered on the night of Apr 02, 2008 by Maxwell Sills and Gary Doran.
%C A138904 Conjecture: For binary expansions of length n, there are d(n) distinct values that will show up as symmetries, where d is the divisor function. The symmetry values will be precisely the divisors of n.
%C A138904 Example: for binary expansions of length 12, one sees that d(12) = 6 distinct values show up as symmetries (1, 2, 3, 4, 6, 12).
%C A138904 Conjecture: For numbers whose binary expansion has length n which has proper divisors which are all coprime: There will be only one number of length n with n symmetries. That number is 2^n - 1. For each proper divisor d (excluding 1), you can generate all numbers of length n that have n/d symmetries like so: (2^0 + 2^d + 2^2d ... 2^(n-d)) * a, where 2^(d-1) <= a < (2^d) - 1. The rest of the expansions of length n will have only the trivial symmetry.
%C A138904 Also the number of rotational symmetries of the n-th composition in standard order (graded reverse-lexicographic). This composition (row n of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of n, prepending 0, taking first differences, and reversing again. - _Gus Wiseman_, Apr 19 2020
%C A138904 From _Gus Wiseman_, Apr 19 2020: (Start)
%C A138904 Aperiodic compositions are counted by A000740.
%C A138904 Aperiodic binary words are counted by A027375.
%C A138904 The orderless period of prime indices is A052409.
%C A138904 Numbers whose binary expansion is periodic are A121016.
%C A138904 Periodic compositions are counted by A178472.
%C A138904 Period of binary expansion is A302291.
%C A138904 Compositions by sum and number of distinct rotations are A333941.
%C A138904 All of the following pertain to compositions in standard order (A066099):
%C A138904 - Length is A000120.
%C A138904 - Necklaces are A065609.
%C A138904 - Sum is A070939.
%C A138904 - Runs are counted by A124767.
%C A138904 - Strict compositions are A233564.
%C A138904 - Constant compositions are A272919.
%C A138904 - Lyndon compositions are A275692.
%C A138904 - Co-Lyndon compositions are A326774.
%C A138904 - Aperiodic compositions are A328594.
%C A138904 - Reversed co-necklaces are A328595.
%C A138904 - Rotational period is A333632.
%C A138904 - Co-necklaces are A333764.
%C A138904 - Reversed necklaces are A333943.
%C A138904 Cf. A000031, A001037, A008965, A019536, A211100, A328595, A328596, A329312, A329313, A329326.
%C A138904 (End).
%H A138904 Maxwell Sills and Gary Doran, <a href="/A138904/b138904.txt">Table of n, a(n) for n = 0..99</a>
%F A138904 a(n) = A070939(n)/A302291(n) = A000120(n)/A333632(n). - _Gus Wiseman_, Apr 19 2020
%e A138904 a(10) = 2 because the binary expansion of 10 is 1010 and it has two rotational symmetries (including identity).
%t A138904 Table[IntegerLength[n,2]/Length[Union[Array[RotateRight[IntegerDigits[n,2],#]&,IntegerLength[n,2]]]],{n,100}] (* _Gus Wiseman_, Apr 19 2020 *)
%Y A138904 Cf. A136441, A138954.
%K A138904 base,easy,nonn
%O A138904 0,4
%A A138904 _Max Sills_, Apr 03 2008, Apr 04 2008