Re: divisibility conditions for binary numbers



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

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):
1 0
----------> ----------->
mod3=0 mod3=1 mod3=2
<---------- <----------
1 0

(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,
etc...


Mitch

.



Relevant Pages

  • Re: Enigma 1692 - Key factors
    ... In just one case a digit has both neighbours ... The triplet is a run of three. ... The obvious thing to do next is to attack divisibility by 7, ... Susan Denham is rather clever at these aint she? ...
    (rec.puzzles)
  • Re: Factoring integers on a classical computer
    ... That reminds me of digit summation congruence, ... That might be useful, basically it is like "casting out nines", sum the ... sum the bytes and test that for divisibility by 255. ... that 345634563456654365436543 is an integral multiple of nine because ...
    (comp.theory)
  • Re: Factoring integers on a classical computer
    ... That reminds me of digit summation congruence, ... That might be useful, basically it is like "casting out nines", sum the ... sum the bytes and test that for divisibility by 255. ... that 345634563456654365436543 is an integral multiple of nine because ...
    (sci.math)
  • Re: Is this true?
    ...  Else repeat to get p2, p3,... ... A '''search engine''' sourced this article: Divisibility rule - ... If the tens digit is odd, and the ones digit is 2, or 6. ... Multiply the right most digit by the left most digit in the sequence ...
    (sci.math)
  • Re: Some maths help in a ebook
    ... multiple-digit number, sum those. ... It's a subset of the divisibility check for 9, known to accountants as "casting out nines". ... N modis the units digit minus the tens digit plus the hundreds digit minus ...
    (comp.dsp)