# Algorithms computing if a number is a multiple of 3

When doing mental calculus one can do:

• Given an integer k, sum all the digits (in base 10), and if the result is a multiple of 3, then k is a multiple of 3.

Do you know of any algorithm working similarily but operating on binary numbers digits (bits)?

• At first, I was thinking of using the ready made functions of my language converting integer to ascii to perform the convertion from base 2 to base 10, then apply the mental calculus trick. But of course then I could also encode the base convertion 2 to 10 myself. I have not done it yet, but I'll give it a try.

• Then I have thought of euclidian division in base 2...

However I wonder if there are other means, algorithms.

-
You may find it interesting: Design DFA accepting binary strings divisible by a number 'n' – Grijesh Chauhan Mar 2 '15 at 12:13

Consider the following two observations (left as an exercise to the reader):

1. The even powers of two are 1 modulo 3.
2. The odd powers of two are -1 modulo 3.

We conclude that that a number (in binary) is divisible by three if and only if the sum of the bits in the even positions equals the sum of the bits in the odd positions modulo 3.

-
This is like the rule for being divisible by 11 in decimal. – Yuval Filmus Jan 11 '13 at 11:17
@YuvalFilmus: Precisely. I was going to add another exercise for the reader but decided against it. – mhum Jan 11 '13 at 19:05
OK, how about finding out if a number written in hexadecimal is divisible by 17 (decimal)? Or 15 (decimal) for that matter? ;-) – vonbrand Jan 27 '13 at 4:16

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.

-
I like the idea, let's try with 9. I feed 1001 in binary. The first bit send me to state1, then state2, then state1 then back to state0. So state0 is multiple of 3. And the complexity of the algorithm is the number of bits used, nothing more. It's awesome ! – Stephane Rolland Jan 12 '13 at 0:28

In binary, numbers 1, 100, 10000 (=100×100), 1000000 (=100×100×100) etc. all give the same remainder after dividing by 11 (three). Therefore if we split a binary number to parts of even length, the sum of the parts gives the same remainder as the original number.

(When splitting the number, we add as many zeroes as necessary to the beginning. For example we would split 10111 to groups 01,01,11 or 0001,0111.)

Mathematically, just split the number into groups of two digits, then add the groups; and repeat this until your result becomes 00 or 11 = the original number was a multiple of three; or 01 or 10 = the original number was not a multiple of three.

For a computer program, using groups of eight or sixteens or thirty-two bits may be faster for your CPU. For example, if eight-bit addition is fastest, just make a sum of all bytes, and again, until the result fits into one byte. Then use one instruction to determine the remaininder after dividing by three.

(Note: We are assuming unsigned integers here. With a signed number, it needs a bit more of an attention. For example 129 is a multiple of 3, but -127 is not, although bits 10000001 mean for former as an unsigned byte and the latter as a signed byte.)

-

While not binary-specific, when in doubt, repeated subtraction is always a surefire way to compute division with remainder (and thus if a number is a multiple of 3).

-
Repeated subtraction is a bad idea. Division with remainder is much faster. – Yuval Filmus Jan 11 '13 at 11:17
probably really really costly in cpu, but it's a different algorithm :-) that doesn't deserve -1 :-( – Stephane Rolland Jan 12 '13 at 0:18