, 2020

Solution:
Note that $a_{1} \equiv 1+1+2+6 \equiv 2 \pmod{8}$. Since $a_{1}+a_{2}$ must be an odd perfect square, we must have $a_{1}+a_{2} \equiv 1 \pmod{8} \Longrightarrow a_{2} \equiv 7 \pmod{8}$. Similarly, since $a_{2}+a_{3}$ is an odd perfect square, we must have $a_{3} \equiv 2 \pmod{8}$. We can continue this to get $a_{2k-1} \equiv 2 \pmod{8}$ and $a_{2k} \equiv 7 \pmod{8}$, so in particular, we have $a_{1000} \equiv 7 \pmod{8}$, so $a_{1000} \geq 7$.

Now, note that we can find some large enough odd perfect square $t^{2}$ such that $t^{2}-a_{1} \geq 23$. Let $a_{2}=t^{2}-a_{1}$. Since $a_{2} \equiv 7 \pmod{8}$, we can let $a_{2}-7=8k$ for some integer $k \geq 2$. Now, since we have $(2k+1)^{2}-(2k-1)^{2}=8k$, if we let $a_{3}=(2k-1)^{2}-7$, then
$$a_{2}+a_{3}=a_{2}+\left((2k-1)^{2}-7\right)=(2k-1)^{2}+\left(a_{2}-7\right)=(2k-1)^{2}+8k=(2k+1)^{2}$$
which is an odd perfect square. Now, we can let $a_{4}=7$ and we will get $a_{3}+a_{4}=(2k-1)^{2}$. From here, we can let $a_{5}=a_{7}=a_{9}=\cdots=2$ and $a_{4}=a_{6}=a_{8}=\cdots=7$, which tells us that the least possible value for $a_{1000}$ is $7$.