Remainders Of Powers Of 2

We do casework based on the parity of $n.$

• Case 1: $n$ is even.

Note that the only power of $2$ which is odd is $1.$ All other elements in $S_n$ are even. The sum of the elements of $S_n,$ therefore, is odd. Since no odd number can be a multiple of an even number, $n$ can't be even.

• Case 2: $n$ is odd.

Let $r$ be the order of $2$ modulo $n,$ so $2^r \equiv 1 \pmod{n}.$ Since the residues $2^x \pmod{n}$ become periodic after $2^r,$ the elements of $S_n$ are equivalent to $\{2^0, 2^1, \cdots , 2^{r-1}\}$ modulo $n.$ Modulo $n,$ the sum of elements of $S_n$ is $\begin{array}{lcll} 2^0 + 2^1 + \cdots + 2^{r-1} & \equiv & 2^r-1 & \pmod{n} \\ & \equiv & 1-1 & \pmod{n} \\ & \equiv& 0 & \pmod{n}. \end{array}$

Conclusion: All such $n$ are the odd positive integers.

There are $\boxed{500}$ odd integers between $1$ and $1000,$ which is our answer.