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

[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

[Утундрий]

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