Simple sequence and prime numbers
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
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
Update: June 2012