The same trick that works in base 10 also works in base 4. So just group the bits into pairs and add them, then repeat on the result until the sum is less than 4. If the sum is divisible by 3 (i.e., if the sum is 3 (or 0, if the original number was 0)), then the number is divisible by 3. Otherwise it isn't. Example: 101110001 (369) -> 1 + 01 + 11 + 00 + 01 = 110 (6) -> 110 (6) -> 1 + 10 = 11 (3) Answer: yes I think this is an n*log(n) algorithm where n is the number of bits, so log(v)*log(log(v)) where v is the value. Tom Keith F. Lynch writes:
Dan Asimov <dasimov@earthlink.net> wrote:
Zak, good question: Is there a quick way to detect multiples of 3 expressed in base 2 ???
Replace any pairs of 1s that have an even number (possibly 0) of 0s between them and that have no other digits between them, with 0s. For instance 11->00, 1001->0000, 100001->00000.
Repeat the above as many times as possible. Then discard any remaining 1s three at a time. The number of 1s left will be the original number's remainder when divided by 3.
Examples:
2015: 11111011111 -> 11111011100 -> 11111010000 -> 11100010000 -> 10000010000. Two 1s left, so its 3-remainder is 2.
2016: 11111100000 -> 11110000000 -> 11000000000 -> 0. Divisible by 3.
2017: 11111100001 -> 11110000001 -> 11000000001 -> 1. One 1 left, so its 3-remainder is 1.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun