Divisibility by 7
johndcook.com
johndcook.com
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.
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.
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://blog.vkistudios.com/index.cfm/2008/12/30/Regular-Expr...
So 12 isn't divisible by 7.
8631 = (7 * 1000)+(7 * 200)+(7 * 30)+(7 * 3)
So 8631 is divisible by 7.
Just keep guessing numbers that get you close and lopping off chunks.
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 - 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?
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).
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.
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?
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.
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.
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.
Express the number in base 7. If the last digit is 0, then the number is divisible by 7. I win!
Ex: 23456 mod 7 = 3+9+8 mod 7 = 6
* 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.
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.
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.)
Do primes come in degrees these days?
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.
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.)