6 ms·

Techniques for Factoring Numbers in Your Head

218 points by exupero 9y ago

czbond 9y ago
I don't have anything exciting to add, except to say thanks for posting it. Math was my weaker spot in school and trying to shore that up.
- factoring_ta 9y ago
  Good luck! You're never too old.
DoreenMichele 9y ago
Tip: you only need to factor it to the midpoint. Factors occur in pairs. Identifying the smallest factors will automatically identify the largest. 100 is divisible by 2. 2x50=100 No need to wonder if 51-99 are factors. They aren't. 50 is your largest factor.
- eleusive 9y ago
  Indeed - you can even extend this idea to only identify factors less than or equal to the square root - all factors greater than this have a matching factor less than the square root.
  - DoreenMichele 9y ago
    You can also prime factor the larger factors. Once you have all the primes, you can build the other numbers. 50 = 2x5x5 So 100 = 2x2x5x5 You can build your other factors of 4,10, 20 and 25 by multiplying the subsets.
bumbledraven 9y ago
Doerfler's _ Dead Reckoning: Calculating Without Instruments _ (pages 47-73) deals extensively with this issue. https://archive.org/stream/deadreckoningcal00doer#page/46/mode/2up https://archive.org/stream/deadreckoningcal00doer#page/46/mo...
- dahart 9y ago
  Picked up a copy of that book a few years ago, I think because of a comment I read here on HN. It is fantastic for learning various mental and pencil/paper techniques. Having read it helped me out with a few problems on Project Euler.
mkl 9y ago
It looks like step 4 should say something like (edited): If b evenly divides a×r_i, where r_i is the current value, divide by b. If not, add or subtract p until the result is evenly divisible by b, then divide by b. And step 6 should loop back to step 4 and define r_i to be the "result". This method is very interesting and systematic, but it seems pretty complicated compared to ad hoc reasoning. E.g. 34 is a multiple of 17, so 680 must be too; 986-680 = 306, which is 34 away from 340, a multiple of 17, so 17 is a factor of 986.
- dahart 9y ago
  Yeah I was thinking one of the steps after the first one should probably mention a. :P The example clarified, but it looks like the steps might be both simpler and more clear by writing the formulas for each step.
- exupero 9y ago
  Yes, a step was missing. I've updated it to include multiplication by "a" and loop back to step 4. And yes, this is more complex than basic reasoning. It's an optimization to the original algorithm, and like most optimized algorithms, is less transparent.
dahart 9y ago
Long division is hard to do in your head, but to determine if a number is a factor, there's a technique in between long division and memorizing a graph walk that is probably easier to do mentally that either one (since you don't have to memorize a graph for each divisor). With "modulo division" you can calculate a running remainder in your head while consuming one digit at a time of the dividend, from left to right. It gets pretty easy with just a little practice. https://en.m.wikipedia.org/wiki/Short_division#Modulo_division https://en.m.wikipedia.org/wiki/Short_division#Modulo_divisi... The division by subtraction is fairly well known, of course, but it reminds me of the surprising square root by subtraction that I only learned about recently. It's probably too much to do mentally, but easy with pencil & paper. To compute the digits of the square root of n, set a = 5n, b = 5. Repeat: if a≥b, set a=a-b, add 10 to b. Then if a<b, add two zeroes to a, and add a zero to b just before the final digit (which will always be ‘5’). I had to code it up myself just to believe it would work. http://www.afjarvis.staff.shef.ac.uk/maths/jarvisspec02.pdf http://www.afjarvis.staff.shef.ac.uk/maths/jarvisspec02.pdf
- mkl 9y ago
  There's no graph-memorising in the linked method. Modulo division looks pretty good though.
- userbinator 9y ago
  The "square root by subtraction" seems like the same algorithm that can be "implemented" by hand relatively easily on early mechanical calculators: https://www.youtube.com/watch?v=K_c9-Y1ouww https://www.youtube.com/watch?v=K_c9-Y1ouww
  - dahart 9y ago
    What is this thing?? I totally have no use for it, and still I want one. I'm very not sure what it's doing, but it looks like a different algorithm to me; there are a surprising number of square root techniques. https://en.m.wikipedia.org/wiki/Methods_of_computing_square_roots https://en.m.wikipedia.org/wiki/Methods_of_computing_square_...
