Let $v_2(n)$ be the the greatest integer $\alpha$ such that $2^{\alpha}|n$. Define the sequence $\{b_n\}$ such that $b_n=a_{n+1}-a_n$ for every positive integer $n$. So, $a_{n+2}-a_{n+1}=2a_{n+1}a_n+1-2a_na_{n-1}-1 \iff b_{n+1}=2a_n(a_{n+1}-a_{n-1})=2a_n(b_n+b_{n-1})$. Let $\{c_n\}$ be the sequence defined by $c_n=v_2(b_n)$ for every positive integer $n$. So, $v_2(b_{n+1})=v_2(2a_n(b_n+b_{n-1})) \iff c_{n+1}=v_2(2)+v_2(a_n)+v_2(b_n+b_{n-1})$ as $v_2$ is multiplicative. Note that every $a_n$ is odd, so $v_2(a_n)=0$, implying that $c_{n+1}=1+min(c_{n-1},c_n)$. By induction, we'll prove the following: $c_{2k}=c_{2k+1}=k+1$ for every positive integer $k$. Base Case: $c_2=c_3=2$ (easily verified). Hypothesis: $c_{2n}=c_{2n+1}=n+1$. Inductive Step: $c_{2(n+1)}=1+min(c_{2n},c_{2n+1})$ and, by the hypothesis, $min(c_{2n},c_{2n+1})=n+1$, so $c_{2(n+1)}=n+2$. $c_{2(n+1)+1}=1+min(c_{2n+1},c_{2(n+1)})$ and, by the hypothesis, $min(c_{2n+1},c_{2(n+1)})=n+1$, so $c_{2(n+1)+1}=n+2$. QED. What we want is $v_2(a_{4006}-a_{4005})=v_2(b_{4005})=c_{4005}=c_{4004}=2003$.