11
$\begingroup$

The question seems simple, but I cannot wrap my head around how to properly count it, or even give a good estimate. I can't find the answer either.

We have two integer numbers $1 < a,b < N$, how many unique products of $a \cdot b$ there are? The possible simplification could be that $N$ is also a prime, as I also interested in a good estimation. My more basic question is it less than $O(N^2)$, but the actual count seems more interesting.

This seems related to How many unique combination of $n$ numbers are there when multiplying $x$ numbers?, though answerer there makes one assumption which is a killer IMO, all the products are distinct ("unless they have to" which, I believe, meant commutativity of multiplication). In the above the statement is clearly false. E.g. $1 \cdot 4 = 2 \cdot 2$ or $4 \cdot 4 = 2 \cdot 8$. $24$ would also appear quite some times.

What have I tried:

The obvious upperbound is $N^2$ which is a clear over-estimation (even if we divide it by 2 due to commutitativity) - we cannot obtain any compound involving prime $p_i$ such as $N < p_i < N^2$.

My approach was to count prime numbers and assume all the possible numbers are compounds of them, the answer from the cited question could be used then, but this is also not true. E.g. for $N=5$ we need to treat $4$ as a (pseudo) prime to get $20$.

I can't figure how to count numbers to be excluded from $N^2$, or which to include and when. I had idea that all numbers greater than $\sqrt{N}$ (or maybe $N/2$) can be treated as those pseudo-primes, but I am not sure if this is the correct way.

$\endgroup$
2
  • 3
    $\begingroup$ Your sequence is A027424 in OEIS (oeis.org/A027424). $\endgroup$
    – Tad
    Jun 23, 2015 at 11:57
  • 1
    $\begingroup$ To unpack Tad's comment a little bit: if you compute it for a few small $N$ (say, up to $N = 5$) and then look it up in the OEIS, you might have found A027424. That entry has a formula and a few different ways to use Mathematica and PARI to compute it for larger $N$. $\endgroup$
    – user153918
    Jun 23, 2015 at 16:53

1 Answer 1

4
$\begingroup$

This is a fairly hard problem, and one that at the very least is not solvable by methods from elementary combinatorics. It's sometimes referred to as Erdős' multiplication table.

For counting the exact number, OEIS A027424 gives several algorithms which compute the number of unique products $M(n)$ in the $n \times n$ multiplication table, but they all rely on computing the entire multiplication table and then counting the number of unique values. Hence their complexity is $\Theta(n^2)$, and it isn't really clear whether there's an algorithm that's much faster than that. See e.g. this question here and this one on MathOverflow.

The asymptotics of $M(n)$ are fairly well established. Erdős proved in 1955 that $M(n) = o(n^2)$, and Ford proved in 2008 arXiv link that (from this answer on Mathoverflow) $$ M(n) \asymp \frac{N^2}{(\log N)^c(\log\log N)^{3/2}}$$ where $$c=1-\frac{(1+\log \log 2)}{\log 2}. $$

$\endgroup$
1
  • $\begingroup$ Oh, my question is a dupe of the one on mathoverflow, I honestly thought it's a simpler problem, and I am just bad at counting. I think you made a nice summary for supposedly more entry level of Math SE, and for technicalities mathoverflow and references are good. I also read the references from OEIS and skimmed over the paper by Ford (after @Tad posted the link ofc) and came to the same conclusion. Thanks for extracting and nicely presenting the important conclusions. $\endgroup$
    – luk32
    Jun 23, 2015 at 20:11

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.