# Does iterating a certain function related to the sums of divisors eventually always result in a prime value?

Let define the following function for integers (from 2): $f(x)=\sigma(x)-1$, where $\sigma$ is the sum of the divisors of $x$. For example $f(6)=6+3+2=11$, $f(5)=5$. Note that $x$ is a fixed point for $f$ if and only if, $x$ is prime.

If we iterate starting at any integer $x$ we get a dynamical system.

Computations with Maple showed that for all integer $x$ in $[2,2000000]$ there exists an integer $n$ such that $(f \circ f \circ \dots \circ f)(x)$ is prime; that is for each integer $x$ the sequence generated is stationary. The question is: can anyone help proving the conjecture ?

Thank you for any help on the subject.

• Welcome on MO! Although what you describe seems nice, I fail to see a question here. Could you please be more specific as to what your question might be? Commented Sep 16, 2014 at 14:30
• The question is to prove that: for every $x\in \mathbb N$ there exists an $n(x)\in \mathbb N$ such that $f^{n(x)}(x)$ is prime. Commented Sep 16, 2014 at 14:52
• I have a question: Are the primes that you got in your experiments uniformly distributed in some sense? Or are there prime numbers that occur more often that others? Commented Sep 16, 2014 at 14:57
• Guy's book on unsolved problems in number theory is a good if old resource for such problems. Start your literature search there. Your operator resembles near perfect numbers, perhaps that literature will help. Commented Sep 16, 2014 at 15:57
• See also OEIS sequence A039654: oeis.org/A039654 Commented Sep 16, 2014 at 16:42

$\sigma(n)$ grows not too much faster than $n$: $\sigma(n) = O(n \log \log n)$. This is slow enough that we should have $\log f^{(n)}(x) = O(n \log n)$ say. Heuristically, the probability that $f^{(n)}(x)$ is prime should be something like $1/\log f^{(n)}(x)$, and since $\sum_n \dfrac{1}{n \log n}$ diverges, we would expect to eventually reach a prime with probability $1$. Of course, this is not a proof, but it does provide some justification for believing the conjecture.

• And the fact that values of $\sigma$ tend to be more composite/have smaller prime factors than typical integers means that the values of $f$ are even more likely to be prime. Commented Sep 16, 2014 at 16:37
• Also, $\sigma(n)$ is likely to have many small prime factors, so $f(n)$ is likely not to, which further improves the odds. Commented Sep 16, 2014 at 16:51
• @DavidSpeyer Do you mean to make a point different from the one that Greg Martin made and if so which, or did you just overlook his comment?
– user9072
Commented Sep 16, 2014 at 17:02
• @quid Just overlooked, sorry. While I'm at it, though, I'll point out that, if $n\equiv 2 \bmod 3$ then $f(n) \equiv 2 \bmod 3$ and, if $n \equiv 3 \bmod 4$ then $f(n) \equiv 3 \bmod 4$. This might be useful. Commented Sep 16, 2014 at 18:11
• Also, unless $n$ is a square or twice a square, $f(n) \equiv 1 \mod 2.$ $f(n) \equiv 0 \mod 3$ seems pretty rare although $f(n) \equiv 0 \mod 5$ seems to happen about $\frac{3}{4}\frac{1}{5}$ of the time. Commented Sep 17, 2014 at 17:22

Every prime occurs at least once (obviously) as the end of a trajectory. However many occur only once and some occur quite often. Since $f$ is non-decreasing it is easy by simple computation to find all $x$ which end up at a particular prime $p$.

Primes such that $p+1$ has many small prime factors are likely to occur often. For example, there are $125$ starting points which end at $5039$ but the nearby primes $5011,5023,5051, 5059$ and $5057$ can be reached only from themselves while $5021$ can be reached starting from itself and one other place, $2650=2\ 5^2\ 53$ with $\sigma(2650)=(2+1)(25+5+1)(53+1)=2\ 3^4\ 31=5022.$ It is not too hard to establish that $\sigma(x)=2651$ has no solutions.

On the other hand, $5040=2^33^25\ 7$ can be factored in may ways as the product of several factors, which must have only small prime factors. Here are all the ways so that each factor is one less than a prime.

$[3, 4, 14, 30], [3, 6, 14, 20], [3, 4, 420], [3, 12, 140], [3, 20, 84], [4, 14, 90], $$[4, 30, 42], [4, 1260], [6, 14, 60], [6, 20, 42], [12, 14, 30], [6, 840],$$ [14, 18, 20], [12, 420], [14, 360], [20, 252], [30, 168], [60, 84]$

These, with $5039$ itself, give the $19$ square free integers with $\sigma(x)-1=5039.$ There are others which are not square free, such as $x=4y$ for odd $y$ with $\sigma(y)=720$ (also examples coming from $\sigma(3^3)=40$ and from $\sigma(2^5)=63$.) There are as well starting points which land at $5039$ after several steps.

I'd expect $6719=(2^6\ 3\ 5 \ 7)-1$ to occur quite often, but I haven't checked.

• "Since f is non-decreasing...". However $\ f(4)=6 > 5=f(5),\$ and this is not the only counterexample. Commented Sep 16, 2014 at 22:06
• I simply meant that $x \le f(x)$ so one can quickly compute the set of all $x$ whose trajectory ends at $p.$ Commented Sep 16, 2014 at 22:32
• You mean: $\ \forall_{n\ge 2}\,f(n)\ge n.\$ (You could say so). Thank you. Commented Sep 16, 2014 at 22:38
• According to the table at oeis.org/A039654/b039654.txt, there are 168 starting points that reach 6719. Commented Sep 17, 2014 at 0:11
• if you take f(n)= sum of divisors+1 and n is a power of 2 you get an infinite sequence of powers of 2; so the probabilistic point of vue is problematic or the point of vue could be " what could be the set of starting points that do not lead to a prime ?" or "what is the set of integers k such that f(n)=k+sum of divisors of n leads always to a prime ?" Commented Oct 15, 2016 at 13:43