If you want only a yes/no of divisibility by 3, a binary number and its reverse have the same divisibility. So an FSM can be made that reads the binary input starting at either end.
On 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.
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