5 ms·
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:
by waterhouse 16y ago
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.
- anigbrowl 16y agoIt 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?
- waterhouse 16y agoI 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).
- anigbrowl 16y agoI guess it depends on how each person's brain works. Long division seems to just unzip itself without any real effort on my part.
- jsc 16y agoThis is essentially Montgomery reduction, widely used in cryptographic implementations. http://en.wikipedia.org/wiki/Montgomery_reduction http://en.wikipedia.org/wiki/Montgomery_reduction