## Extension of Cunningham chains

Expand Messages
• 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
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
• 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
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]
• ... 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
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.
• 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
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]
• 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
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.
Q.E.D.

-Mike Oakes

[Non-text portions of this message have been removed]
• ... 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
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.