Showing posts with label cunningham chains. Show all posts
Showing posts with label cunningham chains. Show all posts

Thursday, 20 June 2019

Generalised Cunningham Chains

I've written about or mentioned Cunningham chains in the following posts over the years:
Monday, 5 October 2015 
Wednesday, 27 April 2016 
Tuesday, 12 April 2016 
Monday, 14 November 2016 
Saturday, 30 April 2016
However, it's been over three years since that last past so it high time to say a little more about them. If, when a prime is multiplied by 2 and 1 added, a new prime is generated then the result is a Cunningham chain of the first type. If, when a prime is multiplied by 2 and 1 subtracted, a new prime is generated then the result is a Cunningham chain of the second type. The process is continued until a composite number is reached and the chain ends, having attained a certain length.

Today I turned 25645 days old and it so happened that this number is a member of OEIS A263311: numbers \(n\) such that each of \(p=6*n+1\), \(q=6*p+1\), \(r=6*q+1\) and \(s=6*r+1\) is prime. The first member of this sequence is 10 which yields \(p=61\), \(q=367\), \(r=2203\), \(s=13219\) and \(t=79315\). Thus we have the chain of primes 61, 367, 2203 and 13219 connected by the rule multiply by 6 and add 1. This is an example of a generalised Cunningham chain where, instead of multiplying by 2 and adding 1, we multiply by 6 and add 1. So to generalise even more, the primes in a generalised Cunningham chain are connected by the rule \(p_i=a*p+b\) where \(p\) is the first prime in the chain and \(a\) and \(b\) are coprime integers. So in the case of 25645, \(a=6\) and \(b=1\) and the primes thus generated are 147871, 887227, 5323363 and 31940179.

Here is another example. Let's consider the starting prime 5333 and the rule \(p_i=5*p+4\). This generates the sequence of primes 5333, 26669, 133349, 666749, 3333749, 16668749 and 83343749, representing a generalised Cunningham chain of length 7. As another example, if we start with 3203 and use the rule \(p_i=3*p+4\), we get the chain 3203, 9613, 28843, 86533 and 259603. Here are some more examples taken from this site. Figure 1 shows  \(p_i=4*p-3\) with \(L\) being the number of primes in the chain with starting primes for the chain shown in the right column.

Figure 1

Figure 2 shows chains created using  \(p_i=6*p-5\) and \(p_i=9*p-8\).

Figure 2

I found a paper (link) that discusses a connection between arithmetic derivatives and Cunningham chains. For example, the following is proposed:
A Cunningham chain of length 17 exists if and only if there exists a prime number \(p\) such that \(n = 2^4p\) satisfies the following differential equation:$$n^{17} = 2^{17} \cdot n + 524272$$

Wednesday, 27 April 2016

Cunningham Chains Revisited

I've already discussed Cunningham chains in an earlier post but today I was 24496 days old and an analysis of the this number led me to a record-breaking example of such a chain. The factors or 24496 are \(2^4 \times 1531\) and \(1531\) turns out to be the smallest prime that leads to a Cunningham chain of the second kind (\(2p-1\)) with a length of \(5: 1531, 3061, 6121, 12241, 24481\)
  • 2131 holds the record for length 4 (2131, 4261, 8521, 17041)
  • 2 holds the record for length 3 (2, 3, 5)
  • 7 holds the record for length 2 (7, 13)
  • 11 holds the record for length 1 (11 only)
These numbers (11, 7, 2, 2131 and 1531) form the first five terms of OEIS A109828. The subsequent five terms are 385591, 16651, 15514861, 857095381 and 205528443121.

Tuesday, 12 April 2016

Prime Number Chains

Now that I have regular Internet access I can resume scrutiny of my numbered days and today's number happens to be 24481 and prime. OEIS A110059 states that 24481 is the member of a sequence such that it is the smallest prime ending a complete Cunningham Chain of the second kind (2x-1) of length n. See my earlier post about Cunningham Chains. The sequence (up to n=13) is:

  1. 11
  2. 13
  3. 5
  4. 17041
  5. 24481
  6. 12338881
  7. 1065601
  8. 1985902081
  9. 219416417281
  10. 105230562877441
  11. 1422461638625281
  12. 444124661486837761
  13. 3105111850422067201
Now n=5 for 24481 and so adding 1 and dividing by 2 successively yields 12241, 6121, 3061 and 1531. So the complete chain is:

1531, 3061, 6121, 12241, 24481

The number is also a prime of the form 1+2n+3n^2 (OEIS A122430) and for 24481 the value on n is 90.

This prime number also has the property that it is a number n such that n remains prime through 5 iterations of the function f(x)=3x+10 (OEIS A023338). Applying this function rule yields progressively 73453, 220369, 661117, 1983361 and 5950093 and thus we have the prime number sequence:

24481, 73453, 220369, 661117, 1983361, 5950093

It also turns out that 24481 is a lucky number. To remind myself what that means, I've attached this definition from WolframAlpha:
Write out all odd numbers: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, .... The first odd number >1 is 3, so strike out every third number from the list: 1, 3, 7, 9, 13, 15, 19, .... The first odd number greater than 3 in the list is 7, so strike out every seventh number: 1, 3, 7, 9, 13, 15, 21, 25, 31, .... 
Numbers remaining after this procedure has been carried out completely are called lucky numbers. The first few are 1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, ... (OEIS A000959). Many asymptotic properties of the prime numbers are shared by the lucky numbers. The asymptotic density is 1/lnN, just as the prime number theorem, and the frequency of twin primes and twin lucky numbers are similar. A version of the Goldbach conjecture also seems to hold.

So it would seem that 24481 is indeed an interesting number.

Monday, 5 October 2015

Cunningham Chain

A Cunningham chain, named after a mathematician by that name, is a sequence of prime numbers formed by successively doubling the initial prime and either adding 1 (Cunningham chain of the first type) or subtracting 1 (Cunningham chain of the second type) to form new primes. The chain terminates with the last prime for which the process produces a composite number. 

For example: 2, 5, 11, 23, 47 form a chain of the first type with length 5 while 2, 3, 5 form a chain of the second type with length 3. All primes in a Cunningham chain are Sophie-Germain primes except the last and safe primes except the first. A Sophie-Germain prime is a prime \(p\) such that 2\(p\)+1 is also prime e.g. 5 is such a prime because 5  x 2+1=11. A safe prime is a prime \(p\) such that (\(p\)-1)/2 is also prime e.g. 23 is such a prime because (23-1)/2=11. 

The cryptocurrency Primecoin whose logo appears in this post makes use of Cunningham chains of both types. Such a cryptocurrency has connections with Anarcho-capitalism, a term much beloved by Jeff Berwick and defined by Wikipedia as: 
a political philosophy that advocates the elimination of political government - which distorts market signals, breeds corruption, and institutionalises monopoly - in favour of individual sovereignty, open markets (laissez-faire capitalism) and absence of invasive private property policies.

Additional posts regarding these sorts of chains can be found at:

 
 
on February 7th 2021