tempthrowaway23 9y ago
Great post, really enjoyed it.
Natsu 9y ago
> Given the number n and prime p, calculate a and b. a is p subtracted from the nearest multiple of 10. b is that same multiple of 10 divided by 10. This part threw me for a bit until I realized that numbers that end in 5 can't be prime, other than 5 itself. And I don't really need a rule to test divisibility by 5.
CurtMonash 9y ago
I factor numbers up to 3 or 4000 as my form of "counting sheep" when I want to relax and sleep. It's not hard. Obviously, you only need to check primes up to the square root of the number in question. 2, 3, 5 and 11 are easy to check. Beyond that, my main trick is to quickly reduce a divisibility check to a check on a smaller number. For example, if I want to know whether 2747 is divisible by 7, that's true if and only if 2040 is, which is divisible by 7 iff 204 is, which is divisible by 7 if 102 is, which is divisible by 7 iff 51 is, and it isn't. Alternatively, 2747 is divisible by 7 iff 2800-2747 = 53 is, which it isn't. To check 13, I might subtract off 2600 to get 147, then also 130 to get 17. Or I might have started by adding 13 to get 2760 and hence 276, then subtracted 260 or 26. To check 17 subtract it once to get 2730 and hence 273. Then add it to get 290 and hence 29. To check 19 subtract 1900 to get 847, then 38 to get 805. Divide by 5 to get 161, add 19, and we've pretty much gotten to "no". For 23 add it to 2747 to get 2770 and 277, then substract 230 to get 47. 2900 - 2747 = 153, which can only be divisible by 29 if it equals 29 x 7 (because else the last digit wouldn't be 3), which it doesn't. Similarly, 31 doesn't divide 353. 2747 - 37 = 2710, and now there's a special trick, because 37 divides 111. 271 - 111 = 136. 136 - 37 = 99, which 37 obviously doesn't divide. At 41 I'll just do a size check. 41 x 57 is too small, and 57 isn't prime anyway. 41 * 77 also couldn't work. So it's 41 x 67 or bust. That's 2400 + 280 + 60 + 7 ... and we have a winner! 2747 = 41 x 67. Checking the multiplication, (40+1) x (70-3) = 2800 + 70 - 120 - 3, which indeed works out to 2747.
- mkl 9y ago
  You should put spaces around your asterisks so they don't make italics (or use ×).
  - CurtMonash 9y ago
    Thanks. I generally have formatting problem on this site, so I appreciate all the help I can get. It's fixed or at least improved now.
    - zamber 9y ago
      Take a look at https://news.ycombinator.com/formatdoc https://news.ycombinator.com/formatdoc Note that code blocks are painful to read on mobile so don't overuse it on text with ridiculously long lines.
