Well that led me down an unexpected rabbit hole. I happened to be looking for ways to subset scatter-gather queries in a distributed database using composite hash keys and this seemed relevant. Grid partitioning (or multi-dimensional indexing) I knew of, but then also found Morton Z-Ordering (Bit-Interleaving), Coprime Matrix Multiplication (Lattice Hashing), Locality-Sensitive Hashing (LSH) / Random Projections and its relation to perceptual hashing.

Then I realized it's on Daniel Lemire's blog which is very fitting. Thanks HN.

Human intuition often is very bad for this kind of question.

For example, for n=2⁶⁴, there are about 4×10¹⁷ primes and about 4×10⁹ squares less than n.