Note that the same sequence (but with given only $a_1>1$) appears in China MO 2020/5. @below, my solution is also with Bertrand's postulate, I will post it here for the sake of having a complete solution. There we go: we have that the terms with greatest prime factor $p_i$ (which is the $i-th$ prime) are $p_i.k$ for all $k=p_{i-1}, p_{i-1}+1,...,p_{i+1}$ (so the sequence consists of such blocks). If we have a square with greatest prime factor $p_i$, then $p_i | k$, which we claim is possible only for $k=p_i$. Indeed, otherwise $p_{i+1}-p_{i-1} \geq 2 p_i$ which readily gives contradiction by the fact that if $g_i$ is the gap between the $i-th$ and $(i+1)-th$ prime, then $p_i>g_i$ - due to Bertrand's postulate (we now have $g_i+g_{i-1}<p_i+p_{i-1}<2p_i$). Btw this was an EGMO TST P4 and I was surprised they gave a problem using Bertrand's postulate for a 1/4 problem.

Spoiler remark

We claim the answer is $m$ prime. Let $p_1,p_2,\ldots$ be a list of prime. Observe that $a_2=4$. We claim the sequence is made up of blocks of the form: $$ \underbrace{p_i^2,p_i\left(p_i+1\right),p_i\left(p_i+2\right),\ldots,p_ip_{i+1}}_{\text{(i)}},\underbrace{p_{i+1}\left(p_{i}+1\right),p_{i+1}\left(p_i+2\right), \ldots,p_{i+1}^2}_{\text{(ii)}} $$(i) follows from $\ell{\left(p_i k\right)}=p_i$ when $k<p_{i+1}$ and (ii) from $\ell{\left(p_{i+1} k\right)}=p_{i+1}$ when $k<p_{i+1}$. Hence, excluding $a_1$, the terms of the sequence are exactly those of the form $p_{i}k$ where $p_{i-1} \leq k \leq p_{i+1}$. To be a square, we must have $p_{i} \vert k$. By Betrand, $2p_{i}>p_{i+1}$ so the only possibility is $k=p_{i}$ which gives the answers we claimed.

Lukaluce wrote: Denote by $l(n)$ the largest prime divisor of $n$. Let $a_{n+1} = a_n + l(a_n)$ be a recursively defined sequence of integers with $a_1 = 2$. Determine all natural numbers $m$ such that there exists some $i \in \mathbb{N}$ with $a_i = m^2$. Proposed by Nikola Velov, Macedonia Not intending to be offensive or something, but Macedonia is, to my knowledge, a region and not a country. Did you intend to write North Macedonia?

Click to reveal hidden text

We will work by induction. We claim that for every prime $p$ there exists such $i$. For $p=2$ we have $i=1$. Let $a_{k}=p^2$ and $q$ be the smallest prime greater than $p$. Set $q=p+x$. Then $a_{k}=p^2, a_{k+1}=p(p+1), \ldots, a_{k+x}=p(p+x)=pq$ Until now $p$ has been the largest divisor because $p+1, \ldots, p+x-1 \leq q$. After $a_{k+x}$ the largest prime divisor is $q$ so we have: $a_{k+x+1}=q(p+1), a_{k+x+2}=q(p+2), \ldots, a_{k+2x}=q(p+x)=q^2$ The claim is now proved. The only thing left to prove is that no $a_{k+1}, \ldots, a_{k+2x-1}$ is not a perfect square. But this is obvious applying Bertrand's postulate. Therefore the only positive integers that there exists some $i \in \mathbb{N}$ with $a_i = m^2$ are prime numbers.

