Сколько простых представимо формой:

[TR63]

При рассмотрении одной местной задачи у меня возникла примерно аналогичная задача: сколько простых чисел представимо формой: $p_n=3+a^a$, $(a)$-положительное натуральное (чётное).

Мои попытки решения.

$7=3+2^2$

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

[ET]

при $n=1$ таких много
но и при $n=2$ они есть и немало: 67, 19, 199,...
Упд, да, зрение уже года 3 как не то..

[dmd]

A166852

[Someone]

TR63 в сообщении #1444297 писал(а):

Далее ищу с помощью Вольфрама. Пока простые не попадаются. Меня устроило бы хоть ещё одно простое число.

С помощью Вольфрама находится ещё $3+1036^{1036}$.

[Aritaborian]

Эх, опередили ;-( Тоже нашёл 1036.

[TR63]

dmd
Someone
Aritaborian,
большое спасибо.
Я посмотрела последовательность, включив переводчик, который говорит, что второе и третье число-это вероятные простые числа. Что означает "вероятные"?

[Aritaborian]

TR63, что-то здесь не так. Если Mathematica, используя функцию PrimeQ, выдаёт True, то это самое настоящее простое число.

[wrest]

TR63 в сообщении #1444316 писал(а):

Что означает "вероятные"?

Числа настолько большие (особенно $3+2770^{2770}$ это чуть больше $9500$ десятичных цифр в записи числа), что доподлинно проверить их на простоту не удалось, но вероятностные тесты говорят о том, что числа эти -- скорее всего простые.

[TR63]

Aritaborian в сообщении #1444317 писал(а):

что-то здесь не так

В английском я ноль.

Aritaborian в сообщении #1444317 писал(а):

это самое настоящее простое число.

Хорошо.

-- 11.03.2020, 15:14 --

wrest, понятно. Спасибо.
На всякий случай, я отталкивалась от последовательности A088430.

[Someone]

Aritaborian в сообщении #1444317 писал(а):

Если Mathematica, используя функцию PrimeQ, выдаёт True, то это самое настоящее простое число.

Где-то в документации я читал, что не обязательно. Есть какая-то граница, выше которой функция не гарантирует.

wrest в сообщении #1444318 писал(а):

доподлинно проверить их на простоту не удалось

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

TR63 в сообщении #1444319 писал(а):

В английском я ноль.

Эх, а я рассчитывал на ссылку Probable Prime.

[Aritaborian]

Someone в сообщении #1444325 писал(а):

Где-то в документации я читал, что не обязательно.

Вообще да, я скорее погорячился... Но вот сходу найти такое место в документации не получается.

[Someone]

Aritaborian в сообщении #1444331 писал(а):

Но вот сходу найти такое место в документации не получается.

У меня тоже. Вероятно, я это в старых версиях видел.
Но функция PrimeQ уж очень быстро работает. Создаётся впечатление, что она ограничивается пробным делением и тестом Ферма, возможно, по нескольким основаниям.

[Aritaborian]

Someone в сообщении #1444334 писал(а):

Но функция PrimeQ уж очень быстро работает.

Но существует ещё отдельная ProvablePrimeQ! Из чего логично сделать вывод, что сама PrimeQ должна работать с гарантией 100 %. Хотя, может, я что-то не так понимаю...

[nnosipov]

Aritaborian в сообщении #1444336 писал(а):

Но существует ещё отдельная ProvablePrimeQ!

Обратите внимание, там буква 'v', а не 'b'. Она (ProvablePrimeQ) якобы выдает сертификат. Вот и надо это проверить на больших числах.

Aritaborian в сообщении #1444336 писал(а):

Из чего логично сделать вывод, что сама PrimeQ должна работать с гарантией 100 %.

А не наоборот ли?

Вообще, документация такова, что ничего толком не узнаешь.

Upd. Сертификат на 100-значное простое практически сразу, а вот на 1000-значное простое уже не дождался. 10 тысяч знаков --- скорее всего, безнадежно.

[Aritaborian]

Да, nnosipov, я и сам это всё понял почти сразу после того, как написал