7 ms·
Divisibility by 7 is a Walk on a Graph (2009)
- Jtsummers 11y agoWhenever I'm bored I either doodle or randomly recall and work out random tidbits of CS theory. One that I did recently was to work out the DFAs that determine the divisibility by various numbers in base 2. You end up with some neat patterns emerging with primes versus non-primes and other details. You also get the modulus for free if you number your states.
- escherize 11y agoWow that's awesome. I decided to re-implement divisiblity by 7 in this manner, since integrating with <horrible system> could wait a few minutes. :) https://gist.github.com/62553ded59ec7e289be6 https://gist.github.com/62553ded59ec7e289be6 Edit: s/division by 7/divisibility by 7 Thanks for pointing that out, omaranto!
- omaranto 11y agoThat is only a test for divisibility by 7, not 'division by 7', which is typically understood to compute the quotient.
- vikane 11y agoAmazing!
- askbypollankit 11y agoCan we build such state diagrams to check divisibility by other digits too?
- omaranto 11y agoYes, it's easy: to test divisibility by n make a graph with n verities labeled 0 through n-1; put black arrows from each vertex k to (k+1) mod n; and put white arrows from each k to 10k mod n. (That's for testing divisibility by n of numbers written in base 10; for others bases just replace the 10 above.)
- zodiac 11y agoYup! If we're trying to compute 3256 % 7 and we know that 325 % 7 = 3, then 3256 % 7 = (325 * 10 + 6) % 7 = (3 * 10 + 6) Computing 10 % 7, 20 % 7 etc generates the white arrows. I think unless we're checking divisibility by primes, though, the white and black arrows won't share edges
- Jtsummers 11y agoMy variation of this requires the input number (I) to be in binary, and read from leftmost digit to the right (most significant to least significant). Here's the table version of N = 2 through N = 4. N = 2 | state | 0 | 1 | |-------+---+---| | 0 | 0 | 1 | | 1 | 0 | 1 | N = 3 | state | 0 | 1 | |-------+---+---| | 0 | 0 | 1 | | 1 | 2 | 0 | | 2 | 1 | 2 | N = 4 | state | 0 | 1 | |-------+---+---| | 0 | 0 | 1 | | 1 | 2 | 3 | | 2 | 0 | 1 | | 3 | 2 | 3 | Each state represents a potential result of I mod N. Constructing it becomes mechanical, as in each state you can either double it (input digit D = 0) or double it + 1 (input digit D = 1). So in N = 4, determining the outputs of state 2: You can double it, and 4 mod 4 = 0, therefore the next state is 0; You can double it + 1, and 5 mod 4 = 1, therefore teh next state is 1. As to making this particular style graph, I'm currently playing around with it. EDIT: Hmm, left something out. You can convert this to any base, you just end up with more transitions out of each state (for a base B, you need B transitions). EDIT Again: omaranto has it correct for generating the article's style of graphs. Guess I should've refreshed before posting, but working it out myself was fun and successfully kept me from sleeping.
- c3534l 11y agoThis gave me an unreasonable amount of pleasure doing.
- sirsar 11y agoThis "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-golf-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.
- raverbashing 11y agoThe weird part is that the regex is much bigger than the DFA (but the DFA is not accepting the symbols directly, it's transforming them first It also seems that regexes can't express accepting expressions like AB where A is accepted by itself (considering AB is accepted), which in the DFA is implemented by sending it to the initial state
- robryk 11y ago> It also seems that regexes can't express accepting expressions like AB where A is accepted by itself (considering AB is accepted), which in the DFA is implemented by sending it to the initial state B* does that.
- newsignup 11y ago> a 12,701 character regex for divisibility by 7: I wonder if that's the optimal regex or can be reduced further using some rules[1] like the ones which we(humans) generally use to do it manually. [1]. https://www.math.hmc.edu/funfacts/ffiles/10005.5.shtml https://www.math.hmc.edu/funfacts/ffiles/10005.5.shtml
- ant6n 11y agoDon't regular expressions have minimal, canonical forms?
- stevebmark 11y agoWHY would you pick an example number that's not divisible by 7?! Academics facing the real world are the strangest creatures. Also this is really cool.
- dmerrick 11y agoThis didn't bother me. I assumed they picked that number _because_ it didn't work, to emphasize that only some numbers would end up back at the white node.
- stevebmark 11y agoClear, simple communication is a skill that takes time and practice to develop! Pointing out that you're not bothered by this strange example will hopefully be a good point for you to reflect on later.
- Johnny555 11y agoThank you, I was thinking the same thing. I followed the graph twice and thought I was doing it wrong before I mentally divided 325 by 7 to find that it's not a multiple of 7
- keithpeter 11y agoI agree the OA would be improved by two examples, one of each. An answer: Counter-examples are important in Maths. Anecdote: Oliver Sacks wrote about autistic twins [1] who could not speak or communicate well to people but who could perform prodigious feats of calculation, including factorising large pimes. Sacks sat with them with a table of prime numbers, and swapped some really large ones after which they took him seriously. Sacks took their reaction to his large primes as proof of their arithmetical ability. The mathematician John Conway (the game of life chap) was quoted on an online forum decades later as saying that Sacks should have suggested some large non-prime numbers as a test of the twins. I'm searching for a reference! [1] http://math-frolic.blogspot.co.uk/2013/02/prime-savants-fascinating.html http://math-frolic.blogspot.co.uk/2013/02/prime-savants-fasc...
- drfuchs 11y agoHere's another human-friendly scheme to test divisibility by 7 that I don't think is popularly known: Write down the number, then cross off the least significant digit, double it, and subtract that from what's left of the number. Repeat until you get zero or an obviously divisible-by-7 number, or not. Example: 325 becomes 32 - 10 = 22, which is obviously not divisibile by 7. Better example: 8638 -> 863 - 16 = 847 -> 84 - 14 = 70 -> 7 - 0 -> 7, so we have a winner. Learned this as a kid (forget where), but it took decades for me to realize why it obviously works.
- colinodell 11y agoSo why does this work?
- hcarvalhoalves 11y ago50 years from now this will be called "drfuchs last theorem"
- newsignup 11y agowith the scribble "but it took decades for me to realize why it obviously works" somewhere in the margins and stating that there wasn't enough room to write that down though..
- pervycreeper 11y ago21=3*7 you are subtracting multiples of 21, then dividing by 10, which is coprime with 7
- orbitur 11y agoThe examples subtracted 10, 16, etc... Those aren't multiples of 21.
- chadzawistowski 11y agoSince you scratched off the last digit, 10 is really 100, plus 5 for the digit you scratched off = 105. 105 is a multiple of 21.
- TeMPOraL 11y agoOh I still have nightmares of this. As others point out, you can use DFAs to determine divisibility by various numbers (base, well, anything you like). I remember spending a few hours banging my head against the desk, trying to figure out how it works with only a bunch of crappy net articles. But it is somewhat fun after you understand it.
- jhurwitz 11y agoFor a bit of an explanation, see David's follow-up blog post: http://blog.tanyakhovanova.com/2010/08/divisibility-by-7-is-a-walk-on-a-graph-ii-2/ http://blog.tanyakhovanova.com/2010/08/divisibility-by-7-is-...
- vinchuco 11y agoFor an explanation on the construction: http://math.stackexchange.com/questions/413296/how-does-the-divisibility-graphs-work http://math.stackexchange.com/questions/413296/how-does-the-...
- joeax 11y agoAnother quick way to check divisibility by 7 is to multiply each digit by 3^x where x is the place (right to left). Good way to check divisibility in your head and useful up to 4-5 digits. As an example, consider 413: 4x9 + 1x3 + 3 = 36 + 3 + 3 = 42 42 is divisible by 7 therefore 413 is too.
- Jtsummers 11y ago10 = 3 (mod 7) So this works because you're substituting the powers of 10 with powers of 3, and we're operating under mod 7 arithmetic. Conveniently, this can also be repeated like drfuchs' method if your numbers are too large to recognize as a multiple of 7 after the first pass. 413 => 4*9+1*3+3 = 42 => 4*3+2 = 14 => 1*3+4=7
- hardlianotion 11y agoWe used to call this casting out nines.
- zuxfer 11y agohelp me, i can't get it to work for 1603.
- psyklic 11y agoIt works. Follow: (1) 1 black then 1 white. (6) 6 blacks then 1 white. (0) 1 white. (3) 3 blacks then 1 white. And you end up at the bottom node, indicating it is divisible by 7.
- thaumasiotes 11y agoYou should be following the 1 white path before the n black paths, not afterwards. In particular, following "3 blacks then 1 white" in the last step, when the final digit is three, is an error; it will produce the wrong modulus for any number that is not divisible by 7. (1) 1 white then 1 black, ending up in state 1 (6) 1 white then 6 blacks, ending up in state 2 (0) 1 white then 0 blacks, ending up in state 6 (3) 1 white then 3 blacks, ending up in state 0 The graph keeps track of ((the number so far) mod 7); following a white arrow multiplies your total by 10, and following a black arrow increases your total by 1.
- sean2 11y agoI can see how you'd like to hold the order of operations correct for readability purposes (especially if the states were labeled with digits), but I don't see where psyklic's method could produce an error for the divisibility test. Your initial white doesn't change anything, since it brings you back to the starting node. Any whites after the the final digit either keep you on the starting node or keep you in the graph where.
- thaumasiotes 11y agoThe graph isn't just a divisibility test, it reports the remainder after division by seven. I specifically acknowledged that this error won't mutate a "divisible by 7" result into "not divisible by 7" (because any number that is divisible by seven will still be divisible by seven after multiplying it by ten), but in every other case it will give you the wrong answer. (e.g. "remainder 2" will mutate into "remainder 6".)
- gizmo686 11y agoI had some fun reverse engineering that. Here is my take at how it works. Label all of the nodes 0 through 6, starting with making the white node 0, and following the black arrows. We can consider each of these nodes to represent a congruence mod 7. Let n be the first digit of the number, and nXXX be the entire number. After we walk n nodes by following the black arrows, we arrive at the node n' = n MOD 7. Notice that n'XXX = nXXX MOD 7. More specifically, nXXX is divisible mod 7 if and only if n'XXX is divisible by 7. Let m be the second digit. At this point, we reduced the problem to testing n'mXX MOD 7. Notice that n'mXXX = (10n' + m)XX. [0] Notice that following the white arrow at an arbitrary node, k, is equivilent to following 10k black arrows. [1] This means that after following the white arrow, we have reduced the problem to mXX. At this point, we simply recurse to the first step until we are out of digits. [0] This construction is slightly improper, in that it involves a single "digit" having a value greater than 10. [1] This can be verified by considering the value of 10k MOD 7, and comparing it with the destination node.
- dools 11y agoAnother interesting feature of dividing by 7 is that the decimal repeats as: 0.142857 = 1/7 0.285714 = 2/7 0.428571 = 3/7 0.571428 = 4/7 0.714285 = 5/7 0.857142 = 6/7 you can see the first digit after the decimal point increases in numerical order through the available numbers in the pattern, the proceeds to repeat in the same order Some other prime denominators behave the same way. For example, 1/17th is 0.0588235294117647 and the first digit after the decimal point increases like 0,1,1,2,2,3,4,4,5,5,6,7,7,8,8,9 ... Where there are 2 of the same number in the sequence, the first time you encounter that number you start from it's first ocurrence so for example 3/17 is 0.2941176470588235 This makes for a pretty spooky party trick but I can tell you from experience it doesn't attract the opposite sex.
- chris_wot 11y agoSeems like something Euler should have already done :-) I jest, of course.
- Figs 11y agoI wrote a post on reddit with some code to generate diagrams with generalized divisibility testing the last time I saw this idea (about two years ago): https://www.reddit.com/r/math/comments/1p9g8t/start_at_the_bottom_pick_any_number_take_the/cd095x4 https://www.reddit.com/r/math/comments/1p9g8t/start_at_the_b... Copied here for the lazy: I wrote a small python script to generate DOT code for graphviz so that you can just input the base and the number to check division and automatically draw the graph. (The resulting graphs aren't as pretty as one made by a human, but it's kind of fun to poke around with it.) Here's the script: base = 10 divby = 7 print "digraph {" print " 0 [shape=doublecircle]" for i in xrange(0, divby): print " ", i, "->", (i+1)%divby print " ", i, "->", (base*i)%divby, "[arrowhead=empty]" print "}" Save it to a file such as `make_graph.py`. Then, as long as you have the graphviz binaries on path, you can render an image like: python make_graph.py > graph.dot dot -Tpng graph.dot -o out.png Here are some sample outputs: - [base = 3, divby = 11](http://imgur.com/cwUmnME http://imgur.com/cwUmnME) - [base = 10, divby = 7](http://imgur.com/O7GYw17 http://imgur.com/O7GYw17) - [base = 10, divby = 10](http://imgur.com/k6xC0CQ http://imgur.com/k6xC0CQ) - [base = 10, divby = 11](http://imgur.com/1SSXKcK http://imgur.com/1SSXKcK) - [base = 16, divby = 7](http://imgur.com/QZzSyva http://imgur.com/QZzSyva) Not all the edges are actually reachable -- e.g. base 10, divby 10 has a black edge from 9 to 0 even though you can't ever wrap around to 0 since `(10 * anything)%10` is zero -- so the biggest you can get to is 9, then when you follow the white edge for 9x you start over at zero... There may also be other edge cases I haven't thought of ;)
- dahart 11y agoThis exact state machine -- divisibility by 7 -- is one of my favorite state machines ever! It was a homework problem in college, and one of the few that stuck with me over the years. The implication of a DFA for divisibility by 7 is that it's easy (with practice) to figure divisibility by 7 in your head for arbitrarily long numbers as fast as someone can say them. Nice party trick! ;) I've also been having debates with people about whether divisibility testing in your head is a simpler operation than long division in your head. When you break it down carefully, long division in your head for a single digit divisor is very similar, and also surprisingly easy to do, the main difference might be simply having to remember quotient digits, and nothing more. I'm curious where the DFA for divisibility by 7 might have originally come from, but I'm pretty sure it was a homework problem in the text I used, "Elements of the theory of Computation" by Lewis and Papdimitriou, Prentice Hall, 1981.