Divisibility by 7 is a Walk on a Graph (2009)
This "walk on a graph" is known formally as a Deterministic Finite Automata. One of the interesting results of automata theory is that every FA has an equivalent regular expression (a subset of the "regexps" in most modern programming languages).Where is this going? Behold, a 12,701 character regex for divisibility by 7: http://codegolf.stackexchange.com/questions/3503/hard-code-g...This doesn't use any recursive features (it is a real Regular Expression in the theoretic sense) so it can be checked in linear time.