, 2016

Solution:
We claim that $a_{1000}$ is constant mod $100$.

$a_{997}$ is divisible by $2$. This means that $a_{998}$ is divisible by $4$. Thus $a_{999}$ is constant mod $5$. Since it is also divisible by $4$, it is constant $\bmod\ 20$. Thus $a_{1000}$ is constant $\bmod\ 25$, since $\phi(25) = 20$. Since $a_{1000}$ is also divisible by $4$, it is constant mod $100$.

We know that $a_{1000}$ is divisible by $4$, and let it be congruent to $k \bmod 25$.
Then $2^{n}$ is divisible by $4$ ($n \geq 2$) and $2^{n} \equiv k \bmod 25$. We can also show that $2$ is a primitive root mod $25$, so there is one unique value of $n \bmod 20$. It suffices to show this value isn't $1$. But $2^{2^{0 \bmod 4}} \equiv 2^{16 \bmod 20}$ $\bmod 25$, so $n \equiv 16 \bmod 20$. Thus there are $1000 / 20 = 50$ values of $n$.