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.

  • $\begingroup$ You mean "Does there exists an $a_0$ such that the sequence doesn't contain a prime element", don't you? $\endgroup$
    – N. S.
    Commented Aug 24, 2018 at 16:28
  • 1
    $\begingroup$ It looks like there are a lot of numbers with this property, with $a_0 = 22$ being the smallest. $\endgroup$
    – Paul
    Commented Aug 29, 2018 at 17:56
  • $\begingroup$ Here the numbers up to 1000 $\endgroup$
    – Paul
    Commented Aug 29, 2018 at 18:32
  • $\begingroup$ It is possible to make the sequence monotonically increase for arbitrarily large number of terms. We can keep increasing the power of $2$ that divides $a_0$. However, I am not sure whether it is possible for the sequence to be unbounded, in other words, monotonically increase forever. This seems most likely for base values such as $a_0=22$. If one can actually prove that there exists a sequence that does not contain any terms of the form $k^2$ or $2k^2$, then the sequence will be unbounded. $\endgroup$
    – Haran
    Commented Sep 18, 2018 at 15:00
  • 1
    $\begingroup$ Alternative formulation: $a_{n+1} = a_n + \sum_{d \mid a_n,\, d < a_n} \left(1 + \mu\left(\frac{a_n}{d}\right)\right) d$ where $\mu$ is the Möbius function. $\endgroup$ Commented Sep 27, 2018 at 16:02

1 Answer 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.

  • $\begingroup$ "as $a_0 \to 0$" should be "as $a_0 \to \infty$. and it's not obvious to me as to why the probability goes to 0 as $a_0 \to \infty$. $\endgroup$ Commented Dec 13, 2018 at 5:44
  • $\begingroup$ If you have an exponential growth, then we are looking at $\sum \frac1{\sqrt{a_0}x^n}=\frac1{\sqrt{a_0}}\sum x^{-n}$ $\endgroup$ Commented Dec 13, 2018 at 9:01
  • $\begingroup$ I didn't know the "if" was carrying over to the next sentence. respectfully, you should write more clearly. $\endgroup$ Commented Dec 13, 2018 at 10:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .