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

31–38 of 38 posts

Re: Techniques for Factoring Numbers in Your Head

#31

Post by dpwm »

peterburkimsher wrote: post #30

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…

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.

Re: Techniques for Factoring Numbers in Your Head

#32

Post by exupero »

mkl wrote: post #8

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

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.

Re: Techniques for Factoring Numbers in Your Head

#33

Post by macintux »

peterburkimsher wrote: post #30

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…

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.

Re: Techniques for Factoring Numbers in Your Head

#35

Post by Scarblac »

peterburkimsher wrote: post #30

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…

3 is easy, the sum of the digits is divisible by 3. So 6 is easy too, divisible by 3 and 2.

Re: Techniques for Factoring Numbers in Your Head

#36

Post by [deleted] »

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.

[deleted]

Re: Techniques for Factoring Numbers in Your Head

#37

Post by superflyguy »

dpwm wrote: post #31
peterburkimsher wrote: post #30

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…

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.

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

Re: Techniques for Factoring Numbers in Your Head

#38

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…

Ack. Error in the second step of the divide-by-19 example -- hat tip to Josh Jordan on Twitter -- and it's now too late to edit.
Post reply on HN