Algorithms computing if a number is a multiple of 3
What about a finite state automaton for the job?



Of course the magic is just computation modulo 3. Adding symbol $a$ behind string $x$ means the "binary value" of the string goes from $val(x)$ for $x$ to $2\cdot val(x)+a$ for $xa$. Consequently from state $p$ and symbol $a$ we move to state $2p+a \bmod 3$, for $p\in \{0,1,2\}$ and $a\in \{0,1\}$. Note $x\in \{0,1\}^*$ is a string, wheras $val(x)\in \Bbb{N}$ is its value as binary string.