Decide if binary encoded number is divisible by 3
you have to use the fact that $2^n\mod 3 = n\mod 2 + 1$:


2 mod 3 = 2
4 mod 3 = 1
8 mod 3 = 2
16 mod 3 = 1
32 mod 3 = 2


and so on. 

The solution then for an $n$ bit number is to use $n$ processors, the $i$th processor will calculate $f_0(i) = i\mod 2 +1 * w[i]$ where w is the little-endian array of bits.

Then, each of the processors can calculate the following: $f_{t+1}(i) &lt;= f_{t}(i) + f_{t}(i+2^t)\mod 3$, for $t \in \{1...log_2(n)\}$ (increasing sequentially of course). $f_{log_2(n)}(0)$ will then contain the sum of the bits mod 3.