71–80 of 115 posts
There is a cute argument (I think it is due to Erdos) that, asymptotically, 0% of the integers in [0,n^2] appears in the "n by n multiplication table": By Erdos-Kac, almost all integers of size about n^2 have about log(log(n^2)) ~ log(log(n)) prime factors. However, almost all integers in the multiplication table have about 2*log(log(n)) prime factors. Kevin Ford gets much more precise asymptotic estimates.
Earlier quoted context omitted.
There are about 18.446 quintillion more 64-bit integers than 32-bit integers.
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.
X = ab and aY 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...
I dream of a future where all 64-bit integers are products of 32-bit integers. Together, we can change math for the better.
Earlier quoted context omitted.
All the primes above 2^32 are out, but that accounts for only two point something percent.
But also all of their multiples. I suspect that those account for the vast majority.
[1] The bounds are important because they guarantee that there is at most one prime factor from that range and this ensures that we are not double counting anything. If the upper bound was larger than the square of the lower bound, then we would have to worry about double counting numbers with more than one large prime factor.
I dream of a future where all 64-bit integers are products of 32-bit integers. Together, we can change math for the better.
> I find it interesting to consider that if you pick a value at random, it will usually fail! That is, most 64-bit integers cannot be written as the product of two 32-bit integers. While I find the 17% number interesting to think about, "most" is far less interesting. Multiplication doesn't care about order so you're instantly cutting 2^64 possibilities down to about 2^63. That's a hair's breadth away from "most" alr…
I dream of a future where all 64-bit integers are products of 32-bit integers. Together, we can change math for the better.
Earlier quoted context omitted.
But also all of their multiples. I suspect that those account for the vast majority.
Each x is prime with probability 1/ln(x), each x has M/x multiples less than M, as a fraction of M that is just 1/x. Together that makes 1/(x ln(x)) with the indefinite integral ln(ln(x)). If we plug in 2^32 and 2^64 [1], we get ln(2). So about 69.3 % of all 64 bit integers should have a prime factor larger than 2^32 and therefore not be the product of two 32 bit integers. That leaves about 13 % unaccounted. Three pr…
Extremely strange way to deliver the headline (right before delivering the headline).