# Why Jigsaw Puzzles Almost Never Have the Number of Pieces it Says on the Box

Image: Wikimedia Commons

This piece was originally published on God Plays Dice.

Patrick Honner tweeted a few days ago:

So let’s say that a number is a “puzzle number” if it’s of the form m x n with m ≤ n ≤ 2m — that is, a puzzle has to have an aspect ratio between 1 (square) and 2. (The choice of 2 is arbitrary here, but any other constant would be more arbitrary.) We can easily work out the first few puzzle numbers:

2 = 1x2, 4 = 2x2, 6 = 2x3, 8 = 2x4, 9 = 3x3

which is enough to find them in the OEIS: that’s A071562, defined as “Numbers n such that the sum of the middle divisors of n (A071090) is not zero.” (What’s a “middle divisor”, you ask? It’s a divisor of n that’s between (square root n/2) and (square root 2n.)) Titling it that way seems a bit strange to me: I’d have called it “Numbers such that the number of middle divisors of n (A067742) is nonzero.”

The first 10,000 puzzle numbers have been calculated; the 10,000th is 35,956. There are 43 under 100, 336 under 1,000, and 2,932 under 10,000 — it doesn’t appear that they have constant density. It’s not hard to take this further — there are 26,870 under 10^5, 252,756 under 10^6, 2,409,731 under 10^7 and 23,169,860 under 10^8. For example, in R, you can generate the puzzle numbers as follows. (This take a few seconds to run. Note that you don’t have to compute any prime factorizations.)

N = 10^8
= rep(0, N)

for (m in 1:floor(sqrt(N))){
maxn = min(2m,floor(N/m))_ a[m(m:maxn)] = a[m*(m:maxn)]+1
}

puzzle = which(a >= 1)

I had at first thought this sequence had a natural density, because I was only trying numbers up to a few hundred in my head, and because the number of middle divisors appears to average somewhere around log (2). There’s a nice heuristic for this — a middle divisor of n is somewhere between (square root n/2) and (square root 2n); the “probability” that a number is divisible by k is 1/k, so the “expected number” of middle divisors of n is: