[henry2023]

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]

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

[adrian_b]

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.

[aidenn0]

That seems intuitively true given that most 32-bit numbers are composite, so if you have

X = ab and aY < 2^32 and bY < 2^32:

X × Y = X/a × aY = X/b × bY = Y × X = aY × X/a = bY × X/b

Which is 6 pairs resulting in the same product. This will be reduced if e.g. aY = X, but still...

[moefh]

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

[henry2023]

Indeed, edited the mistake

[bo1024]

There are about 2^64 more 64-bit integers than 32-bit integers.

[layer8]

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

[brookst]

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]

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

[thaumasiotes]

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.

[nyeah]

What are you assuming about overflow? Three 32-bit numbers multiply out to 96 bits.

[shiandow]

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).

[thaumasiotes]

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 want

    3ᵇ ≡ n (mod 2⁶⁴)

for odd n.

If I'm reading wikipedia correctly, we know that this will fail for some n:

https://en.wikipedia.org/wiki/Primitive_root_modulo_n

> In symbols, g is a primitive root modulo n if for every integer a coprime to n, there is some integer k for which gᵏ ≡ a (mod n).

This is what we want, with g = 3, k = b, a = n₁, and n₂ = 2⁶⁴. Our restriction that n₁ (our n) is odd satisfies the requirement that a be coprime to n₂ (wikipedia's n, the modulus).

The article continues:

> a primitive root exists modulo n if and only if n is 4, pᵏ or 2pᵏ for some odd prime number p and some k ≥ 0.

2⁶⁴ does not satisfy this requirement and therefore there is no primitive root modulo 2⁶⁴. As such, 3 is not a primitive root modulo 2⁶⁴.

[shiandow]

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.