cerved 9y ago
[Math processing error]
factoring_ta 9y ago
Two things which help me in factoring in my head: To know if a number less than 100 is a prime, you just need to remember that 7 x 13 = 91. This is the only number than seems like it might be prime, but isn't. All other composite numbers are multiples of 2, 3, 5 or 11 (easy to check quickly) or 49, widely known to be 7 x 7. Secondly, if you are factoring large numbers, and you have quickly checked for division by 2, 3 and 5, you should then take the number modulo 1001. 1001 = 7 x 11 x 13, the next few primes, so you can use modulo 1001 to check for divisibility by all of these. It's easy to reduce modulo 1001, similarly to reducing modulo 11. 1000 is -1 modulo 1001, 1000000 is 1 modulo 1001, etc. So 31,415,926,535,897 = 31 - 415 + 926 - 535 + 897 mod 1001 These two tidbits are numerical 'coincidences', but they're also related. Remember how 7 x 13 = 91? Well 1 / 11 = 0.0909090909... so 1000 / 11 = 90.9090.., just below 91, and repeating every two digits. Add one one-thousandth of itself and you get 90.9999999 = 91.
dmichulke 9y ago
Slightly OT: > can I factor the current time faster than he can fall asleep? If your son falls asleep within 3 minutes, you might want to consider putting him to bed earlier, especially if his exhaustion is not based on lots of physical activity. Why? Because he must be really tired if he falls asleep like that which might be an indication of sleep deprivation.
peterburkimsher 9y ago
When I was in primary school, I had to memorise the "times tables". I realised that the digits of multiples of 9 that are under 100 always add up to 9. I was surprised when I discovered that other students didn't notice this. Others tables are easy: 10x (just add a 0), 5x (half of 10), 2x, 4x, 8x (keep multiplying by 2). That only leaves 3x, 6x, 7x, and 12x to memorise. Now I have a calculator watch, I don't need to remember the times tables. But when I was younger, it was very important to my teachers. I wish methods like this were taught instead of "just memorise it".
- dpwm 9y ago
  I was actually taught this in a small village primary school as a way to remember the 9 times table up to 90. I think we were also taught how to apply it quickly: If you want n * 9, the first digit is n - 1 and the second is 9 - (n - 1). Of course, it fails at 99. It wasn't until much later that I learnt that all multiples of 9 have the property of their digits adding up to multiples of 9 and that there exist proofs.
  - superflyguy 9y ago
    An easy way of lower multiples of nine is to hold your hands in front of you, and if you want to work out, say, 4 times 9 put down your forth finger and look at the number of fingers on each side of that finger...
- macintux 9y ago
  Another useful trick the other direction, which I'm sure is mentioned somewhere in the article or the comments but what the heck: if the sum of the digits of a number is divisible by 3, so is the original number itself. 123: 1 + 2 + 3 = 6, 6 rem 3 == 0, so 123 is cleanly divisible by 3. 123456789: sum is 45, 4+5 is 9, 9 rem 3 == 0, so 123456789 is divisible by 3.
- Scarblac 9y ago
  3 is easy, the sum of the digits is divisible by 3. So 6 is easy too, divisible by 3 and 2.
wolfi1 9y ago
I can only recommend "What is Mathematics" by Courant and Robbins, which has a great chapter about divisibility

218 points by exupero 9y ago

I don't have anything exciting to add, except to say thanks for posting it. Math was my weaker spot in school and trying to shore that up.

factoring_ta 9y ago
Good luck! You're never too old.

DoreenMichele 9y ago

Tip: you only need to factor it to the midpoint. Factors occur in pairs. Identifying the smallest factors will automatically identify the largest. 100 is divisible by 2. 2x50=100 No need to wonder if 51-99 are factors. They aren't. 50 is your largest factor.

eleusive 9y ago
Indeed - you can even extend this idea to only identify factors less than or equal to the square root - all factors greater than this have a matching factor less than the square root.
- DoreenMichele 9y ago
  You can also prime factor the larger factors. Once you have all the primes, you can build the other numbers. 50 = 2x5x5 So 100 = 2x2x5x5 You can build your other factors of 4,10, 20 and 25 by multiplying the subsets.

bumbledraven 9y ago

Doerfler's _ Dead Reckoning: Calculating Without Instruments _ (pages 47-73) deals extensively with this issue. https://archive.org/stream/deadreckoningcal00doer#page/46/mode/2up https://archive.org/stream/deadreckoningcal00doer#page/46/mo...

dahart 9y ago
Picked up a copy of that book a few years ago, I think because of a comment I read here on HN. It is fantastic for learning various mental and pencil/paper techniques. Having read it helped me out with a few problems on Project Euler.

mkl 9y ago

It looks like step 4 should say something like (edited): If b evenly divides a×r_i, where r_i is the current value, divide by b. If not, add or subtract p until the result is evenly divisible by b, then divide by b. And step 6 should loop back to step 4 and define r_i to be the "result". This method is very interesting and systematic, but it seems pretty complicated compared to ad hoc reasoning. E.g. 34 is a multiple of 17, so 680 must be too; 986-680 = 306, which is 34 away from 340, a multiple of 17, so 17 is a factor of 986.

