Hacker News Reader

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.

View on HN

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.

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

Ha, fair!

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.

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

(You can escape * with \: \*)

Reply on news.ycombinator.com