[math-fun] New proof of Euclid's Theorem
In the December 2006 issue of Am. Math. Monthly , Filip Saidak presents "A New Proof of Euclid's Theorem." Here's a concise rendition: Let f(x) = x^2 + x, let g[0] be a positive integer, and for n = 1, 2, 3, ..., let g[n] = f(g[n-1]). Then g[n] has at least n different prime factors. I omit the proof for those who might enjoy working it out for themselves. The case of g[0] = 1 seems somewhat canonical. I'm curious about which primes appear as factors in the sequence of g[n] (2, 6, 42, 1807, ...). This sequence begins: 2, 3, 7, 13, 43, 73, 139, 181, 547, 607, 1033, 1171, ... Paul
Should that 1807 be 1806 ? There's a paper by Guy & Nowakowski, published long years ago in Delta (don't have the reference by me) Discovering Primes with Euclid, which discusses which primes arise in this kind of sequence. We had help from Lehmer & Selfridge, I remember. R. On Sat, 27 Jan 2007, Paul R. Pudaite wrote:
In the December 2006 issue of Am. Math. Monthly , Filip Saidak presents "A New Proof of Euclid's Theorem." Here's a concise rendition: Let f(x) = x^2 + x, let g[0] be a positive integer, and for n = 1, 2, 3, ..., let g[n] = f(g[n-1]). Then g[n] has at least n different prime factors. I omit the proof for those who might enjoy working it out for themselves.
The case of g[0] = 1 seems somewhat canonical. I'm curious about which primes appear as factors in the sequence of g[n] (2, 6, 42, 1807, ...). This sequence begins: 2, 3, 7, 13, 43, 73, 139, 181, 547, 607, 1033, 1171, ...
Paul _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Mathfunners, Seqfans:
... Let f(x) = x^2 + x, let g[0] be a positive integer, and for n = 1, 2, 3, ..., let g[n] = f(g[n-1]). ...
The case of g[0] = 1 ... which primes appear as factors in the sequence of g[n] ... 2, 3, 7, 13, 43, 73, 139, 181, 547, 607, 1033, 1171, ...
It is, of course, Sloane's A007996... I mean A096263... Augggh! yet another duplicate. It's an easy exercise to prove those sequences are identical. Good luck, reader. -- Don Reble djr@nk.ca -- This message has been scanned for viruses and dangerous content by MailScanner, and is believed to be clean.
On Saturday 27 January 2007 18:07, Paul R. Pudaite wrote:
In the December 2006 issue of Am. Math. Monthly , Filip Saidak presents "A New Proof of Euclid's Theorem." Here's a concise rendition: Let f(x) = x^2 + x, let g[0] be a positive integer, and for n = 1, 2, 3, ..., let g[n] = f(g[n-1]). Then g[n] has at least n different prime factors. I omit the proof for those who might enjoy working it out for themselves.
Pretty, but it seems to me to be just a repackaging of Euclid's original proof and strictly inferior to it: to understand why this proof works, you need to understand exactly the same points as for Euclid's, plus a little extra obfuscating machinery. Question: Suppose you do this with some other integer polynomial f. Under what conditions are you guaranteed to get infinitely many prime factors of the iterates? Obviously not if f = aX^k for some a,k; is that the only way in which you can fail? -- g
participants (4)
-
Don Reble -
Gareth McCaughan -
Paul R. Pudaite -
Richard Guy