An algorithm that always reach the number one.

Question

Using the function below $$ f(n)=\begin{cases} n/2, & n \text{ even} \\ n+\lceil\sqrt{n}\rceil, & n \text{ odd} \end{cases} $$ for an integer $0<n\leq10^4$ it will eventually reach $1$. Has this function been studied before? Does it always work for every $n \in \mathbb{N}$? Note that using the floor function instead of the ceil function will work as well. (Why?)

Answer 1

$(\sqrt{n}+1)^2$ is around $n+ 2\sqrt{n}$, so it takes around 2 jumps to increment $\sqrt{n}$ by 1. That means that in the worst case scenario (ceiling of $\sqrt{n}$ even and $n$ odd) it’ll take at most 3 jumps to increment the root (and you’ll never skip a root), one more jump with the odd rounded root to get to an even number, and a final jump to divide by 2. Within 5 jumps, you’ll reach an even number and divide by two to a number which is less than $(n+4\sqrt{n}+5)/2$ which is less than n when $n>25$.

Since every number reaches a smaller number within 5 moves, eventually (within $5(n-25)$ turns) you’ll hit a number at most 25. You can manually check that every number from 1 to 25 collapses to 1.

The argument is identical for the floor function.