On Tue, May 24, 2016 at 6:10 PM, Keith F. Lynch <kfl@keithlynch.net> wrote:
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.
While it's true that the original number is divisible by 3 just if you have a number of remaining 1's that's a multiple of 3, it's not true that the number of 1's remaining is 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.
Counterexample: 2: 10. one 1 left, but it's 3-remainder is 2, not 1. In general, your rule is correct if there are an even number of 0's after the final 1, but if there are an odd number of 0's after the final 1, you have to subtract the number of 1's from 3 to get the remainder mod 3. Andy