3
$\begingroup$

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

graph

$\endgroup$
  • $\begingroup$ This question reminds me of Project Euler --- some interesting questions. Can you use programming? $\endgroup$ – Andrew Kelley Mar 3 '14 at 3:46
  • $\begingroup$ In fact, I imagine a brute force calculation in C++ would take under a minute: just compute all possible products and stuff them in an unordered_set. $\endgroup$ – Hurkyl Mar 3 '14 at 3:49
  • $\begingroup$ I just checked, and $2(64^{4}) < 100^{4}$. So your initial guess is not correct, but I think this is very similar to what you did notice (about $11^5$). $\endgroup$ – Andrew Kelley Mar 3 '14 at 3:51
  • $\begingroup$ @Hurkyl Thank you for your unordered_set suggestion, the result was found under a second. $\endgroup$ – qwr Mar 3 '14 at 5:04
  • 1
    $\begingroup$ Excel finds a fit $y=0.1326x^{3.2858}$ that looks good to the eye. For a cubic fit, it finds $y = 0.6849x^3 - 15.791x^2 - 35.111^x + 3240.3$ which also looks good. $\endgroup$ – Ross Millikan Mar 3 '14 at 23:13
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hash table and bit array are alternatives to sorting. $\endgroup$ – Hurkyl Mar 3 '14 at 4:05
  • $\begingroup$ I've already written a program for this, I'm just wondering if there's an easy approximation or exact answer by hand. $\endgroup$ – qwr Mar 3 '14 at 4:05
  • $\begingroup$ By the way, the actual number is around $520,000$. $\endgroup$ – qwr Mar 3 '14 at 4:57
  • 1
    $\begingroup$ @qwr: I think the first step towards conjecturing approximately how many there should be would be to compute a table and a graph of the actual exact values for the problem, with $100$ replaced by $n$ for many values of $n$; e.g. maybe every small multiple of $10$, or maybe for all $n < 100$. The graph may give useful clues. You might want to plot the log of the number as well. $\endgroup$ – Hurkyl Mar 3 '14 at 5:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.