divisibility conditions for binary numbers

[Shishir]

Hi All,

Suppose we have a 32 bit binary number. We can tell it is divisible
by looking at the rightmost one bit. If it zero , it is divisible by 2.
If rightmost two bits are zeros then the number is divisible by 4 . If
rightmost three bits are zeros the number is divisible by 8 and so on.

Could anyone has some idea on divisibility of binary numbers by 3,5,6,7
.....

Regards,
Shishir

[Larry Hammick]

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.

In decimal, there are similar tricks for characterising multiples of 3,
9, or 11.

LH

[Robert Israel]

In article <1144320138.0...@i39g2000cwa.googlegroups.com>,
Larry Hammick <larryh...@telus.net> wrote:

>> Suppose we have a 32 bit binary number. We can tell it is divisible
>> by looking at the rightmost one bit. If it zero , it is divisible by 2.
>> If rightmost two bits are zeros then the number is divisible by 4 . If
>> rightmost three bits are zeros the number is divisible by 8 and so on.
>>
>> 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.

Robert Israel isr...@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada

[Mitch]

Robert Israel wrote:
> Larry Hammick <larryh...@telus.net> 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

[Ross A. Finlayson]

Hi,

I call it digit summation congruence or DSC and it is discussed here,
on sci.math, in implementation details and so forth, factorization
methods for binary computers.

Basically you can group the binary digits, bits, from the right in
groups of say, n, and then if the sum of those groups is divisible by
2^n-1, the Mersenne number that is a binary rep-unit, then the extended
precision sequence is divisible by that number.

If you want to test for divisbility by 2^n+1, perhaps it is,
alternately add and subtract the groups and test that sum for
divisbility by the number.

There are a wide variety of divisbility tests, specific to number,
base, totient, etcetera.

Regards,

Ross F.

[Milo Gardner]

The divisibility aspect of any binary number
divided by 3, 7, 10, 11, 13, and by implication
n, was exactly solved in 2,000 BC by an Egyptian
scribe. The text is called the Akhmim Wooden
Tablet, as summarized on:

http://akhmimwoodentablet.blogspot.com

The scribal method works for n < 64, as given
by the identity (64/64), divided by n, with
zero remainder. For n = 3, the 4,000 year
old scribe found the quotient 21, taken
from 64/3, such that the binary series

(16 + 4 + 1)/64 = 1/4 + 1/16 + 1/64 was

written,

with a remainder of one.

Obviously, a modern update for divisors > 64,
can be institutied to the increase the size of
the initial identity to multiplies of 2/p, or
128, 256, 512, and so forth, as needed.

That is, use remainder arithmetic's quotients
and remainders on several levels of this
problem, applying it as needed.

Best Regards,

Milo Gardner

[Narayana]

Here is the python snippet to find the divisibility condition for any radix [not limited to binary], for any divisor and for an infinite stream of digits.
http://code.activestate.com/recipes/577326-infinite-stream-divisor/?in=user-4174427

Thanks,
Narayana

[James Waldby]

That code worked ok for the handful of finite cases I tried, but always
failed to return when given infinite streams via variations of:

import infStrDiv
def gen():
while (1>0):
yield 1
infStrDiv.infinite_stream_divisor(3,2,gen())

(where your recipe-577326-1.py was saved locally as infStrDiv.py)

Obviously, it doesn't make sense to advertise your function as
working "for an infinite stream of digits". At best you could
say arbitrarily many, or indefinitely many, digits.

One more comment re wording: Your post doesn't pin the phrase
"find the divisibility condition" to any specific action or aim,
ie, leaves its meaning ambiguous.

--
jiw