Comment by 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
There are about 18.446 quintillion more 64-bit integers than 32-bit integers.
I think they meant to write "There are about 4 billion TIMES more 64 bit integers than 32 bit integers".
Indeed, edited the mistake
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.
The chance of a random 64-bit integer matching some pair of 32-bit integers is a 100%, though.
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.
Wonder what the limit is as you add more 32 bit integers to the product. Just the primes over 32 bit?
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.
What are you assuming about overflow?
1 reply →