Using your Head is Permitted

However, I will give the following hint: consider the solution to the previous month's riddle.

Let me introduce you to my greatest nemesis.

Its name is the Collatz conjecture, though it is known by many other names, the most popular of which perhaps being the "3n+1" problem. It is a problem that has wasted many mathematician man-years, and continues to waste at least 2-3 days of my time whenever anybody mentions it, because I find it impossible to do anything other than to think about it.

Paul Erdős, whom we mentioned last month, reportedly said about it that "Mathematics may not be ready for such problems," and it remains today as open as it ever was, almost a century after it was first posed.

Describing the conjecture is very easy: take any natural, n. If it is even, divide by 2. If it is odd, multiply by 3 and add 1. You now have a new natural. Repeat the process, continuing to repeat as many times as necessary. The conjecture is that after enough repetitions, one always eventually reaches n=1.

As an example, take n=7. Because it is odd, we multiply it by 3 and add 1, reaching 22. Because 22 is even, we divide by 2 to reach 11. Repeating this further we get 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1. Done.

Here is this month's problem:

Prove that the conjecture is true if we relax it by allowing one to multiply by 3^x instead of 3 when n is odd, where x is an integer greater than zero that one can choose freely, and can be different each time a multiplication is needed throughout the process.

List of solvers: