Простые вида n^n+1

[Ktina]

а) Найти все простые числа вида $n^n+1$ (где $n$ - натуральное), содержащие не более 19 цифр в своей десятичной записи.

б) Тот же вопрос для 616 цифр.

[nnosipov]

Это сводится к тестированию на простоту чисел Ферма. Критерий простоты таких чисел известен.

[Ktina]

nnosipov в сообщении #545779 писал(а):

Это сводится к тестированию на простоту чисел Ферма. Критерий простоты таких чисел известен.

Тест Пепина?

[nnosipov]

Ktina в сообщении #545787 писал(а):

Тест Пепина?

Он самый. Но работает он, конечно, если только число цифр не слишком велико. Несколько сотен цифр на обычном компьютере не проблема.

[Ktina]

nnosipov в сообщении #545810 писал(а):

Ktina в сообщении #545787 писал(а):

Тест Пепина?

Он самый. Но работает он, конечно, если только число цифр не слишком велико. Несколько сотен цифр на обычном компьютере не проблема.

Но на олимпиаде компов нет. Поэтому нужно:

а) доказать, что число $16^{16}+1$ - составное

б) доказать, что в числе $256^{256}+1$ более 616 цифр.

[nnosipov]

Для б) достаточно вычислить $\lg{2}$ до трёх знаков. А вот а) поинтереснее будет. Во всяком случае, наименьший простой делитель $p=2^8k+1$ получается только при $k=1071$. А на какой олимпиаде это было?

[Ktina]

nnosipov в сообщении #545824 писал(а):

Для б) достаточно вычислить $\lg{2}$ до трёх знаков. А вот а) поинтереснее будет. Во всяком случае, наименьший простой делитель $p=2^8k+1$ получается только при $k=1071$. А на какой олимпиаде это было?

Первый пункт - на маргоградской, а второй я придумала в силу того, что первый показался мне чересчур тривиальным.

[svv]

(Откройте тайну!)

Любители олимпиадных задач часто интересуются, на какой олимпиаде была задача. Мне очень интересно, какое это имеет значение? Не сомневаюсь, что имеет, судя по постоянным вопросам "в каком городе давалась задача?", но какое именно?

[Ktina]

svv в сообщении #545840 писал(а):

(Откройте тайну!)

Любители олимпиадных задач часто интересуются, на какой олимпиаде была задача. Мне очень интересно, какое это имеет значение? Не сомневаюсь, что имеет, судя по постоянным вопросам "в каком городе давалась задача?", но какое именно?

(Оффтоп)

У каждой страны (региона, города, ...) свои особенности, что отражается также на условиях и характере олимпиадных задач. Например, для олимпиадных задач Тайваня и Гонк-Конга характерны как перекос в сторону теории чисел, так и расчёт на эрудицию и чисто технические решения. А вот ленинградские олимпиады (особенно отборочный тур) - для особоозарённых. Польские и китайские - заковыристые, а всесоюзки рассчитаны на голый интеллект. В румынских много геометрии, а в американских - комбинаторики. В канадских и шведских почти половина задач - тривиальные (решаются в два-три действия). Французские отличаются заумными условиями. В условиях задач израильских олимпиад немало скоммунизжено с ленинградских и всесоюзных (сразу видно, кто составлял). Ну а маргоградские, как правило, рассчитаны на нестандартное мышление.

P. S.
А, ещё монгольские забыла упомянуть. Как-то читала статью о чемпионах мира по шахматам, в которой каждому чемпиону был поставлен в соответствие какой-нибудь эпитет. Каспаров - быстроменяющийся, Стейниц - экспериментатор, Полгар - убийца и т. п. Так вот, Таль был инопланетянин. Вот и монгольские олимпиады примерно такие же, ни в одни рамки не вписываются.

[svv]

(Оффтоп)

Спасибо, жутко интересно!

Ktina писал(а):

В канадских и шведских почти половина задач - тривиальные (решаются в два-три действия).

Не зря мне в детстве казалось, что Швеция и Канада в каком-то труднообъяснимом смысле образуют пару (при этом я их вовсе не путал). Аналогично -- Польша и Франция, и третья пара -- Чехословакия и Югославия, ну, тут хоть немного понятно.

[ins-]

(Оффтоп)

What can you say about Bulgarian and Iranian math olympiads? I like them both .

[nnosipov]

Ktina в сообщении #545813 писал(а):

Но на олимпиаде компов нет. Поэтому нужно:

а) доказать, что число $16^{16}+1$ - составное

Ксения, какого, пардон, ...!? Вы считали количество цифр в числе $16^{16}+1$? Я вот только сейчас сообразил подсчитать, их оказалось 20!!! А перед этим битый час пытался понять, в чём фокус. Короче, без компа нельзя.

[Ktina]

nnosipov в сообщении #545903 писал(а):

Ktina в сообщении #545813 писал(а):

Но на олимпиаде компов нет. Поэтому нужно:

а) доказать, что число $16^{16}+1$ - составное

Ксения, какого, пардон, ...!? Вы считали количество цифр в числе $16^{16}+1$? Я вот только сейчас сообразил подсчитать, их оказалось 20!!! А перед этим битый час пытался понять, в чём фокус. Короче, без компа нельзя.

Я знаю, чем я Вас запутала. Надо было вместо "а" и "б" написать "1" и "2", так как и $16^{16}$, и $256^{256}$ относятся к пункту б) и только к нему. Однако я была уверена в том, что для Вас очевидно, что в числе $16^{16}$ более 19 цифр, ведь тут даже логарифм не нужен: $16^{16}=2^{64}=2^{60}\cdot 16>10^{18}\cdot 16$

(Оффтоп)

А секрет Полишинеля Вы мне в пику раскрыли? Вот теперь меня забанят и пойду топиться

[nnosipov]

Ktina в сообщении #545919 писал(а):

(Оффтоп)

А секрет Полишинеля Вы мне в пику раскрыли? Вот теперь меня забанят и пойду топиться

(Оффтоп)

Нет, это произошло случайно, в порыве эмоций. Какое там забанят. Не дадим-с Кстати, про олимпиады неплохо написано. Мне вот вспоминаются вьетнамские неравенства, очень экзотичные и нетривиальные. И ещё одна Chinese Girls' Mathematics Olympiad с нехилыми задачами.

[griboedovaa]

A= n^n+1
так как если степень имет нечетный делитель,то число сотавное, чтобы проверить до 616 знака достаточно проверить на простоту при n=2^1,2^2,...,2^8, но все A при таких n будут давать остаток 3 при делении на 6, но простое числа дает только 1 и -1 остаток