Daniel Lemire posted a short math-heavy note about a simple sounding question with a non-obvious answer: among all 64-bit unsigned integers, only 3,215,709,724,700,470,902 of them, about 17%, can be written as the exact product of two 32-bit unsigned integers. The setup matters. There are as many ordered pairs of 32-bit integers as there are 64-bit integers, so at first glance it is tempting to expect broad coverage. But multiplication collapses many different input pairs onto the same output, first because it is commutative and then because composite numbers admit many factorizations. The discussion landed on that distinction. “Most are missing” is not the surprising part. You already lose nearly a factor of two from symmetry alone. The interesting part is how much extra loss comes from repeated products, and how slowly the density falls as numbers grow even though, asymptotically, it still goes to zero.
If you rely on multiplication to spread values across a fixed-width output space, the output set is far sparser and more collision-prone than intuition suggests, which is a useful gut check for hash design, encoding tricks, and low-level systems work.
Mostly intrigued and mildly amused. People found the 17% figure neat, but many immediately argued the headline oversells the surprise because symmetry and heavy aliasing already make broad gaps inevitable.
01 The asymptotic result is the real mathematical punchline, not the 17% headline.
The density of products in the n by n multiplication table tends to zero, but it does so painfully slowly. Even tiny tables already show the effect, with only 37 distinct products out of 100 entries for 0 through 9. That makes the finite 64-bit result feel less magical and more like one point on a very long, slow decay curve.
The surprising fact is not that many values are missing. It is that the reachable fraction eventually vanishes even though the drop is glacial at practical sizes.
02 The cleanest way to think about the result is in bits, not percentages.
The reachable outputs are about 2^61.44 rather than 2^64, so multiplication loses roughly 2.56 bits of output coverage. That is a much milder statement than “83% unreachable,” and it matches other places where huge-looking redundancy in raw counts is modest in information terms, like IEEE-754 NaN encodings and NaN-boxing tricks used by dynamic language runtimes.
Linear sparsity can look dramatic while information loss stays modest. For systems work, the bit-level view is often the more honest one.
03 Having no prime factor above 2^32 is necessary but not sufficient.
Numbers can be 2^32-smooth and still fail because their prime factors cannot be packed into two groups whose products both fit in 32 bits. Examples like 70 in base 10 and 2^62×3 at 64 bits show that the problem is really constrained factor partitioning, not just smoothness testing.
This is stricter than checking for large prime factors. The hard part is whether the factorization can be split into two 32-bit-sized chunks.
04 A Monte Carlo estimate is easy to sketch, but a naive version quietly turns into a factoring problem.
Probabilistic primality tests and bounded Pollard rho can classify some cases quickly, yet they bog down as factors get larger. Replacing partial factorization with Kalai’s method for sampling integers together with their prime factors makes the approximation practical again, and mirrors the kind of machinery used in the underlying math.
Even estimating this density efficiently forces you into number theory machinery. The naive “just sample and factor” instinct does not scale.
01 The headline dresses up a fairly easy threshold crossing.
Commutativity alone almost guarantees that “most” 64-bit values are not hit, so the interesting quantity is not whether the fraction is below 50% but how far below and in what sense. Even the scarcity of high-bit outputs is not extreme enough to make the result feel shocking.
Treat 17% as a quantification of aliasing, not as a paradox. The novelty is in the exact count and asymptotics, not the word “most.”
02 The practical hashing angle may be weaker than the post suggests.
Good hash designers have long known that multiplication over fixed-width integers is highly structured and far from uniform over all possible outputs, so this result is more of a mathematical illustration than an engineering revelation.
Interesting math does not automatically imply new hash guidance. Competent low-level engineers already assume multiplication has strong output bias and collisions.