Задача-красавица с международки

[Ktina]

Доказать, что для любых натуральных $ n $ и $ m $ найдутся $ n $ последовательных натуральных чисел, каждое из которых имеет не менее $ m $ попарно различных простых делителей.

[MrDindows]

Разве это не следует из Китайской теоремы об остатках?

[svv]

Конечно, следует! Расписывать надо?

[MrDindows]

Та тут и расписывать нечего...
Берём $nm$ простых чисел, и по этой теореме найдётся натуральное число, что делится на первые $m$ простых, даёт в остатке $-1$ на следующие $m$, $-2$ на следующие, и тд...
Не уж-то такое на межнаре дали?

[Ktina]

MrDindows в сообщении #525226 писал(а):

Та тут и расписывать нечего...
Берём $nm$ простых чисел, и по этой теореме найдётся натуральное число, что делится на первые $m$ простых, даёт в остатке $-1$ на следующие $m$, $-2$ на следующие, и тд...
Не уж-то такое на межнаре дали?

На межнаре дали даже проще - частный случай m=2
http://www.imo-official.org/problems.aspx
(1989, задача 5)

[Edward_Tur]

Существует ли такое натуральное число $x$, что для всех натуральных $n$ числа $x\mult 2^n+1$ - составные?

[Руст]

бесконечно много. Кажется они имеют даже специальное название (то ли числа Серпинского).

[Edward_Tur]

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

бесконечно много. Кажется они имеют даже специальное название (то ли числа Серпинского).

А в Китае на отборочных соревнованиях (2007, задача 3.3)
http://www.artofproblemsolving.com/Foru ... 36d4d6a541
предлагают найти числа Серпинского
http://ru.wikipedia.org/wiki/Числа_Серпинского

[Cash]

Ну предлагают не найти, а "всего лишь" доказать их существование...

[Батороев]

(Оффтоп)

У меня вопрос немного не по теме...
В статье про числа Серпинского в Википедии дословно сказано:

Цитата:

Например, если рассмотреть последовательность $3\cdot 2^{n}+1$, то в ней регулярно будут встречаться простые числа...

Меня интересует вопрос:
Слово "регулярно" применено здесь для "красного словца" (типа, что такие числа существуют и их много) или это говорит о доказанности того, что число простых данного вида бесконечно? Буду благодарен за любой ответ по существу моего вопроса или близко к "по существу", или хотя бы отдаленно к "по существу"!

[Sonic86]

(Оффтоп)

Батороев в сообщении #525991 писал(а):

Слово "регулярно" применено здесь для "красного словца" (типа, что такие числа существуют и их много) или это говорит о доказанности того, что число простых данного вида бесконечно? Буду благодарен за любой ответ по существу моего вопроса или близко к "по существу", или хотя бы отдаленно к "по существу"!

Для красного словца.
Доказана лишь бесконечность простых в арифметических прогрессиях.
Во всех (вот вообще во всех) остальных последовательностях либо относительно просто доказываем, что простых конечно, либо (если их там бесконечное число, что встречается часто) - ограничиваемся гипотезой и догадками.

Кстати, интересно было бы собрать из гипотез о простых числах, содержащихся в "экспоненциальных" последовательностях от одной переменной какую-то одну общую гипотезу. Для многочленов она есть - это гипотеза Буняковского. А вот например, объединить все гипотезы хотя бы о всех последовательностях $A a^n \pm B b^n$ в одну - было бы интересно (тут только одно "неестественное" исключение - число простых Ферма считается конечным)

[Батороев]

(Оффтоп)

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

Для красного словца.
Доказана лишь бесконечность простых в арифметических прогрессиях.
Во всех (вот вообще во всех) остальных последовательностях либо относительно просто доказываем, что простых конечно, либо (если их там бесконечное число, что встречается часто) - ограничиваемся гипотезой и догадками.

Кстати, интересно было бы собрать из гипотез о простых числах, содержащихся в "экспоненциальных" последовательностях от одной переменной какую-то одну общую гипотезу. Для многочленов она есть - это гипотеза Буняковского. А вот например, объединить все гипотезы хотя бы о всех последовательностях $A a^n \pm B b^n$ в одну - было бы интересно (тут только одно "неестественное" исключение - число простых Ферма считается конечным)

Жаль! Все жду, когда мое нестрогое док-во ВТФ станет строгим.
Слова "считается конечным" в отношении простых Ферма, похоже, Вы тоже применили для "красного словца".

[Sonic86]

(Оффтоп)

Батороев в сообщении #526334 писал(а):

Слова "считается конечным" в отношении простых Ферма, похоже, Вы тоже применили для "красного словца".

Ну да Хотя "считается" $\neq$ "доказано"