Let $a_1, a_2, a_3, \ldots$ a sequence of positive integers that satisfy the following conditions: $$a_1=1, a_{n+1}=a_n+a_{\lfloor \sqrt{n} \rfloor}, \forall n\ge 1$$Prove that for every positive integer $k$ there exists a term $a_i$ that is divisible by $k$
Problem
Source: Peru Cono Sur TST 2020 P6
Tags: number theory
17.11.2023 21:10
Assume, FTSOC, there exists an integer $k$ such that $k\not|a_m$ for all $m \in \mathbb Z^+$. Take $l>\frac{k-1}{2}+2$. Then, $a_{l^2},...,a_{l^2+2l+1}$ is an arithmetic sequence of length $2l+2$ with difference $a_l$. Say $d_1=(a_l,k), d_2=(a_{l^2},k)$. If $d_1=1$, then, since $2l+2>k$, there exists $m \in [l^2,l^2+2l+1]$ s.t. $a_m \equiv 0 (mod k)$. Hence, $(a_l,k)>1$ for all $l>\frac{k-1}{2}+2$. As the set of all divisors of $k$ is finite, there exists a minimal $d_1>1$ such that $(a_l,k)=d_1$ for infinitely many $l>\frac{k-1}{2}+2$. Now, define $d=(d_1,d_2,k)$, and $r_1,r_2$ such that $a_l=d.r_1, a_{l^2}=d.r_2$. For every $p^\alpha ||k$, take a $i_p$ s.t. $r_2+i_p.r_1 \not\equiv 0 (mod p^\alpha)$ (this is obviously possible). Using CRT, take $i\in [0,k]\subset [0, 2l+1]$ s.t $i \equiv i_p (mod p^\alpha) \implies (a_{l^2+i},k)=d$. By minimality, we have $d_1=d$. Hence, $(r_1,k)=1$. But this means that (because $2l+2>k$) $r_2+i.r_1 \equiv \{0,1,...,k-1\} (mod k) \implies$ There exists $m \in [l^2,l^2+2l+1]$ s.t. $r_2+m.r_1 \equiv 0 (mod k) \implies k|a_{l^2+m}$. Contradiction! Thus, our initial hypothesis was incorrect. This is what we desired to conclude.
17.11.2023 22:50
This interesting problem was proposed by A.S. Golovanov on Regional Stage of All-Russian mathematical olympiad in 2018-2019. Here you can find official solution in russian language.