First observe that $p(a_n) \mid a_{n+1}$. Therefore $p(a_{n+1})\ge p(a_n)$. We should also note that $p(a_n)$ gets arbitrarily large as $n$ grows. Let $a_n=b(a_n)p(a_n)$. $p(a_{n+1}) \ge p(a_n)$ implies $$b(a_n)+1 \ge \frac{(b(a_n)+1)p(a_n)}{p(a_{n+1})}=b(a_{n+1}).$$ Therefore the sequence $\{b(a_n)\}$ can't "jump" over any integer. And one can show easily that this sequence is unbounded: Assume on the contrary that $\{b(a_n)\}$ is bounded. This means that for some large $N$ one will have $p(a_N)>\max\{b(a_n)\mid n\in \mathbb{N}\}$. But observe the following: Quote: Lemma. If for some $k$ $p(a_k)>b(a_k)$, then $p(a_{k+1})=p(a_k)$ and therefore $b(a_{k+1})=b(k)+1$. Proof. $a_{k+1}=(b(a_k)+1)p(a_k)$. $b(a_k)+1 \le p(a_k)$, therefore $p(a_k)$ is the greatest prime divisor of $a_{k+1}\square$ By this lemma, we will have $b(a_{N+1})=b(a_N)+1,b(a_{N+2})=b(a_{N+1})+1,\dots,b(a_{N+k})=b(a_{N+k-1})+1$, where for $k$ holds $b(a_{N+k})=p(a_{N+k})=p(a_N)>\max\{b(a_n)\mid n\in \mathbb{N}\}$. Therefore $\{b(a_n)\}$ is unbounded and hits every integer big enough. Therefore for some $N$ we will have $b_N$ be a prime. Now it is pretty straightforward work to show that either ${b(a_N)}^2$ or $p(a_N)^2$ will appear in the sequence. This completes the proof.

I am actually not sure if this solution is the same as the one above, but I'll post it anyways Define $b_n = p(a_n) - \frac{a_n}{p(a_n)}$. We prove two lemmas $(1)$ $\{b_n\}$ is eventually positive We will look at how the sequence changes. If $p(a_n) = p(a_{n+1})$ then the next term in sequence will simply increase by one If $p(a_{n+1})>p(a_n)$ we have $b_{n+1} = p(a_{n+1})-\frac{a_{n+1}}{p(a_{n+1})} > p(a_{n}) - \frac{a_{n}}{p(a_{n})}$ and therefore increased by at least one, which makes the sequence strictly increasing so it is eventually positive $(2)$ if for some $n$ we have $b_n>0$, then we will have a square If this is the case we can write $a_n=px$, where $1 \leq x < p$ then $a_{n+1} = (x+1)p$, but no prime greater then $p$ can divide $x+1 \leq p$. This tells us the sequence will eventually end up at $a_{something}=p^2$ which is what we wanted

niksic wrote: $(1)$ $\{b_n\}$ is eventually positive We will look at how the sequence changes. If $p(a_n) = p(a_{n+1})$ then the next term in sequence will simply increase by one I'm afraid this is incorrect, the next term will instead decrease by one.

A nice blend of discrete continuity and number theory. Congrats to the author for a beautiful problem! Call a positive integer $n$ radioactive if and only if it has a prime factor greater than $\sqrt{n}$. If any radioactive number $np$ where $p>n$ ever appears in the sequence, then the subsequent terms are $(n+1)p$, $(n+2)p$,... thus we will reach $p^2$ soon. Therefore, pretend that none radioactive number ever appears in the sequence. Define $p_n = p(a_n)$ and $b_n = \frac{a_n}{p_n}$. From above we get $b_n > p_n$. Note that $p_n\mid a_{n+1}$ $\implies p_n\leq p_{n+1}$. Thus the sequence $p_n$ is non-decreasing, and it clearly cannot be eventually constant. Thus sequences $\{p_n\}_{n>0}$ and $\{b_n\}_{n>0}$ are both unbounded. Furthermore, note that each increment of the sequence $\{b_n\}_{n>0}$ is at most one since $$b_{n+1}=\frac{a_{n+1}}{p_{n+1}} \leq \frac{a_{n+1}}{p_n} = b_n+1.$$Now, here is the punch line. By discrete continuity, this sequence must hit every prime larger than $b_1$. If $q$ is one such prime and $q=b_n$, then $a_n = qp_n$ is radioactive, contradiction!

