26.3.17

Other Collatz-like Algorithms

I wrote about the Collatz conjecture in relation to finite fields and I came across a few interesting sequences but I didn't discuss the possibility of other Collatz-like algorithms that always reach 1.

Once again, the Collatz problem is defined as follows:

Collatz Algorithm: Given any positive integer n, let a0 = n. For i > 0, let:

ai = ai-1/2 if ai-1 is even
ai = 3*ai-1 + 1 if ai-1 is odd

Conjecture: Given any positive integer, the above recurrence relation returns 1.

This conjecture seems to hold although it hasn't been proven yet.

While looking at a different problem related to generating powers of 2 backwards, I stumbled upon a Collatz-like algorithm, which I generalize below for all positive integers.

Collatz-like Algorithm #1: Given any positive integer n, let a0 = (n+1)/2 if n is odd or a0 = n/2 if n is even. For i > 0, let:

ai = ai-1/2 if ai-1 is even
ai = (ai-1 - 1)/2 +  a0 if ai-1 is odd

Conjecture: Given any positive integer n, the above recurrence relation returns 1, and all integers it reaches before it reaches 1 are strictly less than n

In fact, I claim that:

Claim: If n is even then the Collatz-like Algorithm #1 generates all powers of 2 mod (n-1) in reverse order and if n is odd then it generates all powers of 2 mod n in reverse order.

Example: let n = 36 so a0 = 18
Then:
a1 = 18/2 = 9
a2 = ((9-1)/2) + 18 = 22
a3= 22/2 = 11
a4 = ((11-1)/2) + 18 = 23
a5 = ((23-1)/2) + 18 = 29
a6 = ((29-1)/2) + 18 = 32
a7 = 32/2 = 16
a8 = 16//2 = 8
a9 = 8/2 = 4
a10 = 4/2 = 2
a11 = 2/2 = 1