Hacker News

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

47 points by sebg 4 days ago | 9 comments

Dylan16807 30 minutes ago

> I find it interesting to consider that if you pick a value at random, it will usually fail! That is, most 64-bit integers cannot be written as the product of two 32-bit integers.

While I find the 17% number interesting to think about, "most" is far less interesting. Multiplication doesn't care about order so you're instantly cutting 2^64 possibilities down to about 2^63. That's a hair's breadth away from "most" already, and considering even a tiny amount of overlapping results gets you there.

What gets interesting is actually trying to quantify the overlapping results.

danbruc 21 minutes ago

All the primes above 2^32 are out, but that accounts for only two point something percent.

adgjlsfhk1 24 minutes ago

A lot of the remaining is multiples of 4, which you can either get from having a 2 in both factors or a 4 in one (multiples of 9 are similar).

PaulHoule 21 minutes ago

... or just considering the even numbers almost all of them are 2 x N where N>2^32 and that gets you to within a hair of "most" and if you add in the odd thirds for which the same is true you get a bound of 2/3.

henry2023 4 minutes ago

There are about 4 billion more 64 bit integers than 32 bit integers.

The chance of a random 64 bit integer being a 32 bit integer is 0.0000000233 %

The chance of a random 64 bit integer being a product of two 32 bit integers is 17%

Nice

nyeah 20 minutes ago

At the upper end you burn through the dynamic range pretty quickly. Largest eight products of 8-bit fixed-point numbers:

  {255 through 226 not used}   15 \* 15 = 225 
  {224 through 211 not used}  15 \* 14 = 14 \* 15 = 210 
  {197 through 209 not used}  15 \* 13 = 13 \* 15 = 195    
  14 \* 14 = 196
  {183 through 194 not used}   14 \* 13 = 13 \* 14 = 182

Toy example. Of course with 32-bit x 32-bit products, you skip way more 64-bit numbers than shown above.

pants2 34 minutes ago

I dream of a future where all 64-bit integers are products of 32-bit integers. Together, we can change math for the better.

kleiba2 8 minutes ago

I upvoted you, not because I think your joke is particularly great, but I hate that HN has this tendency to downvote comments that are clearly meant as a humorous contribution. And I get it, no-one wants HN to turn into Reddit. I also understand that not every joke lands. But I just think it's unnecessary to downvote, you could simply ignore.

zamadatix 3 minutes ago

"Ignore" is one of those things that sounds like it's a neutral choice but really isn't in practice - it's still just saying "can only ever be positively pressured". People shouldn't flag, at the very least.