2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Множество произведений двух чисел меньших n
Сообщение09.08.2016, 19:27 


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

 Профиль  
                  
 
 Re: Множество произведений двух чисел меньших n
Сообщение10.08.2016, 13:39 


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

 Профиль  
                  
 
 Re: Множество произведений двух чисел меньших n
Сообщение10.08.2016, 13:55 
Заслуженный участник


04/03/09
906
fractalon в сообщении #1142976 писал(а):
В частности, об асимптотике $f(n)=P(n,n)$?


A027424

 Профиль  
                  
 
 Re: Множество произведений двух чисел меньших n
Сообщение15.08.2016, 23:03 


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

 Профиль  
                  
 
 Re: Множество произведений двух чисел меньших n
Сообщение20.04.2017, 15:58 


08/09/13
210
Я нашёл решение поставленной задачи про $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$. По-моему, результат забавный.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group