News for hackers. Stuff that matters.
Re:Divisibility by 7 is a Walk on a Graph - how does it work? by omaranto on Monday April 30, 2012 @02:33PM (#3910631)
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.

There are no comments on this comment yet.