Задача о безникотиновых числах

[vivaldi]

Назовем натуральное число безникотиновым, если оно является произведением ровно трех простых чисел (не обязательно различных).

Какое максимальное количество последовательных натуральных чисел могут быть безникотиновыми?

(задачу предложила К. Шейнерман)

[Руст]

Число 8 имеет 3 делителя и 7, 9 нет. Соответственно не более 7 подряд $8k+1,8k+2,8k+3,8k+4,8k+5,8k+6,8k+7$. Возможно, что найдется такое $k$ (без компьютера не найти).

[vivaldi]

Руст в сообщении #503785 писал(а):

Число 8 имеет 3 делителя и 7, 9 нет. Соответственно не более 7 подряд $8k+1,8k+2,8k+3,8k+4,8k+5,8k+6,8k+7$. Возможно, что найдется такое $k$ (без компьютера не найти).

Я тоже без компьютера не нашел, но автор задачи заявила, что существует красивое решение.

[Sonic86]

Комп говорит, что:

$$\begin{array}{lllllll} 211673 = 7 \cdot 11 \cdot 2749 \\ 211674 = 2 \cdot 3 \cdot 35279 \\ 211675 = 5^2 \cdot 8467 \\ 211676 = 2^2 \cdot 52919 \\ 211677 = 3 \cdot 37 \cdot 1907 \\ 211678 = 2 \cdot 109 \cdot 971 \\ 211679 = 13 \cdot 19 \cdot 857 \end{array} $$

Вполне возможно, что длина таких цепочек неограниченно возрастает Но как это доказывать?

[venco]

Sonic86 в сообщении #503810 писал(а):

Вполне возможно, что длина таких цепочек неограниченно возрастает

Руст же доказал, что нет.

[Sonic86]

venco в сообщении #503826 писал(а):

Руст же доказал, что нет.

А! Туплю, $k>1 \Rightarrow \Omega (8k)>3, \Omega (8k+8)>3$

А вот если рассматривать число различных простых делителей, равное 3, тогда непонятно.

[VAL]

Sonic86 в сообщении #503829 писал(а):

А вот если рассматривать число различных простых делителей, равное 3, тогда непонятно.

А в этом случае, возможно, и неограниченно расти будет. По крайней мере, 14 штук подряд я нашел довольно быстро.

for i to 14 do ifactor(526094+i) od;
                              5
                           (3)   (5)  (433)

                             4
                          (2)   (131)  (251)

                                    2
                          (11)  (13)   (283)

                           (2)  (3)  (87683)

                           (7)  (17)  (4421)

                             2     2
                          (2)   (5)   (5261)

                           (3)  (31)  (5657)

                          (2)  (23)  (11437)

                           (37)  (59)  (241)

                             3     2
                          (2)   (3)   (7307)

                           (5)  (43)  (2447)

                           (2)  (7)  (37579)

                          (3)  (157)  (1117)

                             2      2
                          (2)   (11)   (1087)
 

[VAL]

VAL в сообщении #504807 писал(а):

Sonic86 в сообщении #503829 писал(а):

А вот если рассматривать число различных простых делителей, равное 3, тогда непонятно.

А в этом случае, возможно, и неограниченно расти будет. По крайней мере, 14 штук подряд я нашел довольно быстро.

А может и ограниченно...
Соображения такие.
Будем рассматривать цепочки последовательных натуральных чисел, каждое из которых имеет ровно $k$ различных простых делителей.

Очевидно, что при $k=1$ максимальная длина цепочки равна и достигается в самом начале натурального ряда.
При $k=2$ самая большая из найденных цепочек имеет длину 8. Такие цепочки начинаются с чисел 142 и 213. И больше среди первого миллиона чисел столь длинных цепочек нет.
Не исключаю, что их и вовсе нет. Ведь, чем дальше в лес в натуральный ряд, тем больше среднее число делителей.

Аналогичная картина может наступить и при больших $k$, только смена тенденции от увеличения к уменьшению длин цепочек будет случаться все позже.

Ясно, что все это рассуждения на пальцах. Но со строгими доказательствами, боюсь, могут возникнуть проблемы.

PS: Случай $k=1$ берусь обосновать строго

[Sonic86]

Слуууушайте! А я ведь вру страшно!!! Решается-то точно так же:
Длина такой последовательности не превосходит длины отрезка $[np_1...p_{k+1};(n+1)p_1...p_{k+1}]$, в котором число различных делителей его концов $\geqslant k+1>k$.

(Оффтоп)

Хорошо, что остановились на этом, щас бы ходил и думал, что число таких чисел бесконечно. Всем большое спасибо за это!!!

Блин! Так можно же максимальную длину тогда найти!

Кстати, уже случай $k=1$ нам говорит, что надо различать максимальную длину для всего натурального ряда и для всех натуральных чисел больше некоторого. При $k=1$ максимальная длина $l(1)=2$ в цепочке $2;3$, а при $n>2$ максимальная длина уже только $1$, но зато бесконечное количество раз.

[VAL]

Sonic86 в сообщении #505067 писал(а):

Слуууушайте! А я ведь вру страшно!!! Решается-то точно так же:
Длина такой последовательности не превосходит длины отрезка $[np_1...p_{k+1};(n+1)p_1...p_{k+1}]$, в котором число различных делителей его концов $\geqslant k+1>k$.

(Оффтоп)

Хорошо, что остановились на этом, щас бы ходил и думал, что число таких чисел бесконечно. Всем большое спасибо за это!!!

Блин! Так можно же максимальную длину тогда найти!

Перечитал трижды. Ничего не понял

[Sonic86]

VAL в сообщении #505071 писал(а):

