Department of Energy Argonne National Laboratory Office of Science NEWTON's Homepage NEWTON's Homepage
NEWTON, Ask A Scientist!
NEWTON Home Page NEWTON Teachers Visit Our Archives Ask A Question How To Ask A Question Question of the Week Our Expert Scientists Volunteer at NEWTON! Frequently Asked Questions Referencing NEWTON About NEWTON About Ask A Scientist Education At Argonne 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?

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.


We 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 (, or at Argonne's Educational Programs

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

Argonne National Laboratory