2026-01-12 20:41:29
The previous post contained an interesting observation:
Is it true more generally that
for large n? Sorta, but the approximation gets better if we add a correction factor.
If we square both sides of the approximation and move the factorials to one side, the question becomes whether
Now the task becomes to estimate the middle coefficient in when we apply the binomial theorem to (x + y)2n.
A better approximation for the middle binomial coefficient is
Now the right hand side is the first term of an asymptotic series for the left. The ratio of the two sides goes to 1 as n → ∞.
We could prove the asymptotic result using Stirling’s approximation, but it’s more fun to use a probability argument.
Let X be a binomial random variable with distribution B(2n, 1/2). As n grows, X converges in distribution to a normal random variable with the same mean and variance, i.e. with μ = n and σ² = n/2. This says for large n,
The argument above only gives the first term in the asymptotic series for the middle coefficient. If you want more terms in the series, you’ll need to use more terms in Stirling’s series. If we add a couple more terms we get
Let’s see how much accuracy we get in estimating 52 choose 26.
from scipy.special import binom
from numpy import pi, sqrt
n = 26
exact = binom(2*n, n)
approx1 = 4**n/sqrt(pi*n)
approx2 = approx1*(1 - 1/(8*n))
approx3 = approx1*(1 - 1/(8*n) + 1/(128*n**2))
for a in [approx1, approx2, approx3]:
print(exact/a)
This prints
0.9952041409266293 1.0000118903997048 1.0000002776131290
and so we see substantial improvement from each additional term. This isn’t always the case with asymptotic series. We’re guaranteed that for a fixed number of terms, the relative error goes to zero as n increases. For a fixed n, we do not necessarily get more accuracy by including more terms.
2026-01-12 20:00:39
A few days ago I wrote two posts about perfect shuffles. Once you’ve cut a deck of cards in half, an in-shuffle lets a card from the top half fall first, and an out-shuffle lets a card from the bottom half fall first.
Suppose we have a deck of 52 cards. We said in the earlier posts that the order of an in-shuffle I is 52. That is, after 52 in-shuffles, a deck returns to its initial order. And the order of an out-shuffle O is 8.
We can think of I and O as generators of subgroups of order 52 and 8 respectively in the group S of all permutations of 52 cards. I was curious when I wrote the earlier posts how large the group generated by I and O together would be. Is it possible to reach all 52! permutations of the deck by some combination of applying I and O? If not, how many permutations can be generated?
I’ve since found the answer in [1] in a theorem by Diaconis, Graham, and Kantor. I don’t know who Kantor is, but it’s no surprise that a theorem on card shuffles would come from Persi Diaconis and Ron Graham. The theorem covers the case for decks of size N = 2n, which branches into different results depending on the size of n and the value of n mod 4.
For N = 52, the group generated by I and O has
26! × 226
elements.
On the one hand, that’s a big number, approximately 2.7 × 1034. On the other hand, it’s quite small compared to 52! = 8 × 1067. So while there are a lot of permutations reachable by a combination of in-shuffles and out-shuffles, your chances of selecting such a permutation from the set of all such permutations is vanishingly small.
To put it yet another way, the number of arrangements is on the order of the square root of 52!, a big number, but not big relative to 52!. (Does this pattern
√52! ≈ 26! × 226
generalize? See the next post.)
Not only does the theorem of Diaconis et al give the order of the group, it gives the group itself: the group of permutations generated by I and O is isomorphic to the group of symmetries of a 26-dimensional octahedron.
[1] S. Brent Morris. Magic Tricks, Card Shuffling and Dynamic Computer Memories. MAA 1998.
The post Combining in-shuffles and out-shuffles first appeared on John D. Cook.2026-01-11 00:05:21
When I wrote about how Primecoin uses prime chains for proof of work, I left out a detail.
To mine a new Primecoin block, you have to find a prime chain of specified length that starts with a number that is a multiple of the block header hash. According to the Primecoin whitepaper
Another important property of proof-of-work for cryptocurrency is non-reusability. … To achieve this, the prime chain is linked to the block header hash by requiring that its origin be divisible by the block header hash.
So given a hash h, you have to find k such that kh is the origin of a prime chain, where “origin” is defined in footnote [2] here.
Strictly speaking, the primes in a Primecoin prime chain are probable primes. Someone verifying a Primecoin blockchain will be satisfied that the block is authentic if the necessary numbers are prime according to the test used by the Primecoin software. Whether the numbers are actually prime is irrelevant.
Probabilistic primality tests are much more efficient than deterministic tests, and most applications requiring primes, such as RSA encryption, actually use probable primes. If a number is rejected as a probable prime, it’s certainly not a prime. If it is accepted as a prime, it very like is prime. More on probable primes here.
If you write your own Primecoin mining software using a different primality test, that’s fine as long as you actually find primes. But if one time you find pseudoprimes, composite numbers that pass your primality test, then your block will be rejected unless your pseudoprimes also pass the Primecoin software’s primality test.
So what is Primecoin’s (probable) primality test? We quote the Primecoin whitepaper:
The classical Fermat test of base 2 is used together with Euler-Lagrange-Lifchitz test to verify probable primality for the prime chains. Note we do not require strict primality proof during verification, as it would unnecessarily burden the efficiency of verification. Composite number that passes Fermat test is commonly known as pseudoprime. Since it is known by the works of Erdös and Pomerance that pseudoprimes of base 2 are much more rare than primes, it suffices to only verify probable primality.
The Fermat test with base b says to test whether a candidate number n satisfies
bn − 1 = 1 mod n.
If n is prime, the equation above will hold. The converse is usually true: if the equation above hold, n is likely to be prime. There are exceptions, such as b = 2 and n = 561 = 3 × 11 × 17.
But what is the Euler-Lagrange-Lifchitz test? The whitepaper links here, a page by Henri Lifchitz that gives results generalizing those of Leonard Euler and Joseph-Louis Lagrange.
Suppose p is an odd prime. Then the Euler-Lagrange test says that if p = 3 mod 4, then q = 2p + 1 is also prime if and only if
2p = 1 mod q.
Lifchitz gives three variations on this result. First, if p = 1 mod 4, then q = 2p + 1 is also prime if and only if
2p = −1 mod q.
Together these two theorems give a way to test with certainty whether 2p + 1, i.e. the next term in a Cunningham chain of the first kind, is prime. However, the test is still probabilistic if we don’t know for certain that p is prime.
The last two results of Lifchitz are as follows. If p and q = 2p − 1 are prime, then
2p − 1 = 1 mod q
if p = 1 mod 4 and
2p − 1 = −1 mod q
if p = 3 mod 4.
The converses of these two statements give probable prime tests for q if we know p is prime.
So we can verify a (probable) prime chain by using Fermat’s test to verify that the first element is (probably) prime and use the Euler-Lagrange-Lifchitz test that the rest of the numbers in the chain are (probably) prime.
2026-01-10 21:56:54
I mentioned bi-twin prime chains in the previous post, but didn’t say much about them so as not to interrupt the flow of the article.
A pair of prime numbers are called twins if they differ by 2. For example, 17 and 19 are twin primes.
A bi-twin chain is a sequence of twin primes in which the average of each twin pair is double that of the preceding pair. For example,
5, 7, 11, 13
is a bi-twin chain because (5, 7) and (11, 13) are twin pairs of primes, and the average of the latter pair is twice the average of the former pair.
There is some variation in how to describe how long a bi-twin chain is. We will define the length of a bi-twin chain to be the number prime pairs it contains, and so the chain above has length 2. The BiTwin Record page describes a bi-twin chain of length k as a chain with k − 1 links.
It is widely believed that there are infinitely many twin primes, but this has not been proven. So we don’t know for certain whether there are infinitely many bi-twin prime chains of length 1, much less chains of longer length.
The bi-twin chain of length three with smallest beginning number is
211049, 211051, 422099, 422101, 844199, 844201
Bi-twin records are expressed in terms of primorial numbers. I first mentioned primorial numbers a few days ago and now they come up again. Just as n factorial is the product of the positive integers up to n, n primorial is the product of the primes up to n. The primorial of n is written n#. [1]
The longest known bi-twin chains start with
112511682470782472978099, 112511682470782472978101
and has length 9.
We can verify the chains mentioned above with the following Python code.
def bitwin_length(average):
n = average
c = 0
while isprime(n-1) and isprime(n+1):
c += 1
n *= 2
return c
for n in [6, 211050, 112511682470782472978100]:
print(bitwin_length(n))
[1] There are two conventions for defining n#. The definition used here, and on the BiTwin Record page, is the product of primes up to n. Another convention is to define n# to be the product of the first n primes.
The priomorial function in Sympy takes two arguments and will compute either definition, depending on whether the second argument is True or False. The default second argument is True, in which case primorial(n) returns the product of the first n primes.
2026-01-10 20:32:19
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.
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))
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 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 prime chain of the required length whose origin a multiple of the hash of the block header [2].
Primecoin allows any of the three kinds of prime chains mentioned above: Cunningham chains of the first or second kind, or a bi-twin prime chain. Primecoin adjusts its mining difficulty over time by varying the length of Cunningham or bi-twin chain needed to mint a new block.
[1] Strictly speaking, Primecoin requires finding probable prime chains, as explained here.
[2] The origin of a prime chain is n if the first item in a Cunningham chain of the first kind is is n + 1, or if the first item in a Cunningham chain of the first kind or a bi-twin chain is n − 1.
The post Prime chains first appeared on John D. Cook.2026-01-09 21:01:39
Suppose you have a set of k hash values, each n bits long. Can you compress the set into less than kn bits?
It’s not possible to compress a list of hashes into less than kn bits, but you can hash a set into fewer bits.
Suppose you have a set of 230, roughly a billion, 64-bit hashes. Sort the set and look at the size of gaps between elements. You might expect that consecutive items on the list are roughly 234 apart, and so you could reconstruct the list by reporting the first item and the gaps between the rest, which are 34-bit numbers, not 64-bit numbers, a savings of 30 bits per hash.
This doesn’t exactly work, but it’s the kernel of a good idea. We don’t know that the distance between hashes can be represented by a 34 bit number. The gap could be more or less than 234, but we don’t expect it to often be much more than 234. So we use a variable-length encoding such that when the distance between values is on the order of 234, or less, we save bits, but we allow for the distance to be any size.
What we’ve described is the essence of Golomb-Rice coding. Its implementation in the Bitcoin protocol is referred to as Golomb-Coded Sets (GCS), described in BIP 158. Golomb-Rice coding is also used other applications where the values to be compressed are not hashes, such as in lossless auto compression.
Let’s go into some detail as to how the distances between sorted values are represented. Suppose you expect the differences to be on the order of M where M is a power of 2. For each difference d, let q and r be the quotient and remainder by M, i.e.
d = qM + r.
Encode q as a unary number, i.e. string of q 1s, and encode r as an ordinary binary number. Then Golomb-Rice coding of d is the concatenation of the representations of q and r. with a 0 in the middle as a separator. Using || to denote string concatenation we have
unary(q) || 0 || binary(r).
In general, unary encoding is extremely inefficient, but we’re betting that q will typically be quite small.
The reason we require M to be a power of 2 is so the representation of r will have a fixed length [1].
Let’s work out an example. Suppose M = 220 and
d = 222 + 123456 = 4 × M + 123456.
Then we write q as 1111 and r as 0011110001001000000 and encode d as the string
111100011110001001000000
You can concatenate the encodings of consecutive d values and still be able to unambiguously decode the result. Because the r representations have a constant length, you know when an r ends and the next q begins.
For example, suppose we have the following string of bits.
1110010011001011001011111001000000110010001110011101111000101111011
We decode the string from left to right. We count how many ones we see, skip over a 0, then regarding the next 20 bits as a binary number.
111 0 01001100101100101111 1 0 01000000110010001110 0 11101111000101111011
We see three 1s before the first 0 and so we conclude q1 = 3. We skip over the 0 and read the value of r.
r1 = 01001100101100101111two = 314159.
Next we see a single 1 before the next 0, so q2 = 1. We read the next value of r as
r2 = 01000000110010001110two = 265358.
Next we see a 0, i.e. there are no 1s, and so the final q3 = 0. And we have
r3 = 11101111000101111011two = 979323.
So our reconstructed values of d are
d1 = q1M+ r1 = 3 × 220 + 314159 = 3459887
d2 = q2M+ r2 = 1 × 220 + 265358 = 1313934
d3 = q3M+ r3 = 0 × 220 + 979323 = 979323.
Now these are difference values. We need to know the smallest value m in order to construct the original set of values from the differences. Then the full values are m, m + d1, m + d1 + d2, and m + d1 + d2 + d3,.
[1] This is the Rice part. Robert Rice simplified Samuel Golomb’s encoding scheme in the special case that M is a power of 2.
The post Compressing a set of hash values first appeared on John D. Cook.
