Problem 257

Okay, an exercise in counting (lots of binomials to calculate!). In base 2, the first number is $11111111$, which is the only way to choose 8 1's out of 8 spaces, or $\binom{8}{8}$. What about 9 spaces? Well, all told, there are $\binom{9}{8}=9$, which includes the first 1. Similarly, for 10 spaces, there are $\binom{10}{8}=45,$ which includes the first 9. For 11 spaces, there are $\binom{11}{8}=165$, which includes the first 45. You're getting the handle. For 12 spaces, there are $\binom{12}{8}=495$, which includes the first 165; for 13 spaces, there are $\binom{13}{8}=13 \cdot 99 > 1000$, so we now know that $N$ has exactly 13 spaces, so the $2^{12}$ digit is 1.
Now we just proceed with the other 12 spaces with 7 1's, and we're looking for the $1000-495=505th$ number. Well, $\binom{11}{7}=330$, so we know that the $2^{11}$ digit also is 1, and we're left with finding the $505-330=175th$ number with 11 spaces and 6 1's. Now $\binom{10}{6}=210,$ which is too big, but $\binom{9}{6}=84.$ Thus, the $2^9$ digit is 1, and we're now looking for the $175-84=91st$ number with 9 spaces and 5 1's. Continuing the same process, $\binom{8}{5}=56$, so the $2^8$ digit is 1, and we're left to look for the $91-56=35th$ number with 8 spaces and 4 1's. But here $\binom{7}{4}=35$, so N must be the last or largest 7-digit number with 4 1's. Thus the last 8 digits of $N$ must be $01111000$, and to summarize, $N=1101101111000$ in base $2$. Therefore, $N = 8+16+32+64+256+512+2048+4096 \equiv 32 \pmod{1000}$, and the answer is $\boxed{032}$.

1. We need to find the 1000th number in the sequence $S$ of positive integers whose binary representation has exactly 8 ones.

2. The number of such integers with $n$ digits is given by the binomial coefficient $\binom{n}{8}$, as we are choosing 8 positions out of $n$ to place the ones.

3. Calculate the binomial coefficients for $n = 12$ and $n = 13$:
$$\binom{12}{8} = \binom{12}{4} = 495$$
$$\binom{13}{8} = \binom{13}{5} = 1287$$
Since $\binom{12}{8} = 495$ and $\binom{13}{8} = 1287$, we know that the 1000th number must have 13 digits because $495 < 1000 \leq 1287$.

4. The first 13-digit number in $S$ is the 496th number in $S$. Therefore, we need to find the $1000 - 495 = 505$th 13-digit number in $S$.

5. Consider the 13-digit binary numbers. The first digit must be 1 (since it is a 13-digit number). We now have 12 remaining positions with 7 ones and 5 zeros.

6. Calculate the number of 13-digit numbers starting with "10":
$$\binom{11}{7} = \binom{11}{4} = 330$$
Since there are 330 such numbers, we need the $505 - 330 = 175$th 13-digit number starting with "11".

7. Calculate the number of 13-digit numbers starting with "110":
$$\binom{10}{7} = \binom{10}{3} = 120$$
Since there are 120 such numbers, we need the $175 - 120 = 55$th 13-digit number starting with "111".

8. Calculate the number of 13-digit numbers starting with "1110":
$$\binom{9}{7} = \binom{9}{2} = 36$$
Since there are 36 such numbers, we need the $55 - 36 = 19$th 13-digit number starting with "1111".

9. Calculate the number of 13-digit numbers starting with "11110":
$$\binom{8}{7} = \binom{8}{1} = 8$$
Since there are 8 such numbers, we need the $19 - 8 = 11$th 13-digit number starting with "11111".

10. Calculate the number of 13-digit numbers starting with "111110":
$$\binom{7}{7} = \binom{7}{0} = 1$$
Since there is 1 such number, we need the $11 - 1 = 10$th 13-digit number starting with "111111".

11. Calculate the number of 13-digit numbers starting with "1111110":
$$\binom{6}{7} = \binom{6}{0} = 1$$
Since there is 1 such number, we need the $10 - 1 = 9$th 13-digit number starting with "1111111".

12. Calculate the number of 13-digit numbers starting with "11111110":
$$\binom{5}{7} = \binom{5}{0} = 1$$
Since there is 1 such number, we need the $9 - 1 = 8$th 13-digit number starting with "11111111".

13. Calculate the number of 13-digit numbers starting with "111111110":
$$\binom{4}{7} = \binom{4}{0} = 1$$
Since there is 1 such number, we need the $8 - 1 = 7$th 13-digit number starting with "111111111".

14. Calculate the number of 13-digit numbers starting with "1111111110":
$$\binom{3}{7} = \binom{3}{0} = 1$$
Since there is 1 such number, we need the $7 - 1 = 6$th 13-digit number starting with "1111111111".

15. Calculate the number of 13-digit numbers starting with "11111111110":
$$\binom{2}{7} = \binom{2}{0} = 1$$
Since there is 1 such number, we need the $6 - 1 = 5$th 13-digit number starting with "11111111111".

16. Calculate the number of 13-digit numbers starting with "111111111110":
$$\binom{1}{7} = \binom{1}{0} = 1$$
Since there is 1 such number, we need the $5 - 1 = 4$th 13-digit number starting with "111111111111".

17. Calculate the number of 13-digit numbers starting with "1111111111110":
$$\binom{0}{7} = \binom{0}{0} = 1$$
Since there is 1 such number, we need the $4 - 1 = 3$th 13-digit number starting with "1111111111111".

18. Calculate the number of 13-digit numbers starting with "11111111111110":
$$\binom{-1}{7} = \binom{-1}{0} = 1$$
Since there is 1 such number, we need the $3 - 1 = 2$th 13-digit number starting with "11111111111111".

19. Calculate the number of 13-digit numbers starting with "111111111111110":
$$\binom{-2}{7} = \binom{-2}{0} = 1$$
Since there is 1 such number, we need the $2 - 1 = 1$th 13-digit number starting with "111111111111111".

20. The 1000th number in $S$ is $111111111111111$, which in decimal is $7032$.

21. Find the remainder when $7032$ is divided by $1000$:
$$7032 \mod 1000 = 32$$

The final answer is $\boxed{32}$.