Does there exist $a_0$, such that $\{a_n\}_{n=0}^{\infty}$ is unbounded?

Solution 1:

Not a complete answer, but a heuristic intuition why probably many numbers fulfill your requirement, in particular $22$.

We want to show $a_n$ is never prime. If you observe the sequence with $a_0=22$ you will notice that all terms are even, and hence not prime. If we can show $a_n$ is even for all $n$, we are done. If we try induction, we find the following.

Recall that $\phi(n)$ is even for all $n>2$, so if $a_{n-1}>2$ is even, then $a_n$ is even if and only if $\sigma(a_{n-1})$ is even. Now recall that $$\sigma(p_1^{k_1}...p_i^{k_i})=(1+p_1+...+p_1^{k_1})(1+p_2+...+p_2^{k_2})...(1+p_i+...+p_i^{k_i}).$$ For odd primes $p$ we have $(1+p+...+p^k)$ is even if and only if $k$ is odd. And for $p=2$ we have $(1+p+...+p^k)$ is odd no matter what $k$ is. Hence $\sigma(n)$ is even if and only if there is an odd prime that divides $n$ an odd number of times. So $\sigma(n)$ is odd if and only if $n$ is a square, or $2n$ is a square.

The rest of this argument will be heuristic. Let's calculate the probability of $\sigma(n)$ being odd. Since we deduced that this is equivalent to either $n$ or $2n$ being a square, we find $\mathbb{P}(\sigma(n)\mbox{ odd})\approx\frac2{\sqrt{n}}$. Therefore $$\mathbb{P}(a_n\mbox{ converges})\lessapprox2\left(\frac1{\sqrt{a_0}}+\frac1{\sqrt{a_1}}+...\right)$$ If $a_n$ grows exponentially, which it appears to do, then this gives us a finite probability that $a_n$ converges. Also notice that this probability itself then also converges to $0$ as $a_0\to\infty$. So heuristically speaking, it seems likely that almost all even $a_0$ make the sequence diverge.

Interestingly, the converse holds for odd numbers, as then $a_n$ is even if and only if $\sigma(a_{n-1})$ is odd, which we just argued has a low probability. Maybe something else can be said about different factors from $2$ though.

In conclusion, as I feel is quite often the case in number theory, it seems likely we know the answer, but there is no clear way to prove this. Again, the main problem is that the sequence is defined by adding and subtracting, but we are interested in the factors, which is what makes it difficult to analyse.