Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Challenge 11: Sequence of Primes

  1. Dec 19, 2013 #1

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Consider the following sequence:
    a1 = p, where p is a prime number.
    an+1 = 2an+1

    Prove there is no value of p for which every an is a prime number, or make me look dumb and construct a counterexample.
     
  2. jcsd
  3. Dec 19, 2013 #2
    First, it follows easily by induction on n that for each n, [itex]a_n = 2^{n-1}(p+1) - 1[/itex]. By Euler's theorem [itex]2^{p-1} \equiv 1 \mod p[/itex], and so [itex]a_p = 2^{p-1}(p+1) - 1 \equiv p+1 - 1 \equiv 0 \mod p[/itex], so [itex]p \vert a_p[/itex], but [itex]p \neq a_p[/itex], so [itex]a_p[/itex] is not prime. Q.E.D.
     
  4. Dec 19, 2013 #3
    This works except when p = 2 because Euler's Theorem applies only when p is relatively prime with 2. But for that case, I checked and [itex]a_6[/itex] = 95 is composite.
     
  5. Dec 19, 2013 #4
    Ah yes, good catch. Thanks for patching that hole.
     
  6. Dec 19, 2013 #5

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You can check p=2 a bit easier because a2 = 5 and you can just apply the odd case starting from there. Nice solution Citan! Are there any other ways of solving it?
     
  7. Mar 7, 2014 #6
    An extension. How often are the sequences prime until the pth term?
    For example 3, 7, 15 is prime until term 3. 5, 11, 23, 47, 95 is prime until the term 5.
    But 7 isn't prime until term 7.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Challenge 11: Sequence of Primes
  1. Challenging problems (Replies: 6)

  2. Master's Challenge (Replies: 15)

  3. A Euclidean Challenge (Replies: 10)

Loading...