Upper bound: just note that if a positive integer $n$ is good then $n-1$ is bad. This combined with the fact that from $1$ to $10$ there are $4$ good numbers (and that $11$ is bad) show that there are at most $4 + 999990/2 =499999$ good numbers. Lower bound: For brevity, let $f(n)$ denote the number of good numbers in $\{1,2,\ldots,n\}$. We'll prove by (strong) induction that for any even $n$, there are at least $(n+2)/4$ good numbers in $\{1,\ldots,n\}$. This will imply that there are at least $\lceil 1000002/4 \rceil > 250000 $ good numbers from $1$ to $1000000$. The base case here will be $n=2$; this is obvious as $1$ is good. For the inductive step, assume the above statement is true for $n=2,4,6,\ldots,2k-2$. Now note that - $p_{2k}-1$ is even, so there are $f(p_{2k}-1)\geqslant (p_{2k}+1)/4$ good numbers in $\{1,2,\ldots,p_{2k}-1\}$. - the numbers in $\{p_{2k},p_{2k}+1,\ldots,2k\}$ will get reduced to $\{0,1,\ldots,2k-p_{2k}\}$ after a move. If $2k-p_{2k}\geqslant 3$, by the inductive step, the number of good numbers in this set is at least $f(2k-1-p_{2k})\geqslant (2k+1-p_{2k})/4$. Else, $2k-p_{2k}=1$ and this set has $1\geqslant (2k+1-p_{2k})/4$ good numbers. Adding the above two, we have $f(2k)\geqslant (2k+2)/4$, so we're done. $\blacksquare$