jmc

We use the Principle of Inclusion-Exclusion (PIE). If we join the adjacent vertices of the regular $n$-star, we get a regular $n$-gon. We number the vertices of this $n$-gon in a counterclockwise direction: $0,1,2,3,\dots ,n-1.$ A regular $n$-star will be formed if we choose a vertex number $m$, where $0\le m\le n-1$, and then form the line segments by joining the following pairs of vertex numbers: $(0\mathrm{mod}n,m\mathrm{mod}n),$ $(m\mathrm{mod}n,2m\mathrm{mod}n),$ $(2m\mathrm{mod}n,3m\mathrm{mod}n),$ $\cdots ,$ $((n-2)m\mathrm{mod}n,(n-1)m\mathrm{mod}n),$ $((n-1)m\mathrm{mod}n,0\mathrm{mod}n).$ If $\gcd (m,n)>1$, then the star degenerates into a regular $\frac{n}{\gcd (m,n)}$-gon or a (2-vertex) line segment if $\frac{n}{\gcd (m,n)}=2$. Therefore, we need to find all $m$ such that $\gcd (m,n)=1$. Note that $n=1000=2^3{5}^3.$ Let $S=\{1,2,3,\dots ,1000\}$, and $A_i=\{i\in S\mid i\text{ divides }1000\}$. The number of $m$'s that are not relatively prime to $1000$ is: $\mid A_2\cup A_5\mid =\mid A_2\mid +\mid A_5\mid -\mid A_2\cap A_5\mid$ $=\lfloor \frac{1000}{2}\rfloor +\lfloor \frac{1000}{5}\rfloor -\lfloor \frac{1000}{2\cdot 5}\rfloor$ $=500+200-100=600.$ Vertex numbers $1$ and $n-1=999$ must be excluded as values for $m$ since otherwise a regular n-gon, instead of an n-star, is formed. The cases of a 1st line segment of (0, m) and (0, n-m) give the same star. Therefore we should halve the count to get non-similar stars. Therefore, the number of non-similar 1000-pointed stars is $\frac{1000-600-2}{2}=\boxed{199}.$