Полиномиальные генераторы простых чисел

[mathpath]

Знакопеременный полином имеет форму
1 ± n ± n^2 ± n^3 ± ... ± n^k, n > 1, k > 1.

Я задался вопросом - как много простых может сгенерить такой полином
Был задан диапазон 100 > n > 2, 10 > k > 1
Оказалось, что для n=2 полином генерит 159 простых , всего 1024 варианта, т.е. 15%
Для n=3 генерится 139 простых, или 13%
Для n=33 генерится 66 простых, или 6%
Средний процент генерации составил 4%
При увеличении k процент простых будеть падать
При увеличении n процент простых также естественно будеть падать

Наибольшая плоность генерации у n=2

Например:

(Оффтоп)

========================================================================================================================
ТАБЛИЦА 1: ВСЕ НАЙДЕННЫЕ ПРОСТЫЕ ЧИСЛА (ПОЛНОСТЬЮ)
========================================================================================================================

--- n = 2 (найдено 159 простых чисел) ---
№ | последовательность знаков | значение | последние 10
---------+----------------------------------------------------------------+----------------------------------+------------------
1 | ---------+ | 3 | 3
2 | +--------+ | 7 | 7
3 | -+-------+ | 11 | 11
4 | --+------+ | 19 | 19
5 | +-+------+ | 23 | 23
6 | +++------+ | 31 | 31

....

--- n = 3 (найдено 139 простых чисел) ---
№ | последовательность знаков | значение | последние 10
---------+----------------------------------------------------------------+----------------------------------+------------------
1 | ---------+ | 29527 | 29527
2 | --+------+ | 29581 | 29581
3 | +-+------+ | 29587 | 29587
4 | -++------+ | 29599 | 29599
5 | -+++-----+ | 29761 | 29761
6 | ----+----+ | 30013 | 30013
7 | +++-+----+ | 30091 | 30091


....

--- n = 100 (найдено 28 простых чисел) ---
№ | последовательность знаков | значение | последние 10
---------+----------------------------------------------------------------+----------------------------------+------------------
1 | --+------+ | 98989898989900989901 | ...9900989901
2 | +-+-+----+ | 98989899009900990101 | ...9900990101
3 | +-+--+---+ | 98989900989900990101 | ...9900990101
4 | ---+++---+ | 98989901010098989901 | ...0098989901
5 | -++-+-+--+ | 98990099009901009901 | ...9901009901
6 | -+---++--+ | 98990100989899009901 | ...9899009901

Возможно ли в принципе найти хоть какую-то закономернссть в знакогенерации, которая порождает простые числа

[mathpath]

Вот примеры:

2 = + 2^2 - 2^1 [k=2]
3 = 1 + 2^2 - 2^1 [k=2]
5 = -1 + 2^2 + 2^1 [k=2]
7 = 1 + 2^2 + 2^1 [k=2]
11 = 1 + 2^3 + 2^2 - 2^1 [k=3]
13 = -1 + 2^3 + 2^2 + 2^1 [k=3]
17 = -1 + 2^4 + 2^3 - 2^2 - 2^1 [k=4]
19 = 1 + 2^4 + 2^3 - 2^2 - 2^1 [k=4]
23 = 1 + 2^4 + 2^3 - 2^2 + 2^1 [k=4]
29 = -1 + 2^4 + 2^3 + 2^2 + 2^1 [k=4]
31 = 1 + 2^4 + 2^3 + 2^2 + 2^1 [k=4]
37 = -1 + 2^5 + 2^4 - 2^3 - 2^2 + 2^1 [k=5]
41 = -1 + 2^5 + 2^4 - 2^3 + 2^2 - 2^1 [k=5]
...
9941 = -1 + 2^13 + 2^12 - 2^11 - 2^10 + 2^9 + 2^8 - 2^7 + 2^6 + 2^5 - 2^4 + 2^3 - 2^2 + 2^1 [k=13]
9949 = -1 + 2^13 + 2^12 - 2^11 - 2^10 + 2^9 + 2^8 - 2^7 + 2^6 + 2^5 - 2^4 + 2^3 + 2^2 + 2^1 [k=13]
9967 = 1 + 2^13 + 2^12 - 2^11 - 2^10 + 2^9 + 2^8 - 2^7 + 2^6 + 2^5 + 2^4 - 2^3 + 2^2 + 2^1 [k=13]
9973 = -1 + 2^13 + 2^12 - 2^11 - 2^10 + 2^9 + 2^8 - 2^7 + 2^6 + 2^5 + 2^4 + 2^3 - 2^2 + 2^1 [k=13]

Но как вывести из этого систему ?

Для получения следующего простого числа часто достаточно изменить знак одного члена или добавить или убрать 1

Есть еще понятия - сбалансированная двоичная система и сбалансированная троичная система

[mathpath]

OEIS A014580 - про бинарные неприводимые многочлены
Они тоже генерят простые числа
Интерес представляют многочлены длиной 3 :

x=2
x^2 + x + 1  = 7
x^3 + x + 1  = 11
x^3 + x^2 + 1 = 13
x^4 + x + 1 = 19
x^5 + x^2 + 1 =  37
...
x^39 + x^25 + 1 =  549789368321
x^39 + x^30 + 1 = 550829555713

Мой поисковик дошел до 39-й степени и больше ничего не находит

Вопрос: теоретически как долго это может продолжаться ?

Многочлены длиной 5 генерят сильно больше простых чисел, но это другая история

UPD::

x^41 + x^6 + 1 =  2199023255617
x^41 + x^15 + 1 =  2199023288321

Найдено для 41-й степени
Т.е. появилась дыра для 40-й
Дыры были и раньше, например для 25 и 32 степеней

