A sequence of primes $p_1, p_2, \dots$ is given by two initial primes $p_1$ and $p_2$, and $p_{n+2}$ being the greatest prime divisor of $p_n + p_{n+1} + 2018$ for all $n \ge 1$. Prove that the sequence only contains finitely many primes for all possible values of $p_1$ and $p_2$.
Problem
Source: Nordic Mathematical Contest 2018 Problem 2
Tags: number theory
10.04.2018 20:05
Choose a positive integer $n>2018$ and $n>p_1,p_2$.Consider the sequence $a_i =n! +i+1$.Then obviously,$a_1,a_2, \dots a_{n-1}$ are $n$ consecutive composite numbers. Now,assume that the sequence $p_i$ has infinitely many primes.Consider the smallest $k$ such that $p_k$ is bigger than $a_{n-1}$.Since $a_1, \dots a_{n-1}$ are composite,then $p_{k-1},p_{k-2}<a_1$.We have two cases: 1-both $p_{k-1},p_{k-2}$ are odd. so $p_{k-1}+p_{k-2}+2018$ is even and divisible by $p_k$,so we should have $p_{k-1}+p_{k-2}+2018 \geq 2 p_k$ which is obviously wrong. 2-one of $p_{k-1},p_{k-2}$ is 2. so we should have $2+p_{k-1}+2018 \geq p_k$ which is again wrong for big $n$(bigger than 2020). Finally,both cases lead to contradiction and we are done.
18.07.2020 14:51
Let $f(n)$ denote the largest prime factor of $n$ Let $K = max(p_1, p_2, 1010)$, so $K \geq 1010$. So, $$K! + 2, K! + 3, \cdots K! + 1010$$are 1009 consecutive composite numbers. Let $p_t$ be the first prime in the sequence that is greater than $K! + 1$ (i.e. we assume ftsoc that such a $t$ exists, as it must exist if there are infinitely many primes in the sequence). Clearly $t > 2$ by our choice of $K$. So, $p_{t-1}, p_{t-2} \leq K! + 1$. Hence, $p_{t-1} + p_{t-2} + 2018 = 2 \left( \frac{p_{t-1} + p_{t-2}}{2} + 1009 \right)$ (if either $p_{t-1}$ or $p_{t-2}$ were 2, then the result is the same). So, $p_t = f \left(2 \left( \frac{p_{t-1} + p_{t-2}}{2} + 1009 \right) \right) = f \left( \frac{p_{t-1} + p_{t-2}}{2} + 1009 \right) \leq K! + 1$ as $ \frac{p_{t-1} + p_{t-2}}{2} \leq K! + 1$. Now we have $p_t \leq K! + 1$, contradiction. Hence, there are only finitely many primes in our sequence.
21.05.2021 20:02
green_leaf wrote: Let $f(n)$ denote the largest prime factor of $n$ Let $K = max(p_1, p_2, 1010)$, so $K \geq 1010$. So, $$K! + 2, K! + 3, \cdots K! + 1010$$are 1009 consecutive composite numbers. Let $p_t$ be the first prime in the sequence that is greater than $K! + 1$ (i.e. we assume ftsoc that such a $t$ exists, as it must exist if there are infinitely many primes in the sequence). Clearly $t > 2$ by our choice of $K$. So, $p_{t-1}, p_{t-2} \leq K! + 1$. Hence, $p_{t-1} + p_{t-2} + 2018 = 2 \left( \frac{p_{t-1} + p_{t-2}}{2} + 1009 \right)$ (if either $p_{t-1}$ or $p_{t-2}$ were 2, then the result is the same). So, $p_t = f \left(2 \left( \frac{p_{t-1} + p_{t-2}}{2} + 1009 \right) \right) = f \left( \frac{p_{t-1} + p_{t-2}}{2} + 1009 \right) \leq K! + 1$ as $ \frac{p_{t-1} + p_{t-2}}{2} \leq K! + 1$. Now we have $p_t \leq K! + 1$, contradiction. Hence, there are only finitely many primes in our sequence. WOWOWOW How did u think of such an elegant and beautiful construction.
01.01.2022 09:43
Polish Mo 2001
23.01.2023 06:02
lazizbek42 wrote: Polish Mo 2001 thanks!
21.08.2023 15:27
green_leaf wrote: Let $f(n)$ denote the largest prime factor of $n$ Let $K = max(p_1, p_2, 1010)$, so $K \geq 1010$. So, $$K! + 2, K! + 3, \cdots K! + 1010$$are 1009 consecutive composite numbers. Let $p_t$ be the first prime in the sequence that is greater than $K! + 1$ (i.e. we assume ftsoc that such a $t$ exists, as it must exist if there are infinitely many primes in the sequence). Clearly $t > 2$ by our choice of $K$. So, $p_{t-1}, p_{t-2} \leq K! + 1$. Hence, $p_{t-1} + p_{t-2} + 2018 = 2 \left( \frac{p_{t-1} + p_{t-2}}{2} + 1009 \right)$ (if either $p_{t-1}$ or $p_{t-2}$ were 2, then the result is the same). So, $p_t = f \left(2 \left( \frac{p_{t-1} + p_{t-2}}{2} + 1009 \right) \right) = f \left( \frac{p_{t-1} + p_{t-2}}{2} + 1009 \right) \leq K! + 1$ as $ \frac{p_{t-1} + p_{t-2}}{2} \leq K! + 1$. Now we have $p_t \leq K! + 1$, contradiction. Hence, there are only finitely many primes in our sequence. That's really impressive.