Множество произведений двух чисел меньших n

[fractalon]

Что можно сказать о размере множества $P(n,m)=\{{ab\ :\ 1 \le a \le n, 1 \le b \le m}\}$? В частности, об асимптотике $f(n)=P(n,n)$?

[fractalon]

Или об асимптотике $g(n)=P(n,m)$ при фиксированном $m$? Ясно, что там $\Theta (n)$, но как растёт $h(m) = \lim \limits_{n \to \infty} \frac{P(n,m)}{n}$?

[12d3]

fractalon в сообщении #1142976 писал(а):

В частности, об асимптотике $f(n)=P(n,n)$?

A027424

[fractalon]

А сколько на интервале $1, \dots, \frac{n!}{m!}$ чисел, не делящихся ни на одно из чисел $m, ..., n$?
Если научиться отвечать на этот вопрос, можно будет построить график $h(n)$. Для построения графика подойдёт даже не математическое решение а итеративное какое-то, через динамическое программирование...

[fractalon]

Я нашёл решение поставленной задачи про $h(m) = \lim \limits_{n \to \infty} \frac{P(n,m)}{n}$, оставлю здесь, может быть, кому-то будет интересно.

Итак, очевидно, что если $kn < x < (k+1)n$, то $x \in P(n,m) \Leftrightarrow \exists d \in [k;m]: d | x$.
Соответственно, $h(m) = \sum \limits_{k=1}^{m} {\varphi(k,m)}$, где $\varphi(k,m)$ - плотность, которую имеет среди натуральных множество чисел, делящихся по крайней мере на одно из чисел $k, k+1, \dots, m$. По формуле включений-исключений получаем $\varphi(k,m) = 1 - \prod \limits_{t=k}^{m} \left( {1 - \frac{1}{t}} \right) = \frac{m-k+1}{m}$. Поэтому $h(m)=\sum \limits_{k=1}^{m} \frac{k}{m} = \frac{m+1}{2}$.

Получается, $P(n,m) \sim \frac{m+1}{2} n$ при фиксированном $m$. По-моему, результат забавный.