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

[gipokrat]

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

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

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

[nimepe]

$12^k-k=p$ Находим решение данного уравнения обратным методом:

$12^k=p\frac{k_1p_1}{k_1m+(k_1-1)p_1}$

$ -k=p\frac{k_1m-p_1}{k_1m+(k_1-1)p_1}$,отсюда:

$kln12=ln(p\frac{k_1p_1}{k_1m+(k_1-1)p_1})$, $k=p\frac{p_1-k_1m}{k_1m+(k_1-1)p_1}$(А)

упростим формулы (А), взяв $k_1=1$

-- добавлено через 8 минут --

$k=\frac{1}{ln12}lnp\frac{p_1}{m}$, $ k=p\frac{p_1-m}{m}$

-- добавлено через 20 минут --

Метод проверен И И.
В формулах $k$ задается любое простое число(можно брать любое).Затем задаются такие значения $p_1 ,m$ чтобы получились целые совпадающие значения $k$

-- добавлено через 9 минут --

Если по двум формулам значения$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 с не сильно большим праймориалом, не запуская относительно тяжеловесный тест Ферма.

[nimepe]

Пример проверки решения обратным методом(проверка ИИ):
p=2305843009213693951

m=135514110173460987 ,p_1=135514110173460988,k=17,0155196847189217,k=17,01551968471.Сразу видно, что решения нет.Этот метод более производителен чем прямой.