On Sat, Dec 17, 2011 at 3:39 PM, Bill Gosper <billgosper@gmail.com> wrote:
DanA>What got me started on this was trying to factor 2257, and after finding no small prime factors, noticing that 2257 = 37 + 2220 = 37 + 20*111 = 37 + 20*3*37 = 37*61.
But that was just a lucky break, and I was wondering if there are better ways than routinely checking each prime in order (or relying on luck).
--Dan I did 2257 -> 257-2 ->255 *2 ->51, so 7,11,13,fail 257-1 so 23,29 fail (2001=3 23 29) 257+2 -> 259 = 222-37, 37 win (111=3*37). Had that failed 257-3*2 ->251, so 17,59 fail 257-7*2->243, so 19,53 fail, 2*2257 = 4514 -> 514+1 *2 ->103, so 31,43 fail (3999 = 3*31*43) ...
I.e., memorize a bunch of multiples of the small primes near multiples of 1000.
For the cofactor, 2257-7*37=1998=2*999=2*27*37, so 54+7=61 is the cofactor. Check: In this case 61*37 = 2220+37 is extremely easy, but usually it's easier to test for divisibility by the cofactor than to actually multiply: 2257 + 183 =2440 = 40*61. --rwg Normally you don't try seven digits, but when it ends in 25 ... I just did my blood pressure prescription: 3580225.
My favorite factorization was of a friend's phone #, 3367. Hmm, 1/3;2/3. Muliply by 3: 10101. Multiply by 11: 111111 = 1001*111, so 7 11 13 3 37/3/11 [...]