On Aug 16, 7:29 pm, Ralph Boland <[email protected]> wrote:
> On Aug 14, 1:45 am, richa gupta <[email protected]> wrote:
>
> > can we check the divisibility of a given number by 3 withoutusing
> > operators like '/' or '%'.
> > I want the efficient solution to this problem ..
>
> > can someone help ??
> > --
> > Richa Gupta
> > (IT-BHU,India)
>
> If the number is an arbitrarily large binary number then
> 0) Let X be the input number.
> 1) Add the binary values of each byte of X. Let result be X.
> 2) If X > 255 goto step 1).
> 3) Look up the answer in a table or
> b1) treat X as a base 16 number and add digits. Let the
> result be X.
> b2) if X > 16 go to step b1.
16 should be 15 here. That is: if X > 15 go to step b1.
> b3) The original number is divisible by 3 IFF X is
> divisible by 3 (X in {0,3,6,9,12,15}).
>
Note that the rule of 3s and the rule of 9s for decimal numbers is be
being
applied here but for the the number 255 and its factors; that is
3, 5, 15, 17, 51, and 85.
It works for the same reason that the rule of 9's (and its factor
rules; i.e.
rule of 3's) works for decimal numbers.
We could call these rules for base 256 numbers
the rule of 3s base 256, the rule of 5's base 256, the rule of 15's
base 256 etc.
> The above algorithm can be modified to use 16 bit numbers or 32 bit
> numbers instead of bytes.
For 16 bit numbers for the digit base the method can be applied
to factors of 2^16 -1, that is 3,5,17, and 257.
However step 3 cannot be applied to 17 or 257.
For 32 bit numbers you have the additional factor 2^16 + 1 (and the
numbers in its prime factorization but unfortunately 2^ 16 + 1 is
prime).
> It can also be modified to determine if the input number is divisible
> by 5,6,7,9,12, 14, or 15.
To do digits 7 or 9 one has to use base 64 digits instead of base
256.
(7 * 9 = 63 = 64 - 1).
> I believe divisibility by 13 can also be done but a different
> algorithm is needed.
>
> Ralph Boland
Ralph Boland
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