[Dmitriy40]

mathpath в сообщении #1721596 писал(а):

Т.е. появилась дыра для 40-й
Дыры были и раньше, например для 25 и 32 степеней

? k=25; for(q=1,k-1, for(x=2,1e1, if(ispseudoprime(y=x^k+x^q+1), print("x=",x,", x^",k,"+x^",q,"+1=",y))))
x=3, x^25+x^3+1=847288609471
x=5, x^25+x^3+1=298023223876953251
x=6, x^25+x^3+1=28430288029929701593
x=8, x^25+x^3+1=37778931862957161710081
x=6, x^25+x^4+1=28430288029929702673
x=8, x^25+x^7+1=37778931862957163806721
x=6, x^25+x^10+1=28430288029990167553
x=3, x^25+x^18+1=847676029933
x=6, x^25+x^18+1=28430389589886369793
x=3, x^25+x^21+1=857748962647
x=6, x^25+x^21+1=28452224980570079233
x=8, x^25+x^22+1=37852718839251999916033
? k=32; for(q=1,k-1, for(x=2,1e1, if(ispseudoprime(y=x^k+x^q+1), print("x=",x,", x^",k,"+x^",q,"+1=",y))))
x=3, x^32+x^11+1=1853020189028989
x=9, x^32+x^15+1=3433683820292512690548981183931
x=5, x^32+x^17+1=23283064366149902343751
x=6, x^32+x^17+1=7958661109963327543836673
? k=40; for(q=1,k-1, for(x=2,1e1, if(ispseudoprime(y=x^k+x^q+1), print("x=",x,", x^",k,"+x^",q,"+1=",y))))
x=3, x^40+x^16+1=12157665459099975523
x=3, x^40+x^18+1=12157665459444349291
x=5, x^40+x^21+1=9094947017729759216308593751
x=6, x^40+x^22+1=13367494538843865689542688243713
x=3, x^40+x^28+1=12157688335849383763
x=3, x^40+x^30+1=12157871350189023451
x=9, x^40+x^30+1=147808829456737081591299413720677730803
x=3, x^40+x^31+1=12158283132453212749
x=5, x^40+x^37+1=9167706593871116638183593751
x=9, x^40+x^37+1=148011585010250375885789771537256251371
x=3, x^40+x^39+1=16210220612075905069

Если же вопрос конкретно про x=2, то:

? for(k=2,999, for(q=1,k-1, if(ispseudoprime(2^k+2^q+1), next(2))); print1(k,", "))
8, 25, 32, 40, 43, 48, 56, 58, 64, 96, 104, 112, 120, 128, 134, 140, 145, 152, 160, 176, 185, 192, 208, 212, 224, 235, 240, 244, 248, 252, 256, 264, 272, 280, 286, 288, 292, 302, 304, 308, 320, 326, 332, 348, 356, 360, 384, 392, 394, 400, 416, 418, 432, 448, 452, 464, 472, 488, 498, 500, 502, 503, 508, 512, 528, 538, 544, 547, 552, 554, 560, 563, 564, 576, 578, 592, 596, 599, 608, 632, 638, 640, 652, 656, 664, 672, 688, 712, 715, 728, 736, 744, 746, 752, 768, 792, 796, 800, 808, 816, 820, 824, 832, 836, 840, 848, 856, 858, 860, 864, 878, 882, 896, 898, 904, 916, 920, 924, 960, 962, 968, 976, 983, 992,

[mathpath]

Дыр почему-то больше не становится
Т.е. полином продолжает генерить простые, и скорее всего так будет и дальше, поскольку число вариантов с возрастанием степени естественно увеличивается, и хотя плотность простых чисел падает, все равно идет компенсация

[mathpath]

Вот такое полином шестой степени с рациональными коэффициентами - OEIS A330363 - генерит 58 простых подряд , начиная с -45 и заканчивая 12:
$ P(x) = {1\over72}x^6 + {1\over24}x^5 - {1583\over72}x^4 - {3161\over24}x^3 + {200807\over36}x^2 + {97973\over3}x - 11351 $$ $$|P(n)| \hbox{ is prime for } -45 \le n \le 12. $

[mathpath]

Еще два рекордсмена - первый находит 57 простых подряд
$ \frac{1}{4}(n^5-133n^4+6729n^3-158379n^2+1720294n-6823316) $

Второй находит 56 простых подряд
$ \frac{1}{36}(n^6-126n^5+6217n^4-153066n^3+1987786n^2-13055316n+34747236) $

Таблица рекордов:
https://mathworld.wolfram.com/Prime-Gen ... omial.html

[Утундрий]

Что-то похожее я видел у Ю. В. Матиясевича.

[mathpath]

Утундрий в сообщении #1721905 писал(а):

Что-то похожее я видел у Ю. В. Матиясевича.

Да, кажется так:
Существует многочлен от нескольких переменных с целыми коэффициентами, множество положительных значений которого (при подстановке целых неотрицательных переменных) в точности совпадает с множеством всех простых чисел.
Многочлен этот имеет чудовищную степень и 26 переменных (в более поздних работах число удалось уменьшить до 10, но классический результат — 26).
Степень многочлена очень велика (порядка 25-30).

Многочлен Матиясевича не порождает простые числа последовательно при росте одной переменной.
Перебирая все возможные комбинации целых неотрицательных значений 26 переменных, вы будете получать множество чисел. Среди них будут отрицательные, нули, составные числа — но каждое простое число обязательно встретится как положительное значение этого многочлена при каком-то наборе переменных.

[Dmitriy40]

mathpath в сообщении #1722193 писал(а):

Среди них будут отрицательные, нули, составные числа

Составных не будет - все положительные числа будут простыми. Разве что кроме 1.