Once again, the Collatz problem is defined as follows:

**Collatz Algorithm:**Given any positive integer n, let a

_{0}= n. For i > 0, let:

a

_{i}= a

_{i-1}/2 if a

_{i-1}is even

a

_{i}= 3*a

_{i-1}+ 1 if a

_{i-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 a

_{0}= (n+1)/2 if n is odd or a

_{0}= n/2 if n is even. For i > 0, let:

a

_{i}= a

_{i-1}/2 if a

_{i-1}is even

a

_{i}= (a

_{i-1}- 1)/2 + a

_{0}if a

_{i-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 a

_{0}= 18

Then:

a

_{1}= 18/2 = 9

a

_{2}= ((9-1)/2) + 18 = 22

a

_{3}= 22/2 = 11

a

_{4}= ((11-1)/2) + 18 = 23

a

_{5}= ((23-1)/2) + 18 = 29

a

_{6}= ((29-1)/2) + 18 = 32

a

_{7}= 32/2 = 16

a

_{8}= 16//2 = 8

a

_{9}= 8/2 = 4

a

_{10}= 4/2 = 2

a

_{11}= 2/2 = 1