Re: [math-fun] Binary number divisible by 3? (was Re: FW: squares beginning with n)

* David Wilson <davidwwilson@comcast.net> [May 26. 2016 07:51]:

To tell if a binary numeral is divisible by 3: Repeatedly remove adjacent pairs of matching digits (00 or 11) until remaining digits are alternating. If number of 1's in remaining number a multiple of 3, so was original number.

All these recipes are consequence of the following. Let N be written in base B and D = B+1. Then N is divisible by D iff the alternating sum of over the digits of N is divisible by D. As far as I recall one obtains such rules by considering numbers as polynomials where the "free variable" is taken to be the base B (and the digits are the coefficients). One checks divisibility by "x - D" = B - D.

[...]