Nice! Note that Gareth has proved something sharper: for every orbit, the number of elements in the orbit with 1 in the 2^i position equals the number of elements in the orbit with 0 in the 2^j position, whenever i+j equals 1 less than the common length of our bit-strings (that is, when bit-string reversal exchanges the 2^i position with the 2^j position). I don't believe that base two is special. I believe (based on experiments) that for every radix r > 1, and for every length m, if you look at an orbit of the base-r add-1-and-reverse map on digit-strings of length m (defined in the obvious way), the number of elements in the orbit with a in the r^i position equals the number of elements in the orbit with b in the r^j position, whenever a+b equals r-1 and i+j equals m-1. Does Gareth's method apply to this broader conjecture? My conjecture implies that, whenever the digits a,b sum to r-1, each orbit of the map has the property that the total number of occurrences of the digit a equals the total number of occurrences of the digit b. See the worksheet http://jamespropp.org/Silly-way-to-add-1.docx , which I created for my son's third grade class. (When I showed him the decimal add-1-and-reverse operation, my normally math-averse son declared "That's fun math! Can you show it to my class?" and the next day his teacher said "Yes". So now I'm supposed to create a worksheet and lead the students in an activity. But it's a little intellectually dishonest of me to hand out a worksheet like this, with its teasing questions at the end, without actually knowing the answer myself. Gareth, you're helping me do my homework!) Jim Propp On Tue, Sep 29, 2015 at 10:20 PM, Gareth McCaughan < gareth.mccaughan@pobox.com> wrote:
On 29/09/2015 21:16, James Propp wrote:
Conjecture: In each orbit, there are exactly as many 0s as 1s.
The conjecture is correct.
With an odd number of bits, there is only one orbit, containing all the m-bit numbers and hence certainly having the same number of 0s as 1s.
With an even number of bits: suppose we have 2n bits, and for any n-bit strings a,b define <a|b> to be reverse(a) concat b. Then the successor of <a|b> is <b+1|a> except that if b=N:=2^n-1 then it's <0|S(a)> instead, where S(a) = reverse(reverse(a)+1). So then e.g. the orbit of <0|0> goes <0|0> <1|0> <1|1> <2|1> etc., ending up with ... <N|N-1> <N|N> <0|0>.
A little more generally, the orbit of <0|b> goes <0|b> <b+1|0> <1|b+1> ... <N-b|N> <0|S(N-b)> so now we need to understand the iteration b -> S(N-b). The first operation, b -> N-b, flips all the bits. Then the second flips bits from the left up to and including the first 0. Together, this is the same as: scan from the left until finding the first 1, then flip all bits after that. Now note that this is obviously an involution; it has order 1 if b=0 or b=1, and order 2 otherwise.
So. The orbits are as follows.
<0|0> <1|0> <1|1> <2|1> ... <N|N-1> <N|N>
<0|1> <2|0> <1|2> <3|1> ... <N|N-2> <N-1|N>
for b=2..N-1: <0|b> <b+1|0> <1|b+1> ... <N|N-b-1> <N-b|N> ... <0|b'> <b'+1|0> <b'+1|1> ... <N|N-b'-1> <N-b'|N>
where b' = S(N-b) = the result of flipping all bits in b after the first 1.
(Sanity check: the orbit beginning <0|0> has size 2N+1; the orbit beginning <0|1> has size 2N-1; the orbit beginning <0|b> has size 2(N-b)+1 + 2(N-b')+1, and if the first 1-bit in b is in position 2^k then b+b' equals 2^(k+1) + (2^k-1), and there are 2^(k-1) such orbits. Total is 2N+1 + 2N-1 + sum {k=1..n-1} of (4N+2-2^(k+2)-2^(k+1)-2)2^(k-1) and with a little pain one may verify that this equals 2^(2n).)
OK, so now let's count bits. Each orbit or half-orbit has the form <0|b> <b+1|0> ... <N|N-b-1> <N-b|N> and now we need merely observe that this is invariant under the following operation: replace each <a|b> with <N-b|N-a> and take the entries in reverse order. And this interchanges the counts of 0-bits and 1-bits, which therefore must be equal; we're done.
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun