Decide if binary encoded number is divisible by 3 Let's consider the language over $\{0,1\}$ containing such words $w$ that: 
$$w = m_1m_2..m_n $$ where $m_i$ has length $n$. (so $|w|=n^2$) and $$m_1 + m_2 + ..  + m_n \mod 3 = 0$$

($m_i$ we interpret as binary encoded number).

Prove, that the language is $NC^1$ class. 



The first problem is:  How to decide whether $m_i$ is divisible by $3$? 

$m_i = a_na_{n-1}...a_0$ where $a_i$ is a bit, so the number interpreted is:
$v = a_0 \cdot 2^0 + a_1 \cdot 2 + .. + a_n \cdot 2^n$.

My only observation is:

$$2^{2k+1} \mod 3 = 1 \\
2^{2k} \mod 3 = 2$$

Please hint me.
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.