15
$\begingroup$

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.

Improve this question
$\endgroup$
1

4 Answers 4

Reset to default
22
$\begingroup$

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.

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

What about a finite state automaton for the job?

enter image description here

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.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ 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 ! $\endgroup$
    – Stephane Rolland
    Jan 12, 2013 at 0:28
  • $\begingroup$ Is this concept in the link related? I think it is more simpler. geomathry.wordpress.com/2017/02/13/0-1-and-a-new-number $\endgroup$
    – user13005
    Jan 31, 2018 at 0:37
  • 1
    $\begingroup$ @WaqarAhmad Yes, related, not simpler. The transitions in a finite automaton can also be used to describe a L2R evaluation, like in your explanation. The transitions define $\bar00=\bar0$, $\bar01=\bar1$, $\bar10=\bar2$, $\bar11=\bar0$, $\bar20=\bar1$, $\bar21=\bar2$. Here we have three states, so three symbols for the states are necessary. Your symbols $\Theta,1,0$ are the evaluations of numbers modulo $1,2,0$ respectively, and the first symbol in your L2R evaluation is the "state". If you want discussion, it is perhaps better to start a new question on the site! $\endgroup$
    – Hendrik Jan
    Jan 31, 2018 at 1:29
  • $\begingroup$ Don't about programming. Will this thing be more efficient in a ternary computer? $\endgroup$
    – user13005
    Jan 31, 2018 at 4:18
  • $\begingroup$ Curiously, if we want to read the bit-string from the least significant bit, thus from right to left, we obtain exactly the same automaton: Automaton for telling whether a binary number is a multiple of 3 $\endgroup$
    – Hendrik Jan
    Jan 27, 2022 at 15:24
4
$\begingroup$

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.)

Improve this answer
$\endgroup$
0
$\begingroup$

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).

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Repeated subtraction is a bad idea. Division with remainder is much faster. $\endgroup$
    – Yuval Filmus
    Jan 11, 2013 at 11:17
  • 3
    $\begingroup$ probably really really costly in cpu, but it's a different algorithm :-) that doesn't deserve -1 :-( $\endgroup$
    – Stephane Rolland
    Jan 12, 2013 at 0:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.