# of runs of identical bits in n_2

[Wouter Meeussen]

hi,

if we write a number in binary, then we can count runs of identical bits :

 111100010101011111000
 ^   ^  ^^^^^^^    ^
 4   3  1111115    3

read as (4 ones, 3 zeros, 1 one ...)

BUT:
if we then count the number of "bins" or "switches+1", we lose the
information to
completely reconstruct the original number, but we gain a nice pattern :
we find :

Table[Length[Length/@Split[IntegerDigits[n,2]]],{n,1,255}]
=
{1,2,1,2,3,2,1,2,3,4,3,2,3,2,1,2,3,4,3,4,5,4,3,2,3,4,3,2,3,2,1,2,3,4,3,4,5,4,
  3,4,5,6,5,4,5,4,3,2,3,4,3,4,5,4,3,2,3,4,3,2,3,2,1,2,3,4,3,4,5,4,3,4,5,6,5,4,
  5,4,3,4,5,6,5,6,7,6,5,4,5,6,5,4,5,4,3,2,3,4,3,4,5,4,3,4,5,6,5,4,5,4,3,2,3,4,
  3,4,5,4,3,2,3,4,3,2,3,2,1,2,3,4,3,4,5,4,3,4,5,6,5,4,5,4,3,4,5,6,5,6,7,6,5,4,
  5,6,5,4,5,4,3,4,5,6,5,6,7,6,5,6,7,8,7,6,7,6,5,4,5,6,5,6,7,6,5,4,5,6,5,4,5,4,
  3,2,3,4,3,4,5,4,3,4,5,6,5,4,5,4,3,4,5,6,5,6,7,6,5,4,5,6,5,4,5,4,3,2,3,4,3,4,
  5,4,3,4,5,6,5,4,5,4,3,2,3,4,3,4,5,4,3,2,3,4,3,2,3,2,1}

surprisingly, a nice folding pattern underlies this:


Flatten[NestList[Flatten[{1+Reverse[#] , #}]&,{1},7]]

This could in principle be used to calculate the "bins-count" for a very
large number
without having to explicitly generate its binary representation.

Of course, for the perfect numbers (2^P -1) 2^(P-1), P = Mersenne prime,
the "bins-count" is allways 2.

the EIS contains this as:
- ----------------------
%I A005811 M0110
%S A005811 0,1,2,1,2,3,2,1,2,3,4,3,2,3,2,1,2,3,4,3,4,5,4,3,2,3,4,3,
%T A005811 2,3,2,1,2,3,4,3,4,5,4,3,4,5,6,5,4,5,4,3,2,3,4,3,4,5,4,3,
%U A005811 2,3,4,3,2,3,2,1
%N A005811 Number of 1's in Gray code for n.
%R A005811 SIAC 9 144 1980.
%K A005811 easy,nonn
%O A005811 0,3
%F A005811 a(2n+1) = 2a(n)-a(2n)+1, a(4n) = a(2n), a(4n+2) = 1+a(2n+1).
%A A005811 njas,jos,sp

is there a deeper connection (that I don't see) between the above and
http://www.astro.virginia.edu/~eww6n/math/GrayCode.html  ??
quote:
>>  The code is called reflected because it can be generated in the
following manner. Take the Gray code 0, >>  1. Write it forwards, then
backwards: 0, 1,
>>  1, 0. Then append 0's to the first half and 1's to the second half: 00,
01, 11, 10.
>>  Continuing, write 00, >>  01, 11, 10, 10, 11, 01, 00 to obtain: 000,
001, 011,
>>  010, 110, 111, 101, 100, ... (Sloane's A014550). 
endquote

after all, my folding formula generates them a bit differently.

wouter.
Dr. Wouter L. J. MEEUSSEN
w.meeussen.vdmcc at vandemoortele.be
eu000949 at pophost.eunet.be