The rule in the article can be written as a regular expression.
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.
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.
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:
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 - 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).
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:
N = a * 10^4 + b * 10^3 + c * 10^2 + d * 10^1 + e
and since 10 ≡ 1 (mod 9), this reduces to
N ≡ a * 1^4 + b * 1^3 + c * 1^2 + d * 1^1 + e (mod 9)
≡ a + b + c + d + e (mod 9).
If a+b+c+d+e < 10, then clearly that is the digital sum, and it's also N mod 9. If a+b+c+d+e ≥ 10, then we take the digital sum of that, which will again be the same as taking it mod 9. For a quick concrete example, the number 758 -> 7+5+8 = 20 -> 2+0 = 2, and 758 = 2 + 9 * 84, so it is 2 mod 9. Or we could say that 758 = 7 * 100 + 5 * 10 + 8 = 7 * 1 + 5 * 1 + 8 = 7+5+8, which is clearly the same number we got while taking the digital sum.
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?
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?
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.
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.
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.
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.
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.
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.)
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 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!
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.
* 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
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.
(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.)
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.