Patterns from an Algorithm

Question

Consider the following algorithm:

1. pick an integer $n> 0$.

2. If $n$ is even, divide by 2. If $n$ is odd, find the least perfect square $m^2$ greater then $n$ and add $m^2$+n.

3. Repeat step 2. with either $n/2$ or $n + m^2$.

The conjecture is this algorithm will always terminate at a 1 or an 11. To show it terminates can be done by induction. Why do 1 and 11 appear? Is there anything significant about the number of "termination points" (here, just 1 and 11, so 2 termination points.)?

Generalization: The algorithm seems to terminate for all $n$ when replacing the least perfect square greater than n with the greatest perfect square less than n. It also seems to terminate when square is replaced by any power.

How can I understand this algorithm and its variations better, and in particular, the numbers where it terminates?

Answer 1

The calculations were done by Dr. Matthijs Coster found it was true for 100,000 numbers; and Neil Fernandez reached 1.2*10^6 .

Answer 2

It is not surprising that there is a small number of final cycles. I don't think there is an easy way to show there are only $2$. If $n$ is large and odd, $m^2$ will not be much larger than $n$, so adding it approximately doubles $n$. If $m$ is even, $m^2 \equiv 0 \pmod 4, n+m^2$ will be odd and equivalent to $n \pmod 4$. If $m$ is odd, $m^2 \equiv 1 \pmod 4$ and $n+m^2$ will be even, so we will divide by $2$ next time. We then have a $\frac 12$ chance to divide by $2$ again, so there is a downward bias. To avoid a cycle, you need to find an $n$ such that the next bigger square is even more than it is odd over the long run.

Given a cycle, there are chains that will feed into it. As you say, the cycle including $1$ is $1,5,14,7,16,8,4,2$. That means that $10,28,32$ and any number that is one of these multiplied by a power of $2$ will feed into it. For example, $3 \to 7$, so any number of the form $3\cdot 2^n$ will feed this cycle.

I don't know how to prove there are no cycles composed of larger numbers than you have tested. The usual way would be to find some number that you could prove any larger number must reach a smaller one, then to compute all the trajectories up to that number. The downward bias I noted does not provide such a bound, it is just a heuristic argument.