Hacker News new | past | comments | ask | show | jobs | submit login
Test for Divisibility by 13 (johndcook.com)
238 points by pmontra 7 days ago | hide | past | favorite | 46 comments

You might also like weighted digit sums.

I'll copy the example from german Wikipedia article [0] as you might generalize from that easier as when I would write it down in mathematical notation:

Here are the weights for 7:

    1 ≡ 1 (mod 7)
    10 ≡ 3 (mod 7)
    100 ≡ 2 (mod 7)
    1000 ≡ −1 (mod 7)
    10000 ≡ −3 (mod 7)
    100000 ≡ −2 (mod 7)
    1000000 ≡ 1 (mod 7)
    10^n ≡ a_n (mod 7)
Then multiply the weights with the digit on the respective position and sum up. Repeat if you like. If the resulting number is divisible by 7, you know that the initial number also was.



8x (-2) + 5x (-3) + 3x (-1) + 6x 2 + 2x 3 + 9x 1 = -16-15-3+12+6+9 = -7, therefore 853629 is divisible by 7.

[0] https://de.wikipedia.org/wiki/Quersumme#Gewichtete_Quersumme

Instead of remembering the weighted sequence, you can also compute it implicitly as you go (when reading the number from left to right). Example:

    ^ 8 (mod 7) is 1, remember that
     ^ 1 · 10 (mod 7) is 3, and 3 + 5 (mod 7) is 1, remember that
      ^ 1 · 10 + 3 (mod 7) is 6
       ^ 6 · 10 + 6 (mod 7) is 3
        ^ 3 · 10 + 2 (mod 7) is 4
         ^ 4 · 10 + 9 (mod 7) is 0
Hence 853629 (mod 7) = 0 and it is divisible by 7. The corresponding code would be

    def modulo(number, k):
        val = 0;
        for digit in str(number):
            val = (val * 10 + int(digit)) % k
        return val
Of course, you can apply the modulo within the intermediate calculations as well, so instead of multiplying by 10 you can e.g. multiply by 3 = 10 (mod 7) instead. The key idea is that you can go from one weight to the next by multiplying with 10 (mod 7), so if you sum some weighted digits you can update all the weights at once with a simple multiplication.

The advantage is that you only need a small amount of memory (a single number between 0 and 6), so this is a kind of general divisibility rule where you only have to do small calculations in your head.

If I may digress a bit into automata theory, this means that you can construct a finite state automaton that determines whether a number is divisible by 7 (or any other constant) by reading its digits from left to right. Additionally, if a finite state automaton can do something reading from left to right, there is another automaton doing the same thing but reading from right to left. This means that there is also a 'simple' divisibility rule when starting with the least significant digit, though it may be a bit harder to find.

Mind. Blown.

This is basically what also happens during long division! I marked the remainder of the previous operation in each line with a bracket (no italics in code formatting, sadly), appending another digit of the dividend behind them is the same operation as multiplying the 'remembered' number by 10 and adding the next digit to it:

    8 5 3 6 2 9  /  7  =  1 2 1 9 4 7; remainder 0
  - 7                       
   [1]5            How long division works:
  - 1 4   <-------     subtract largest possible multiple,     
   ----                 note remainder in next line, append
     [1]3               next digit from number at top, and 
    -   7               repeat until done. And make sure to
     ----               keep track of the result.
      - 6 3                 
        - 2 8
          - 4 9
             [0]  <= final remainder = 0, i.e. 7 is a divisor of the number
Thanks a lot for your comment, this was insightful!

I never thought about that! That definitely is an interesting connection.

This is essentially Horner's method for calculating the value of a polynomial. [1]

In your example, you calculate the value of the polynomial 8x^5+5x^4+3x^3+6x^2+2x^1+9 with x=10. The value is 853629, of course, but it you perform your calculation modulo 7, you have precisely followed Horner's method in the field F_7. To further simplify the calculation, note (as you did!) that 10 is congruent to 3 mod 7, so use x=3 instead of x=10.

[1] https://en.wikipedia.org/wiki/Horner's_method

That's much easier than the (separate) div 7 rule that this blog post links to: https://www.johndcook.com/blog/2010/10/27/divisibility-by-7/

Maybe not mechanically easier, but easier to remember.

Woah. That's very elegant and simple.

Interesting. I'll translate this bit from the entry:

One can also find periodical sequences for other natural numbers. E.g.,

* for 11, the sequence +1, -1, ...

* for 13, the sequence 1, -3, -4, -1, 3, 4, ...

For most divisors, it is not practical to test divisibility this way, as there are only few easily remembered weight sequences.

I came in the comments section with the intent of asking HN about generalized divisibility rules for any number N with any base B. Looks like you provided the goods.

You are welcome, I am glad I could help :)

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.

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

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.

A more formal treatment can be found in "Elementary Number Theory and its Applications", Kenneth H. Rosen, 3rd Ed, specifically Chapter 4, "Applications of Congruences".