$a_1=2,a_2=4,a_3=6,a_4=9,a_5=12,a_6=15,a_7=20,a_8=25$ For writing purposes, let $p_n=l(a_n)$. Claim 1. If such $m$ exists, it must be a prime. Let $t=\frac{a_n}{p_n}$. $a_n+p_n= p_n(t+1)=a_{n+1}$ We will analyze when $a_{n+1}$ is a perfect square.Divide into 3 cases. Case 1. $p_n=a_n$. Then $2a_n$ is a perfect square, meaning $a_n=2^{2k-1}$ obviously, it is impossible for bigger $k$. Hence $k=1$ is the only solution (which is a prime) Case 2. $p_n=t+1$ We have $a_n=t^2+t$. Then $a_n+p_n=t^2+2t+1=(t+1)^2=a_{n=1}$ By definition, $a_n=p(p-1)$ where $p$ is a prime. then $a_{n=1}= p^2 \Rightarrow$ when $m$ is a prime. Case 3. $ (p_n)^{2k+1}=t+1$ Then we have $a_n= (p_n)^{2k+1} \cdot ((p_n)^{2k+1}-1)$. Let $p_n=p$. We have: $$a_{n+1}= p^{2k+1}(p^{2k+1}-1) + p= p(p^{2k}(p-1)(1+p+p^2+...+p^{2k})+1)$$Obviously, this expression can't be a perfect square since $p|a_{n+1},p^2 \nmid a_{n+1}$ Hence, we have proven that, if such $m$ exists, it must be a prime number. $\square$ Claim 2. all primes works for $m$. From case 2. we know that if our claim 2. is true, $a_{i-1}= (m-1)^2+(m-1)=m^2-m=m(m-1)$. Choose $a_{i-2}= m^2-2m=m(m-2)$. Choose $a_{i-3}= m(m-3)$ repeat until $(m-k)$ becomes a prime. After, we have $a_{i-k}= m(m-k)$ where both $m,(m-k)$ are prime.( the same sequence from above solutions).Then repeat the prosses by $a_{i-k-r}=(m-r)(m-k)$ where $(m-r),(m-k)$ are prime.Obviously, this sequence works. and since primes are getting smaller and smaller, we will left with $a_j=2$ for some $j$. We will just go in reverse direction with letting $j=1$. By our sequence, we will not miss any primes $m$.Hence we are done $\blacksquare$

Denote $p_{k}$ and $p_{k+1}$ as two consecutive primes where $p_{k+1}>p_{k}$. Claim 1. In the equation $a_{i}=m^{2}$ $m$ cannot be composite. Proof Let $a_{n}=p_{k}^{2}, a_{n+x}=p_{k+1}^{2}$. Then we have $a_{n+1}=p_{k}(p_{k}+1), a_{n+2}=p_{k}(p_{k}+2), \dots , a_{n+y}=p_{k}p_{k+1}, \dots , a_{n+x-1}=p_{k+1}(p_{k+1}-1), a_{n+x}=p_{k+1}^2$ According to Bertrand's postulate there is no integer between $p_{k}+1$ and $p_{k+1}-1$ that is divisible by $p_{k}$. So, from $a_{n+1},a_{n+2}, \dots , a_{n+y}$ there is no whole square that is divisible by $p_{k}$. Similiarly, there is no whole square from the sequence $a_{n+y+1},a_{n+y+2}, \dots , a_{n+x}$ that is divisible by $p_{k+1}$. Thus there is no whole square of composite number between $p_{k}^2$ and $p_{k+1}^2$. Claim 2. $m$ can be any prime. Proof Since there is no composite whole square between $p_{k}^2$ and $p_{k+1}^2$(from the sequence $a_{i}$) and $p_{k}, p_{k+1}$ are consecutive primes, $m$ can be any prime number. So the answer is $m$ can be any prime.

VicKmath7 wrote: Note that the same sequence (but with given only $a_1>1$) appears in China MO 2020/5. @below, my solution is also with Bertrand's postulate, I will post it here for the sake of having a complete solution. There we go: we have that the terms with greatest prime factor $p_i$ (which is the $i-th$ prime) are $p_i.k$ for all $k=p_{i-1}, p_{i-1}+1,...,p_{i+1}$ (so the sequence consists of such blocks). If we have a square with greatest prime factor $p_i$, then $p_i | k$, which we claim is possible only for $k=p_i$. Indeed, otherwise $p_{i+1}-p_{i-1} \geq 2 p_i$ which readily gives contradiction by the fact that if $g_i$ is the gap between the $i-th$ and $(i+1)-th$ prime, then $p_i>g_i$ - due to Bertrand's postulate (we now have $g_i+g_{i-1}<p_i+p_{i-1}<2p_i$). Btw this was an EGMO TST P4 and I was surprised they gave a problem using Bertrand's postulate for a 1/4 problem. Assassino9931 wrote:

