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$
6
  • $\begingroup$ This question reminds me of Project Euler --- some interesting questions. Can you use programming? $\endgroup$ Commented Mar 3, 2014 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$ Commented Mar 3, 2014 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$ Commented Mar 3, 2014 at 3:51
  • $\begingroup$ @Hurkyl Thank you for your unordered_set suggestion, the result was found under a second. $\endgroup$ Commented Mar 3, 2014 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$ Commented Mar 3, 2014 at 23:13

2 Answers 2

Reset to default
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$
4
  • $\begingroup$ Hash table and bit array are alternatives to sorting. $\endgroup$ Commented Mar 3, 2014 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$ Commented Mar 3, 2014 at 4:05
  • $\begingroup$ By the way, the actual number is around $520,000$. $\endgroup$ Commented Mar 3, 2014 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$ Commented Mar 3, 2014 at 5:12

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.