Unique number of numbers multiplied together

Question

I'm sure this has been asked before, but how many unique numbers can be made from multiplying $4$ numbers, each between $1$ and $100$?

My guess is the all numbers from $1$ to $100^4$ except those with prime factors above $100$. However this excludes numbers like $11^5$. Then I would also have to exclude numbers with more than $4$ prime factors, and each one is $\ge 11$. I'm probably still missing some though.

Is there a way to find or get an estimate of this number without using a computer? I'm guessing something to do with the prime counting function. Any insight is appreciated.

Edit: Here are some data points (range, unique numbers). Can anyone find a pattern?

10,275
20,2670
30,8679
40,21346
50,49076
60,89247
70,149530
80,253818
90,381413
100,520841

Answer 1

You are looking at a four-dimensional analogue of the famous "Erdös multiplication table problem". In that problem, we want to know $N_2(x)$, the number of distinct integers occur in the form $mn$ where $1\le m\le x$ and $1\le n\le x$. Clearly $N_2(x)$ is less than $x^2$; Erdös was the first to show that $N_2(x)/x^2$ tends to $0$ as $x$ tends to infinity. A series of improvements, culminating in work of Kevin Ford, showed that $N_2(x)$ is about $x^2$ divided by a small power of $\log x$.

You're now asking about $N_4(x)$, defined similarly. I suspect that $N_4(x)$ is about $x^4$ divided by a slightly larger power of $\log x$. In particular, there are probably methods for getting lower bounds for $N_2(x)$ (e.g., showing that $N_2(x)/x^{2-\varepsilon}$ tends to infinity with $x$, for any fixed $\varepsilon>0$) that could be extended to show that $N_4(x)$ is eventually larger than $x^\alpha$ for every $\alpha<4$.

Answer 2

The simple computer route to this is to do four nested loops. You can require that each number be at least as large as the one before, which gives somewhat more than $\frac 1{4!}100^4 \approx 4,200,000$ products (the divisor is smaller when there are duplicates), then sort the products and throw out duplicates. I suspect it is rather close to $4E6$ because there won't be many duplicates, but that is a guess. Even up to $1000$ is easily within desktop computer speed.