Простые числа вида 12^k-k

[gipokrat]

При каких натуральных $k$ число $12^k-k$ является простым?

Вычислительный поиск дал первые четыре подходящих значения: 1, 5, 401, 7171.

Как найти следующие значения? Что известно о множестве всех таких $k$?

[lel0lel]

gipokrat в сообщении #1731351 писал(а):

При каких натуральных $k$ число $12^k-k$ является простым?

В подобных последовательностях, как правило, нельзя указать все значения $k$. Значений может быть бесконечно много. Можно вспомнить про простые числа Мерсенна $M_p=2^p-1$. Строго не доказана их конечность/бесконечность. Для нахождения следующего простого иногда требуются годы работы многих компьютеров. Некоторые свойства $M_p$ очевидны, например показатель $p$ должен быть простым числом. Есть и другие, но тема не о них.

gipokrat в сообщении #1731351 писал(а):

Что известно о множестве всех таких $k$?

Как минимум, что это нечётные не кратные $3$. Если потребовать, чтобы $12^k-k$ не делилось на $5$, это приводит к тому, что $k$ не сравнимо с $3$ и $17$ по модулю $4\cdot 5=20$. Если потребовать, чтобы $12^k-k$ не делилось на $7$, это приводит к тому, что $k$ не сравнимо с $17, 19$ и $27$ по модулю $6\cdot7=42$. При желании можно продолжать, но на практике (речь про численный поиск) легче отсеять составные с маленькими делителями проверкой их gcd с не сильно большим праймориалом, не запуская относительно тяжеловесный тест Ферма.

[Ende]

Выделена в пургаторий тема «Очередные ребусы nimepe»

[Someone]

gipokrat в сообщении #1731351 писал(а):

Вычислительный поиск дал первые четыре подходящих значения: 1, 5, 401, 7171.

А до какого числа $k$ проверили?

[gipokrat]

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

А до какого числа $k$ проверили?

Прошу прощения, я ошибся. Число $12^{7171}-7171$ оказалось вероятно простым, а не доказанно простым. ChatGPT подвёл.
Ошибка возникла из-за того, что я принял результат вероятностного теста за доказательство простоты.

[Someone]

gipokrat в сообщении #1731827 писал(а):

Прошу прощения, я ошибся. Число $12^{7171}-7171$ оказалось вероятно простым, а не доказанно простым. ChatGPT подвёл.
Ошибка возникла из-за того, что я принял результат вероятностного теста за доказательство простоты.

А ChatGPT Вас предупредил?
Проверить можно с помощью программы Primo (https://www.ellipsa.eu/public/primo/primo.html). Но автор Windows не поддерживает, только Linux. У меня старая версия 3.0.9, которая была для Windows, число

$$\sum\limits_{k=1}^{2653}{(-1)^{2653-k}k!},$$

содержащее $7934$ цифры, проверяла $571\text{ час }50\text{ минут }16\text{ секунд}$. В вашем числе $12^{7171}−7171$ чуть меньше цифр: $7739$.
А число $12^{401}-401$ ($433$ цифры) проверяется за $14{,}26\text{ секунды}$.
Я как-то даже число

$$\sum\limits_{k=1}^{3069}{(-1)^{3069-k}k!}$$

проверил ($9371$ цифра). Программа считала (по её подсчётам) $3231\text{ час }3\text{ минуты }8\text{ секунд}$. Очень удачно, что программу можно прерывать, а потом запускать для продолжения.

И, кстати, с помощью программы pfgw64 (https://sourceforge.net/projects/openpfgw/) я нашёл Вам ещё одну кандидатуру: $12^{82351}-82351$. Примерно за сутки.

[gipokrat]

Someone
Спасибо за Primo и особенно за ещё одного кандидата!

[Shadow]

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

Вам ещё одну кандидатуру: $12^{82351}-82351$

Maple isprime (5× Miller–Rabin + Lucas) согласен, что простое.

[Someone]

Shadow в сообщении #1731858 писал(а):

Maple isprime (5× Miller–Rabin + Lucas) согласен, что простое.

Но это, к сожалению, не гарантирует, что число простое. Этот тест вероятностный. В сильно подавляющем числе случаев число действительно простое, но гарантии нет.

gipokrat в сообщении #1731835 писал(а):

Спасибо за Primo и особенно за ещё одного кандидата!

Я закончил проверку на числе $12^{82385}-82385$, которое, согласно записи в лог-файле, делится на $2942263$:

Primality testing 12^82385-82385 [N-1/N+1, Brillhart-Lehmer-Selfridge]
factors: 2942263
12^82385-82385 is factored (3.1660s+0.0014s)

Информация о числе $12^{82351}−82351$ в лог-файле выглядит так:

Primality testing 12^82351-82351 [N-1/N+1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 3
Running N+1 test using discriminant 11, base 1+sqrt(11)
Calling N-1 BLS with factored part 0.01% and helper 0.00% (0.05% proof)
12^82351-82351 is Fermat and Lucas PRP! (443.1984s+0.0013s)

Возможность доказательства простоты зависит от того, насколько "глубоко" факторизуются числа $N\pm 1$. Если суммарно они факторизуются не менее чем на $30\%$, то доказательство возможно. Доказательство может выглядеть, например, так:

Primality testing (10^50000)/2+(10^16667)*28975-1 [N-1/N+1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 11
Running N+1 test using discriminant 17, base 1+sqrt(17)
Calling N+1 BLS with factored part 33.35% and helper 0.02% (100.08% proof)
(10^50000)/2+(10^16667)*28975-1 is prime! (165.1617s+0.0010s)

Если захотите продолжить поиск кандидатов в простые числа вашего вида или какого-нибудь другого, рекомендую именно программу https://sourceforge.net/projects/openpfgw/. Под Windows её лучше запускать в консоли cmd.exe. Если понадобятся какие-нибудь консультации — пишите.