10
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ Mar 17, 2017 at 15:40
  • 2
    $\begingroup$ @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. $\endgroup$
    – TonyK
    Mar 17, 2017 at 15:50
  • $\begingroup$ 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. $\endgroup$ Mar 17, 2017 at 16:00
  • 2
    $\begingroup$ Where does this question come from? $\endgroup$
    – Igor Rivin
    Mar 21, 2017 at 21:08
  • $\begingroup$ I assume that the (alleged) result is the same if you take an arbitrary prime factor, not just the largest one... $\endgroup$
    – Igor Rivin
    Mar 22, 2017 at 22:41

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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.) $\endgroup$ Mar 21, 2017 at 0:22
  • $\begingroup$ Speaking of heuristics: if the sequence were not bounded, it would make quite a prime number generator. $\endgroup$ Mar 22, 2017 at 8:25
  • $\begingroup$ For the case $m=1$, see OEIS sequence A284170 which I recently contributed. $\endgroup$ Mar 22, 2017 at 20:34
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Mar 22, 2017 at 14:10
  • $\begingroup$ 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. $\endgroup$ Mar 22, 2017 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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