Getting in a few more licks ... Pretesting 2257 for small factors: Already mentioned: Check for 2,5 based on last digit. 3: Cross out digits that add to a multiple of 3; here, 225. Leaves 7, not a multiple of 3. 7,11,13 subtract 2002, leaving 255 = 3 * 5 * 17. No 7 or 11 or 13. 23,29 subtract 2001, leaving 256 = 2^8. No 23 or 29. In the same spirit, 17*19*31 = 10013. Add 10013 to 2257, -> 12270 -> 1227 -> 3 * 409. [It's OK to divide out by numbers that are not multiples of 17 or 19 or 31. Here, we drop 10 and 3, to get from 12270 down to 409.] Recognize 409 as prime (She's real fine, my 409). No 17,19,31. We've got 999 for 37, and 2501 or 10004 for 41 & 61, 301 or 3999 for 43, 10011 for 47 & 71, etc. Deciding how far to go, before switching to another approach, seems to be a matter of taste & habit. I usually go up to 31, then switch. Here, with a limit of sqrt2257 = 47+, it's reasonable to just do the last few tests. Another idea --- There's a nice scheme mentioned in my CRC Math Tables handbook c. 1960. The handbook has a table of factorizations to 2000, and gives an extender scheme to get to 20K. The credit goes to Prof. Leonard Caners. Take the square root, to see how far you need to test. sqrt2257 = 47+. Develop two sequences to look for divisors: The 1-9 sequence, and the 3-7s. To do the 1-9 first: Find the largest # ending in 1, <= the sqrt bound. Here, 41. Add or subtract either the number or its triple to the target, forcing the last digit to 0. Here, we add the triple of 41, 123, getting 2380. Drop the final 0 digit. Now, 41 divides our target iff it divides 238. Nope. Count down the divisors by 10s, and the adjusted target by 3s. 31 divides our target iff it divides 235. Nope. 21 " " " 232. No. 11, 229. No. 1, 226. Yes, but a divisor of 1 doesn't count. -9, 223. (Let's just say 9 for the divisor.) No joy. 19, 220. No. 29, 217. No. 39, 214. No. 49, over the limit. This finishes the 1-9 sequence. Now, the 3-7s. We add 43 to 2257, getting 2300. Drop the final 0. We count down the divisors by 10, and the adjusted target by 1s. 43 divides our target iff it divides 230. Uhn uh. 33, 229. No. 23, 228. No. 13, 227. No. 3, 226. No. 7, 225. No. 17, 224. No. 27, 223. No. 37, 222. Bingo! [If we get to 47, 221 without a hit, our target is prime.] If the units digit of the target is not 7, make obvious adjustments to increment or decrement the adjusted target. CRC includes a proof sketch, which I found confusing, more so than simply working through an example. A case of the algebra complicating the obvious arithmetic. This has several plusses and minuses as a mental method. If the factor table is in the book in front of you, it's pretty effective. You move your finger over the table, while mentally counting the divisor down or up, looking for a match. Without the factor table, you need to know the multiples of primes, so you can recognize that 228 is not a multiple of 23 without doing any arithmetic (which would erase the puny internal state we have). Recognizing multiples is a lot easier than determing 'not a multiple'; it's somewhat like the PDP6 reporting an address fault if the memory doesn't respond promptly. I did a little googling to find out about Prof. Caners, since I'd never heard of him in connection with number theory. I didn't find much. He's mentioned in the copyright records for 1961, as the author of "The Algebraic Approach, to accompany Arithmetic, by Marer &al.", published by Little, Brown, a textbook company. His brother's obit at http://freepages.genealogy.rootsweb.ancestry.com/~meilleuro/Simonne/50823.ht... has him in San Diego, and the Social Security Death Index gives his dates as 27 Feb 1900 - 20 Dec 1991. Rich ---- Quoting Dan Asimov <dasimov@earthlink.net>:
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?
--Dan
________________________________________________________________________________________ It goes without saying that .
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun