This question comes from a maths contest (infer no calculators or other electronic calculating aids) for 14-16 year olds (infer no use of complicated theorems, but those accessible to high-school students).

Consider the sequence $\;a_1,a_2,a_3,a_4,... \; $ such that $\;a_1=2 \;$ and for every positive integer $n$,

$a_{n+1}=a_n+p_n \;,\;$ where $\;p_n\;$ is the largest prime factor of $\;a_n\;$ The first few terms of the sequence are $\;2,4,6,9,12,15,20.\;$ What is the largest value of $\;n\;$ such that $\;a_n\;$ is a four-digit number ?

The road so far:

Continuing the sequence:

$\underbrace{2,4,\color{red}{6}}_{\text{add}\; 2},\underbrace{9,12,\color{red}{15}}_{\text{add}\; 3},\underbrace{20,25,30,\color{red}{35}}_{\text{add}\; 5},\underbrace{42,49,56,63,70,\color{red}{77}}_{\text{add}\; 7},\underbrace{88,99,110,121,132,\color{red}{143}}_{\text{add}\; 11},\underbrace{156,\ldots}_{\text{add}\; 13} $

Inferring from the above:

  1. The numbers to be added to get the next number in the sequence are the prime numbers: $\qquad \qquad \qquad \qquad \qquad2,3,5,7,11,13,17,\ldots$
  2. The numbers in red are the product of two successive prime numbers:$$\begin{align} 2 &\times 3=6\\ 3 &\times 5=15\\ 5 &\times 7=35\\ &\vdots\\ \text{thence}&\\ &\vdots\\ 91 &\times 97=8827\\ 97 &\times 101=\color{blue}{9797} \longleftarrow \\ 101 &\times 103=10403\\ \end{align}$$ and $9797$ is the largest $4$-digit number in the sequence.
  3. $$ \begin{array}{c|ccccc} n & 3 & 6 & 10 &16& 22 \\ \hline \hline \text{current}\; n-\text{previous}\; n & - &\color{DarkOrange}{ 3 }& \color{DarkOrange}{4} &\color{DarkOrange}{6}& \color{DarkOrange}{6}\\ \hline a_n & 6&15&35&77&143 \\ \hline \text{highest prime factor of}\; a_n & 3&5&7&11&13\\ \text{lowest prime factor of}\; a_{n-1} & -&2&3&5&7&\\ \text{difference} & -&\color{DarkOrange}{ 3 }& \color{DarkOrange}{4} &\color{DarkOrange}{6}& \color{DarkOrange}{6}\\ \end{array}$$

My problem is how do I now correlate the numbers in $\;\color{DarkOrange}{\text{orange}}\;$ to find the $\;n\;$ which results in $\;a_n=9797\;$.


Just observe that to get a product of the form $p_np_{n+1}$ from $p_np_{n-1}$ you have to wait for $p_{n+1}-p_{n-1}$ terms. So the required $n$ is, to get to a prime product $p_kp_{k+1}$ is $\sum_{j=1}^k(p_{j+1}-p_{j-1})+1=p_{k+1}+p_k-2$ where I have defined $p_0=1$. So for your case the answer is $103+101-2=202$.


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.