# Consider 4 positive integers a,b,c,d having exactly 10^11 bits (considering the leading zeroes) in the binary representations

Consider 4 positive integers a,b,c,d having exactly 10^11 bits (considering the leading zeroes) in the binary representations. Positions are numbered from 1 to 10^11. Every 3rd bit of a is equal to 1 (in other words bits number 3,6,9 and so-on), every 7th bit of b is equal to 1, every 4th bit of c is equal to 1, every 5th bit of d is equal to 1. The task is to determine the number of 1 bits in a ⊕ b ⊕ c ⊕ d, where ⊕ is bitwise XOR operation.

• What are your thoughts about this question? – Yuval Filmus Dec 25 '20 at 11:24

## 1 Answer

The value of $$(a \oplus b \oplus c \oplus d)_i$$ depends on whether $$i$$ is divisible by $$3,4,5,7$$, and in particular, by $$i \bmod 3\cdot 4\cdot 5\cdot 7$$. In order to complete the calculation, you need to know, for each $$j \in \{0,\ldots,3\cdot 4\cdot 5\cdot 7 - 1\}$$, how many indices $$i \in \{1,\ldots,10^{11}\}$$ satisfy $$i \equiv j \pmod{3\cdot 4\cdot 5\cdot 7}$$.