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 .
Hello mr Asimov, yes maybe : since 1001 is 7 * 11 * 13 then by just looking at the number we know if it is a multiple of 1001, ... but the number of course has to be a mutiple of 1001 which is somewhat rare. There are tricks for each prime up to 97 I believe but the application is too complicated to be made mentaly. The only shortcut I know is to use complements, for example with 19 , it is simpler to figure out a way to exclude a multiple of 19 if we consider that 19 = 20 - 1. The same for 11, 31, 41, 61, etc,. Carefuly applied this could lead to a simple trick to exclude a series of primes in one shot (sort of). just a thought, best regards, Simon Plouffe Le 16/12/2011 21:03, Dan Asimov a écrit :
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
On Fri, Dec 16, 2011 at 12:03 PM, Dan Asimov <dasimov@earthlink.net> 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?
Check the smaller primes by division, and at some point when you're close to sqrt(N) it gets easier to think about 2257 + a^2 = b^2, where you know that the values of a can't be so big. Squares are easier to compute, rather than dividing, and after a while you can learn all the squares < 10000 pretty well (or at least learn the ones up to 25, and then use things like (25+n)^2 = (25-n)^2 + 100n to get the rest). --Joshua Zucker
Following on Joshua's comment, I remember being taught the following procedure. Take the greatest square below 2257; this is 47^2 = 2209. The residue after this square is removed is 48. Now we want to calculate N^2 - 2257 for successive N after 47. They are fairly easily generated: 48 + (47 + 48) = 145 145 + (48 + 49) = 242 242 + (49 + 50) = 341 341 + (50 + 51) = 442 442 + (51 + 52) = 545 545 + (52 + 53) = 650 We are looking for perfect squares in this sequence, and so far we haven't found one. But in fact we've now swept clean a fairly big area around 47. The square root of 650 is bigger than 25, so 2257 has no factors between 47 and 47-26 = 21. So after eliminating 7, 11, and 13 by the 1001-trick, the only primes left to check are 17 and 19. I find that checking divisibility is usually easier than actually dividing. You can add or subtract multiples of the candidate divisor freely, and you can also divide by primes that aren't equal to the candidate, without affecting divisibility. For 2257 and 17, my thought process goes from 2257 to 2240, to 224, to 112, to 56, ... which I can factor fast and doesn't have any 17's. For 19, it's even easier: 2257 to 2200, which again one can "see" all the factors of, and 19 isn't among them. So 2257 is prime. Without pencil and paper, I usually skip the square searching and progress straight to testing candidate divisors, which I somehow find easier to do in my head. On Fri, Dec 16, 2011 at 3:21 PM, Joshua Zucker <joshua.zucker@gmail.com>wrote:
On Fri, Dec 16, 2011 at 12:03 PM, Dan Asimov <dasimov@earthlink.net> 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?
Check the smaller primes by division, and at some point when you're close to sqrt(N) it gets easier to think about 2257 + a^2 = b^2, where you know that the values of a can't be so big. Squares are easier to compute, rather than dividing, and after a while you can learn all the squares < 10000 pretty well (or at least learn the ones up to 25, and then use things like (25+n)^2 = (25-n)^2 + 100n to get the rest).
--Joshua Zucker
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
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, 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
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>
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
Rich:
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.
Apparently based on Caners' Aug.-Sep. 1956 American Mathematical Monthly article 'On Tables of Factors and Primes': http://www.jstor.org/pss/2309039
participants (7)
-
Allan Wechsler -
Dan Asimov -
Fred W. Helenius -
Hans Havermann -
Joshua Zucker -
rcs＠xmission.com -
Simon Plouffe