Ask A Scientist Mathematics Archive

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?

Response #:  1 of 2
Author:      hawley
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.

Response #:  2 of 2
Author:      rcwinther
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 < 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.