k_sze | You know how, for numbers expressed in base 10, there is a way to check whether an integer is divisible by 3 or 9 by recursively summing the digits? Is there a pattern to this trick that extends to other bases? Are there special requirements for this kind of trick to hold for a certain base? |
rindolf | k_sze: i think it is (b-1) |
rindolf | k_sze: you can also use a https://en.wikipedia.org/wiki/Finite-state_machine |
rindolf | k_sze: which works for any number base and modulo |
int-e | rindolf: right, 10_b = 1_b (mod b-1) |
k_sze | rindolf, 3 is not b-1 for base 10, so why does it hold? |
int-e | k_sze: it also works for divisors of b-1. |
int-e | 3 | 9. |
rindolf | k_sze: because 9 is divisible by 3 |
k_sze | interesting. So for base 16, I could check the divisibility of 15, 3, and 5 using this trick? |
int-e | Yes. |
int-e | And 1, but that's silly. |
* rindolf | divides himself by 1 and gets a remainder of 0 ;) |
* k_sze | divides himself by 1 and get NaN. |
rindolf | k_sze: heh |
* rindolf | divides k_sze 's mum by 1 and gets +\inf |
mawk | k_sze: you can find other tricks by just playing with the numbers in the relevant base |
mawk | like divisibility by 11 in base 10, for abcd you do d-c+b-a |
rindolf | mawk: in the general case one can generate an FSM for any given number base and modulo |
mawk | yes I'm sure |
int-e | or a regular expression |
int-e | which is a terrible idea ;) |
rindolf | int-e: heh |
int-e | (The FSM for divisibility by d will have up to d states (sometimes you can get away with fewer, notably for divisors of the base)... but regular expressions based on DFAs tend to be large.) |
rindolf | int-e: i see |
int-e | rindolf: It's not stopping people from doing that though: https://github.com/olligobber/DivisibilityRegex |
int-e | And I tried it for divisibility by 7 once myself (with computer help, of course) and ended up with 10789 characters, plus 4 for an initial '^(' and a final ')$'. |
mawk | ugly |
mawk | ...fedcba = a + 3b + 2c - d - 3e - 2f + ... |
mawk | like this ? |
rindolf | int-e: oooh, Haskell |
mawk | or is there something smarter |
int-e | rindolf: http://paste.debian.net/1161958/ is my regex :P |
int-e | sheer beauty ;) |
mawk | I mean mod 7 of course |
int-e | mawk: The usual rule for this is to split the number into groups of 3, and alternatingly add and subtract them. |
mawk | but with the coefficients I've put right |
mawk | or did I make a mistake |
int-e | mawk: they're right |
mawk | ah good |
int-e | mawk: but hard to remember, I guess. |
mawk | yeah nobody needs divisibility by 7 anyway |
mawk | 7 is not a pretty number |
int-e | cba - fed + ihg - lkj ... is easier to remember. And it also works for 11 and 13. |
int-e | (7*11*13 = 1001) |
nejimban | write N = 10*a + b, then N is divisible by 7 if and only if b - 2a is divisible by 7 |
mawk | ah yes |
mawk | b-4a you mean ? |
int-e | Nobody really cares because we have calculators and computers and pocket-sized distraction rectangles. |
mawk | lol |