4 ms·
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
by 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 agoUsing 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.