Let $p_1,p_2,...$ be a sequence of natural numbers. $p_1$ and $p_2$ are prime and $p_n$ for $n\ge 3$ is the largest prime divisor of $p_{n-1}+p_{n-2}+2014$. Prove that $(p_n)$ is bounded.

  • $\begingroup$ Wow! Starting from $p_1=2=p_2-1$ it becomes eventually periodic. In general ???? I wan't to see how to approach such a proof. $\endgroup$ – Pp.. Jan 23 '15 at 14:58
  • $\begingroup$ @Pp..: Of course "eventually periodic" and "bounded" are identical for this sequence. $\endgroup$ – Charles Jan 23 '15 at 15:02
  • $\begingroup$ @Charles What is the "Of course"? Just need to say something, no matter what? $\endgroup$ – Pp.. Jan 23 '15 at 15:50

Let $P_n = \max(p_1,\ldots,p_n)$. We show that $p_{n+1} \leq P_n + 2016$.

If $p_n=2$ or $p_{n-1}=2$ this follows from $p_{n+1} \leq p_n + p_{n-1} + 2014$. If $p_n$ and $p_{n-1}$ are both odd, then $p_n + p_{n-1} + 2014$ is even so we have $p_{n+1} \leq \frac12(p_n + p_{n-1} + 2014) < P_n + 2016$ (note that this is also true when $p_n + p_{n-1} + 2014$ happens to be a power of $2$).

So to reach a large prime $Q$, we first have to reach a prime in the interval $[Q, Q-2016]$. However, there are arbitrarily long stretches of arbitrarily large composite numbers (for instance, $N!+2$, $N!+3$, ..., $N!+N$ gives $N-1$ consecutive composite numbers) so our sequence of prime numbers will be bounded.


This is a partial solution, for sequences that don't have $2$ in them.
If $2$ does not appear, then $p_n$ are all odd. If $p_n$ is also unbounded, then to get beyond 100000, there must be several terms in a row with $p_{n+2}=(p_n+p_{n+1}+2014)/2$, $p_{n+3}=(p_{n+1}+p_{n+2}+2014)/2$. The remainders when you divide by $5$ must follow one of the following sequences $$\{1,1,3,4,3,3,0\}, \{1,2,1,1\}, \{1,4,2,0\}, \{2,3,2,2,4,0\}, \{3,1,4\}, \{3,3,0\}, \{4,4,1,2\}$$
so one of the $p_n$ is a multiple of $5$. This contradicts $p_n$ being prime and greater than $90000$. So we can't have ten odd numbers in a row without some $p_{n+2}\leq(p_n+p_{n+1}+2014)/4$.

If $2$ does appear, then it must reappear infinitely often, otherwise the first half of this proof applies. Let $q_m=p_{i_m}$ be the sequence of $p_n$ immediately before each $2$. Suppose $q_{k+1}>q_k$ and $q_k$ large enough. We can't afford to divide even numbers by more than 2, or odd numbers by more than 1. This forces the following sequence: $$q_m,2,q_m+2016,q_m+4032,q_m+4031$$
But $q_m+4031$ is even, and we have a contradiction, so $2$ must reappear instead of $q_m+4031$. So the only way that $q_{m+1}>q_m$, if $q_m$ is large enough, is if $q_{m+1}=q_m+4032$.
If $q_{m+1}<q_m$, then there must have been a reduction by a factor $2$ at some point, with at most two increases by $2016$ and ten increases by $2014/2$. To ensure that $q_m$ increase unboundedly, we need several increases of $q_m$ with no reduction in between. But then we will have a sequence $q_m+4032k, (k=1,2,3,4,5)$, one of which is a multiple of $5$, and we have a contradiction.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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