If $2\not | a_1$ then $2|a_2$ So let $2|a_1$ Let $a_1=2^x 3^y q$ where $x \geq 1$ and $(6,q)=1$ Then $a_2=2^x 3^y q+2^{x-1} 3^y q=2^{x-1} 3^{y+1} q$ If we continue this way we will get that for some $i$ we have $a_i=3^{z}q$ where $z>0$ and $(6,q)=1$ $a_i=3^z q$ $a_{i+1}=2^2 *3^{z-1} q$ $a_{i+2}= 2*3^{z}q$ $a_{i+3}=3^{z+1} q$ And so if $a_i=3^z q$ with $(6,q)=1$ then $a_{i+3k}= 3^{z+k}q,a_{i+3k+1}= 4 *3^{z+k-1} q,a_{i+3k+2}=2*3^{z+k}q$ and so $a_{n+3}=3a_n$ PS. I am sure, that problem is old

Yeah PAMO problems are not original : (

Already posted two day ago: https://artofproblemsolving.com/community/c6h2570566

Let $2<p_1<...<p_k$ be the prime divisors of $a_1$. Assume that there is no $m$ such that $a_m=2^k$. Using induction we will prove that for $t>N$ where $N$ is a natural number we have $v_p(a_{1+t})=0$. For ${p_k}$, $N=v_{p_{k}}(a_1)$ works. Assume that we have $v_{p_{i}}(a_{1+t})=0$ for $t>N$ where $i \in \{d+1,...,k\}$. For $d$, $t>N+v_{p_{i-1}}(a_1)$ works (we used $a_{n+1}=(p_n+1)\frac{a_n}{p_n}$ which shows every step decreases the number of greatest prime). Thus number of odd primes eventually will be 0 which contradicts the assumption. Let $a_m=2^k$. We have $a_{m+2l}=2^{k+l}$ and $a_{m+2l+1}=3\cdot 2^{k+l-1}$ which gives $a_{n+3}=3a_n$.

anyone__42 wrote: Let $(a_i)_{i\in \mathbb{N}}$ and $(p_i)_{i\in \mathbb{N}}$ be two sequences of positive integers such that the following conditions hold: $\bullet ~~a_1\ge 2$. $\bullet~~ p_n$ is the smallest prime divisor of $a_n$ for every integer $n\ge 1$ $\bullet~~ a_{n+1}=a_n+\frac{a_n}{p_n}$ for every integer $n\ge 1$ Prove that there is a positive integer $N$ such that $a_{n+3}=3a_n$ for every integer $n>N$ There are $2$ possible cases Case 1-: $a_1$ is odd Then for any $p_1$ let $v_2(p_1+1)=k$ then observe $p_2=p_3=... =p_{k+1}=2$ and also By the given recurrence we ca get that $a_i=\frac{a_1(p_1+1)3^{i-2}}{2^{i-2}p_1}$ for all $3\leq i\leq k+2$ And also $p_{k+3}=3$ So $a_{k+3}=\frac{a_{k+2}(4)}{3}=\frac{a_1(p_1+1)\times 3^{k-1}}{2^{k-2}p_1}=3a_k$ Similarly we can use strong induction and get that $a_{n+3}=3a_n \forall n>k-1$ $\blacksquare$ Case 2-: $a_1$ is even Then let $v_2(a_1)=k$ Then we have $p_1=p_2=_3=... =p_k=2$ and also by the recurrence relation given, we can get that $a_i=\frac{3^{i-1}a_i}{2^{i-1}}\forall 2\leq i\leq k+1$ So $2\nmid a_{k+1}\implies p_{k+1}=3$ and we will have $a_{k+2}=\frac{a_{k+1}(4)}{3}=\frac{3^{k-1}a_1}{2^{k-2}p_1}=3a_{k-1}$ and now we can use strong induction and get that $a_{n+3}=3a_{n}\forall n >k-2$ $\blacksquare$

anyone__42 wrote: Yeah PAMO problems are not original : ( When I saw this problem, I also thought that it felt very familiar. That said, I know the person who proposed it, and they would not have intentionally proposed a problem that they found from some other source. That doesn't mean that it hasn't been used before; it is possible that two different people independently invented the same problem.

You're right