In general, add one and then permute the bits (according to some fixed permutation) seems like it can have very complicated dynamics. On Tue, Sep 29, 2015 at 9:55 AM, Allan Wechsler <acwacw@gmail.com> wrote:

This is fairly cool. 1 bit: a single 2-cycle. 2 bits: 1+3 = 4.

3 bits: a single cycle of 8.

4 bits: 4+5+7 = 16.

How far have you gone?

On Tue, Sep 29, 2015 at 9:49 AM, James Propp <jamespropp@gmail.com> wrote:

...

I've been playing with the compound operation on bit-strings of length m in which you (a) add 1 mod 2^m and (b) reverse the order of the bits.

Has anyone seen this before? It seems sufficiently simple that I doubt I'm the first person to have played with it.

Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

If you look at what this operation does to 1 2 3 4 ... you get 1, 3, 1, 5, 3, 7, 1, 9, 5, 13, 3, 11, 7, 15, 1, 17, 9, 25, 5, 21, 13, 29,... which is A030101 This has a different definition from yours: it doesn't add 1 before reversing. Best regards Neil Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com On Tue, Sep 29, 2015 at 10:14 AM, Allan Wechsler <acwacw@gmail.com> wrote:

5 bits: a single cycle of 32, unless I screwed up.

On Tue, Sep 29, 2015 at 9:59 AM, Allan Wechsler <acwacw@gmail.com> wrote:

...

In general, add one and then permute the bits (according to some fixed permutation) seems like it can have very complicated dynamics.

On Tue, Sep 29, 2015 at 9:55 AM, Allan Wechsler <acwacw@gmail.com> wrote:

...

This is fairly cool. 1 bit: a single 2-cycle. 2 bits: 1+3 = 4.

3 bits: a single cycle of 8.

4 bits: 4+5+7 = 16.

How far have you gone?

On Tue, Sep 29, 2015 at 9:49 AM, James Propp <jamespropp@gmail.com> wrote:

...

I've been playing with the compound operation on bit-strings of length m in which you (a) add 1 mod 2^m and (b) reverse the order of the bits.

Has anyone seen this before? It seems sufficiently simple that I doubt I'm the first person to have played with it.

Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

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

My son's third-grade class liked my 25-minute presentation. But I still haven't proved that the phenomenon works for decimal digit-strings of arbitrary length m. I've rewritten Warren and Gareth's analyses of the add-1-and-reverse map to see how much of their work carries over to the more general radix-r case. The analysis of the size of the orbit of 00...0 requires no new ideas for r

2. But for my equidistribution conjecture (in any orbit, the number of elements with a in the r^i position equals the number of elements with b in the r^j position when a+b = r-1 and i+j = m-1), I find that when r is bigger than two, Gareth's map b -> S(N-b) is not an involution, which is going to make the analysis harder; and when r is odd, things are even trickier.

I'm going to include here the details that I worked out for the case where r is ten (modifying notation where I felt changes were called for), stopping where I ran out of steam. Theorem: If m is even (resp. odd), then the size of the orbit of 00...0 is 2*10^(m/2)-1 (resp. 10^m). Proof: For the even case, write m = 2n. If a,b are n-digit strings, write < a | b > for reverse(a) b (the concatenation of reverse(a) and b) and write N for 10^n-1. Then < a | b > --> < b+1 | a > if b<N < 0 | S(a) > if b=N where S(a) = reverse(reverse(a)+1). It's now easy to see that 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 > after 2N+1 = 2(10^n-1)+1 = 2(10^n)-1 steps, QED. For the odd case, write m = 2n+1. If a,b are n-digit strings, and i is a digit, write < a | i | b > for reverse(a) i b and write N for 10^n-1 as before. Then: < a | i | b > --> < b+1 | i | a > if b<N < 0 | i+1 | a > if b=N for i = 0,1,...,m-2, and < a | m-1 | b > --> < b+1 | m-1 | a > if b<n < 0 | 0 | S(a) > if b=N where S(a) = reverse(reverse(a)+1). Now, suppose we start with < 0 | 0 | b >. Then both sides count up (first one, then the other, etc.) for 2(N-b) steps until we get to < N-b | 0 | N >, which --> < 0 | 1 | N-b > in one step. Then both sides count up for 2b steps until we get to < b | 1 | N >, which --> < 0 | 2 | b > in one step. (Looking at the way the middle digit behaves in this orbit --- being 0 for 2(N-b)+1 steps, then being 1 for 2b+1 steps, then being 2 for 2(N-b)+1 steps, then being 3 for 2b+1 steps, etc. --- we begin to see why the case where the base r is odd is going to be different.) And so forth, until we get to < b | 9 | N >, which --> < 0 | 0 | S(b) > in one step. (Total number of "-->" steps: 5((2(N-b)+1) + (2b+1)) = 5(2N+2) = 10(N+1) = 10(10^n) = 10^(n+1).) Then the same process leads us to < 0 | 0 | S(S(b)) >, etc., with the "kets" b, S(b), S(S(b)), ... counting in digit-reverse order until we get back to zero. The number of different kets we see is 10^n. So we have run through all the 10^n 10^(n+1) = 10^(2n+1) = 10^m possibilities, QED. Conjecture: In any orbit of the add-1-and-reverse map acting on decimal strings of length m, the number of elements with a in the r^i position equals the number of elements with b in the r^j position when a+b = 9 and i+j = m-1. Beginnings of a proof: With an odd number of digits, there is only one orbit, containing all the m-digit numbers and hence certainly having the same number of a's in the 10^i position as b's in the 10^j position, for ALL a,b,i,j. With an even number of digits: As before, the successor of < a | b > is < b+1 | a > except when b=N=10^n-1 in which case it's < 0 | S(a) >, with S(a) = reverse(reverse(a)+1). 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, takes the nines-complement of all the digits. Then the second operation increments digits from the left up to and including the first non-9. Together, this is the same as: tens-complement all the digits from the left until finding the first non-zero digit, then nines-complement all digits after that. At this point (handling the base-two case) Gareth wrote "Now note that this is obviously an involution; it has order 1 if b=0 or b=1, and order 2 otherwise." That was true for base two, but isn't true for base ten. Anyone see what to say next? Jim On Fri, Oct 2, 2015 at 3:07 PM, James Propp <jamespropp@gmail.com> wrote:

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

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. Verified from m=1 to 30 bits. Kerry On Tue, Sep 29, 2015 at 10:32 AM, Adam P. Goucher <apgoucher@gmx.com> wrote:

Here's a Mathematica app for 'add c and reverse':

Manipulate[ Graph[Map[(FromDigits[#, 2] -> Mod[FromDigits[Reverse[#], 2] + c, 2^m]) &, Tuples[{0, 1}, m]]], {m, 2, 10, 1}, {{c, 1}, 1, 2^m - 1, 1}]

...

Sent: Tuesday, September 29, 2015 at 2:49 PM From: "James Propp" <jamespropp@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: [math-fun] Add 1 and reverse

I've been playing with the compound operation on bit-strings of length m in which you (a) add 1 mod 2^m and (b) reverse the order of the bits.

Has anyone seen this before? It seems sufficiently simple that I doubt I'm the first person to have played with it.

Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

You should WolframTaP Graph[FromDigits[#, 2] -> Mod[FromDigits[Reverse[#], 2] + 1, 512] & /@ Tuples[{0, 1}, 9]] (which will become dull if they ever implement Planarize.) --rwg On 2015-09-29 10:32, Adam P. Goucher wrote:

Here's a Mathematica app for 'add c and reverse':

Manipulate[ Graph[Map[(FromDigits[#, 2] -> Mod[FromDigits[Reverse[#], 2] + c, 2^m]) &, Tuples[{0, 1}, m]]], {m, 2, 10, 1}, {{c, 1}, 1, 2^m - 1, 1}]

...

Sent: Tuesday, September 29, 2015 at 2:49 PM From: "James Propp" <jamespropp@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: [math-fun] Add 1 and reverse

I've been playing with the compound operation on bit-strings of length m in which you (a) add 1 mod 2^m and (b) reverse the order of the bits.

Has anyone seen this before? It seems sufficiently simple that I doubt I'm the first person to have played with it.

Jim Propp