Divisibility by 7 is a Walk on a Graph - how does it work?(blog.tanyakhovanova.com)
blog.tanyakhovanova.com
Divisibility by 7 is a Walk on a Graph - how does it work?
http://blog.tanyakhovanova.com/?p=262
7 comments
Great comment. Am I the only person waiting for someone to provide the regular expression intimated at above?
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.
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.
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.
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...
I also found a solution on stackoverflow: http://codegolf.stackexchange.com/questions/3503/hard-code-g...
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...
[deleted]
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:
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.
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
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.
jowair already said this [1], but here's a less concise explanation:
The black arrows implement the operation of adding one mod 7, the white arrows implement the operation of multiplying by ten mod 7. The decimal expansion of a number tells you how to build it out of the operations of adding 1 and multiplying by 10, for example, to get 321, start at 0 and then do the operations +1, +1, +1, x10, +1, +1, x10, +1. Of course, if you do the operations mod 7, by following the arrows in the graph, instead of getting your number you get its residue mod 7.
[1]: http://news.ycombinator.com/item?id=3909866
The black arrows implement the operation of adding one mod 7, the white arrows implement the operation of multiplying by ten mod 7. The decimal expansion of a number tells you how to build it out of the operations of adding 1 and multiplying by 10, for example, to get 321, start at 0 and then do the operations +1, +1, +1, x10, +1, +1, x10, +1. Of course, if you do the operations mod 7, by following the arrows in the graph, instead of getting your number you get its residue mod 7.
[1]: http://news.ycombinator.com/item?id=3909866
A quicker mnemonic for me is that the white arrows are multiplying by 3 mod 7, which is an equivalent operation to multiplying by 10 mod 7.
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.
And there are graphs going either way, either starting from most or least significant digit. (Take previous modulus, *10 mod N, + next digit mod N), or (Take previous modulus, + 10^(next digit) mod N)
I've been waiting decades for anyone to be interested in a divisible-by-7 test that works right-to-left. Only 7 states required:
#include <stdio.h>
int x[7][10] = {
/* 0 */ {0, 2, 4, 6, 1, 3, 5, 0, 2, 4},
/* 1 */ {5, 0, 2, 4, 6, 1, 3, 5, 0, 2},
/* 2 */ {3, 5, 0, 2, 4, 6, 1, 3, 5, 0},
/* 3 */ {1, 3, 5, 0, 2, 4, 6, 1, 3, 5},
/* 4 */ {6, 1, 3, 5, 0, 2, 4, 6, 1, 3},
/* 5 */ {4, 6, 1, 3, 5, 0, 2, 4, 6, 1},
/* 6 */ {2, 4, 6, 1, 3, 5, 0, 2, 4, 6}
};
int divisible_by_7(char *b)
{
char *p = b; while (*p) p++; // skip to NUL
int state = 0;
while (--p >= b)
state = x[state][*p-'0'];
return !state;
}
int main(int argc, char *argv[])
{
int i;
for (i = 1; i<argc; i++)
printf("%s is%s divisible by 7\n", argv[i], divisible_by_7(argv[i]) ? "" : "n't");
return 0;
}Would this help solve the ITA Software "luck sevens" puzzle? (http://www.itasoftware.com/careers/puzzle_archive.html) I never understood how to do that one except by brute force.
"Write a program to compute the sum of all the integers between 1 and 10^11 both divisible by seven and, when the decimal digits are reversed, are still divisible by seven."
"Write a program to compute the sum of all the integers between 1 and 10^11 both divisible by seven and, when the decimal digits are reversed, are still divisible by seven."
There's a sequence of numbers for jumping over all n-smooth numbers. The problem is that the sequences get very large very fast: http://alquerubim.blogspot.com.br/2011/12/candidatos-primos....
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