We claim that $a_{1000}$ is constant $\bmod 100$. $a_{997}$ is divisible by 2. This means that $a_{998}$ is divisible by 4. Thus $a_{999}$ is constant $\bmod 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 $\bmod 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 \mathrm{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 \text { mod } 4}} \equiv 2^{16 \text { mod } 20}$ $\bmod 25$, so $n \equiv 16 \bmod 20$. Thus there are $1000 / 20=50$ values of $n$.