On 29/09/2015 18:39, Kerry Mitchell wrote:
My initial calculations show that the orbit of 0 under "add 1 and reverse bits" is periodic:
- if the number of bits (m) is odd, then the period is 2^m, - if the number of bits is even, then the period is 2^(m/2+1)-1.
Warren's proved this for the even case. The odd case is correct too. Suppose our number of bits is 2n+1. If a,b are n-bit strings, write <a|b> for reverse(a) 0 b <a#b> for reverse(a) 1 b. And write N for 2^n-1. Then: <a|b> -> <b+1|a> if b<N <0#a> if b=N <a#b> -> <b+1#a> if b<n <0|S(a)> if b=N where S(a) = reverse(reverse(a)+1). Now, suppose we start with <0|b>. Then both sides count up independently until we get to <N-b|N>, which -> <0#N-b>. Then both sides count up again until we get to <b#N>, which -> <0|S(b)>. Then the same process leads us to <0|S(S(b))>, etc., with the <0|___> counting in bit-reverse order until we get back to zero. A little bookkeeping verifies that at this point we have run through all the 2^(2n+1) possibilities. -- g