Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Techniques for Factoring Numbers in Your Head

exupero.org

Post reply on HN
Print view View original

21–30 of 38 posts

Re: Techniques for Factoring Numbers in Your Head

#21

Post by vorg »

CurtMonash wrote: post #18

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 on…

> 2040 is, which is divisible by 7 iff 204 is

I don't follow that one.

To check whether 2747 is divisible by 7, I divide the multiple of 100 (i.e. 2700) by 50 (i.e. 54), add it to the remaining two digits, 47 (i.e. 101), then see if that's divisible by 7.

Re: Techniques for Factoring Numbers in Your Head

#22

Post by factoring_ta »

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.

Re: Techniques for Factoring Numbers in Your Head

#24

Post by ohwaitnvm »

vorg wrote: post #21
CurtMonash wrote: post #18

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 on…

> 2040 is, which is divisible by 7 iff 204 is I don't follow that one. To check whether 2747 is divisible by 7, I divide the multiple of 100 (i.e. 2700) by 50 (i.e. 54), add it to the remaining two digits, 47 (i.e. 101), then see if that's divisible by 7.

He reduced 2040 to 204 by dividing by 2 and 5 because he’s not interested in the factoring so much as just whether 7 is a factor.

Re: Techniques for Factoring Numbers in Your Head

#25

Post by CurtMonash »

mkl wrote: post #19
CurtMonash wrote: post #18

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 on…

You should put spaces around your asterisks so they don't make italics (or use ×).

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.

Re: Techniques for Factoring Numbers in Your Head

#26

Post by CurtMonash »

ohwaitnvm wrote: post #24
vorg wrote: post #21

Earlier quoted context omitted.

> 2040 is, which is divisible by 7 iff 204 is I don't follow that one. To check whether 2747 is divisible by 7, I divide the multiple of 100 (i.e. 2700) by 50 (i.e. 54), add it to the remaining two digits, 47 (i.e. 101), then see if that's divisible by 7.

He reduced 2040 to 204 by dividing by 2 and 5 because he’s not interested in the factoring so much as just whether 7 is a factor.

Correct.

If I'm checking for any prime other than 2 or 5 -- each of which has it own quick-check anyway via the last digit only -- it's always OK to drop trailing zeros.

Re: Techniques for Factoring Numbers in Your Head

#27

Post by dmichulke »

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.

Re: Techniques for Factoring Numbers in Your Head

#28

Post by CurtMonash »

CurtMonash wrote: post #18

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 on…

To be clear: This whole thing make massive use of the lemma "If prime p divides b but doesn't divide a+b, then it also doesn't divide a."

Re: Techniques for Factoring Numbers in Your Head

#29

Post by zamber »

CurtMonash wrote: post #25
mkl wrote: post #19

Earlier quoted context omitted.

You should put spaces around your asterisks so they don't make italics (or use ×).

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.

Take a look at 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.

Re: Techniques for Factoring Numbers in Your Head

#30

Post by peterburkimsher »

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".

Post reply on HN