Divisibility by 7(johndcook.com)
johndcook.com
Divisibility by 7
http://www.johndcook.com/blog/2010/10/27/divisibility-by-7/
12 comments
If you're interested in deterministic finite automata, you might enjoy the game Manufactoria:
http://www.kongregate.com/games/PleasingFungus/manufactoria
In the game, you deal with robots that come with a tape of binary digits (red and blue dots), and you can build a maze using conveyer belts, branch points (which read a dot from the front of the robot's tape), and things that write dots to the end of the tape. You have tasks to fulfill; they start with easy things like "Accept robots with no red dots", then "Accept robots with the same number of red and blue dots", then "Reverse the input string" (that one is unpleasantly hard), and so on.
In particular, there are some user-submitted levels, and one asks, "Accept if the input number is congruent to 3 mod 7." (Input string is interpreted as a binary number, read left-to-right normally, with blue = 1 and red = 0.) I have a pretty nice solution to that one.
http://www.kongregate.com/games/PleasingFungus/manufactoria
In the game, you deal with robots that come with a tape of binary digits (red and blue dots), and you can build a maze using conveyer belts, branch points (which read a dot from the front of the robot's tape), and things that write dots to the end of the tape. You have tasks to fulfill; they start with easy things like "Accept robots with no red dots", then "Accept robots with the same number of red and blue dots", then "Reverse the input string" (that one is unpleasantly hard), and so on.
In particular, there are some user-submitted levels, and one asks, "Accept if the input number is congruent to 3 mod 7." (Input string is interpreted as a binary number, read left-to-right normally, with blue = 1 and red = 0.) I have a pretty nice solution to that one.
Thanks. I tried it. The biggest challenge seems to be to make your layout planar.
I like the graph-way of dividing by 7. It's not intuitive and it's not easy to remember, but at least it looks cool.
http://imgur.com/wCE6z.png
Start at 0. Read the number left to right, and for each digit D, go D black edges. Whenever moving from digit to another, go a red edge.
http://imgur.com/wCE6z.png
Start at 0. Read the number left to right, and for each digit D, go D black edges. Whenever moving from digit to another, go a red edge.
How does this work?
It's a deterministic finite automaton (state machine) for dividing by seven. In effect, it's the graph expansion of a regular expression.
http://blog.vkistudios.com/index.cfm/2008/12/30/Regular-Expr...
http://blog.vkistudios.com/index.cfm/2008/12/30/Regular-Expr...
By the way, at http://slexy.org/view/s2QFWeNxZo is a (horrible) regular expression you can pop into "grep -xe" to test decimal numbers for divisibility by 7. (Found with a Haskell programm I wrote via conversion from the DFA.)
Here's what I generally do: Add or subtract multiples of 7 so that the final digit will be 0, drop the final 0 (i.e. divide by 10), and repeat. To illustrate:
37289 -> subtract 49 -> 37240 -> divide by 10 -> 3724 -> subtract 14 -> 3710 -> 371 -> subtract 21 -> 350 -> this is 35 * 10, and 35 is a multiple of 7.
The method described in the article is equivalent to my method, with the stipulation that one always subtracts, and that there is a mechanical process for picking the number to subtract (i.e. you multiply the number by 21).
37289 -> drop 9 from the end and subtract 18, which is equivalent to subtracting 189 and dividing by 10 -> 37289 - 189 / 10 -> 37100 / 10 -> 3710 -> drop 0 from end and subtract 0 -> 371 -> drop 1 from end, subtract 2, equivalent to subtracting 21 and dividing by 10 -> 371 - 21 / 10 -> 350 / 10 -> 35.
Advantages of my method:
a) This works with divisibility by any number at all (except for the factors of 2 and 5, which can be dealt with easily). For example, divisibility by 13:
594875 -> subtract 65 -> 594810 -> divide by 10 -> 59481 -> add 39 -> 59520 -> 5952 -> subtract 52 -> 5900 -> 59 -> not multiple of 13.
b) You don't need to remember any magic number to do it--in this case, you take the last digit, multiply it by the magic number -2, and add it to the remainder of the number. (For divisibility by a general m (coprime to 10), a magic number is any x such that x * 10 ≡ 1 (mod m). We see that adding 5 times the last digit would also work for divisibility by 7.)
c) It is quite elementary. It's based on the facts that 1) adding a multiple of 7 (or whatever your number is) won't change the divisibility, and 2) dividing by 10 won't change the divisibility.
37289 -> subtract 49 -> 37240 -> divide by 10 -> 3724 -> subtract 14 -> 3710 -> 371 -> subtract 21 -> 350 -> this is 35 * 10, and 35 is a multiple of 7.
The method described in the article is equivalent to my method, with the stipulation that one always subtracts, and that there is a mechanical process for picking the number to subtract (i.e. you multiply the number by 21).
37289 -> drop 9 from the end and subtract 18, which is equivalent to subtracting 189 and dividing by 10 -> 37289 - 189 / 10 -> 37100 / 10 -> 3710 -> drop 0 from end and subtract 0 -> 371 -> drop 1 from end, subtract 2, equivalent to subtracting 21 and dividing by 10 -> 371 - 21 / 10 -> 350 / 10 -> 35.
Advantages of my method:
a) This works with divisibility by any number at all (except for the factors of 2 and 5, which can be dealt with easily). For example, divisibility by 13:
594875 -> subtract 65 -> 594810 -> divide by 10 -> 59481 -> add 39 -> 59520 -> 5952 -> subtract 52 -> 5900 -> 59 -> not multiple of 13.
b) You don't need to remember any magic number to do it--in this case, you take the last digit, multiply it by the magic number -2, and add it to the remainder of the number. (For divisibility by a general m (coprime to 10), a magic number is any x such that x * 10 ≡ 1 (mod m). We see that adding 5 times the last digit would also work for divisibility by 7.)
c) It is quite elementary. It's based on the facts that 1) adding a multiple of 7 (or whatever your number is) won't change the divisibility, and 2) dividing by 10 won't change the divisibility.
It seems like you're doing it backwards?
37289 - 35000 = 2289 - 2100 = 189 - 140 = 49 / 7 = 0. It's just quick and dirty long division, but easy to do quickly. I'm perplexed about what advantage you see in starting at the small end?
37289 - 35000 = 2289 - 2100 = 189 - 140 = 49 / 7 = 0. It's just quick and dirty long division, but easy to do quickly. I'm perplexed about what advantage you see in starting at the small end?
I think you're asking why I think my method is better than the long division you mention. I've used that method too, in the past. Hmm... On paper, they seem pretty similar, but I think it is easier to answer the question "What multiple of 7 can we add or subtract from the final digit n to get 0?" (a memory lookup if you know single-digit multiplication and pay attention to final digits) than "What's the biggest multiple of 7 we can subtract from the leading digits mn?" (requires a couple of tries and comparisons).
If the first two digits happen to be "21" or "42", etc., a multiple of 7 by themselves, then I will probably notice and subtract that out. But that's fairly rare (1/7 assuming uniform distribution).
Overall, I find working from the small end more rewarding. Note that I never have to add or subtract anything larger than 7 x 5, and, 7/10 of the time, I don't have to add/subtract anything that isn't 7, 14, or 21. (I sometimes choose to add/subtract larger numbers to avoid carrying a hundreds digit.)
And note that I do this with 13 and 17 and so on as well. Then long division becomes even harder, whereas it's no harder to determine which multiple to add/subtract (as you just need to look at the last digits; 13 and 23 are like 3, and 17 is like 7), and maybe just a bit harder to calculate this multiple (e.g. last digit = 5 -> add 23 x 5 = 115; last digit = 9 -> subtract 23 x 3 = 69).
If the first two digits happen to be "21" or "42", etc., a multiple of 7 by themselves, then I will probably notice and subtract that out. But that's fairly rare (1/7 assuming uniform distribution).
Overall, I find working from the small end more rewarding. Note that I never have to add or subtract anything larger than 7 x 5, and, 7/10 of the time, I don't have to add/subtract anything that isn't 7, 14, or 21. (I sometimes choose to add/subtract larger numbers to avoid carrying a hundreds digit.)
And note that I do this with 13 and 17 and so on as well. Then long division becomes even harder, whereas it's no harder to determine which multiple to add/subtract (as you just need to look at the last digits; 13 and 23 are like 3, and 17 is like 7), and maybe just a bit harder to calculate this multiple (e.g. last digit = 5 -> add 23 x 5 = 115; last digit = 9 -> subtract 23 x 3 = 69).
I guess it depends on how each person's brain works. Long division seems to just unzip itself without any real effort on my part.
This is essentially Montgomery reduction, widely used in cryptographic implementations.
http://en.wikipedia.org/wiki/Montgomery_reduction
http://en.wikipedia.org/wiki/Montgomery_reduction
Also interesting is division by 7 resulting in a decimal.
1/7= .142857 repeating
2/7= .285714 rep
3/7= .428571 rep
4/7= .571428 rep
5/7= .714285 rep
6/7= .857142 rep
It's the same string of six digits, the only difference is which digit you start at.
1/7= .142857 repeating
2/7= .285714 rep
3/7= .428571 rep
4/7= .571428 rep
5/7= .714285 rep
6/7= .857142 rep
It's the same string of six digits, the only difference is which digit you start at.
My reaction to the above link is "lolwut". The page talks about the fact that the digital sums ("horizontal addition") of the powers of 2 form a repeating sequence (1,2,4,8,7,5), and proceeds to call this "the MATHEMATICAL FINGERPRINT OF GOD".
I can sympathize with people who look at the whole beautiful structure of mathematics and see the touch of God, but the premise of that page seems to be that this particular phenomenon--by itself--is huge and revolutionary and supernatural. In fact, a student of modular arithmetic would see it as fairly trivial. Two observations suffice to explain it:
1. The digital sum of a decimal integer is just that integer mod 9. (This gives us, as a special case, the divisibility rule for 9: N is divisible by 9 iff its digits add to a multiple of 9.) To illustrate with five digits, the number N = abcde (base 10) is equal to:
2. The powers of 2 mod 9 are periodic. (In general, the powers of N mod M are periodic, for any integers N and M.) Specifically, they are: 1, 2, 4, 8, 16 ≡ 7 (mod 9), 14 ≡ 5 (mod 9), 10 ≡ 1 (mod 9), and we are back at 1. This is exactly the "1,2,4,8,7,5" sequence that page talks about.
So, the above page talks about an elementary result of modular arithmetic as though it, by itself, were some logic-defying mystery. Seems pretty dishonest to me. Maybe it's a joke site. I saw a donation link, so maybe these guys are successful trolls.
I'm a bit curious as to the motives of the parent commenter. You seem to be a long-time member of HN (account is more than 2 years old). Was it a joke, or did you suspect something fishy but didn't know what it was and posted it here hoping someone would explain it for you, or did you actually take the author at his word, or what?
I can sympathize with people who look at the whole beautiful structure of mathematics and see the touch of God, but the premise of that page seems to be that this particular phenomenon--by itself--is huge and revolutionary and supernatural. In fact, a student of modular arithmetic would see it as fairly trivial. Two observations suffice to explain it:
1. The digital sum of a decimal integer is just that integer mod 9. (This gives us, as a special case, the divisibility rule for 9: N is divisible by 9 iff its digits add to a multiple of 9.) To illustrate with five digits, the number N = abcde (base 10) is equal to:
N = a * 10^4 + b * 10^3 + c * 10^2 + d * 10^1 + e
N ≡ a * 1^4 + b * 1^3 + c * 1^2 + d * 1^1 + e (mod 9)
≡ a + b + c + d + e (mod 9).
2. The powers of 2 mod 9 are periodic. (In general, the powers of N mod M are periodic, for any integers N and M.) Specifically, they are: 1, 2, 4, 8, 16 ≡ 7 (mod 9), 14 ≡ 5 (mod 9), 10 ≡ 1 (mod 9), and we are back at 1. This is exactly the "1,2,4,8,7,5" sequence that page talks about.
So, the above page talks about an elementary result of modular arithmetic as though it, by itself, were some logic-defying mystery. Seems pretty dishonest to me. Maybe it's a joke site. I saw a donation link, so maybe these guys are successful trolls.
I'm a bit curious as to the motives of the parent commenter. You seem to be a long-time member of HN (account is more than 2 years old). Was it a joke, or did you suspect something fishy but didn't know what it was and posted it here hoping someone would explain it for you, or did you actually take the author at his word, or what?
You can generate rules like these for arbitrary integers/primes(much easier than trying to remember them in my opinion). Take 41.
Example: 1476 is divisible by 41? 147 - 4 * 6 = 123. 12 - 4 * 3 = 0. Yes.
Example: 3321 is divisible by 41? 332 - 4 * 1 = 328. 32 - 4 * 8 = 0. Yes
What's the rule? Take the last digit off, multiply by 4 and subtract.
How to find the rules is left as an exercise.
Example: 1476 is divisible by 41? 147 - 4 * 6 = 123. 12 - 4 * 3 = 0. Yes.
Example: 3321 is divisible by 41? 332 - 4 * 1 = 328. 32 - 4 * 8 = 0. Yes
What's the rule? Take the last digit off, multiply by 4 and subtract.
How to find the rules is left as an exercise.
I usually just use a calculator.
Sorry, that's gonna sound rude, but the comments got me thinking.
In all seriousness, are we ever that far from a calculator? I'm sure just about every cell phone has one built in. I understand the importance of a fundamental understanding of mathematics, but at some point do we shift the approach?
Novelty vs. practicality.
Sorry, that's gonna sound rude, but the comments got me thinking.
In all seriousness, are we ever that far from a calculator? I'm sure just about every cell phone has one built in. I understand the importance of a fundamental understanding of mathematics, but at some point do we shift the approach?
Novelty vs. practicality.
Even sitting at a computer, if I can do a calculation in my head, it's usually faster than attempting to do it with a calculator and it usually allows me to keep the mental flow of whatever it is that I'm doing at the moment.
Agreed. I placed my comment after reading waterhouse's comment (http://news.ycombinator.com/item?id=1852464) which on first read seemed like a lot of effort.
The counter argument (to my snide calculator comment) is that we become overly dependent on helpers.
There's a story about a young person standing next to their locked car in a shopping center parking lot. The battery in their key fob had gone dead. Seemingly locked out, the young car owner called dad for help. Dad sighed and said to use the damn key.
There's a story about a young person standing next to their locked car in a shopping center parking lot. The battery in their key fob had gone dead. Seemingly locked out, the young car owner called dad for help. Dad sighed and said to use the damn key.
This wouldn't work with a lot of cars. It's often the case that if you lock with a fob, you must open with a fob, but if you lock with your key you can open with either the fob or the key.
This method is useful and calculator is completely useless when you solve a problem in number theory -- for instance, you may want to prove that for every natural number, some P(n) implies some Q(n), and it may be easier to prove that P(n) implies divisibility by 7, which in turns implies Q(n). You cannot enter n into a calculator, you know.
Good point. I keyed into the method ("For example, start with 432. Split into 43 and 2. Subtract 4 from...") more so than the theory of the original article. It reminded me of these wacky (ingenious?) shortcuts for doing basic math that I recall reading about. Sorry no reference on those. As far as I remember, they involved some form of shifting numbers around, transposing digits, drawing grids, etc. These were before calculators (er, phones) were in every pocket. I think calculators were just starting to show up on snazzy watches at the time I was learning these math shortcuts.
(warning: funny one)
Express the number in base 7. If the last digit is 0, then the number is divisible by 7. I win!
Express the number in base 7. If the last digit is 0, then the number is divisible by 7. I win!
More seriously, if you consider that the series 10^0, 10^1, 10^2, 10^3, etc. in modulo 7 runs as 1, 3, 2, -1, -3, -2, (loop with period 6), the remainder upon dividing a decimal number FEDCBA by 7 = the remainder on dividing (A-D) + 3(B-E) + 2(C-F) by 7.
Ex: 23456 mod 7 = 3+9+8 mod 7 = 6
Ex: 23456 mod 7 = 3+9+8 mod 7 = 6
Clever but most people won't remember these tricks. I for one would appreciate a refresher on the other divisibility rules/tricks.
I do math contests competitively, so I remember these things. Here are some rules:
Divisibility by 2: Last digit is divisible by 2 (0, 2, 4, 6, or 8).
Divisibility by 3: Sum of digits is divisible by 3. (You can repeatedly sum the digits until the sum is small enough to manage easily.)
Divisibility by 4: Last two digits are divisible by 4 (00, 04, 08, 12, ...). If you don't know your multiples of four, you can divide the two digits by 2 and then see if it's even.
Divisibility by 5: Last digit is divisible by 5 (0 or 5).
Divisibility by 6: Divisible by 2 and by 3. (Works similarly for all composite numbers, of course. Like 10, 14, 15, etc. Make sure the factors you're checking are relatively prime (share no common factors), or it won't work. For example, divisibility by 2 and 6 does not imply divisibility by 12.)
Divisibility by 8: Last three digits are divisible by 8 (000, 008, 016, ...). Probably faster to divide the last three by 2 at least once then check divisibility by 4.
Divisibility by 9: Sum of digits is divisible by 9. (You can repeatedly sum the digits until the sum is small enough to manage easily.)
Divisibility by 11: Alternating sum of digits is divisible by 11. (Almost always turns out to be -11, 0, or 11. Example: 66374. 6 - 6 + 3 - 7 + 4 = 0, so 66374 is divisible by 11.)
Divisibility by 2: Last digit is divisible by 2 (0, 2, 4, 6, or 8).
Divisibility by 3: Sum of digits is divisible by 3. (You can repeatedly sum the digits until the sum is small enough to manage easily.)
Divisibility by 4: Last two digits are divisible by 4 (00, 04, 08, 12, ...). If you don't know your multiples of four, you can divide the two digits by 2 and then see if it's even.
Divisibility by 5: Last digit is divisible by 5 (0 or 5).
Divisibility by 6: Divisible by 2 and by 3. (Works similarly for all composite numbers, of course. Like 10, 14, 15, etc. Make sure the factors you're checking are relatively prime (share no common factors), or it won't work. For example, divisibility by 2 and 6 does not imply divisibility by 12.)
Divisibility by 8: Last three digits are divisible by 8 (000, 008, 016, ...). Probably faster to divide the last three by 2 at least once then check divisibility by 4.
Divisibility by 9: Sum of digits is divisible by 9. (You can repeatedly sum the digits until the sum is small enough to manage easily.)
Divisibility by 11: Alternating sum of digits is divisible by 11. (Almost always turns out to be -11, 0, or 11. Example: 66374. 6 - 6 + 3 - 7 + 4 = 0, so 66374 is divisible by 11.)
Seeing this list of silly things one might find useful in high school math contests made me nostalgic for those days...
I find this kind of things extremely handy in my everyday job. Especially in meetings, since often you are forced to do mental arithmetic to estimate the magnitude of a parameter, etc. Abusing the calculator can put your brain in poor shape, just like muscles!
Seriously? You use divisibility tests to make estimations? I hope nothing much is riding on those estimates...
Silly? Some people do math for a living.
I do math for a living. Needing to now whether a small integer is divisible by 7 rarely comes up. And when it dos we tend to let dumb machines handle the easy stuff, leaving humans free to think.
Those people don't get paid by the hour, so they use a calculator :)
They're not that silly actually.
Division is the most 'complicated' of the arithmetic operations and if you rely on doing sums in your head frequently then knowing such shortcuts can speed up the calculations considerably.
It also helps in checking results of other calculations.
Division is the most 'complicated' of the arithmetic operations and if you rely on doing sums in your head frequently then knowing such shortcuts can speed up the calculations considerably.
It also helps in checking results of other calculations.
I know:
* 2 - if it ends in 0,2,4,6,8, it's divisible by 2
* 3 - if the sum of the digits is divisible by 3, so is the number
* 4 - Ignore everything but the last 2 digits. If the last 2 digits make a number that's divisible by 4, the whole number is (eg. anything ending in 52 is divisible by 4 because 52 is divisible by 4)
* 5 - If it ends in 0 or 5, it's divisible by 5.
* 6 - do an and of the 2 and 3 tests.
* 8 - Same as the 4 test, only last 3 digits.
* 9 - same as 3, only the digit sum needs to be divisible by 9 instead of 3
* 10 - If it ends in 0, it's divisible by 10.
So I guess the only one I don't know is 11.
* 2 - if it ends in 0,2,4,6,8, it's divisible by 2
* 3 - if the sum of the digits is divisible by 3, so is the number
* 4 - Ignore everything but the last 2 digits. If the last 2 digits make a number that's divisible by 4, the whole number is (eg. anything ending in 52 is divisible by 4 because 52 is divisible by 4)
* 5 - If it ends in 0 or 5, it's divisible by 5.
* 6 - do an and of the 2 and 3 tests.
* 8 - Same as the 4 test, only last 3 digits.
* 9 - same as 3, only the digit sum needs to be divisible by 9 instead of 3
* 10 - If it ends in 0, it's divisible by 10.
So I guess the only one I don't know is 11.
11 = add the first, third, fifth, etc.. digits, if the sum matches that for the second, fourth, sixth, etc.. then the number is divisible by 11.
Not quite:
5060 is an exception to your rule.
As described before, if (even digit sum) - (odd digit sum) is divisible by 11, then the number is divisible by 11.
5060 is an exception to your rule.
As described before, if (even digit sum) - (odd digit sum) is divisible by 11, then the number is divisible by 11.
If you are not careful you will learn something new. Thanks for the tip.
The Wikipedia has a good article:
http://en.wikipedia.org/wiki/Divisibility_rule
http://en.wikipedia.org/wiki/Divisibility_rule
Here's how to divide by 3: http://www.math.dartmouth.edu/~doyle/docs/three/three.pdf
If the last two digits are divisible by four, the entire number is divisible by four. For instance: 62857724. 24 is divisible by four, so the whole thing is.
You may want to post your jobs at
http://www.hackernewsjobs.com/
(Since last time people requested that I not cross post things from here, I am not going to do that, but you can email me (in profile) to do so, or post directly.)
http://www.hackernewsjobs.com/
(Since last time people requested that I not cross post things from here, I am not going to do that, but you can email me (in profile) to do so, or post directly.)
slightly different alorithm:
http://www.cut-the-knot.org/blue/div7-11-13.shtml
http://www.cut-the-knot.org/blue/div7-11-13.shtml
-n = -10a-b ~ -3a -b ~ -6a -2b ~ a - 2b mod 7
And in general for every number m and base b you can build a finite automata that gives you x mod m for numbers x expressed as a string of digits in base b. The accepting automaton that accepts in case of x mod 7 = 0 for base 10 is just a special case and gives you the regular expression mentioned above.
I am working on the regular expression for 7. In the meantime, look at this regular expression for divisibility by 3 (http://blog.vkistudios.com/index.cfm/2008/12/30/Regular-Expr...). The author shows his work.