Only 17% of all 64-bit Integers are products of two 32-bit integers

11 points by rbr


dzwdz

This article doesn't really say much, sadly, except pointing out the hash function usecase. It does link the (vibe)code used to compute this result, and Algorithms for the Multiplication Table Problem (coauthored by the author of that repo) (submitted 2019, revised 2021):

Let M(n) denote the number of distinct entries in the n×n multiplication table. The function M(n) has been studied by Erdős, Tenenbaum, Ford, and others, but the asymptotic behaviour of M(n) as n→∞ is not known precisely. Thus, there is some interest in algorithms for computing M(n) either exactly or approximately. We compare several algorithms for computing M(n) exactly, and give a new algorithm that has a subquadratic running time. We also present two Monte Carlo algorithms for approximate computation of M(n). We give the results of exact computations for values of n up to 2^30, and of Monte Carlo computations for n up to 2^100'000'000, and compare our experimental results with Ford's order-of-magnitude result.

I like how this brings up multiplication tables, it makes it a bit easier for me to visualize this. There's some mildly interesting backstory in the introduction, showing yet another use for this:

The history of such [exact] computations goes back to Brent and Kung, who considered how much area and time are needed to perform an n-bit binary multiplication on a VLSI chip. For this, they needed a lower bound on M(2^n − 1).

Also potentially of interest:

As far as we are aware, this project represents the first time that the Bach algorithm for producing random factored numbers has been usefully implemented

As for the results: they've computed exact values for k=[18..30] (which the graph in TFA didn't include, for some reason?). "The computation took about 7 weeks on Butler University’s BigDawg cluster which has 32 Intel Xeon E5-2630 processors (a total of 192 cores)".

They only ran the Monte Carlo estimations for a few mostly non-computery rules, so we don't have an original estimation for 2^32 to compare with, but they got 16.44% for N=2^40-1. The highest they went is 1.21% for N=10^8-1. I don't think they shared the amount of time the estimations took, but I'd assume they were pretty cheap (not to imply that knowing the exact value isn't interesting!).

You might also find their lecture slides interesting, also A027417, A027424, A027384.