Spoiler remark

I found an approach using induction , even though it is quite messy . Let $p_i$ be the $i$'th prime number. All such $m$ is $p_i$ for every $i \in \mathbb{N}$, in particular $p_1=2, p_2=3,\cdots$. First of all, we claim that for every $i \in \mathbb{N}$ there exist some $j \in \mathbb{N}$ such that $a_j={p_i}^2$. For the first few sequence we have, $$a_1=2, a_2=4, a_3= 6,\cdots$$. The claim is true for $i=1$ since $a_2=4=p_1^2$. Assume the claim is true for some integer $i \in \mathbb{N}$. Let $j \in \mathbb{N}$ be the number such that $a_j={p_i}^2$. Notice that for every integer $1\le k \le p_{i+1}-p_{i}-1$, $p_i+k$ doesn't have a prime factor greater than $p_i$ and $p_{i+1}$. Using this fact, we have $l(p_i(p_i+k))=p_i$ and $l(p_{i+1}(p_i+k))=p_{i+1}$ for every integer $1\le k \le p_{i+1}-p_{i}-1$. Lemma. For every integer $1\le k \le p_{i+1}-p_{i}$, we have $$a_{j+k}=p_i(p_i+k)$$Proof. For $k=1$, this is clearly true. If this is true for some integer $1\le k \le p_{i+1}-p_{i}-1$, then we have $$a_{j+k+1}=a_{j+k}+l(a_{j+k})= p_i(p_i+k) + p_i=p_i(p_i+k+1)$$. So it is also true for $k+1$. By Induction, we are finished. In particular we have $a_j+p_{i+1}-p_i=p_{i+1}p_i$. Using the same method, we can also get $$a_{j+p_{i+1}-p_i+k}=p_{i+1}(p_i+k)$$for every integer $1\le k \le p_{i+1}-p_{i}$. That means $a_{j+2(p_{i+1}-p_i)}=p_{i+1}^2$. So our claim is also true for $i+1$, by induction we are finished. As a corollary for this well-defined sequence, we have $v_{p_i}(a_{j+k})=1$ and $v_{p_{i+1}}(a_{j+p_{i+1}-p_i})=1$ for all integer $1\le k \le p_{i+1}-p_{i}-1$. So, there are no perfect squares "in between" $a_j=p_{i}^2$ and $a_{j+2(p_{i+1}-p_i)}=p_{i+1}^2$. Hence, by induction again there are no such $m$ except $p_i$. As desired.

The answer is $m=p$ where $p$ is a \(prime\) Let $p_1,p_2,p_3,...$ be the primes serially \(Claim:\) If we get an $a_k=p_{i-1} p_i$ then there is an integer $l$ so that $a_l=(p_j)^2$ for $j>i$ \(Proof:\) Let $a_k$ be $p_{i-1} p_i$ We define $q_1$ to be $p_i-p_{i-1}$ and $q_2$ to be $p_{i+1}-p_{i-1}$ Now it is trivial to show that $a_{k+b}=(p_{i-1}+b)p_i$ where $b\leq q_2$ so $a_{k+ q_1}=(p_{i-1}+q_1)p_i=(p_i)^2$ Now $a_{k+q_2}=p_i p_{i+1}$ Now by the same logic we can get every square of primes greater than $p_i$. Now $a_1=2,a_2=4,a_3=6=3*2$ so by above \(Claim\) we will get every square of primes. Now we will prove that $m \ne p$ where $p$ is a \(prime\) is not what we desire. Now from the upper proof we know $a_{k+b}=(p_{i-1}+b)p_i$ for some $p_i$ and $b\leq p_{i+1}-p_{i-1}$ where $a_k=p_{i-1} p_i$ We assume $a_{k+b}$ is a square(\(not\) $(p_i)^2$) then it is true that $p_i|p_{i-1}+k$ Then it is also true that $k\geq 4p_i-p_{i-1}$ Which leads us to $p_{i+1}\geq 4p_i$ But using \(Bertrand's\) \(postulate\) we know for $i>1$ , $p_{i+1}<2p_i$ and which leads to a \(contradiction\). $\square$

$\boxed{ANSWER:m\in p}$

Attachments: