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. 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 But all this is lame vs JHC's and Rich's methods. Rich sketched his on Date: Tue, 4 Oct 2005 18:47:46 -0700 . Conway sent many methods, e.g.
From conway@math.Princeton.EDU Wed Feb 7 12:24:59 1996
Some time ago I was boasting about my mental factorization algorithm, but when rwg asked "how fast?" I could only reply "pretty fast", because I hadn't done any systematic timing, and of course the times taken vary dramatically with the form of the number. I forgot to display my prowess to rwg when I met him at the Gathering for Gardner, too, dammit. However, I now have some results. I still suffer greatly from insomnia, and have been playing "The Nsomniac's Game". This is played in the small hours by an insomniac with a luminous digital clock by the bedside, which shows a 3-digit number n. [For example, at 3:49 am, n would be 349.] Then the "current number" in the Nsomniac's game is | 1000N + n |. (I allow negative N.) The game is to factorize the successive current numbers while they remain current, except that the first one need only be factorized before the second one ceases to be current (because your first glance at the clock might be only a few seconds before it changes). I can play up to the 15somniac's game quite well, but am particularly comfortable with the 10somniac's one. I think it was last Saturday night (of course I mean Sunday morning) that I played 10somniac for about 4 consecutive hours. Usually I was factorizing numbers quite a few minutes ahead of the current one, so that every now and then I could take 5 minutes off; but since sleep still didn't come I was always able to take up where I left off. The only failure to meet the time limit was a technical one. I did find the correct factor 79 of 10349 in time (i.e., before 3:50 am), but then couldn't get it to divide this number correctly, so presumed I must have slipped, and redid the algorithm, finding 79 again, but the clock had changed to 350 by the time I'd sorted this out. Any factorisation gives a check, but it's quite possible that I wrongly declared some numbers to be prime. I actually caught myself just about to do this at 4:43, when I'd found "3 times 3481" and had apparently shown the second factor prime, when I recalled that in fact it's 59^2. I had the feeling that my 10somniac times are usually less than 30 seconds per number. I've reorganized the algorithm slightly, and the version I use now tests primes up to 100, which is all that's needed for 10somniac, since the only composites < 11000 with no factor < 100 are easily remembered: 10201, 10403, 10609, 10807. For use up to 15somniac, I supplement the basic algorithm by an ad hoc way of finding the next few primes, using 101.109 = 11009, 103.107 = 11021, 97.113 = 11000 - 39. (Namely I subtract 11000, then subtract 9, then subtract 12, then add 60, at each stage checking the appropriate primes. This allows me to miss the 97 test from the main algorithm, and carries me up to 127^2 = 16129.) Well, you're not all interested in my sleeping problems. During a few of my real waking hours, I've been working on a speeded-up mental way of finding large factors by differences of squares, in which a few of you MAY be interested; I'll report on it soon. [My basic algorithm will test numbers well beyond 10^4; certainly up to 10^5, for factors below 100, and my ground plan is to use the new method for factors beyond 100. However, factorizers who are slightly less keen could use it over other ranges.] John Conway But I haven't been able to find his most impressive one, which turned out to be only part of an even superior method published by a Harvard(?) professor in the 1920s(?) --rwg