dahart 9y ago
Yeah I was thinking one of the steps after the first one should probably mention a. :P The example clarified, but it looks like the steps might be both simpler and more clear by writing the formulas for each step.
exupero 9y ago
Yes, a step was missing. I've updated it to include multiplication by "a" and loop back to step 4. And yes, this is more complex than basic reasoning. It's an optimization to the original algorithm, and like most optimized algorithms, is less transparent.

dahart 9y ago

Long division is hard to do in your head, but to determine if a number is a factor, there's a technique in between long division and memorizing a graph walk that is probably easier to do mentally that either one (since you don't have to memorize a graph for each divisor). With "modulo division" you can calculate a running remainder in your head while consuming one digit at a time of the dividend, from left to right. It gets pretty easy with just a little practice. https://en.m.wikipedia.org/wiki/Short_division#Modulo_division https://en.m.wikipedia.org/wiki/Short_division#Modulo_divisi... The division by subtraction is fairly well known, of course, but it reminds me of the surprising square root by subtraction that I only learned about recently. It's probably too much to do mentally, but easy with pencil & paper. To compute the digits of the square root of n, set a = 5n, b = 5. Repeat: if a≥b, set a=a-b, add 10 to b. Then if a<b, add two zeroes to a, and add a zero to b just before the final digit (which will always be ‘5’). I had to code it up myself just to believe it would work. http://www.afjarvis.staff.shef.ac.uk/maths/jarvisspec02.pdf http://www.afjarvis.staff.shef.ac.uk/maths/jarvisspec02.pdf

mkl 9y ago
There's no graph-memorising in the linked method. Modulo division looks pretty good though.
userbinator 9y ago
The "square root by subtraction" seems like the same algorithm that can be "implemented" by hand relatively easily on early mechanical calculators: https://www.youtube.com/watch?v=K_c9-Y1ouww https://www.youtube.com/watch?v=K_c9-Y1ouww
- dahart 9y ago
  What is this thing?? I totally have no use for it, and still I want one. I'm very not sure what it's doing, but it looks like a different algorithm to me; there are a surprising number of square root techniques. https://en.m.wikipedia.org/wiki/Methods_of_computing_square_roots https://en.m.wikipedia.org/wiki/Methods_of_computing_square_...

tempthrowaway23 9y ago

Great post, really enjoyed it.

Natsu 9y ago

> Given the number n and prime p, calculate a and b. a is p subtracted from the nearest multiple of 10. b is that same multiple of 10 divided by 10. This part threw me for a bit until I realized that numbers that end in 5 can't be prime, other than 5 itself. And I don't really need a rule to test divisibility by 5.

CurtMonash 9y ago

I factor numbers up to 3 or 4000 as my form of "counting sheep" when I want to relax and sleep. It's not hard. Obviously, you only need to check primes up to the square root of the number in question. 2, 3, 5 and 11 are easy to check. Beyond that, my main trick is to quickly reduce a divisibility check to a check on a smaller number. For example, if I want to know whether 2747 is divisible by 7, that's true if and only if 2040 is, which is divisible by 7 iff 204 is, which is divisible by 7 if 102 is, which is divisible by 7 iff 51 is, and it isn't. Alternatively, 2747 is divisible by 7 iff 2800-2747 = 53 is, which it isn't. To check 13, I might subtract off 2600 to get 147, then also 130 to get 17. Or I might have started by adding 13 to get 2760 and hence 276, then subtracted 260 or 26. To check 17 subtract it once to get 2730 and hence 273. Then add it to get 290 and hence 29. To check 19 subtract 1900 to get 847, then 38 to get 805. Divide by 5 to get 161, add 19, and we've pretty much gotten to "no". For 23 add it to 2747 to get 2770 and 277, then substract 230 to get 47. 2900 - 2747 = 153, which can only be divisible by 29 if it equals 29 x 7 (because else the last digit wouldn't be 3), which it doesn't. Similarly, 31 doesn't divide 353. 2747 - 37 = 2710, and now there's a special trick, because 37 divides 111. 271 - 111 = 136. 136 - 37 = 99, which 37 obviously doesn't divide. At 41 I'll just do a size check. 41 x 57 is too small, and 57 isn't prime anyway. 41 * 77 also couldn't work. So it's 41 x 67 or bust. That's 2400 + 280 + 60 + 7 ... and we have a winner! 2747 = 41 x 67. Checking the multiplication, (40+1) x (70-3) = 2800 + 70 - 120 - 3, which indeed works out to 2747.

