Aaaand Fred shows that I did it wrong ... I got a sign backward. Start with the smallest square greater than N, and work up from there. I also remember that John Conway is a past master of this, and can usually factor 4 to 5 digit numbers in his head in less than a minute. The archives of Math-Fun contain his discussion of the "N-somniac" game (which I find actually keeps me awake, but your mileage may vary). On Fri, Dec 16, 2011 at 3:36 PM, Fred W. Helenius <fredh@ix.netcom.com>wrote:
On 12/16/2011 3:03 PM, Dan Asimov wrote:
Take a number like 2257 (say< 10000), easily checked to have no prime factors< 13.
To find the least prime factor of such a number N, is there on average a faster way (after having excluded primes< 13) than the naïve method of dividing it by each prime in order<= sqrt(N) until one divides N evenly?
Fermat's factorization method can be combined with trial division to make a practical technique for mental factorization of 4-digit numbers. You can find the details in this Wikipedia article, http://en.wikipedia.org/wiki/**Fermat%27s_factorization_**method<http://en.wikipedia.org/wiki/Fermat%27s_factorization_method> , but the idea is that an odd composite N must be the difference of squares, and if the factors are relatively close, the larger square will not be much larger than N. In this case, the next square after 2257 is 48^2 = 2304, but since N is 1 mod 4, the difference cannot be a square. The next odd square is 49^2 = 2401 and the difference is 144 = 12^2. Thus 2257 = 49^2 - 12^2 = 37 61.
By the way, you can test for divisibility by 7, 11 and 13 simultaneously by "casting out 1001s". In this case, 2257 - 2002 = 255 = 3 5 17, so none of them is a divisor. (If you get a less obvious three-digit remainder, say 481, you can multiply it by 10 or 100 and repeat: 48100 - 48048 = 52, so it's a multiple of 13.)
-- Fred W. Helenius fredh@ix.netcom.com
______________________________**_________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>