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.

  • You mean "Does there exists an $a_0$ such that the sequence doesn't contain a prime element", don't you? – N. S. Aug 24 at 16:28
  • 1
    It looks like there are a lot of numbers with this property, with $a_0 = 22$ being the smallest. – Paul Aug 29 at 17:56
  • Here the numbers up to 1000 – Paul Aug 29 at 18:32
  • 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. – Haran Sep 18 at 15:00
  • 1
    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. – Peter Taylor Sep 27 at 16:02

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.

  • "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$. – mathworker21 Dec 13 at 5:44
  • 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}$ – SmileyCraft 2 days ago
  • I didn't know the "if" was carrying over to the next sentence. respectfully, you should write more clearly. – mathworker21 2 days ago

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.