2014 dxdy logo

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

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




 
 Оценка сверху на НОК(1,...,k)
Сообщение23.06.2007, 21:42 
Пусть k-натуральное, а $N_k$ - наименьшее общее кратное всех натуральных чисел от 1 до k. Доказать неравенство $N_k=<k^{8/3}k!^{1/3}$.

 
 
 
 Оценка сверху на НОК(1,...,k)
Сообщение30.06.2007, 16:37 
Помогите решить Задачу АльфииР про НОК, а то мне тоже нужно его ршить.

 
 
 
 
Сообщение02.07.2007, 00:28 
Аватара пользователя
Я докажу для случая $k=6m,$ на общий случай распространите сами.

Заметим, что НОК(1,...,k) равно произведению максимальных степеней простых, не превосходящих k, т.е.
$$\mbox{НОК}(1,...,k) = \prod_{2\leq p\leq k} p^{\lfloor \log_p k\rfloor} \leq k^2 \prod_{5\leq p\leq k} p^{\lfloor \log_p k\rfloor}.$$

Заметим, что для простого $p\geq 5$ его степень сравнима с 1 или 5 по модулю 6. Поэтому
$$\prod_{5\leq p\leq k} p^{\lfloor \log_p k\rfloor} \leq \prod_{j=0}^{m-1} (6j + 1)(6j+5).$$

Нетрудно показать, что для любого $j$
$$(6j + 1)(6j+5) \leq [(6j+1)(6j+2)(6j+3)(6j+4)(6j+5)(6j+6)]^{1/3}$$
и поэтому
$$\prod_{j=0}^{m-1} (6j + 1)(6j+5) \leq (6m)!^{1/3}.$$

Итак, для $k=6m$ мы получили:
$$\mbox{НОК}(1,...,k) \leq k^2 k!^{1/3}.$$

 
 
 
 
Сообщение02.07.2007, 14:44 
Всё понятно, только не понятно, как доказать общий случай или с чего начать.

 
 
 
 
Сообщение02.07.2007, 18:13 
Аватара пользователя
:evil:
Начать с частного. Если $n = 6j + r$, то у Вас есть оценка для $\text{НОК}(1,… 6j)$, и Вам теперь надо оценить $\text{НОК}(1,… n) = \text{НОК}(\text{НОК}(1,… 6j), 6j+1,…6j+r)$

 
 
 
 
Сообщение02.07.2007, 22:05 
Аватара пользователя
Maxal, можешь подробнее объяснить, откуда ты взял неравенство


maxal писал(а):
$$\prod_{5\leq p\leq k} p^{\lfloor \log_p k\rfloor} \leq \prod_{j=0}^{m-1} (6j + 1)(6j+5).$$




Я так понял, что ты для всякого p ищешь j, такой что либо
$p^{\lfloor \log_p k\rfloor}=6j+1$ либо p^{\lfloor \log_p k\rfloor}=6j+5$$,
и тогда
$$p^{\lfloor \log_p k \rfloor}<=(6j+1)(6j+5).$$
Но ведь для разных p такие j могут быть одинаковыми, и тогда в произведении справа некоторые j должны встречаться более одного раза.

 
 
 
 
Сообщение03.07.2007, 00:02 
Аватара пользователя
Asalex писал(а):
Maxal, можешь подробнее объяснить, откуда ты взял неравенство
maxal писал(а):
$$\prod_{5\leq p\leq k} p^{\lfloor \log_p k\rfloor} \leq \prod_{j=0}^{m-1} (6j + 1)(6j+5).$$

Я так понял, что ты для всякого p ищешь j, такой что либо
$p^{\lfloor \log_p k\rfloor}=6j+1$ либо p^{\lfloor \log_p k\rfloor}=6j+5$$,
и тогда
$$p^{\lfloor \log_p k \rfloor}<=(6j+1)(6j+5).$$

Нет, это неравенство слишком слабое.

Покажите, что
1) для различных простых $p$ числа $p^{\lfloor \log_p k \rfloor}$ является различными (следует из основной теоремы арифметики);
2) множество $\{ p^{\lfloor \log_p k \rfloor} : 5\leq p\leq k\}$ является подмножеством множества $\{ 6j+1, 6j+5 : j=0,1,\dots,m-1\}$, где  $k=6m$.

Из 1) и 2) следует неравенство
$$\prod_{5\leq p\leq k} p^{\lfloor \log_p k\rfloor} \leq \prod_{j=0}^{m-1} (6j + 1)(6j+5).$$

 
 
 
 
Сообщение03.07.2007, 10:58 
Может я покажусь слишком навязчивым :oops: , но мне не понятно как довести это доказательство в ощем виде до конца.

 
 
 
 
Сообщение03.07.2007, 12:13 
Аватара пользователя
Понятно, что в общем случае достаточно доказать для $k=6m+1$ и для $k=6m+5$.

Для $k=6m+1$ имеем
$$\mbox{НОК}(1,\dots,k)\leq k\cdot\mbox{НОК}(1,\dots,k-1)\leq k(k-1)^2 (k-1)!^{1/3} < k^3 (k-1)!^{1/3} = k^{8/3} k!^{1/3}.$$

Для $k=6m+5$ легко проверить, что
$$\mbox{НОК}(1,\dots,k)\leq (k-4) k\mbox{НОК}(1,\dots,k-5)\leq (k-4) k (k-5)^2 (k-5)!^{1/3} \leq k^{8/3} k!^{1/3}.$$

 
 
 
 
Сообщение03.07.2007, 12:20 
Аватара пользователя
Cлучай k=6m+r, r=1,..4


$$\prod_{5 \leq p \leq k} p^{\lfloor \log_p k \rfloor} \leq (6m+1)  \prod_{j=0}^{m-1} (6j+1)(6j+5) \leq (6m+1) (6m)!^ \frac {1}{3} =(6m+1)^ \frac {2}{3} (6m+1)!^ \frac {1}{3} \leq  k^ \frac {2}{3} k!^ \frac {1}{3}$$


Cлучай k=6m+5
$$\prod_{5 \leq p \leq k} p^{\lfloor \log_p k \rfloor} \leq \prod_{j=0}^{m} (6j+1)(6j+5)\leq (6m+6)!^ \frac {1}{3} $$


$$ HOK(1,..k) \leq (6m+5)^2 (6m+6)!^ \frac {1}{3}=(6m+5)!^ \frac {1}{3} (6m+5)^2 (6m+6)^\frac{1}{3}\leq(6m+5)!^ \frac {1}{3} (6m+5)^\frac{8}{3}=k!^ \frac {1}{3} k^\frac{8}{3}$$

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group