# If $p_{n}$ is the largest prime factor of $p_{n-1}+p_{n-2}+m$, then $p_{n}$ is bounded

Conjecture

Let $m$ be give positive integer numbers,a sequence $p_{1},p_{2},\cdots$of primes satisfies the following condition:for $n\ge 3$,$p_{n}$ is the greatest prime divisor $p_{n-1}+p_{n-2}+m$, Prove that the sequence is bounded.

I have solved it when $m$ is even number, but for $m$ is odd, I can't solve it.

When $m$ is even, let $b_{n}=\max\{p_{n},p_{n+1}\}$ for $n\ge 1$

Lemma: for all $n$ we have $$b_{n+2}\le b_{n}+m+2$$

Proof: certainly $p_{n+1}\le b_{n}$, so it suffices to show that $p_{n+2}\le b_{n}+m+2$. If either $p_{n}$ or $p_{n+1}$ equals $2$, then we have $$p_{n+2}\le p_{n}+p_{n+1}+m=b_{n}+m+2$$ otherwise, $p_{n}$ and $p_{n+1}$ are both odd, so $p_{n}+p_{n+1}+m$ is even. Because $p_{n+2}\neq 2$ divides this number, we have $$p_{n+2}\le\dfrac{1}{2}(p_{n}+p_{n+1}+m)\le b_{n}+\frac{m}{2}$$ This proves the claim.

Choose $k$ large enough so that $b_{1}\le k\cdot (m+3)!+1$. We prove by induction that $b_{n}\le k\cdot (m+3)!+1$ for all $n$. If this statement holds for some $n$, then $$b_{n+1}\le b_{n}+m+2\le k\cdot (m+3)!+m+3$$ if $b_{n+1}>k\cdot (m+3)!+1$ ,then let $q=b_{n+1}-k\cdot (m+3)!$, we have $1<q\le m+3$, so we have $q|(m+3)!$, hence, $q$ is proper divisor of $k\cdot (m+3)!+q=b_{n+1}$, which is impossible, because $b_{n+1}$ is prime.

Thus $p_{n}\le b_{n}\le k\cdot(m+3)!+1$ for all $n$.

But if $m$ is an odd number, then $p_{n}+p_{n+1}+m$ is an odd number, so we can't have the following inequality: $$p_{n+2}\le\dfrac{1}{2}(p_{n}+p_{n+1}+m)!$$.

So how to prove this case?

• As $p_{n-2},p_{n-1}$, and $p_n$ are approximately the same, the only possibility is that $p_{n-2}+p_{n-1}+m=2p_n$, so $m$ must be even. – Péter Komjáth Mar 17 '17 at 15:40
• @PéterKomjáth: I think that $p_n$ just means the $n^\mathrm{th}$ prime in the sequence, not the $n^\mathrm{th}$ largest prime. – TonyK Mar 17 '17 at 15:50
• Also it is not clear that $p_n + p_{n-1} +m$ cannot assume an unbounded number of prime values, although in this case it should be provable that it leads to large multiples of 3 also. Gerhard "Life Is Easier Modulo Three" Paseman, 2017.03.17. – Gerhard Paseman Mar 17 '17 at 16:00
• Where does this question come from? – Igor Rivin Mar 21 '17 at 21:08
• I assume that the (alleged) result is the same if you take an arbitrary prime factor, not just the largest one... – Igor Rivin Mar 22 '17 at 22:41

If $m$, $p_1$ and $p_2$ are odd we will have $p_{n+1} \le (p_n + p_{n-1} + m)/3$ unless $p_n + p_{n-1} + m$ is prime. Heuristically one should expect prime values of $p_n + p_{n-1} + m$ to be very rare if the $p_n$ are large, so it should be unusual for $p_{n+1}$ to get very much larger than $\max(p_1, p_2, m)$. For example, I tried $m=1$ and odd primes $p_1, p_2 < 1000$. In each case, the sequence eventually became periodic; the largest prime that occurred was $55289$ (for $p_1 = 809$, $p_2 = 449$). However, I would find it surprising if it were possible to prove $p_n$ is always bounded.

• In line 3, I believe unusual for $p_n$'' should reference $p_{n+1}$. (I could not offer this as an edit since it did not require changing at least six characters---questionable requirement.) – Brian Hopkins Mar 21 '17 at 0:22
• Speaking of heuristics: if the sequence were not bounded, it would make quite a prime number generator. – Elizabeth S. Q. Goodman Mar 22 '17 at 8:25
• For the case $m=1$, see OEIS sequence A284170 which I recently contributed. – Robert Israel Mar 22 '17 at 20:34

Here's a thought too long for a comment, but prompted by Gerhard's comment and Robert's answer: It seems to me that when $m = 3$ (or $3k$), and $p_n, p_{n-1}$ are both not small, we cannot have the sequence "succeed"--i.e. hit a prime without having to divide--twice in a row.

That is, suppose $p_{n+1} = p_n + p_{n-1} + 3$; for all of these to be prime (and not 3) we must have $p_n \equiv p_{n-1}$ mod 3 and $p_{n+1}\equiv 2p_n$ mod 3. Then $p_{n+1} + p_n + 3\equiv 0$ mod 3, forcing $p_{n+2}\le(p_{n+1} + p_n+3)/3$.

Then it seems to me we can bound the sequence unless $p_n$ is very small very frequently. I am blanking on how to push this argument further but suggest it for anyone interested.

• More generally, the recurrence without gpf is a Fibonacci sequence shifted by m, which for most starting points means an eventual division by m . The fly in the ointment is m=1 and p_I=-1, by which I mean not the bounded sequence but modulo some large product of primes. Your mission, should you choose to accept it, is to show we can't climb the arithmetic progression this way using only primes. Gerhard "Do Not Climb Every Mountain" Paseman, 2017.03.22. – Gerhard Paseman Mar 22 '17 at 14:10
• An interesting and possibly illuminating example has $m=1$ and the first two primes being $5$ and $11$. This should indicate what we are up against. Gerhard "Often End Signature Preposition With" Paseman, 2017.03.22. – Gerhard Paseman Mar 22 '17 at 15:07