Ytukyg

Suppose ${a_n}_{n=0}^{infty}$ is a sequence, defined by the recurrence relation

$$
a_{n+1} = phi(a_n) + sigma(a_n) - a_n,
$$

where $sigma$ denotes the divisor sum function and $phi$ is Euler's totient function. Does there exist $a_0$ such that the corresponding ${a_n}_{n=0}^{infty}$ is unbounded?

As $phi(a_n) + sigma(a_n) geq 2a_n$ (see here: Is $phi(n) + sigma(n) geq 2n$ always true?), every sequence of this type is monotonically non-decreasing. This means that it is bounded iff it contains an element $a_n$ such that $phi(a_n) + sigma(a_n) = 2a_n$. We know, that to satisfy this equation, $a_n$ must either be $1$ or prime (see: Find all positive integers $n$ such that $phi(n)+sigma(n)=2n$.). Thus, the question is equivalent to: "Does every such sequence ${a_n}_{n=0}^{infty}$ with $a_0 geq 2$ contain a prime element?". And I do not know how to proceed further.

Any help will be appreciated.

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})approxfrac2{sqrt{n}}$. Therefore $$mathbb{P}(a_nmbox{ converges})lessapprox2left(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_0toinfty$. 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.