# of runs of identical bits in n_2
Wouter Meeussen
eu000949 at pophost.eunet.be
Sun Jul 12 16:27:47 CEST 1998
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
More information about the SeqFan
mailing list