Перечитал трижды. Ничего не понял

Что именно? Там просто эмоций много. Попробую еще раз:
Пусть $\omega (n)$ - число различных простых делителей числа ($\omega (1)=0$).
Тогда для заданного $k$ $\omega (n p_1...p_{k+1}) \geqslant k+1>k$ и $\omega (n p_1...p_{k+1}+p_1...p_{k+1}) \geqslant k+1>k$, а значит длина искомой цепочки не превосходит $np_1...p_{k+1}+p_1...p_{k+1} - np_1...p_{k+1}-1 = p_1...p_{k+1}-1 \leqslant C_k$. При $k=2$ длина последовательности не превосходит $2 \cdot 3 \cdot 5 -1 = 29$. Однако, она может быть даже меньше. Я перебрал интервал $10^7-10^8$ - там уже нет цепочек даже длины $8$. Т.е. моя оценка завышенная. Интересно, какая оценка точная? Причем интересны 2 оценки: одна для всех натуральных чисел, вторая - для всех достаточно больших натуральных чисел

[VAL]

Sonic86 в сообщении #505082 писал(а):

VAL в сообщении #505071 писал(а):

Перечитал трижды. Ничего не понял

Что именно? Там просто эмоций много. Попробую еще раз:
Пусть $\omega (n)$ - число различных простых делителей числа ($\omega (1)=0$).
Тогда для заданного $k$ $\omega (n p_1...p_{k+1}) \geqslant k+1>k$ и $\omega (n p_1...p_{k+1}+p_1...p_{k+1}) \geqslant k+1>k$, а значит длина искомой цепочки не превосходит $np_1...p_{k+1}+p_1...p_{k+1} - np_1...p_{k+1}-1 = p_1...p_{k+1}-1 \leqslant C_k$. При $k=2$ длина последовательности не превосходит $2 \cdot 3 \cdot 5 -1 = 29$. Однако, она может быть даже меньше. Я перебрал интервал $10^7-10^8$ - там уже нет цепочек даже длины $8$. Т.е. моя оценка завышенная. Интересно, какая оценка точная? Причем интересны 2 оценки: одна для всех натуральных чисел, вторая - для всех достаточно больших натуральных чисел

Так понятнее.
Хотя еще понятнее, по-моему так:
Среди тридцати чисел, идущих подряд, найдется число, имеющее не менее трех простых делителей. Значит, при $k=2$ длина цепочки не превосходит 29
Аналогично дпя других $k$.
Действительно, все просто! Выходит ограниченность очевидна. Остается вопрос о точных границах.

[Sonic86]

Обозначим $L(k)$ - максимальная длина цепочек натуральных чисел с $\omega (j)=k$, а $l(k)$ - максимальная длина таких цепочек, встречающихся в $\mathbb{N}$ бесконечно много раз. Ясно, что $l(k) \leqslant L(k) \leqslant p_1 \dots p_{k+1}-1$. Попытался я найти эти длины для небольших $k$ на компе, но не получается практически ничего.
Ясно, что $l(1)=1, L(1)=2$ (исключительные цепочки длины 2 - это $2;3$ и $8;9$, это следует из гипотезы Каталана (хотя можно и ручками доказать)). Предположительно $l(2)=5, L(2)=8$, исключительных цепочек 5: $91 \dots 96; 141 \dots 148; 212 \dots 219; 334 \dots 339; 2302 \dots 2308$ (проверено до $10^9$). А вот для $k=3$ уже что-то странное: предположительно $l(3)=L(3)=16$, выглядит странно, но я проверил до $3 \cdot 10^9$ - цепочки длины $16$ встречаются до $2 \cdot 10^9$, цепочки длины $15$ и еще дальше. Если число исключительных цепочек очень быстро растет с ростом $k$, то эмпирический подход плох.

[mihiv]

При $k=2$ можно улучшить оценку для максимальной длины цепочки $L(2)$.
Действительно,в самом неблагоприятном случае 6-е число в цепочке делится на 6,т.е. имеет вид $N=2^n3^m$.Будем считать первое число в цепочке достаточно большим.Предположим цепочку можно продлить ещё по крайней на 12 элементов.Тогда число $N+6=2^n3^m+2\cdot 3=2\cdot 3(2^{n-1}3^{m-1}+1)=2^l3^p\qquad (1)$.
Для того,чтобы это число имело такой вид в скобках должно быть $2^q$ или $3^s$.
Пусть оно равно $2^q$.Это возможно только если $n=1$,и,следовательно,$N=2\cdot 3^m$
Тогда число $N+12=2\cdot 3(3^{m-1}+2)$,здесь число в скобках нечетное и поэтому должно быть степенью 3($m$ считаем больше 1,т.к. $N$ по условию достаточно велико).Получили противоречие.

Предположим теперь,что выражение в скобках в формуле (1) равно $3^s$,это возможно,только если $m=1$ и,следовательно,

$$N=2^n3,N+6=2\cdot 3(2^{n-1}+1),N+12=2^23(2^{n-2}+1)\qquad (2)$$

Выражения в круглых скобках в (2) нечетные числа и поэтому равны степеням 3($n$ считаем больше 2,т.к. $N$ достаточно велико).Следовательно,

$$\dfrac {2^{n-1}+1}{2^{n-2}+1}=3^r,r\geq 1$$

Сдругой стороны это отношение $\leq \dfrac {2^{n-1}+1}{2^{n-2}}<3$ Противоречие.Отсюда $L(2)\leq 17$

[Mega Sirius12]

Цитата:

(задачу предложила К. Шейнерман)

(Оффтоп)

а почему она не могла сама запостить задачу?-и куды она подевалась?