Divisibility by 7 is a Walk on a Graph - how does it work?

Divisibility by any n is a walk on a graph with n nodes, each one representing one of the modulus equivalence classes 0 .. n-1.

This graph is just deterministic finite automaton[1] with some fancy rules to make it easier to remember and to draw less arrows. What this proves is that that when you look at natural numbers as a words over {0, 1, ..., 9} alphabet, numbers divisible by 7 form a regular language[2]. This method generalizes to divisiblity by any number, not just 7, though it requires some cunning to come up with a nice way of representing the DFA like in OP's post, without tens or hundreds of arrows.

Another cool thing in this is that existence of such graph implies existence of a regular expression testing divisibility by 7. Indeed, it's easy to check divisibility by 2 or 5 using regular expressions, it's /^.[star](0|2|4|6|8)$/ and /^.[star](0|5)$/, where [star] means star operator (HN markup changes it to italics). It's a bit less clear how to construct similar regular expression for 7, but if follow closely the proof of equivalence between regular languages and languages recognizable by finite state automata, you can reconstruct the regular expression checking the divisibility by 7 from OP's graph.

[1] - http://en.wikipedia.org/wiki/Deterministic_finite_automaton [2] - http://en.wikipedia.org/wiki/Regular_language

You asked "how does it work?" so let me answer that. How it works:

Okay, so the black arrows represent adding one, and the white arrows represent multiplying by ten. The circle that you see represents the fact that after we hit 7 when adding by one, we "loop around" to 0 again, because 7 has remainder 0 when divided by 7.

So we are constructing (in their example) 325 by saying:

    Instruction     | Number | Remainder
    start with 0.   |    0   |  0
    add 3.          |    3   |  3
    multiply by 10. |   30   |  2
    add 2.          |   32   |  4
    multiply by 10. |  320   |  5
    add 5.          |  325   |  3

Now the only thing you really need to know is that "multiply by 10" is only a function of the current remainder, it can never depend on the rest of the digits we've processed before in any other way.

To see this, just write out the number. The number is 7 k + r for some remainder r. Multiplying by 10 produces 70k + 10 r. Taking the remainder when you divide by 7 is just... (10 r) % 7, because the first term is divisible by 7. So you only need to keep track of the remainder.

In fact, 10 r is really 7r + 3r, and the 7r is also divisible by 7, which means that the white arrows really just multiply by 3. That is why 0 maps to 0, 1 maps to 3, 2 maps to 6, and 3 maps to 9 % 7 == 2.

I've written out the Regex for divisibility by 3 before, it's a bit of a beast. I've had a blog post half-finished for ages where I talked about just this thing, but I never got around to actually computing the re for divisibility by 7. Maybe this will provide the impetus...

On HN: http://news.ycombinator.com/item?id=1859007

I also found a solution on stackoverflow: http://codegolf.stackexchange.com/questions/3503/hard-code-g...