The Collatz conjecture, a.k.a. the 3*n* + 1 problem, a.k.a. the hailstone conjecture, asks whether the following sequence always terminates.

Start with a positive integer *n*.

- If
*n*is even, set*n*←*n*/2. Otherwise*n*← 3*n*+ 1. - If
*n*= 1, stop. Otherwise go back to step 1.

The Collatz conjecture remains an unsolved problem, though there has been progress toward a proof. Some people, however, are skeptical whether the conjecture is true.

This post will look at a **polynomial analog** of the Collatz conjecture. Instead of starting with a positive integer, we start with a polynomial with coefficients in the integers mod *m*.

If the polynomial is divisible by *x*, then divide by *x*. Otherwise, multiply by (*x* + 1) and add 1. Here *x* is analogous to 2 and (*x* + 1) is analogous to 3 in the (integer) Collatz conjecture.

Here is Mathematica code to carry out the polynomial Collatz operation.

c[p_, m_] := PolynomialMod[ If[ (p /. x -> 0) == 0, p/x, (x + 1) p + 1 ], m ]

If *m* = 2, the process always converges. In fact, it converges in at most *n*² + 2*n* steps where *n* is the degree of the polynomial [1].

Here’s an example starting with the polynomial *x*^{7} + *x*^{3} + 1.

Nest[c[#, 2] &, x^7 + x^3 + 1, 15]

This returns 1, and so in this instance 15 iterations are enough.

If *m* = 3, however, the conjecture is false. In [1] the authors report that the sequence starting with *x*² + 1 is periodic with period 6.

The following code produces the sequence of values.

NestList[c[#, 3] &, x^2 + 1, 6]

This returns the sequence

- 1 +
*x*^{2} - 2 +
*x*+*x*^{2}+*x*^{3} - 2
*x*^{2}+ 2*x*^{3}+*x*^{4} - 2
*x*+ 2*x*^{2}+*x*^{3} - 2 + 2
*x*+*x*^{2} *x*+*x*^{3}- 1 +
*x*^{2}

## Related posts

[1] Kenneth Hicks, Gary L. Mullen, Joseph L. Yucas and Ryan Zavislak. A Polynomial Analogue of the 3*n* + 1 Problem. The American Mathematical Monthly, Vol. 115, No. 7. pp. 615-622.