How to increase the lower bound on possible counter-examples to the Collatz Conjecture?

Question

According to Wikipedia, all positive integers up to $2^{60}$ have been tested and follow the Collatz Conjecture. This got me thinking, could one write a program that tests integers of the form $2^{60} +n$? Because obviously, if all integers below $2^{60}$ follow the conjecture, then if repeated iterations of the Collatz function to numbers of the form $2^{60}+n$ yields a number smaller than this bound, then that number automatically must also follow the conjecture, right?

For example, take the number $2^{60} +1$. It is clearly an odd number, so

$3(2^{60}+1) +1= 3*2^{60}+4$

This number is clearly even, so

$(3*2^{60}+4)/4=3*2^{58}+1$

This number is obviously smaller than $2^{60}$, so therefore $2^{60}+1$ must follow the conjecture! Could one write a program to do this rapidly, increasing this bound?

Answer 1

What you have observed is that $2^{k}+n$ follows the same path as $n$, at least for a little bit. In fact, $2^{k}+n$ and $n$ take the same patterns of "divide by $2$", "$3n+1$", but with every division you decrease $k$ by $1$. This means that eventually your power of two becomes $1$, and you lose all your predictive power. If this happened sufficiently slowly, it would actually be enough to give a proof by induction of the conjecture! Unfortunately, there are several forms of numbers which will always beat you - On example is $2^{k}-1$. Note that this maps as $2^{k}-1 \to 3\cdot 2^{k}-4 \to 3\cdot 2^{k-1}-1>2^{k}-1$, and this sequence will clearly not decrease until your power of two is exhausted. There are a few other patterns; if you want to explore them, have a look at cycles of negative numbers under the collatz iteration.