Remix.run Logo
Remix clone Hacker News
new | show | ask | jobsGithub
▲ henry2023 2 hours ago

There are about 4 billion 64 bit integers for each 32 bit integer.

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

▲HWR_14 2 hours ago | parent | next [-]

There are about 18.446 quintillion more 64-bit integers than 32-bit integers.

▲adrian_b an hour ago | parent | next [-]

True, but there are as many 64-bit integers as pairs of 32-bit integers.

Therefore the fact that relatively few 64-bit numbers are products of 32-bit integers means that a lot of pairs of 32-bit integers give by multiplication the same product.

▲moefh an hour ago | parent | prev | next [-]

I think they meant to write "There are about 4 billion TIMES more 64 bit integers than 32 bit integers".

▲henry2023 an hour ago | parent [-]

Indeed, edited the mistake

▲ 2 hours ago | parent | prev [-]
[deleted]
▲layer8 2 hours ago | parent | prev | next [-]

The chance of a random 64-bit integer matching some pair of 32-bit integers is a 100%, though.

▲brookst 2 hours ago | parent | prev | next [-]

Or, the odds of a random 64-bit integer being a 32-bit integer are the same as you or me guessing a random 32 bit integer.

▲rao-v 2 hours ago | parent | prev [-]

Wonder what the limit is as you add more 32 bit integers to the product. Just the primes over 32 bit?

▲thaumasiotes an hour ago | parent [-]

If you're allowed to multiply as many 32-bit numbers as you want, the only numbers you won't be able to achieve by so doing are those with any prime factor larger than 2^32.

This is more than just the prime numbers. For example, a 41-bit prime can be multiplied by 16 and it will still fit into 64 bits.

▲ 42 minutes ago | parent | next [-]
[deleted]
▲ an hour ago | parent | prev | next [-]
[deleted]
▲nyeah 39 minutes ago | parent | prev [-]

What are you assuming about overflow?

▲ 27 minutes ago | parent [-]
[deleted]