[math-fun] mental factoring
so, just to make FH's point clearer, the amazing fact that 1001=7*11*13 allows you to check N for divisibility by 11, 13, or 7 all at once as follows. 1. compute N mod 1001 by subtracting the most-sig 3-digit block of N (assumed 6 digits long) from the least-sig 3-digit block. Then take absolute value. 2. Result is a 3-digit number abc. 3. Check divisibility by 11 by computing a-b+c and if result is 0 (or divisible by 11) then N was divisible by 11. Otherwise not. 4. You're on your own about dividing the 3-digit number by 7 and 13, but you could just memorize all multiples of 7 and 13 up to 999 for instant result or just subtract out some obvious multiple like 130, 260, and then you only need to memorize multiples of 13 up to 130. --- Also of course divisibility by 2 and 3 and 5 are trivial to check (for 3, sum of digits must be divisible by 3; for 5 and 2, the last digit alone reveals). Not bad. Personally, though, I think trying to go further is pretty stupid in the modern age. I used to know John Conway and he was very impressive, but his interest in doing this kind of mental-calculation trick to amaze people, actually struck me as the least-impressive thing about him.
4. You're on your own about dividing the 3-digit number by 7 and 13, but you could just memorize all multiples of 7 and 13 up to 999 for instant result or just subtract out some obvious multiple like 130, 260, and then you only need to memorize multiples of 13 up to 130.
it's easier than that. to find out if a number is divisible by 7, take the last digit, double it, and subtract it from the rest of the number. the new one is divisible by 7 when the old one is. to find out if a number is divisible by 13, take the last digit, multiply it by 4, and add it to the rest of the number. the new one is divisible by 13 when the old one is. erich
You can do a similar trick with 999=27*37 to "cast out" 37 pretty quickly. Other values of 10^n +/- 1 handle some other primes, but of course with diminishing returns. When bored I pretty much attempt to factor every number I see, or take square roots, or invert numbers (to decimal expansions). Anytime I put down a book I'm reading I calculate the decimal fraction of the book I've read, out to as many digits as possible; helps me fall asleep I guess. -tom On Fri, Dec 16, 2011 at 1:57 PM, Warren Smith <warren.wds@gmail.com> wrote:
so, just to make FH's point clearer, the amazing fact that 1001=7*11*13 allows you to check N for divisibility by 11, 13, or 7 all at once as follows.
1. compute N mod 1001 by subtracting the most-sig 3-digit block of N (assumed 6 digits long) from the least-sig 3-digit block. Then take absolute value.
2. Result is a 3-digit number abc.
3. Check divisibility by 11 by computing a-b+c and if result is 0 (or divisible by 11) then N was divisible by 11. Otherwise not.
4. You're on your own about dividing the 3-digit number by 7 and 13, but you could just memorize all multiples of 7 and 13 up to 999 for instant result or just subtract out some obvious multiple like 130, 260, and then you only need to memorize multiples of 13 up to 130.
---
Also of course divisibility by 2 and 3 and 5 are trivial to check (for 3, sum of digits must be divisible by 3; for 5 and 2, the last digit alone reveals).
Not bad. Personally, though, I think trying to go further is pretty stupid in the modern age. I used to know John Conway and he was very impressive, but his interest in doing this kind of mental-calculation trick to amaze people, actually struck me as the least-impressive thing about him.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
participants (3)
-
Erich Friedman -
Tom Rokicki -
Warren Smith