MarkBcc168 wrote: If any radioactive number $np$ where $p>n$ ever appears in the sequence, then the subsequent terms are $(n+1)p$, $(n+2)p$,... thus we will reach $p^2$ soon. Why?

Mockhuynh2501 wrote: MarkBcc168 wrote: If any radioactive number $np$ where $p>n$ ever appears in the sequence, then the subsequent terms are $(n+1)p$, $(n+2)p$,... thus we will reach $p^2$ soon. Why? It's trivial, only see that a radioactive number $n $ can't have two prime factors greater than $\sqrt {n} $. We have that $a_{n+1}=a_n+p (a_n) $ then if appears a radioactive number $a_k=kq $ where $q>k $ see that: $$a_{k+1}=a_k+p (a_k)=kq+q=(k+1)q\implies a_r=rq $$ Since $k <q ~\exists M:k+M=q $ Then let $r=k+M $ and we are done.

ComiCabE wrote: First observe that $p(a_n) \mid a_{n+1}$. Therefore $p(a_{n+1})\ge p(a_n)$. We should also note that $p(a_n)$ gets arbitrarily large as $n$ grows. Let $a_n=b(a_n)p(a_n)$. It is obvious that if $p(a_{n+1})> p(a_n)$, then we have $b(a_n)+1 \ge \frac{(b(a_n)+1)p(a_n)}{p(a_{n+1})}=b(a_{n+1})$. And if $p(a_{n+1})=p(a_n)$, then one has $b(a_{n+1})=b(a_n)+1$. Therefore the sequence $\{b(a_n)\}$ can't "jump" over any integer. And one can show easily that this sequence is unbounded: Assume on the contrary that $\{b(a_n)\}$ is bounded. This means that for some large $N$ one will have $p(a_N)>\max\{b(a_n)\mid n\in \mathbb{N}\}$. This is an immediate contradiction since $b(a_{N+1})=b(a_{N})+1>\max\{b(a_n)\mid n\in \mathbb{N}\}$. Therefore $\{b(a_n)\}$ is unbounded and hits every integer big enough. Therefore for some $N$ we will have $b_N$ be a prime. Now it is pretty straightforward work to show that either ${b(a_N)}^2$ or $p(a_N)^2$ will appear in the sequence. This completes the proof. In the CMO I answered this and only got 3 marks out of 21. The marking scheme is so strange that you have to literally follow what the official solution says.

Practically no other solutions are allowed.

Thank you.

mofumofu wrote: Given any positive integer $c$, 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\ge 2$. Prove that there must exist at least one perfect square in sequence $\{a_n\}$. We have $$\frac{a_{n+1}}{p(a_{n+1})} =\frac{p(a_n)}{p(a_{n+1})}\left( \frac{a_n}{p(a_n)}+1\right) \leqslant \frac{a_n}{p(a_n)}+1.$$If $\{ a_n/p(a_n)\}$ is bounded, we get that eventually, $a_n=p\cdot c$ for some prime $p>c$. So, $a_{n+p-c}=p^2$. If $\{ a_n/p(a_n)\}$ is unbounded, we get that eventually $a_n/p(a_n)=q$ for some prime $q$. So, $a_{n+|q-p(a_n)|}=\left( \max \{ q,p(a_n)\}\right)^2$.

mofumofu wrote: Given any positive integer $c$, 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\ge 2$. Prove that there must exist at least one perfect square in sequence $\{a_n\}$. Isn’t this $n\ge 1$? Can anyone check the official papers?

.................

