My Personal Favourite NT Problem from CNO 2019, P5

投稿日:2023/5/16最終更新日:2025/5/18

Find the square in the sequence

Problem Statement

Given any positive integer $c > 1,$ denote $p(c)$ as the largest prime factor of $c.$ A sequence $\{a_n\}$ of positive integers satisfies $a_1 > 1$ and $a_{n+1} = a_n + p(a_n)$ for all $n \geq 1.$ Prove that there must exist at least one perfect square in the sequence $\{a_n\}.$

Solution

We have to show two examples of sequence

$$\begin{aligned} a_1 &= 7 \mapsto 14 \mapsto 21 \mapsto 28 \mapsto 35 \mapsto 42 \mapsto 49 \\ a_1 &= 12 \mapsto 15 \mapsto 20 \mapsto 25 \end{aligned}$$

We observe, that if $p(a_n)$ is very large, then it will stay constant for many iterations until we reach the value $p(a_n)^2.$ This observation can be formalized in claim.

Claim 1.

If $p(a_n)^2 \geq a_n,$ then

$$\forall n \leq k \leq m : p(a_k) = p(a_n),$$

where m is maximal such that $a_m \leq p(a_n)^2.$

Moreover, $a_m = p(a_n)^2$

Proof

We will prove the first part of the claim inductively. The base case is clear by $f(k) = f(k).$ By our induction hypothesis, we have for any $n \leq k < m$

$$p(a_n) \mid a_k + p(a_n) = a_k + p(a_k) = a_{k + 1}.$$

Because $a_{k+1} \leq p(a_n)^2,$ no longer prime divisor may divide

$$\frac{a_{k+1}}{p(a_n)} \leq a_n$$

Thus, $p(a_{k + 1}) = p(a_n).$ In the second part, we see that

$$a_m \leq p(a_n)^2 < a_{m + 1} = a_m + p(a_n),$$

or

$$p(a_n)^2 - p(a_n) < a_m \leq p(a_n)^2,$$

which implies with $p(a_n) \mid a_m,$ that

$$a_m = p(a_n)^2. \quad\quad\quad\quad\quad \blacksquare$$

Now, we compare the sequences $\{\frac{a_n}{p(a_n)}\}$ and $\{p(a_n) \}.$ When

$$\frac{a_n}{p(a_n)} \leq p(a_n),$$

we are immediately done by 1.

We have,

$$\frac{a{n+1}}{p(a_{n+1})} \leq \frac{a_{n + 1}}{p(a_n)} = \frac{a_n + p(a_n)}{p(a_n)} = \frac{a_n}{p(a_n)} + 1.$$

So if $\{\frac{a_n}{p(a_n)} \}$ grows without bound, it hits very integer $\leq \frac{a_1}{p(a_1)}.$ At least one of those is a prime $q$ because there are indefinitely many primes. The definition of $p$ implies

$$p(a_n) \geq q = \frac{a_n}{p(a_n)}$$