020. Odd 8-Bit Numbers

Find the largest odd number that divides the sum of the natural numbers less than or equal to 255 in which 1 appears an odd number of times when expressed in binary.

---

Among the natural numbers less than 255, there are 128 that have an odd number of 1s when expressed in 8-bit binary. $$\begin{aligned} \binom{8}{1} + \binom{8}{3} + \binom{8}{5} + \binom{8}{7} = 8 + 56 + 56 + 8 = 128 \end{aligned}$$

Now, let $x$ be a natural number less than or equal to 255 that has an odd number of 1s when expressed in binary. If changing 0 to 1 and 1 to 0 for this $x$, that becomes $$\begin{aligned} 11111111_2 - x = 255 - x \end{aligned}$$

Since subtracting an odd number from 8 is also an odd number, the value above also has an odd number of 1s when expressed in binary. So, if thinking about it in pairs, the sum of all numbers with an odd number of 1s is $$\begin{aligned} (1 + (255 - 1)) + (2 + (255 - 2)) + \cdots + (127 + (255 - 127)) = 255 \times \frac{128}{2} = 255 \times 2^6 \end{aligned}$$

Therefore, the largest odd number that divides this sum is 255.