Why puzzles almost never have the number of pieces listed on the box

This piece was originally published on God plays dice.

Patrick Honner tweeted a few days ago:

So let’s say a number is a “puzzle number” if it has the form mxn with m ≤ n ≤ 2m – i.e. a puzzle must 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 calculate the first numbers of the puzzle:

2 = 1×2, 4 = 2×2, 6 = 2×3, 8 = 2×4, 9 = 3×3

which suffices to find them in the OEIS: it is A071562, defined as “Numbers n such that the sum of the median divisors of n (A071090) is not zero”. (What is a “median divisor”, you ask? It’s a divisor of not it’s between (square root n/2) and (square root 2n.)) Naming it that way seems a little odd to me: I would have called it “Numbers such that the number of median 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 – they don’t seem to have a constant density. It’s not hard to go 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 takes 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))){
maximumn = min(2m,soil(N/m))_
a[m(m:max
n)] = one[m*(m:maxn)]+1
}

puzzle = which(a >= 1)

I had originally 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 median divisors seems to average around log ( 2). There’s a nice heuristic for this – a median 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 median divisors of n is:

Screenshot 2020-08-24 at 8.41.32 AM.png

But there must be more numbers as you go that have many mean divisors and more zeros. This is similar to the behavior you see for the “how many ways can an integer be written as a sum of two squares” problem. In this case, the “average” is π/4, but an integer greater than one can be written as a sum of two squares if and only if its first decomposition does not contain any prime number congruent to 3 mod 4 raised to an odd power; asymptotically the number of positive integers below x that are the sum of two squares goes as bx / (log square root x) for a constant b (the constant is the Landau-Ramanujan constant). This connection could come from the fact that the two sequences are multiplicative. For sums of two squares, this follows from characterization based on factorization or from the fact that

Screenshot 2020-08-24 at 8.42.53 AM.png

For puzzle numbers, this stems from a remark by Franklin T. Adams-Watters in the OEIS entry. So numbers that have a lot of factors tend to be sums of two squares and to be puzzle numbers in different ways; as we reach larger numbers, these begin to “crowd out” the smaller numbers.

The Mathematical Internet has noticed this at least once before. John D. Cook wrote in 2014, “Puzzles that say they have 1,000 pieces have about 1,000 pieces, but probably not exactly 1,000. The puzzle pieces are usually arranged in a grid, so the number of pieces the along one side must be a divisor of the total number of pieces. This means there aren’t many ways to make a puzzle with exactly 1,000 pieces, and most have awkward aspect ratios.

1000 as 25 by 40 seems reasonable, but 27 x 37 = 999 or 28 x 36 = 1008 would also work. I guess you wouldn’t actually see a 999 piece puzzle because the lawyers would claim the 1000 piece appeal was false advertising. A puzzle blog says that most “500 piece” puzzles are actually 27 x 19 = 513 and most “1000 piece” puzzles are 38 x 27 = 1026 – these two aspect ratios are approximations of (square root 2). This is a good aspect ratio to use if you want to be able to create both “500 piece” and “1000 piece” (or more generally, “N piece” and “2N piece”) versions of the same puzzle. Similarly, the A0, A1, … series of paper sizes used in most countries of the world have this aspect ratio and therefore a piece of paper can be cut into two A(n+1) pieces.