Collatz analog in C lang.

A few days ago I kept thinking about an analog of the Collatz conjecture for polynomials with coefficients mod m. When m = 2, the conjecture is true, but when m = 3 the conjecture is false.

I wrote some Mathematica code to make it work with polynomials as polynomials. Then a comment on that post made me realize that the m = 2 case could easily be implemented in integers using bit shifts and XOR.

Recall that the rule was that if p(x) has a constant term, multiply by (x + 1) and add 1. Otherwise divide by x.

It’s easy to represent polynomials mod 2 as integers: set the nth bit from the right to 1 if and only if the coefficient of xn is 1. This assumes we’re counting from 0. Dividing by x corresponds to shift bits to the right, and multiplying by x corresponds to shifting bits to the left. Polynomial addition corresponds to XOR.

So here’s the Collatz operation in verbose C:

    if (x != 1)
        if (x & 1)
            x = x ^ (x << 1) ^ 1;
        else
            x >>= 1;        

Here it is in terse C:

    (x == 1) ? 1 : (x & 1) ? x ^ (x << 1) ^ 1 : x >> 1;        

Due to the operator precedent rules for C, all the parentheses can be removed, resulting in even more terse/cryptic code.

    x == 1 ? 1 : x & 1 ? x ^ x << 1 ^ 1 : x >> 1;        

The left shift above can overflow, and it’s not clear how large the inputs to this iteration can be. We know that the iterates will eventually converge to 1, but it’s not obvious how large the iterations can get before they start getting smaller.