Re:Techniques for Factoring Numbers in Your Head
by CurtMonash on Thursday January 04, 2018 @05:32AM
(#16069253)
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
by vorg on Thursday January 04, 2018 @04:50AM
(#16069091)
> 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
by ohwaitnvm on Thursday January 04, 2018 @04:59AM
(#16069129)
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
by CurtMonash on Thursday January 04, 2018 @05:30AM
(#16069244)
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
by CurtMonash on Thursday January 04, 2018 @03:58PM
(#16074011)
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.
Re:Techniques for Factoring Numbers in Your Head
by mkl on Thursday January 04, 2018 @04:15AM
(#16068962)
You should put spaces around your asterisks so they don't make italics (or use ×).
Re:Techniques for Factoring Numbers in Your Head
by CurtMonash on Thursday January 04, 2018 @05:27AM
(#16069233)
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
by zamber on Thursday January 04, 2018 @06:12AM
(#16069438)
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.
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.