n => 2n+1 to get prime: seed = 73

[David Wilson]

There is theory very close to what you are doing, but not exactly.

For odd n, let the sequence R_n(k) = n*2^k-1 for k >= 1.  For example, R_13 is the
sequence

    25, 51, 103, 207, 415, 831, ...

n is called a Riesel number if no primes occur in its Riesel sequence.  13 is not
a Riesel number because 103 shows up in its Riesel sequence.

For any n, R_n satisfies the recurrence

   R_n(k+1) = 2*R_n(k)+1,

That is, precisely the relationship you are investigating.

Every odd number belongs to a unique R_n.  Specifically, your starting number 73
belongs to R_37, which starts

   73, 147, 295, 591, 1183, 2368, ...

That is R_37 is precisely the sequence you are considering.  However, 37 is not
a Riesel number precisely because 73 is prime.

You saw the "obvious pattern" in the divisors of R_37.  Specifically, prime divisors
show up periodically in the sequence.  For example, 3 divides R_37(2k), and
5 divides R_37(4k+3), etc.  This is true for any prime that divides any element of
a Riesel sequence.

In fact, the way that we prove that a number is Riesel is by showing that there is
a periodic sequence of prime divisors.  The first proven Riesel number is 509203.
R_509203 looks like

  1018405, 2036811, 4073623, 8147247, 16294495, ...

It has a cyclic pattern of divisors:

  5, 3, 241, 3, 5, 3, 13, 3, 5, 3, 7, 3, 5, 3, 17, 3, 5, 3, 13, 3, 5, 3, 7, 3, ...

where these 24 divisors repeat forever.  This means that every element of R_509203
is (properly) divisible by 3, 5, 7, 13, 17 or 241, and is therefore composite.  So 509203
is Riesel.

If R_n does not have a cyclical pattern of divisors, a probabilistic argument indicates
that R_n should have a prime element, and n should not be Riesel.  However, this is
not a proof that n is not Riesel, to do this we must prove there is a prime in R_n, and
the only way we know to do this is to find and exhibit that prime.

n = 509203 is the smallest proven Riesel number; it has long been conjectured that it
is in fact the smallest Riesel number.  To prove this, it is necessary to show that all
n < 509203 are non-Riesel.  Unfortunately, there are a few stubborn n < 509203 for
which neither a cyclic pattern of divisors of R_n or a prime element of R_n has been
established.  Eliminating these Riesel candidates is the goal of the Riesel Sieve Project
(www.rieselsieve.com).  You can go there for more background information.
(note, more Riesel numbers are given in A101036).

To sum up:

The kind of sequence you are investigating has been looked at before.  For this type
of sequence, you can either show it contains no primes by finding a cyclic pattern of
divisors, or show it does contain a prime by finding it.  For some numbers, finding the
prime is very difficult.  You are lucky that Don Reble came to your assistance in this
instance (I will assume that he is correct that 74*2552-1 is prime).

There are much more difficult examples than the one you gave, though.  For example,
R_2293 =

    4585, 9171, 18343, 36687, 73375, ...

(see http://www.prothsearch.net/rieselsearch.html).  So problems such as yours are
known and heavily investigated.

     

----- Original Message ----- 
  From: זקיר סעידוב - ד\"ר/Zakir Seidov Ph.D. 
  To: ham ; seqfan at ext.jussieu.fr 
  Sent: Friday, March 11, 2005 6:29 AM
  Subject: n => 2n+1 to get prime: seed = 73


  Dear Seqfans,
  The operation n => 2n+1 quickly gives primes for most "seed" values of n.
  But for some seeds, the transformed numbers keep being composite.
  The first "tough" number is n=73.
  Here is the list of least divisors of transformed numbers
  (I do not consider "seed" itself which in this case happened to be prime ):
  {3,5,3,7,
  3,5,3,19,
  3,5,3,47,
  3,5,3,7,
  3,5,3,61,
  3,5,3,29,
  3,5,3,7,
  3,5,3,1439,
  3,5,3,73,
  3,5,3,7,
  3,5,3,19,
  3,5,3,46703,
  3,5,3,7,
  3,5,3,22247,
  3,5,3,59,
  3,5,3,7,
  3,5,3,761,
  3,5,3,73,
  3,5,3,7,
  3,5,3,19,
  3,5,3,137,
  3,5,3,7,
  3,5,3,131381,
  3,5,3,2411639,
  3,5,3,7}.
  The clear pattern is seen, which may help to search the prime case.
  My request is:
  Can the n =>2n+1 transformation, in this particular case,
   lead to prime number (and when?),
  may anyone bother to find it?
  What about general theory?

  Thank you very much,
  Zak

  PS  The last considered number, 
  93806144416888975710756037197823,
  has the full list of divisors as follows:
  {{7, 1}, {13, 1}, {599, 1}, {21214924397, 1}, {81118812239619751, 1}} -
  at least according to Mathematica.
  And next three numbers are clearly composite according the pattern mentioned.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20050311/ef1cd502/attachment-0001.htm>