Hacker News Reader

Comment by drfuchs | Hacker News Reader

My preferred way to test divisibility by 13: Take the number, cross off the one's digit, but multiply that digit by 9, and take the product and subtract it from the modified original number. Repeat until you only have a digit or two, and what's left is a multiple of 13 iff the original number was.

Clearer as an example: Is 4173 divisible by 13? First iteration: 417 - (3 x 9) = 390. Second: 39 - (0 x 9) = 39. And 39 is divisible by 13, so 4173 is. (No worries if the last subtraction gives a negative result; same rule applies.)

To test for divisibility by 7, do exactly the same thing, but multiply the one's digit by 2 instead of 9. For 17, use 5. For 11, use 1.

I learned the divisible-by-7 trick from a book when I was a kid, but didn't figure out why it works, and how to generalize it, until I was embarrassingly adult. Left as an exercise for the reader.

View on HN

Who wants to multiply by 9, though? The version of the 13 test I've seen has you multiply by 4 and add instead:

4173 -> 417 + (3 x 4) = 429 -> 42 + (9 x 4) = 78, which is divisible by 13, so 4173 is.

Of course, these two tests work for the same reason. You're saying 10a + b is divisible by 13 iff a - 9b is, I'm saying 10a + b is divisible by 13 iff a + 4b is, and those differ by 13b.

But multiplying by 9 is so easy! You can check you’re right if (a) the first digit of the result is 1 less than the number you started with, and (b) the digits sum to 9

or multiply by 10 and subtract the number that you were trying to multiply by 9. I.E.: 12 x 9 = 12 x 10 - 12 = 108

That’s how I taught my daughter.

but that only works up to 10.. my method works for any number, and you could adapt it for x11... see below

Lucky for us, all digits are less than 10.

What is 23 x 9 with that trick?

Just going off the trick above would t it just be: 23 x 10 - 23 = 230 - 23 = 207...

I guess I’m confused what point you’re making?

I was talking about the grand-parent comment's method:

> You can check you’re right if (a) the first digit of the result is 1 less than the number you started with

The first digit of the result is 2 ... And the number that you started with is also 2, which is not 1 less... I guess I am not smarter then a 5th grader

Wow! You definitely are smarter than me, the gp, at least! You’re right that my claim isn’t right in general. Hell, not even past 10, I can now see!

I’m curious, how did you find that counterexample? I kind of ‘overfitted’ my mental model to the first 10 integers. But as a statistician I’m only in the business of being approximately right...! Nice catch.

23x9=207 starts with 20 which is 3 less than 23... 24x9=216, and 21 is 3 less than 24. 11x9=99 and 9 is 2 less than 11, 12x9=108 and 10 is 2 less than 12. So 0-9 are offset by 1, 10-19 are offset by 2, 20-29 offset by 3, 30-49 offset by 4?

ROT13: Xvyyvat gur ynfg qvtvg naq fhogenpgvat gjvpr gur ynfg qvtvg sebz jung'f yrsg vf whfg fhogenpgvat n zhygvcyr bs gjraglbar naq qvivqvat ol gra.

Well said!

It's obvious if you look at the version with 11 first.

I find the alternating digit sum method is easier to use for 11. They're competely equivalent, but your method makes it seem like you need to remember more state. For example, to test 678101 for divisiblity by 11 you'd go "678101, 67809, 6771, 676, 61, nope". With the alternating digits method you go "1, 1, 2, -6, 1, -5, nope" only dealing with one-digit numbers at every step. Maybe with practice you learn to ignore the leading digits until you need them.

For 11 the even faster method is to just do this:

    678101 -> 6-7+8-1+0-1 = 5 -> no bueno
    874632 -> 8-7+4-6+3-2 = 0 -> divides by 11

The exact same idea, but even less "state" needed as you put it.

Think you're doing the exact same as me but I started from the right. 1-0+1-7+8-6. This way you end up with the remainder mod 11, if you start from the left you sometimes need to flip the sign at the end.

Reply on news.ycombinator.com