Re: divisibility conditions for binary numbers
- From: "Mitch" <maharri@xxxxxxxxx>
- Date: 7 Apr 2006 10:28:48 -0700
Robert Israel wrote:
Larry Hammick <larryhammick@xxxxxxxxx> wrote:
the OP wrote
Could anyone has some idea on divisibility of binary numbers by 3,5,6,7
I don't think much can be said, but given a binary number
x = \sum_n ( k_n 2^n )
where each digit k_n is 0 or 1, let
A = the number of k_n's which are 1 and n is even
B = the number of k_n's which are 1 and n is odd
Then x is divisible by 3 if and only if A-B is divisible by 3.
E.g 1110101 (binary) is divisible by 3 since A=4 and B=1.
For 5, note that 2^j == 1, 2, -1, -2 mod 5 for j == 0, 1, 2, 3 mod 4
respectively. So let A, B, C, D be the number of k_n which are 1
with n congruent to 0, 1, 2, 3 mod 4, and take A + 2 B - C - 2 D.
Then x is divisible by 5 iff the result is divisible by 5.
E.g. for 11110101 we have A = 2, B = 1, C = 2, D = 1, result = 0
so it's divisible by 5. You may find it easier to start at the right
end and go digit-by-digit, adding or subtracting 1 or 2 for each
1 as appropriate.
You can construct a similar trick for divisibility by any odd
Yes, this is a cute trick that turns up as an exercise in automata
theory. It generalizes easily for -any- divisor/modulus and any base.
Such things are always finite automata/regular languages, where the
states are the moduli, and the transitions are the digits. Reading a
numeral from MSD to least, each new digit multiplies by the base and
adds the digit, and the state you're left in is the modulus of the
numeral. For example,
Binary numbers divisible by 3 have the DFA (follow the edges as you
read the digits left to right, starting from the leftmost state):
mod3=0 mod3=1 mod3=2
(with a self loop labeled 0 on the first state, and a self loop labeled
1 on the last)
Creating the DFA is not too hard: for a given state (modulus) a new
digit corresponds to multiplying by the base and adding the digit,
leading to a new state. E.g., if your binary number (so far) is 2 mod 3
(that is = 3k+2), then appending a 1 doubles the number and adds 1 or
2*(3k+2)+1 = 6k+5 = 6k'+2 = 3k''+2 which is in the same modulus class.
Do the same thing for all moduli and all digits.
The corresponding regular expression (for mod3=0) is:
(0 + 1(01*0)*1)*
Notice that 1001_2 = 9 is divisible by 3, and by the regular
expression, we could put any number of 1's beteen the pair of 0's and
still be divisible by 3: 10101_2 = 21, 101101_2 = 45, 1011101_2 = 93,