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

Extension of Cunningham chains

Expand Messages
  • Jack Brennen
    First I give an equivalent definition of a Cunningham chain: - A Cunningham chain of the first kind (second kind) is a sequence of integers of the form k*2^n-1
    Message 1 of 6 , Nov 12, 2004
    • 0 Attachment
      First I give an equivalent definition of a Cunningham chain:

      - A Cunningham chain of the first kind (second kind) is a sequence
      of integers of the form k*2^n-1 (k*2^n+1) where k is a fixed
      positive odd integer, and n ranges over two or more consecutive
      nonnegative integers, and where each member of the sequence has
      exactly 2 positive divisors.

      You'll note this is a pretty standard definition of a Cunningham
      chain, except I've defined it in terms of number of divisors
      rather than primality. Why? Because I'm looking at an extension
      of Cunningham chains where all of the members of the sequence have
      an equal number of positive divisors, but that number is not 2.

      So far, I've found a "4-divisor Cunningham chain" (of the second kind)
      of length 18:

      80935905*2^13+1 == 254993 * 2600177
      80935905*2^14+1 == 1951 * 679679071
      80935905*2^15+1 == 71 * 37353630071
      80935905*2^16+1 == 11 * 482201406371
      80935905*2^17+1 == 15667 * 677119483
      80935905*2^18+1 == 389 * 54542061389
      80935905*2^19+1 == 19 * 2233353882139
      80935905*2^20+1 == 4133 * 20534102957
      80935905*2^21+1 == 2797 * 60684624613
      80935905*2^22+1 == 2181271 * 155629351
      80935905*2^23+1 == 13 * 52226121551557
      80935905*2^24+1 == 853 * 1591886471677
      80935905*2^25+1 == 1489 * 1823880672049
      80935905*2^26+1 == 11 * 493774240123811
      80935905*2^27+1 == 44287967 * 245281823
      80935905*2^28+1 == 689383 * 31515234007
      80935905*2^29+1 == 76446859 * 568396579
      80935905*2^30+1 == 28879 * 3009254692399

      It looks like chains with 4 divisors each seem
      to be easiest to find, but 8 divisors each might be worth looking
      into as well. The best "8-divisor Cunningham chain" I've found,
      without spending a lot of time on it:

      302457*2^13+1 == 5 * 97 * 5108717
      302457*2^14+1 == 59 * 83 * 1011937
      302457*2^15+1 == 11 * 12041 * 74827
      302457*2^16+1 == 19 * 1993 * 523459
      302457*2^17+1 == 5 * 1129 * 7022789
      302457*2^18+1 == 23 * 2521 * 1367423
      302457*2^19+1 == 37 * 71 * 60363371
      302457*2^20+1 == 73 * 373 * 11647477
      302457*2^21+1 == 5 * 329267 * 385279
      302457*2^22+1 == 337 * 11273 * 333929
      302457*2^23+1 == 67 * 119677 * 316423
      302457*2^24+1 == 13 * 251 * 1555129151

      Can anybody find any longer such chains each with an equal number
      of divisors, either with 4, 8, or some other number?


      Jack
    • mikeoakes2@aol.com
      In a message dated 13/11/2004 03:14:25 GMT Standard Time, jack@brennen.net writes: Can anybody find any longer such chains each with an equal number of
      Message 2 of 6 , Nov 13, 2004
      • 0 Attachment
        In a message dated 13/11/2004 03:14:25 GMT Standard Time, jack@...
        writes:

        Can anybody find any longer such chains each with an equal number
        of divisors, either with 4, 8, or some other number?





        With 3 divisors, each must be the square of a prime, of course.
        Are there any such chains of length > 1? (I haven't searched.)

        -Mike Oakes


        [Non-text portions of this message have been removed]
      • Jack Brennen
        ... Yes, there are a few easy examples. There are no examples of such chains with length 2; this can probably be proven in several ways, but a simple
        Message 3 of 6 , Nov 13, 2004
        • 0 Attachment
          Mike wrote:
          > With 3 divisors, each must be the square of a prime, of course.
          > Are there any such chains of length > 1? (I haven't searched.)

          Yes, there are a few easy examples. There are no examples of
          such chains with length > 2; this can probably be proven in
          several ways, but a simple analysis of the solutions to the
          Pell equations (x^2 = 2*y^2 +/-1) suffices.

          Of length 2, the following very small examples exist:

          k=5, n=(0,1), k*2^n-1 == (4,9) (Only example of form k*2^n-1)

          k=3, n=(3,4), k*2^n+1 == (25,49)
          k=105, n=(3,4), k*2^n+1 == (841,1681)

          And some bigger ones:

          k=248204571168918457275, n=(3,4), k*2^n+1
          k=22980046115755920139039424449209532289506425, n=(3,4), k*2^n+1

          I'm not sure if there are any more. An heuristic argument would
          indicate that the total number of such chains is finite.
        • mikeoakes2@aol.com
          Jack wrote:- ... In fact, there are chains of length 2, but no longer. [ The first few are:- 2^2, 3^2 5^2, 7^2 29^2, 41^2 ] The proof is relatively
          Message 4 of 6 , Nov 13, 2004
          • 0 Attachment
            Jack wrote:-
            >>Can anybody find any longer such chains each with an equal number
            >>of divisors, either with 4, 8, or some other number?

            I wrote:
            >With 3 divisors, each must be the square of a prime, of course.
            >Are there any such chains of length > 1? (I haven't searched.)

            In fact, there are chains of length 2, but no longer.
            [
            The first few are:-
            2^2, 3^2
            5^2, 7^2
            29^2, 41^2
            ]
            The proof is relatively straightforward.
            Anyone?

            -Mike Oakes


            [Non-text portions of this message have been removed]
          • mikeoakes2@aol.com
            Jack s post ... crossed with mine. Yes, your method is exactly what I used. General solution of the Pell eqn. is given by (x[n] + y[n]*sqrt(2)) = (1 +
            Message 5 of 6 , Nov 13, 2004
            • 0 Attachment
              Jack's post
              >Yes, there are a few easy examples. There are no examples of
              >such chains with length > 2; this can probably be proven in
              >several ways, but a simple analysis of the solutions to the
              >Pell equations (x^2 = 2*y^2 +/-1) suffices.
              crossed with mine.

              Yes, your method is exactly what I used.
              General solution of the Pell eqn. is given by
              (x[n] + y[n]*sqrt(2)) = (1 + sqrt(2))^n
              This gives the recurrence relations:
              x[n] = x[n-1] + 2*y[n-1]
              y[n] = x[n-1] + y[n-1]
              Iterating:-
              x[n] = 3*x[n-2] + 4*y[n-2]
              y[n] = 2*x[n-2] + 3*y[n-2]
              For a 3-term chain,
              x[n] = y[n-2*k] for some k >= 1
              But x[n] > y[n-2] > y[n-2*k] for all k >= 1.
              Contradiction.
              Q.E.D.

              -Mike Oakes


              [Non-text portions of this message have been removed]
            • Jack Brennen
              ... Add to that a 4-divisor Cunningham chain (of the first kind) of length 18: 899643225*2^8+1 == 173 * 1331263963 899643225*2^9+1 == 2347 * 196257917
              Message 6 of 6 , Nov 13, 2004
              • 0 Attachment
                I previously wrote:
                > So far, I've found a "4-divisor Cunningham chain" (of the second kind)
                > of length 18...

                Add to that a "4-divisor Cunningham chain" (of the first kind) of length 18:

                899643225*2^8+1 == 173 * 1331263963
                899643225*2^9+1 == 2347 * 196257917
                899643225*2^10+1 == 53 * 17381786083
                899643225*2^11+1 == 397 * 4640980667
                899643225*2^12+1 == 821 * 4488354019
                899643225*2^13+1 == 2351 * 3134784049
                899643225*2^14+1 == 1531 * 9627534029
                899643225*2^15+1 == 19 * 1551553115621
                899643225*2^16+1 == 71 * 830408709769
                899643225*2^17+1 == 11 * 10719821526109
                899643225*2^18+1 == 193 * 1221948567743
                899643225*2^19+1 == 101 * 4670021258899
                899643225*2^20+1 == 532663 * 1770996473
                899643225*2^21+1 == 499 * 3780939055301
                899643225*2^22+1 == 9008023 * 418890713
                899643225*2^23+1 == 19427 * 388467306037
                899643225*2^24+1 == 122953 * 122758360583
                899643225*2^25+1 == 5205467 * 5799098797


                So I've got two examples of length 18, a "4DCC1K" and a "4DCC2K". :)


                The challenge is this: find a chain of length 19, any number
                of divisors you wish. :)
              Your message has been successfully submitted and would be delivered to recipients shortly.