Primecoin and Cunningham Prime Chains

Summary

The title of this post has a double meaning. We will look at chains in the sense of number theory and in the sense of cryptocurrency, i.e. Cunningham chains and blockchains, that involve prime numbers. Cunningham chains A chain of primes is a sequence of prime numbers in which each is almost double its predecessor. That is, the next number after p is 2p ± 1. In a Cunningham chain of the first kind, the successor of p is 2p + 1. For example, 41, 83, 167. In a Cunningham chain of the second kind, the successor of p is 2p − 1. For example, 19, 37, 73. Two questions come up immediately. First, are there infinitely many Cunningham chains? Second, how long can a Cunningham chain be? What is known and what is conjectured are at opposite ends of the spectrum. It is unknown whether there are infinitely many Cunningham chains of length 2, but it is conjectured that there are infinitely many Cunningham chains of all lengths. According to this page, the longest known Cunningham chains of the first kind has length 17, and the longest known Cunningham chain of the second kind has length 19. We can verify these results with the following Python code. from sympy import isprime def chain_length(start, kind): p = start c = 0 while isprime(p): c += 1 p = 2*p + kind return c print(chain_length(2759832934171386593519, 1)) print(chain_length(79910197721667870187016101, -1)) Bi-twin chains A number n is the basis of a bi-twin chain of length k if n − 1 is the start of a Cunningham chain of the first kind of length k and n + 1 is the start of a Cunningham chain of the second kind of length k. I say more about bi-twin prime chains in the next post. Primecoin Primecoin was one of the first cryptocurrencies, coming out four years after Bitcoin. Primecoin is still going, though its market cap is six orders magnitude smaller than that of Bitcoin. What’s interesting about Primecoin is that it uses finding prime chains as its proof of work task [1]. To mint a new Primecoin block, you must find a ...