What a beautiful problem! Here is my solution: Assume to the contrary We call $p(a_n)=p_n$ for simplicity Claim 1:$p_{n+1}\geq p_{n}$ Proof:Since $p_n$ divides $a_{n+1}$ it will be $\leq p_{n+1}$ Claim 2:There cannot exist index n such that $$a_n\leq p^2$$. Proof:If $a_n=p^2$,a contradiction, otherwise assume $a_n=pk, 0\leq k\leq p-1$,Then for every $l:0\leq l\leq p-k,p_{n+l}=p$ and for $l=p-k,a_{n+p-k}=p^2$ again contradiction So $a_n>p_n^2$ for all naturals n. Consider the sequence $b_n=\frac {a_n}{p_n}-p_n$. Clearly every term of this sequence is positive Claim 3:The sequence $<b_n>$ is non increasing. Proof:$\frac {a_{n+1}}{p_{n+1}}=\frac {a_n+p_n}{p_{n+1}}\leq \frac {a_n}{p_n}+1\leq \frac {a_n}{p_n}+p_{n+1}-p_{n}$.This implies the claim. So this implies that there is some positive integer $k$ for all large n such that $a_n=p_n(p_n+k)$.Now we will be only talking about integers satisfying this property If $p_n=p_{n+1}\Rightarrow a_n=a_{n+1}$ a contradiction.So $p_{n+1}>p_{n}$ Also from this we get that $k$ is greater than any term of the strictly increasing sequence of positive integers $<p_i>$,a contradiction. So our assumption is overall contradictory and we are done.

For each $n$ let $p_n$ be the largest prime factor of $a_n$, and let $q_n=\frac{a_n}{p_n}$. Then $a_n=p_nq_n$ and $$a_{n+1}=p_n(q_n+1)$$The main claim is CLAIM 1. For each $n\in\mathbb N$ we have either (i) $q_{n+1}=q_n+1$ OR (ii) $q_{n+1}\leq q_n$ Proof. Obviously if $p(q_n+1)<p_n$ then $p_{n+1}=p_n$, hence $q_{n+1}=q_n+1$. Now suppose $p(q_n+1)>p_n$, then $p_{n+1}=p(q_n+1)$. Now we have $$q_{n+1}=\frac{p_n(q_n+1)}{p_{n+1}}$$Hence it suffices to show $$p_n\leq q_n(p_{n+1}-p_n)$$which is true since $p_{n+1}-p_n\geq 1$ and $p_n\leq p(q_n+1)-1\leq q_n+1-1=q_n$ $\blacksquare$ Now suppose that there is no perfect square in the sequence. Notice that the sequence $p_n$ is nondecreasing. Pick a sufficiently large $k$. Let $q$ be the smallest prime greater than $q_k$. CLAIM 2. $q_n\leq q$ for all $n>k$ Proof. Firstly notice that if $p_k>q_k$ then we must have $q_{k+1}=q_k+1$, so eventually $q_{m}=p_k$ and we are done. Hence assume $q_k>p_k$ Suppose on the contrary that $q_n>q$ for some $n$, then from CLAIM 1 we must have $q_m=q$ for some $m$, hence $p_{m+1}=q$ and $q_{m+1}<q$. Now if there exists some $m_1>m$ so that $q_{m_1}=q$ then $a_{m_1}=q^2$, contradiction. By CLAIM 1 we have $q_n\leq q$ for all $n>m$. This proves the CLAIM. $\blacksquare$ Now $q_n$ is bounded above, so $p_n$ must be unbounded (otherwise (i) of CLAIM 1 must happen eventually and $q_n$ will be unbounded), but this is impossible since $p_n<p(q_n)<q$. This completes the proof.

I think I have a pretty elegant solution.

We consider the iterates where the largest prime factor jumps, i.e. $\{ n_k \}$ the iterates such that $p(a_{n_k}) > p(a_{n_k-1})$. To simplify the notation, we denote $p_k = p(a_{n_k})$ and we write $a_{n_k} = b_{k} p_k p_{k-1}$. Claim: $b_k$ is non-increasing, i.e. $b_{k} \ge b_{k+1}$.