mkl 9y ago
You should put spaces around your asterisks so they don't make italics (or use ×).
- CurtMonash 9y ago
  Thanks. I generally have formatting problem on this site, so I appreciate all the help I can get. It's fixed or at least improved now.
  - zamber 9y ago
    Take a look at https://news.ycombinator.com/formatdoc https://news.ycombinator.com/formatdoc Note that code blocks are painful to read on mobile so don't overuse it on text with ridiculously long lines.

cerved 9y ago

[Math processing error]

factoring_ta 9y ago

Two things which help me in factoring in my head: To know if a number less than 100 is a prime, you just need to remember that 7 x 13 = 91. This is the only number than seems like it might be prime, but isn't. All other composite numbers are multiples of 2, 3, 5 or 11 (easy to check quickly) or 49, widely known to be 7 x 7. Secondly, if you are factoring large numbers, and you have quickly checked for division by 2, 3 and 5, you should then take the number modulo 1001. 1001 = 7 x 11 x 13, the next few primes, so you can use modulo 1001 to check for divisibility by all of these. It's easy to reduce modulo 1001, similarly to reducing modulo 11. 1000 is -1 modulo 1001, 1000000 is 1 modulo 1001, etc. So 31,415,926,535,897 = 31 - 415 + 926 - 535 + 897 mod 1001 These two tidbits are numerical 'coincidences', but they're also related. Remember how 7 x 13 = 91? Well 1 / 11 = 0.0909090909... so 1000 / 11 = 90.9090.., just below 91, and repeating every two digits. Add one one-thousandth of itself and you get 90.9999999 = 91.

dmichulke 9y ago

Slightly OT: > can I factor the current time faster than he can fall asleep? If your son falls asleep within 3 minutes, you might want to consider putting him to bed earlier, especially if his exhaustion is not based on lots of physical activity. Why? Because he must be really tired if he falls asleep like that which might be an indication of sleep deprivation.

peterburkimsher 9y ago

When I was in primary school, I had to memorise the "times tables". I realised that the digits of multiples of 9 that are under 100 always add up to 9. I was surprised when I discovered that other students didn't notice this. Others tables are easy: 10x (just add a 0), 5x (half of 10), 2x, 4x, 8x (keep multiplying by 2). That only leaves 3x, 6x, 7x, and 12x to memorise. Now I have a calculator watch, I don't need to remember the times tables. But when I was younger, it was very important to my teachers. I wish methods like this were taught instead of "just memorise it".

dpwm 9y ago
I was actually taught this in a small village primary school as a way to remember the 9 times table up to 90. I think we were also taught how to apply it quickly: If you want n * 9, the first digit is n - 1 and the second is 9 - (n - 1). Of course, it fails at 99. It wasn't until much later that I learnt that all multiples of 9 have the property of their digits adding up to multiples of 9 and that there exist proofs.
- superflyguy 9y ago
  An easy way of lower multiples of nine is to hold your hands in front of you, and if you want to work out, say, 4 times 9 put down your forth finger and look at the number of fingers on each side of that finger...
macintux 9y ago
Another useful trick the other direction, which I'm sure is mentioned somewhere in the article or the comments but what the heck: if the sum of the digits of a number is divisible by 3, so is the original number itself. 123: 1 + 2 + 3 = 6, 6 rem 3 == 0, so 123 is cleanly divisible by 3. 123456789: sum is 45, 4+5 is 9, 9 rem 3 == 0, so 123456789 is divisible by 3.
Scarblac 9y ago
3 is easy, the sum of the digits is divisible by 3. So 6 is easy too, divisible by 3 and 2.

wolfi1 9y ago

I can only recommend "What is Mathematics" by Courant and Robbins, which has a great chapter about divisibility