Only 17% of all 64-bit Integers are products of two 32-bit integers • Hacker News Board

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

#111

Post by shiandow » Wed, Jun 03, 2026, 10:05 PM UTC

thaumasiotes wrote: post #104

shiandow wrote: post #95

Earlier quoted context omitted.

If you bring overflow into the mix things become a lot more complicated. You likely don't even need 32 bits, the numbers 2 and 3 might be enough (I don't know for sure or if there's a quick way to check).

Well, if you "bring overflow into the mix", what you get depends on your behavior when overflowing. If you say that you want to be doing modular arithmetic instead of arithmetic, it doesn't look like 2 and 3 are enough. You're looking for a solution to 2ᵃ * 3ᵇ ≡ n (mod 2⁶⁴) If n is even, we can supply any number of 2 factors by fiddling with a. We can assume without loss of generality that n is odd and a = 0. Now we…

Interesting, one of those situations where the odd primes behave slightly differently. Which means it's probably above my paygrade.

I did say things would get complicated.

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

#112

Post by kurlberg » Wed, Jun 03, 2026, 10:20 PM UTC

tucnak wrote: post #71

kurlberg wrote: post #67

There is a cute argument (I think it is due to Erdos) that, asymptotically, 0% of the integers in [0,n^2] appears in the "n by n multiplication table": By Erdos-Kac, almost all integers of size about n^2 have about log(log(n^2)) ~ log(log(n)) prime factors. However, almost all integers in the multiplication table have about 2*log(log(n)) prime factors. Kevin Ford gets much more precise asymptotic estimates.

They address this argument in the blog.

Where?

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

#113

Post by svat » Thu, Jun 04, 2026, 2:44 PM UTC

bonzini wrote: post #69

_alternator_ wrote: post #65

> You might be able to come up with a more efficient algorithm. Challenge accepted. Suppose we want to know the answer to 3 decimal places (so we'd match the headline). And suppose I allow my algorithm to be wrong one in a thousand times ("probably approximately correct"). Then sample some constant number C of random 64 bit integers. Run the following algorithm which separates each random sample into one of three cla…

Even if you have 32-bit factors the number may not be the product of two 32-bit numbers. For example 2^62*3 cannot be split as either (2^32, 2^30*3) or (2^31, 2^31*3). In both cases one factor does not fit in 32 bits.

I think by "have 32 bit factors" the GP actually means "has a factorization as a product of two 32-bit numbers", rather than the natural meaning that doesn't work, as you pointed out.

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

#114

Post by svat » Thu, Jun 04, 2026, 2:53 PM UTC

Dylan16807 wrote: post #108

svat wrote: post #100

Earlier quoted context omitted.

The word “most” is indeed not very surprising if taken to mean >50% (as you do), but the surprising fact (admittedly not relevant for 2^64 in the quoted sentence) is that “most” can be replaced with “almost all” in the technical sense meaning “tending to 1” i.e. “1 - o(1)”, i.e. “eventually greater than 1-epsilon for any epsilon”. Here's the multiplication table up to 9 (so for n=10 in place of n=2^64), and it alread…

It's an interesting fact, but it's weakened a lot by happening so slowly and not matching the everyday definition of "almost all". And it's weakened even more by realizing that while you can get the raw fraction as low as you want, shrinking your list of products by n digits requires numbers with an exponential number of digits.

I think your second paragraph is the same as “so slowly”, just quantified. And I'd argue that the technical meaning of “almost all” does match the everyday definition: if you told someone that “for sufficiently large N, almost all 2N-bit numbers are not the product of two N-bit numbers”, they'd probably think of “almost all” as a fraction like 99.99% or 99.999999% or whatever, and whatever fraction they picked, the statement would be true (with the threshold for “sufficiently large” depending on the fraction they picked).

So whether “only 17%” is interesting or not depends on whether you see it as a stand-in for “less than half”, or “a number close to 0”.

(Posting this comment mainly to correct an error in my previous comment: in both places that I wrote “n=2^64” I should have instead written “n=2^32”.)

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

#115

Post by Dylan16807 » Thu, Jun 04, 2026, 8:15 PM UTC

svat wrote: post #114

Dylan16807 wrote: post #108

Earlier quoted context omitted.

It's an interesting fact, but it's weakened a lot by happening so slowly and not matching the everyday definition of "almost all". And it's weakened even more by realizing that while you can get the raw fraction as low as you want, shrinking your list of products by n digits requires numbers with an exponential number of digits.

I think your second paragraph is the same as “so slowly”, just quantified. And I'd argue that the technical meaning of “almost all” does match the everyday definition: if you told someone that “for sufficiently large N, almost all 2N-bit numbers are not the product of two N-bit numbers”, they'd probably think of “almost all” as a fraction like 99.99% or 99.999999% or whatever, and whatever fraction they picked, the s…

> if you told someone that “for sufficiently large N, almost all 2N-bit numbers are not the product of two N-bit numbers”, they'd probably think of “almost all” as a fraction like 99.99% or 99.999999% or whatever, and whatever fraction they picked, the statement would be true (with the threshold for “sufficiently large” depending on the fraction they picked).

I think people would agree with that, yes. But that's a significantly weaker claim than your original one. The original version was "tends to 1 at large n" = "almost all", but this version is that once you reach large n it's "almost all". These different tests give completely different answers for the numbers you'd ever actually use.

And entirely separate from that, if you laid it out as "for 8 million* digit numbers, only one in a billion are products of 4 million digit numbers, so only enough to fill out 7,999,991 digits", I don't know if that really qualifies for "almost all" anymore. The fraction of hits is important, but so is the fraction of digits and entropy, and as you make the numbers bigger you approach 0.0% loss of digits and entropy.

* Placeholder number, I did not do the actual calculation here.