Finally we show that $b_k$ will be $1$.

Remark that, by definition, $p(a_1) \le p(a_2)\le \cdots$. Write the sequence up to the point at which $p(a_k) < p(a_{k+1})$, so the sequence is $a_1=p_1d_1, a_2 = p_1(d_1+1), \cdots, p_1e_1 = a_{k+1}$. Then there exists some $p_2 \mid e_1$ with $p_1<p_2$. Let $d_2 = p_1 \cdot \frac{e_1}{p_2}$. Define future $p_i,d_i,e_i$ this way. Observe that $e_i \ge p_i$, hence the $e_i$ are unbounded because the sequence of $p_i$ must be infinite and increasing. Let $p$ be the minimal prime larger than $d_1$. There must exist a minimal $e_i\ge p$. If we have $p = e_i$, we are done: after $p_ip$, the following terms are $(p_i+1)p,(p_i+2)p,\cdots,p^2$. So suppose $e_i>p$. As $d_i < e_{i-1} < p$, we see that $p_ip$ is equal to some $a_n$. As $e_i>p$, this means that $p_i > p$. Hence the following terms are $p_i(p+1),p_i(p+2),\cdots,p_i^2$ and we are done.

niksic wrote: I am actually not sure if this solution is the same as the one above, but I'll post it anyways Define $b_n = p(a_n) - \frac{a_n}{p(a_n)}$. We prove two lemmas $(1)$ $\{b_n\}$ is eventually positive We will look at how the sequence changes. If $p(a_n) = p(a_{n+1})$ then the next term in sequence will simply increase by one If $p(a_{n+1})>p(a_n)$ we have $b_{n+1} = p(a_{n+1})-\frac{a_{n+1}}{p(a_{n+1})} > p(a_{n}) - \frac{a_{n}}{p(a_{n})}$ and therefore increased by at least one, which makes the sequence strictly increasing so it is eventually positive Seriously... what the hell are you talking about?

Let $b_n = \frac{a_n}{p(a_n)}$. Then, since $p(a_{n+1})\ge p(a_n)$, and \[b_{n+1}=(b_n+1)\frac{p(a_n)}{p(a_{n+1})},\]either $p(a_{n+1})= p(a_n)$ and $b_n$ increases by $1$, or $p(a_{n+1})> p(a_n)$ \[\implies b_{n+1}<b_n+1\]\[\implies b_{n+1}\le b_n.\]We claim $b_n$ is unbounded. Suppose it is bounded above by $M$. Note that \[p(a_{n+1})\mid (b_n+1)p(a_n)\]So it follows by induction that $p(a_n)\le \max(M+1,p(a_1))$. So $b_n$ and $p(a_n)$ are bounded, therefore $a_n$ is bounded, which is false. Now, let $p$ be a prime greater than $b_1$ and let $k$ be minimal such that $b_k\ge p$. \[\implies b_{k-1}\le p-1\]\[\implies 1\ge b_k-b_{k-1} \ge p - (p-1) = 1\]therefore $b_k = p$. It now suffices to solve the problem for $a_1 = rs$, with $r<s$ primes. But now it is clear that the sequence will be \[rs,(r+1)s,\dots,s.s\]so we are done.

Here is my solution: https://calimath.org/pdf/CNO2019-5.pdf And I uploaded the solution with motivation to: https://youtu.be/agI_e7t3yag

