Loading ...
Sorry, an error occurred while loading the content.

Prime chains x-->Ax+B

Expand Messages
  • WarrenS
    I wanted long chains of primes of the following kind. Want P to be prime. Want Q=4P+1 to be prime. And continue: R=4Q+1 prime, S=4R+1 prime, etc. I also was
    Message 1 of 143 , Nov 11, 2010
    • 0 Attachment
      I wanted long chains of primes of the following kind.
      Want P to be prime. Want Q=4P+1 to be prime. And continue:
      R=4Q+1 prime, S=4R+1 prime, etc.
      I also was interested in the same thing but with -1's instead of +1's.

      Examples:
      +chainlength=3: 3, 13, 53
      -chainlength=3: 3, 11, 43
      But: There are no other 3-long-chains if the initial P is among the first 2000 primes.

      This led me to prove the following easy once you see it THEOREM:
      The above two examples are the unique 3-long 4x+1 and 4x-1
      chains. There are no others.

      PROOF:
      f(x)=4x+1 always leads to a multiple of 3 after at most 2 iterations
      (and ditto for 4x-1); this is seen by working mod 3; and this prevents 3 primes
      in a chain unless one of the primes actually IS 3.
      QED

      Doh...

      Similar proofs show that x-->Ax+B prime-chains are bounded in length
      under various conditions:
      * if B=0 then obviously not even 1 step is possible
      * if B and A have a common divisor then obviously not even 1 step is possible
      * if A and B have same parity then obviously not even 1 step is possible
      starting from an odd prime
      * otherwise if gcd(B,A-1)=1 then the linear congruential sequence generator
      x-->Ax+B (mod M) will be full period M for any prime M dividing A-1
      hence the chain length cannot be longer than M primes in a row...
      So...

      THEOREM: the only possible unboundedly long x-->Ax+B prime chains must
      have B a multiple of every prime divisor of A-1,
      and B nonzero, gcd(A,B)=1, and the parities of A,B must differ.

      For example 2x+1, 2x-1, 3x+2, 3x+4, 3x-2, 4x+3, and 4x-3:
      Fairly long chains of these sorts:

      2x+1: start with 89, get 6 primes.
      2x-1: start with 1531 or 6841, get 5 primes. With 16651 get 7 primes.
      3x+2: start with 1129, get 5 primes; or 10009, get 6 primes.
      3x+4: start with 3203, get 5 primes.
      3x-2: start with 61 or 761, get 5 primes.
      4x+3: start with 17231, get 8 primes.
      4x-3: start with 523, get 6 primes; start with 5869 to get 7 primes.
      5x+2: start with 373 or 1171, get 5 primes.
      5x+4: start with 263 or 1217, get 5 primes; with 5333 get 7 primes.
      5x-2: start with 1229 to get 5 primes; or 4337 to get 8 primes.
      5x-4: start with 367 or 463 to get 5 primes.

      One might CONJECTURE that the necessary conditions of the theorem also
      suffice. It would be better to make such a conjecture after getting rather more
      numerical evidence than this, though.

      --
      Warren D. Smith
      http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
      and
      math.temple.edu/~wds/homepage/works.html
    • djbroadhurst
      ... Suppose that we want to start with a square and get a square. Then we must solve the Diophantine equation y^2 = a*x^2 + b For any pair (a,b), Dario will
      Message 143 of 143 , Jan 7, 2011
      • 0 Attachment
        --- In primenumbers@yahoogroups.com,
        Kevin Acres <research@...> wrote:

        > x=a*x+b either is a square or has a square as a major factor.

        Suppose that we want to start with a square and get a square.
        Then we must solve the Diophantine equation
        y^2 = a*x^2 + b

        For any pair (a,b), Dario will tell us all the solutions:
        http://www.alpertron.com.ar/QUAD.HTM

        David
      Your message has been successfully submitted and would be delivered to recipients shortly.