A positive integer $c$ is given. The sequence $\{p_{k}\}$ is constructed by the following rule: $p_{1}$ is arbitrary prime and for $k\geq 1$ the number $p_{k+1}$ is any prime divisor of $p_{k}+c$ not present among the numbers $p_{1}$, $p_{2}$, $\dots$, $p_{k}$. Prove that the sequence $\{p_{k}\}$ cannot be infinite. Proposed by A. Golovanov
Problem
Source: Tuymaada 2002
Tags: limit, number theory proposed, number theory
07.12.2006 15:52
Maybe not hard,This is my solution: $p_{k+1}\leq p_{k}+c$, but $\lim_{x\to \infty}\frac{\pi (x)}{x}=0$ contraduction. And there is another proof without the non-elemetry result: $p_{k+1}\leq p_{k}+c$,suppose that $p_{k+1}=\frac{p_{k}+c}{d_{k}}$ if there exist $l$such that $d_{l},d_{l+1},....d_{l+c+2}=1$ then $p_{i+1}=p_{i}+c ,\forall i=l,\dots,l+c+2$ but there must exist $i\in[l+1,l+c+1]$ such that $p_{i}=p_{l}+(l-i)c$is divisible by $c+1$ then $p_{i}$is not a prime ,contraduction. so there do not exist $c+2$ consecutive $p_{k}$ such that $p_{k+1}=p_{k}+c$ so $p_{k+c+2}\leq \frac{1}{2}p_{k}+c(c+1)+\frac{c}{2}$ thus $p_{k+m}\leq \frac{1}{2}p_{k}+A$ where $m,A$be constant.then$p_{k+lm}-2A \leq \frac{1}{2^{l}}(p_{k}-2A)$ when $l-\to \infty$ $p_{k+lm}\leq 0$ contraduction.
07.12.2006 19:44
Yes, that isn't hard (in contrary to some other Tuymaada's problems)
08.12.2006 11:05
Can you post some other Tuymaada's problems?I haven't heard such a contest before...
08.12.2006 16:50
http://www.guas.info/competit/tuyme.htm - here you can find problems from Tuymaada 2000-2006