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.