On 2016-05-25 06:41, Marc LeBrun wrote:

...

="Joerg Arndt" <arndt@jjj.de> For every base b and every (tentative) divisor d one can obtain a periodic sequence of weights such that the weighted sum of digits tells whether a base-b number is divisible by d.

Yes, I recall working out a similar thing some years ago, and being amused that one could reasonably easily mentally test for divisibility by, say, 17 or 19 (which may come in handy for factoring the number on my alarm clock).

As a kid I encountered "The Trachtenberg Method of Speed Mathematics" which espouses a bunch of special-case methods for rapidly multiplying by specific small d. The divisibility tests here are sort of related.

It's kind of interesting that this weighted-summing works LSB-to-MSB, the opposite of naïve long division.

As I think ACW mentioned long ago, base 10 mod 7 works LSD-to-MSD-to-LSD: First, convert to base 100 (LSD-to-MSD), optionally reducing the bidigits mod 7. Then MSD-to-LSD, double what you have and add the next digit, again mod 7 ad libitum. E.g., 2016 -> 40+16 -> 5+2 -> 0 Of course you can do 7, 11, and 13 simultaneously using base 1000 instead of 100, and left-to-right subtracting what you have from the next tridigit. This gets you mod 1001. So all we need is a slick three digits mod 13. --rwg