3 ms·

There's a similar test for divisiblity by 13: cross off the least significant digit, quadruple, and add to what's left. Example: 325 becomes 32 + 20 = 52 which

There's a similar test for divisiblity by 13: cross off the least significant digit, quadruple, and add to what's left. Example: 325 becomes 32 + 20 = 52 which is divisible by 13. Example: 8632 -> 863 + 8 = 871 -> 87 + 4 = 91 which is divisible by 13. It works because 39 = 40-1 is divisible by 13 (similarly to why the 7 test works because 21 = 20+1 is divisible by 7).

Jtsummers 11y ago
An equivalent test would be to use a factor of -9 instead of 4. 325 => 32 - 9 * 5 = 32 - 45 = -13 The method itself comes from the fact that what we're doing is really just modular arithmetic. Which has the wonderful property that, as long as all manipulations mod N don't fundamentally change the base we can keep repeating them. Similar to my mod 7 breakdown: AB = 0 (mod 13) 10*A + B = 0 (mod 13) 40*A + 4*B = 0 (mod 13) A + 4*B = 0 (mod 13) A - 9*B = 0 (mod 13) // because 4 = -9 (mod 13) This is neat. A similar construction should be doable for any number. EDIT: I have a rule of not questioning down votes, but many of my comments that get down voted have something disagreeable in them (well, I agree with them, but it's typically political/management style/economics/etc.). But how does a break down of modular arithmetic become worth down voting?
- nkurz 11y ago
  Oops. That makes more sense now that you point it out. I thought they were just little scrolling arrows, and never understood why they didn't work right. Sorry about that. (While it's a good general practice not to question downvotes, there are some cases that just leave you wondering what the other person was thinking. This is one of the explanations I've imagined, although usually I just assume big fingers on a tiny touchscreen.)
- madcaptenor 11y ago
  Doing it with -9 instead of +4 will terminate faster. But on the other hand one has to think about negative numbers. It's an interesting tradeoff. "A similar construction should be doable for any number." - yes, except 2 and 5. You just need to find a multiple of the number that's 1 more or less than a multiple of 10. In fact, we can even come up with a test for divisibility by 3 (or 9) this way: just add the last digit to the rest of the number repeatedly until you can tell if the result is divisible by 3 (or 9): 4752 -> 475+2 = 477 -> 47+7 = 54 -> 5+4 = 9 is divisible by 3 and 9 3752 -> 375+2 = 377 -> 37+7 = 44 -> 4+4 = 8 isn't divisible by 3 or 9 4755 -> 475+5 = 480 -> 48+0 = 48 -> 4+8 = 12 -> 1+2 = 3 is divisible by 3 but not 9. Of course this ends up being equivalent to the usual "add all the digits" test.
  - Jtsummers 11y ago
    Using the same approach I used to construct the formulation, divisibility by 2 and 5 actually just break down to the normal "is the last digit even" or "is the last digit 5 or 0" tests. We end up with: 10*A + B = 0 (mod 2) B = 0 (mod 2) and: 10*A + B = 0 (mod 5) B = 0 (mod 5) Of course, these are trivially small cases and we've all learned the patterns. An interesting case with N = 4, the quick method I learned in grade school was to look at the last two digits. But using the approach I've adopted here, you get something more complex: 10*A + B = 0 (mod 4) 2*A + B = 0 or 2*A - 3*B = 0 (mod 4) If we instead break N into ABC (A * 100 + B * 10 + C = N): 100*A + BC = 0 (mod 4) BC = 0 (mod 4) And we've got the method I learned in school. EDIT: Formatting.

Jtsummers 11y ago

An equivalent test would be to use a factor of -9 instead of 4. 325 => 32 - 9 * 5 = 32 - 45 = -13 The method itself comes from the fact that what we're doing is really just modular arithmetic. Which has the wonderful property that, as long as all manipulations mod N don't fundamentally change the base we can keep repeating them. Similar to my mod 7 breakdown: AB = 0 (mod 13) 10*A + B = 0 (mod 13) 40*A + 4*B = 0 (mod 13) A + 4*B = 0 (mod 13) A - 9*B = 0 (mod 13) // because 4 = -9 (mod 13) This is neat. A similar construction should be doable for any number. EDIT: I have a rule of not questioning down votes, but many of my comments that get down voted have something disagreeable in them (well, I agree with them, but it's typically political/management style/economics/etc.). But how does a break down of modular arithmetic become worth down voting?

nkurz 11y ago
Oops. That makes more sense now that you point it out. I thought they were just little scrolling arrows, and never understood why they didn't work right. Sorry about that. (While it's a good general practice not to question downvotes, there are some cases that just leave you wondering what the other person was thinking. This is one of the explanations I've imagined, although usually I just assume big fingers on a tiny touchscreen.)
madcaptenor 11y ago
Doing it with -9 instead of +4 will terminate faster. But on the other hand one has to think about negative numbers. It's an interesting tradeoff. "A similar construction should be doable for any number." - yes, except 2 and 5. You just need to find a multiple of the number that's 1 more or less than a multiple of 10. In fact, we can even come up with a test for divisibility by 3 (or 9) this way: just add the last digit to the rest of the number repeatedly until you can tell if the result is divisible by 3 (or 9): 4752 -> 475+2 = 477 -> 47+7 = 54 -> 5+4 = 9 is divisible by 3 and 9 3752 -> 375+2 = 377 -> 37+7 = 44 -> 4+4 = 8 isn't divisible by 3 or 9 4755 -> 475+5 = 480 -> 48+0 = 48 -> 4+8 = 12 -> 1+2 = 3 is divisible by 3 but not 9. Of course this ends up being equivalent to the usual "add all the digits" test.
- Jtsummers 11y ago
  Using the same approach I used to construct the formulation, divisibility by 2 and 5 actually just break down to the normal "is the last digit even" or "is the last digit 5 or 0" tests. We end up with: 10*A + B = 0 (mod 2) B = 0 (mod 2) and: 10*A + B = 0 (mod 5) B = 0 (mod 5) Of course, these are trivially small cases and we've all learned the patterns. An interesting case with N = 4, the quick method I learned in grade school was to look at the last two digits. But using the approach I've adopted here, you get something more complex: 10*A + B = 0 (mod 4) 2*A + B = 0 or 2*A - 3*B = 0 (mod 4) If we instead break N into ABC (A * 100 + B * 10 + C = N): 100*A + BC = 0 (mod 4) BC = 0 (mod 4) And we've got the method I learned in school. EDIT: Formatting.