What is the probability for an integer in the interval $[1,n^2]$ not to be the product of two integers in the interval $[1,n]$?
i know it is at least $$\sum_{i=1}^{\infty}\left(\log(1+\frac{1}{2i-1})\right)^{2i-1}.$$
Asked
Active
Viewed 76 times
1
-
3It is asymptotic to 1. This is equivalent to asking about the cardinality $#{ i \cdot j: 1 \le i,j \le n}$ (just divide by $n^2$ to get the probability of the complement event). This is a well studied cardinality, introduced and studied by Erdős and is known as the multiplication table problem. Thanks to Ford (who built on Erdős and Tenenbaum) we know the order of magnitude to this cardinality. You just want it to be $o(n^2)$, which is not hard. See this MO thread for background and literature: https://mathoverflow.net/questions/31663/distinct-numbers-in-multiplication-table – Ofir Gorodetsky Mar 22 '22 at 10:27