The Collatz conjecture, a.k.a. the 3n + 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 ← 3n + 1.
- If n = 1, stop. Otherwise go back to step 1.
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² + 2n steps where n is the degree of the polynomial .
Here’s an example starting with the polynomial x7 + x3 + 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  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 + x2
- 2 + x + x2 + x3
- 2 x2 + 2 x3 + x4
- 2 x + 2 x2 + x3
- 2 + 2 x + x2
- x + x3
- 1 + x2
 Kenneth Hicks, Gary L. Mullen, Joseph L. Yucas and Ryan Zavislak. A Polynomial Analogue of the 3n + 1 Problem. The American Mathematical Monthly, Vol. 115, No. 7. pp. 615-622.