3 ms·
And the less well known "add and subtract alternative digits" works for dividing by 11, that is, the base plus one, in any base. And for any divisors of 11.
by dmurray 8y ago
And the less well known "add and subtract alternative digits" works for dividing by 11, that is, the base plus one, in any base. And for any divisors of 11.
- QuercusMax 8y agoYou mean any divisors of [base + 1], right?
- dmurray 8y agoYes.
- taejo 8y agoAnd much more generally, "numbers divisble by n written base b" is a regular language decidable by an n-state DFA (and thus in linear time, looking at each digit exactly once). And see https://blog.plover.com/math/divisibility-by-7.html https://blog.plover.com/math/divisibility-by-7.html for a state machine that's even simpler (you only need edges for +1 and ×b, rather than +d×b for each digit d)