Comment by xyzzyz | Hacker News Reader

Comment by xyzzyz | Hacker News Reader

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

Great comment. Am I the only person waiting for someone to provide the regular expression intimated at above?

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...

If you want regular expressions for divisibility, here’s the little toy I made last time this came up on HN: http://s3.boskent.com/divisibility-regex/divisibility-regex....

You can do any number in any base up to 36 (subject to limitations of patience and available RAM, naturally).

The resulting regular expressions are not terribly friendly. You have to remember that converting a DFA to a regex can lead to exponential blow-up in size.

I wouldn't want to actually compute it, but here's one way you can do it:

Let R_i be an unknown regexp that matches base 10 expansion of numbers with residue i mod 7 (for simplicity, include the empty string --representing 0-- in the strings matched for R_0). We want R_0 and will get it from a system of equations for R_0, ..., R_6.

The key is that any string matched by, say (R_j)k is a number congruent to 10j+k mod 7, so we get the equation R_i = sum( R_j k ) + delta_i0 where

* the sum means union, i.e., operator | for regexes, and is taken over all 0<=j<=6 and 0<=k<=9 such that 10j+k = i mod 7, and

* delta_i0 is a term which is not there unless i=0 in which case it is equal to epsilon, (the language consisting solely of) the empty string.

You solve such a system by solving for one unknown at a time and substituting. An equation of the form R = RD | A, where R is one of the unknowns, and does not appear in either D or A, has solution R = AD*. You take that solution and plug it into all other equations, and repeat until you just get an equation for R_0. It's solution is the regex you want (except maybe you didn't want it to also match the empty string). Obviously this should not be done by hand.

http://codegolf.stackexchange.com/questions/3503/hard-code-g...

Reply on news.ycombinator.com