4 ms·
> For example, being able to tell if a number is divisible by 2 or 5 by only looking at the last digit. That still seems like it is generalizable to any base
by dtech 8y ago
> For example, being able to tell if a number is divisible by 2 or 5 by only looking at the last digit.
That still seems like it is generalizable to any base by taking prime factors of any base-n.
- CydeWeys 8y agoIt is, but there's nothing special about 2 or 5 except that they're factors of 10.
- schoen 8y agoThere's a stronger generalization: it's true of any divisor of the base (not just prime divisors and not just proper divisors). For example, it works for divisibility by 6 in base 12, or divisibility by 10 in base 10. (Also, the digital root test, where you add up the digits, works for any divisor that is also a divisor of the base minus 1, so for example hexadecimal has a digital root test for divisibility by 3, 5, or 15.)
- dmurray 8y agoAnd 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)