Оценка сверху на НОК(1,...,k)

[АльфияР]

Пусть k-натуральное, а $N_k$ - наименьшее общее кратное всех натуральных чисел от 1 до k. Доказать неравенство $N_k=<k^{8/3}k!^{1/3}$.

[Vir]

Помогите решить Задачу АльфииР про НОК, а то мне тоже нужно его ршить.

[maxal]

Я докажу для случая $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}.$$

[Vir]

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

[незваный гость]

Начать с частного. Если $n = 6j + r$, то у Вас есть оценка для $\text{НОК}(1,… 6j)$, и Вам теперь надо оценить $\text{НОК}(1,… n) = \text{НОК}(\text{НОК}(1,… 6j), 6j+1,…6j+r)$

[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).$$ Но ведь для разных p такие j могут быть одинаковыми, и тогда в произведении справа некоторые j должны встречаться более одного раза.

[maxal]

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).$$

[Vir]

Может я покажусь слишком навязчивым , но мне не понятно как довести это доказательство в ощем виде до конца.

[maxal]

Понятно, что в общем случае достаточно доказать для $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}.$$

[Asalex]

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}$$