home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / math / 10496 < prev    next >
Encoding:
Text File  |  1992-08-21  |  2.2 KB  |  56 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!darwin.sura.net!jvnc.net!princeton!lentil.princeton.edu!jwr
  3. From: jwr@lentil.princeton.edu (Jaroslaw Tomasz Wroblewski)
  4. Subject: Re: Primes in x_{n+1} = ax_n+b (was Re: u(v^n)w prime puzzle)
  5. Message-ID: <1992Aug21.180614.17635@Princeton.EDU>
  6. Sender: news@Princeton.EDU (USENET News System)
  7. Nntp-Posting-Host: lentil.princeton.edu
  8. Organization: Princeton University
  9. References: <a_rubin.714331997@dn66> <1992Aug21.103132.29967@ecrc.de>
  10. Date: Fri, 21 Aug 1992 18:06:14 GMT
  11. Lines: 43
  12.  
  13. In article <1992Aug21.103132.29967@ecrc.de> jeanmarc@ecrc.de writes:
  14. >Let a,b be integers, and (x_n) be a sequence s.t. x_{n+1} = a x_n + b
  15. >
  16. >My question is: does it contain infinitely many primes ?
  17. >
  18. >There are trivial cases, where the answer is no:
  19. >1/ if (a x_0 + b = x_0) the sequence is constant.
  20. >2/ if (a = -1) the sequence alternates between two values x_0 and x_1.
  21. >3/ if ((a,b) > 1 or (x_0,b) > 1) then the sequence clearly contains only composite numbers.
  22. >
  23. >What about the other cases ?
  24.  
  25. For any odd b we can see easily that x_n=2^n-b satisfies the relation
  26. x_{n+1} = a x_n + b with a=2 and is not a trivial case above.
  27.  
  28. For b=1 we get Mersene numbers. Most people will bet there are infinitely
  29. many primes here, but I would not expect any proof coming.
  30.  
  31. However there exist odd b such that the sequence x_n=2^n-b contains finitely
  32. many primes. That is the case because one can pick b in such a way that
  33. For n=1(mod 2)    3|2^n-b
  34. For n=2(mod 4)    5|2^n-b
  35. For n=0(mod 3)    7|2^n-b
  36. For n=4(mod 12)  13|2^n-b
  37. (So far everything except 8(mod 12) is covered)
  38. For n=0(mod 8)     17|2^n-b
  39. For n=20(mod 24)  241|2^n-b
  40.  
  41. Then for every n the number 2^n-b will be divisible by at least one of the
  42. primes 3,5,7,13,17,241.
  43.  
  44. Therefore 1 and the above determined b will give different answer to your
  45. question. This shows that even making a good guess when such sequences
  46. contain infinitely many primes is tricky.
  47.  
  48. Once we pick b as above I do not see a reason why other sequences
  49. satisfying x_{n+1} = 2 x_n + b should also contain only finitely many
  50. primes. Knowing a and b alone may not be enough to decide how many primes
  51. does a sequence have.
  52.  
  53. --
  54.  
  55. Jarek (Jaroslaw Tomasz Wroblewski) ,   E-mail jwr@math.Princeton.EDU
  56.