For the convenience, let $p_n = p(a_n)$ and $b_n = \frac{a_n}{p_n}$. Then we have $a_{n+1} = a_n + p_n$ and $a_n = p_nb_n$ for all $n \ge 1$. Note that $p_n \mid a_{n+1}$. thus $p_{n+1} \ge p_n$ and thus the sequence $(p_n)_{n\ge 1}$ is unbounded. Consider the following claim: Claim: There exists $n$ such that $a_n \le p_n^2$. Proof. Assume the contrary, $a_n > p_n^2$ for all $n \ge 1$. Then we get $b_n > p_n$ for all $n \ge 1$. Note that $b_{n+1} = \frac{a_{n+1}}{p_{n+1}} = \frac{a_n + p_n}{p_{n+1}} \le \frac{a_n + p_n}{p_n} = b_n + 1$, so the sequence $(b_n)_{n \ge 1}$ increases at most 1. Since $b_n > p_n$, thus the sequence $(b_n)_{n \ge 1}$ is unbounded. Combined with the fact that the sequence $(b_n)_{n \ge 1}$ increases at most 1, we see that the sequence $(b_n)_{n \ge 1}$ contains all sufficiently large positive integers. Let $q$ be a large enough prime. Then there exists $n$ such that $b_n = q$. Since $b_n > p_n$, so $p_n = p(a_n) = p(qp_n) = q$, a contradiction. $\blacksquare$ If $a_n \le p_n^2$ for some $n$, then it's not hard to see that the sequence eventually hits $p_n^2$, as needed. $\blacksquare$

This kind of NT looks like someone truly cooked ngl. First we let $a_n=r_n \cdot p(a_n)$ for all positive integers $n$ and note that since $p(a_n) \mid a_{n+1}$ we have $p(a_{n+1}) \ge p(a_n)$, now note that we have: $$r_{n+1}=\frac{(r_n+1)p(a_n)}{p(a_{n+1})} \le r_n+1$$Which means that in its range the sequence $r_n$ cannot skip any integer, now suppose FTSOC that $r_n$ was bounded, then back to looking at the $p(a_n)$ we note that we cannot have $p(a_{n+1})=p(a_n)$ happening for some $n>N$ since then at some point we would reach some $a_i=(k+\ell)p(a_n)$ for which $k+\ell$ has a prime divisor greater than $p(a_n)$ (since of course $\ell$ ranges from $1$ to some constant it cover all integers below it), therefore $p(a_{n+1})=p(a_n)$ is slowly going to increase and can become arbitrarily large as we wanted. Now we assumed that there exists $M>r_n$ for all positive integers $n$, so we choose $p(a_i)>M$ (in fact $p(a_{\ell})>M$ is now true for all $\ell \ge i$), now remember how $p(a_i) \mid a_{i+1}$ then $p(a_i) \mid p(a_{i+1})r_{i+1}$, note that if $p(a_{i+1})>p(a_i)$ then $p(a_i) \mid r_{i+1}$ but by size reasons this can't happen so $p(a_i)=p(a_{i+1})$, but now if we repeat this process for $i+1$ we get $p(a_{i+1})=p(a_{i+2})$ and so on but this means that $p(a_n)$ remains constant at some point and thus bounded, which we have seen earlier that such thing cannot happen contradicting $r_n$ bounded, therefore the sequence $r_n$ is unbounded above. Since we have $r_n$ unbounded as well it in fact is now surjective in $\mathbb Z_{>0}$, we will finally use the fact that $p(a_n)$ is the "biggest" prime divisor of $a_n$, now take all indexes $i$ such that $r_i$ is prime, then since $a_i=r_i \cdot p(a_i)$ we must have $p(a_i) \ge r_i$, if $r_i=p(a_i)$ then we get $a_i$ is a perfect square, if $p(a_i)>r_i$ we have that $a_{i+1}=(r_i+1)p(a_i)$, now if $p(a_{i+1}) \ne p(a_i)$ then $p(a_{i+1}) \mid r_i+1$ but then $p(a_{i+1}) \le r_i+1 \le p(a_i)$ so $p(a_{i+1})=p(a_i)$ contradiction!, so $p(a_{i+1})=p(a_i)$ and now $r_{i+1}=r_i+1$ and now $a_{i+2}=(r_i+2)p(a_i)$, if we continue with the same logic you will realice that as long as $r_i+k \le p(a_i)$ we have $p(a_i)$ fixed in the next $k-1$ terms, this of course means that when we reach some $r_i+\ell=p(a_i)$ we would get $a_{i+\ell}=p(a_i)^2$ thus having a perfect square in the sequence and thus we are done .