[sdenton4]

Concatenating arbitrary 32 bit ints covers all possible 64 bit ints. So the space of all pairs of 32 bit ints is in bijection with 64 bit ints.

Commutativity introduces a relation on pairs of 32 bit ints (a,b) ~ (b,a), which accounts for one bit of information. Thus, at most 50% of 64bit ints show up as products of 32 bit ints.

[FabHK]

Ah, fair enough, thanks everyone. So basically the argument is if that we have a deterministic function taking a pair (x_1, x_2) with x_i in X with |X| = M, then the function can produce at most M^2 outputs. And knowing that the function is symmetric cuts it down to M(M+1)/2. (Which is still far bigger than the 2M in my addition analogy.) Cheers.

[Dylan16807]

Except the perfect squares don't reduce by half, so it's not quite 50% but it's very close.

[thesz]

Some of them, with notable exception of perfect squares of primes, can be expressed by products of different combinations of factors.

E.g., 6^2 = (223)3 = 2(233).

One of ~22 (ln(2^32)) perfect squares will be a square of perfect prime. Most won't.

[mkl]

Decoding this so it's readable: 6^2 = (2*2*3)*3 = 2*(2*3*3).

(You can escape * with \: \*)

[sdenton4]

Ha, fair!