Гипотеза о зекрых числах

[Ktina]

Числа 3 11 85 1029 15631 279943 ... - это числа вида

$$n^{n+1}+n+1,\quad n\in\mathbb{N}$$

Для удобства дадим им название - зекрые числа.

Существует гипотеза, что все зекрые числа, за исключением первых двух (3 и 11), являются составными.

Например, зекрое число, номер которого даёт остаток 1 при делении на 3, обязательно кратно трём. Также среди нескольких первых зекрых чисел немало кратных 5, 7, 11, 13 и 17. Однако, к примеру, 14-е зекрое число, 155568095557812239, не кратно ни одному простому числу, меньшему 277. Тем не менее, может, какая-то закономерность тут всё таки есть?

[mihaild]

Как минимум при $n < 2000$ других простых нет. На этом крайне важном результате мои познания ТЧ и матпакетов заканчиваются:)

[Ktina]

mihaild
Благодарю за посильную помощь. Гипотеза, на мой взгляд, интересная.

[kotenok gav]

Ktina! Вы что, свою гипотезу в Википедию добавили?

[Ktina]

kotenok gav
Пишите в личку, пожалуйста.

[TR63]

kotenok gav в сообщении #1321271 писал(а):

Ktina! Вы что, свою гипотезу в Википедию добавили?

kotenok gav, я думаю, что у Ktina, наоборот, контрпример к той гипотезе. Если сравнить гипотезу из Вики с ВТФ, то утверждения не аналогичны (у них на общее свойство идёт разное минимальное количество операций; отсюда как следствие возможность осечки при экстраполяции). Возможно, Ktina думает, что все остальные числа будут составные.

[daniel starodubtsev]

При n < 2500 простых нет.

[Ktina]

daniel starodubtsev в сообщении #1355003 писал(а):

При n < 2500 простых нет.

Это на 500 больше, чем у mihaild.
Что Вы использовали?

[Dmitriy40]

А в чём собственно проблема? Вот за минуту набрал код на PARI/GP и он за 13 минут выдал результат:

? for(n=1,2000,if(ispseudoprime(n^(n+1)+n+1),print(n)))
1
2
? ##
  ***   last result computed in 5min, 31,909 ms.
? for(n=2000,2500,if(ispseudoprime(n^(n+1)+n+1),print(n)))
? ##
  ***   last result computed in 7min, 39,845 ms.
?

Часов за 5 досчитает и до 5000 наверное.

[mihaild]

Я не помню уже точно что использовал, но вот такой код https://github.com/mihaild/dxdy/blob/ma ... rs/main.py за полчаса до 5000 досчитывает. Результатов нет.

[Dmitriy40]

Хм, а действительно, проверка на первые простые почти в четыре раза ускоряет. Думал isprime и так это делает, ан нет ...

[mihaild]

Тут думаю важна не сама по себе проверка на простые числа, а то, что вычислить $n^{n + 1} \mod p$ сильно быстрее, чем просто $n^{n + 1}$.

[Dmitriy40]

В питоне не знаю, я испытывал код PARI/GP:

? p=primes([3,10^6]);for(n=3,2000,x=n^(n+1)+n+1;for(i=1,#p,if(x%p[i]==0,next(2)));if(ispseudoprime(x),print(n)))
? ##
  ***   last result computed in 1min, 24,835 ms.

Как видно тут $n^{n+1}+n+1$ вычисляется всегда (и занимает лишь 9с суммарно с проверкой на простые). Вся программа при этом выполняется полторы минуты вместо пяти с половиной.

(Статистика делителей)

Ради интереса даже проверил сколько чисел проходят дальше на проверку, а сколько отсеиваются делением на простые до миллиона:
666,134,87,82,43,47,27 штук делятся на простые 3,5,7,11,13,17,19;
1312 делятся на простые до 100;
1602 на простые до тысячи;
1796 на простые до 10 тысяч;
1832 на простые до 100 тысяч;
1849 на простые до миллиона;
149 прошли дальше в isprime.
При этом пропуск делящихся на простые до 100 вычисления вообще не ускоряет (те же 5.5 минут), хотя количество проверок на простоту уменьшается аж втрое. Т.е. основные тормоза таки в проверке на простоту огромных чисел. Разумно проверять на простые только до 100 тысяч, это увеличивает время лишь на 2 секунды, с 1:25 до 1:27.

[daniel starodubtsev]

Предлагаю обобщение: числа вида $n^k^n^+^1 + kn + 1$ принимают простые значения только при достаточно малых $n$

Случай $k = 1$ уже рассмотрен (простые найдены только при $n\leqslant2$)
$k = 2$ и $n < 1000$ простые при $n=2$ и $n = 4$
$k = 3$ и $n < 1000$ простое выходит только при $n = 1$
$k = 4$ и $n < 500$ простое при $n = 2$

Для больших $k$ еще не проверял.

[Ktina]

daniel starodubtsev в сообщении #1369992 писал(а):

Предлагаю обобщение...

Спасибо за великолепное предложение!
Верю, что за обобщением последует обобщение обобщения.