Simple sequence and prime numbers ``` Author: existing Here is a simple question: suppose you start with an arbitrary natural, n and you iterate f(n) = 2n + 1 with n as a seed, will this sequence always contain a prime? Replies: This is a question I have never seen before. I suspect it is true, but I have no idea how to prove it as a theorem. Maybe assume the opposite and reach a contradiction? Another thought: maybe something along the same line as the standard proof that there are infinitely many primes. hawleyWe could sure use a number theorist! 'existing's' interesting question may be restated as follows (though doing so has not enabled me to answer it): does there exist a positive integer n such that (n + 1) * 2^k-1 is composite for every positive integer k? (If there is one such integer, then there are infinitely many such integers: each choice of k, that is, each subsequent iteration, gives a new one.) If the answer turns out to be "no", then the result may be stated as: for *each* positive integer n, there are *infinitely many* choices of positive integer k such that (n + 1) * 2^k - 1 is prime. I did some numerical experimenting using the symbolic algebra program called Macsyma and, if there is such an n, the smallest it can be is 73 (that is, for each n = 1, 2, . . . , 72 Macsyma found a value of k that produced a prime, different k's for different n's in general); n = 73 gives a composite result for k up through 630 (the number corresponding to k = 630 is approxi- mately 3 x 10^191) This, of course, does not prove that n = 73 "works", but if it does, so do 147, 295, 591, etc. The only other candidate rcwinther< 200 is 190. It is interesting that, for all n < 200 other than 73, 147, and 190, a prime pops up by the 25th iteration, and usually much sooner. Click here to return to the Mathematics Archives ```

NEWTON is an electronic community for Science, Math, and Computer Science K-12 Educators, sponsored and operated by Argonne National Laboratory's Educational Programs, Andrew Skipor, Ph.D., Head of Educational Programs.

For assistance with NEWTON contact a System Operator (help@newton.dep.anl.gov), or at Argonne's Educational Programs

Educational Programs
Building 360
9700 S. Cass Ave.
Argonne, Illinois
60439-4845, USA
Update: June 2012