Digit Divisibility

In effect, we are looking at the numbers from 0 to $2^{11} - 1$ written out in binary. We can now show something similar to the rule for divisibility by 11 in base 10: $2^0 \equiv 1 \pmod{3}$ . Let us assume that $2^{2k} \equiv 1 \pmod{3}$ then $2^{2k+1} \equiv 2 \times 1 \equiv 2 \pmod{3}$ and $2^{2(k+1)} \equiv 2 \times 2 \equiv 1 \pmod{3}$ . Since $2^0 \equiv 1 \pmod{3}$ , we have that $2^{2k} \equiv 1 \pmod{3} \forall k \in \mathbb{N}$ and $2^{2k+1} \equiv -1 \pmod{3} \forall k \in \mathbb{N}$ . So, for the final condition to hold, we see in fact that the number must be a multiple of 3. So the question now trivially becomes how many multiples of 3 are there less than or equal to $2^{11} - 1$ including 0, to which the answer is $\fbox{683}$

First and second sums have to be congruent modulo 3, and they both express the amount of 1s in those placements. Let's count the cases (number of 0s/1s in the even positions):

a) 0 1s in the even positions --> 0, 3 or 6 1s in the odd positions, so total of cases here = C(5,0) * (C(6,0) + C(6,3) + C(6,6)) = 1 * (1 + 20 + 1) = 22 b) 1 1 in the even positions --> 1 or 4 1s in the odd positions, so total of cases here = C(5,1) * (C(6,1) + C(6,4)) = 5 * (6 + 15) = 105 c) 2 1s in the even positions --> 2 or 6 1s in the odd positions, so total of cases here = C(5,2) * (C(6,2) + C(6,5)) = 10 * (15 + 6) = 210 d) 3 1s in the even positions --> 0, 3 or 6 1s in the odd positions, so total of cases here = C(5,3) * (C(6,0) + C(6,3) + C(6,6)) = 10 * (1 + 20 + 1) = 220 e) 4 1s in the even positions --> 1 or 4 1s in the odd positions, so total of cases here = C(5,4) * (C(6,1) + C(6,4)) = 5 * (6 + 15) = 105 f) 5 1s in the even positions --> 2 or 6 1s in the odd positions, so total of cases here = C(5,5) * (C(6,2) + C(6,5)) = 1 * (15 + 6) = 21

So total of cases = 22 + 105 + 210 + 220 + 105 + 21 = 683