The 7 * 11 * 13 = 1001 development in particular appears just after example 4.4 and is then generalized to arbitrary bases by theorem 4.3. For example to divide by five in octal, do the alternating sum trick on digits grouped in pairs, because 5 divides 8^2+1.

Though it quickly stops being useful for manual checks, Fermat's Little Theorem is a fun gizmo. It says for any prime `p` (say, 17) and base `a` not divisible by it (10), we have that `a^(p-1) % p == 1`. Put another way, so long as we meet the criteria (prime, doesn't divide base), we can form a divisibility test by summing blocks of `p-1` (16) digits and testing the result, just like the `3` case.

Further, since `p-1` is even we can take the square root of both sides (`a^((p-1)/2) % p == +/-1`) and use either the sum or alternating sum tricks with blocks half that size, depending on the sign of the final `1`.

This is pretty interesting especially since I just finished an assignment a couple of days ago for my proofs course that was all about proving the divisibility of large integers and the sums of their digits.

Modular arithmetic, pretty fun stuff even if i'm incredibly bad at it.

This brings back memories from my abstract algebra class in college when we had to derive similar rules. Of course I've completely forgotten how most of the theory works now.

Crazy how we forget the things we don't use regularly, eh? I used to love calculus in school, but now I doubt I remember but the basics of vasics

>A number is divisible by 2 if its last digit is divisible by 2.

How does this work when the last digit is 0?

Zero is divisible by any integer except by itself.

Thank you. Completely misread that.

0 is divisible by every integer.

Edit: Modified because the downvotes maybe didn't realize I am honestly asking a question here:

Take the divisible by 3 rule: digits add up to a number divisible by 3, then the original number is divisible by 3. But 144 will get you 9. What in number theory tells you that 9 is divisible by 3?

These algorithms all reduce the division problem into some fixed range. For instance, in the case of 3, we are able to reduce the divisibility of an arbitrary integer by 3 into the divisibility of a single digit number by 3. In the 13 case described in the article, we reduce the problem to a 3 digit number. The base case can then just be a lookup table.

As for how to generate the base table, recall that we say a divides n provided there exists some b such that ab = n. In this case we're talking about integers, although this is the definition for any ring.

Therefore, proving 3 divides 9 is as simple as noting that 3 * 3 = 9, and likewise we can prove 3 divides 6 by noting that 3 * 2 is 6.

Proving a lack of divisibilty is a little bit trickier. For this, you'll want to first prove the division algorithm which, in the case of the integers, says that for any two integers a and n, there exists unique integers b and r with abs(r) < abs(a) such that ab + r = n.

Given this, we can then note that, for instance, 7 = 3 * 2 + 1. Therefore 7 cannot be divisible by 3 as that would imply there exists some other integer b such that 7 = 3 * b + 0 contradicting that the integers from the division algorithm are unique.

You might then wonder: well, how do we know 3 * 2 is 6? Well, to stop these questions from recursing endlessly, we need to define the integers. One reasonable definition is "the initial element in the ring category" which gives us that the integers are a ring by definition. As such, we have axiomatically that there are integers 0 and 1, a commutative operation + with identity 0 that is closed under inverses, an associative operation * with identity 1, and that * distributes over +. If we then define 2 to be 1 + 1, 3 to be 1 + 1 + 1, and 6 to be 1 + 1 + 1 + 1 + 1 + 1, we can use distributivity to prove that 3 * 2 = 3 * (1 + 1) = (3 * 1) + (3 * 1) = 3 + 3 = 6.

Thanks, that's exactly the sort of explanation I was looking for.

Isn't the answer as simple as: the definition of multiplication (or division)? I mean: you can apply that definition also to the original numbers; these are just tricks to make it easier/faster.

  while (n > 9)
    n = sum_digits(n);

  return (n == 3 || n == 6 || n == 9);

Why won't Wordfence let me to see this website with Tor browser?

Interesting but what’s the reasoning to commit facts like this to memory when I have a calculator one swipe away?

The same type of reasoning that explains why it makes sense to create a calculator app instead of use one i.e. sometimes it's not the answer that matters rather the skills you learned to come up with the answer that you can now take with you to unsolved problems.

I think it is slightly different. Just rote memorization of the facts can be done, yes. However, these facts require a lot of mechanics of numbers to work. Such that the benefit is less from remembering the facts and more from working them.

Is akin to knowing the idea of how to drive a stick shift, and knowing how to drive a stick shift.

Because breaking out your calculator when you want to figure out whether you can divide 22 students evenly into groups of three is going to get you laughed at.

Divisibility by 13 is of course not as useful/applicable as divisibility by three, but the question is then more nuanced: "Why should I memorize this particular divisibility trick?"

If you know that house number 235 is on the odd side of the road, you've committed a divisibility fact to memory.

This involves less memory than knowing how to use your calculator app to check.

For the exam. After that most of us will quickly forget it.

That way other people can use it too.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact