Существует ли такое простое число?

[Someone]

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

Запускал wrest.

Я понял так, что это как раз список не отсеянных.

wrest в сообщении #1333302 писал(а):

На них мозгов не хватает на проверку простоты. Остальные проверены и не подходят.

Конечно, интересно, какие тесты выполнялись.

[wrest]

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

Конечно, интересно, какие тесты выполнялись.

Запускалась функция ispseudoprime из PARI/GP, которая проверяет на простоту (вероятную). Функция запускалась на планшете, ответа по каждому числу я ждал не более 30 секунд.
"Кандидаты" были отобраны перебором всех простых чисел в диапазоне между 1 и 100 000, для которых функция PARI/GP ispseudoprime не смогла за 30 секунд вернуть ответ является ли простым числом сумма, составленная по правилам первого поста темы.
Все остальные суммы для простых из указанного диапазона, кроме составленных из "кандидатов", признаны функцией ispseudoprime составными числами. В доках написано что если функция говорит что число составное то оно точно составное, а если говорит что простое, то оно "highly likely" простое.

[waxtep]

Мне почему-то* кажется, что $S(p)=34$ безнадежно как класс и надо браться за следующее возможное $S(p)=64$, начиная прямо с наименьшего красивого числа $19999999^{64}+64^{19999999}$. Но число это солидное, больше $10^{10^{7.5}}$

* - потому что тут и $n=6$, то есть как бы $6\times6$, или, как выразился по совершенно другому поводу мой коллега, "вот такое спортлото". (На научности или доказательности данного аргумента ни в коей мере не настаиваю)

[Someone]

wrest в сообщении #1333345 писал(а):

Запускалась функция ispseudoprime из PARI/GP

Она, скорее всего, делимость на небольшие простые числа не проверяет.

wrest в сообщении #1333345 писал(а):

Функция запускалась на планшете, ответа по каждому числу я ждал не более 30 секунд.

30 секунд — это очень мало. Она просто не успевает вычислить результат применения МТФ.

Я запустил проверку ваших кандидатов на PFGW.

waxtep в сообщении #1333347 писал(а):

надо браться за следующее возможное $S(p)=64$, начиная прямо с наименьшего красивого числа $19999999^{64}+64^{19999999}$. Но число это солидное, больше $10^{10^{7.5}}$

Это безнадёжно. Придётся ограничиться $S(p)=34$.

[Ktina]

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

Потому что он никогда раньше не ошибался.

Всё когда-то бывает впервые.

[Someone]

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

Я запустил проверку ваших кандидатов на PFGW.

Проверка закончена. Все составные.
Файл с данными (abba.txt):

(Оффтоп)

ABC $a^$b+$b^$a
37987 34
55897 34
57787 34
67993 34
74797 34
76597 34
77893 34
79657 34
79693 34
84697 34
84787 34
86677 34
86767 34
87973 34
89917 34
90997 34
94777 34
94993 34
95947 34
96973 34
97387 34
97927 34
98467 34
98737 34
98773 34
99277 34
99367 34

Командная строка:

pfgw64.exe -f -lLog.txt abba.txt

Ключ -f означает, что сначала выполняется поиск малого простого делителя (в каком интервале, программа определяет сама). Если делитель не найден, то для проверяемого числа $P$ вычисляется $3^{P-1}\pmod{P}$. Если результат не равен $1$, то число составное (малая теорема Ферма).
Файл отчёта (Log.txt):

(Оффтоп)

Recognized ABC Sieve file: 
37987^34+34^37987 has factors: 491

55897^34+34^55897 has factors: 2647

57787^34+34^57787 has factors: 42281

67993^34+34^67993 has factors: 883

74797^34+34^74797 has factors: 1045819

76597^34+34^76597 has factors: 8923

77893^34+34^77893 has factors: 173

79657^34+34^79657 has factors: 6323

79693^34+34^79693 has factors: 13093

84697^34+34^84697 is composite: RES64: [6D35DD311B14E3FD] (992.5931s+444.5129s)
84787^34+34^84787 has factors: 6997

86677^34+34^86677 has factors: 45232127

86767^34+34^86767 has factors: 251

87973^34+34^87973 has factors: 821

89917^34+34^89917 is composite: RES64: [71C2581437BBA2B1] (1073.8121s+931.2788s)
90997^34+34^90997 has factors: 1123

94777^34+34^94777 is composite: RES64: [B29A9602E23D3332] (1134.2858s+542.3037s)
94993^34+34^94993 has factors: 11863

95947^34+34^95947 is composite: RES64: [6B6EB61EEFB56BD8] (1150.7790s+561.5780s)
96973^34+34^96973 has factors: 523

97387^34+34^97387 has factors: 67399

97927^34+34^97927 has factors: 467

98467^34+34^98467 has factors: 3467

98737^34+34^98737 has factors: 2887

98773^34+34^98773 has factors: 85531

99277^34+34^99277 has factors: 3709

99367^34+34^99367 has factors: 4253

[waxtep]

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

Ключ -f означает, что сначала выполняется поиск малого простого делителя (в каком интервале, программа определяет сама).

При этом, алгоритм выдает наименьший простой делитель (если находит), или один из малых? Если первое, попытка разгадать в нем какую-либо структуру, видимо, обречена

[Someone]

waxtep в сообщении #1333366 писал(а):

алгоритм выдает наименьший простой делитель (если находит), или один из малых?

Наименьший. Просто последовательным делением.

[wrest]

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

Она, скорее всего, делимость на небольшие простые числа не проверяет.

Видимо так, потому что простым перебором второй делитель Ktina-суммы числа $37987$ находится на планшете за минуту (и равен $7005703$). А первый ($491$) и вовсе за $20$ миллисекунд. Правда, третье простое в разложении, если есть, то больше чем $10^7$ и дальше мучить планшет я не стал.

Ну что ж, теперь буду знать, что если PARI/GP надолго затрудняется с определением простоты, стоит попробовать малые делители "вручную".

Не нашел гуглом что такое pfgw64.exe -- она есть в исходных кодах (или готовое binary для arm)?

[kotenok gav]

wrest в сообщении #1333377 писал(а):

Не нашел гуглом что такое pfgw64.exe -- она есть в исходных кодах (или готовое binary для arm)?

http://primes.utm.edu/bios/page.php?id=175

[waxtep]

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

Это безнадёжно. Придётся ограничиться $S(p)=34$.

А! Ну да, наибольшее известное простое $2^{77232917}-1\approx10^{10^{7.37}}$ имеет раза в полтора меньше цифр, т.е. это самый передний край

-- 19.08.2018, 11:42 --

waxtep в сообщении #1333347 писал(а):

наименьшего красивого числа $19999999^{64}+64^{19999999}$

Ну оно-то делится на $5$

[lel0lel]

waxtep в сообщении #1333295 писал(а):

1. Смотрим только $p=6m+1,S(p)=6n-2$, иначе оно будет на $2$ или $3$ делиться.
2. И, только составные $S(p)+1$, иначе будет делиться на $S(p)+1$ (МТФ).

Второй пункт усиливается:
$2^{*}$. $S(p)$ не должно иметь делителей $d$ таких, что $d+1$ простое и $S(p)+1$ делится на $d+1$.

По этой причине $S(p)=64$ можно не рассматривать, у него есть делитель $4$, значит итоговое число будет делиться на 5.

[waxtep]

lel0lel в сообщении #1333420 писал(а):

По этой причине $S(p)=64$ можно не рассматривать, у него есть делитель $4$, значит итоговое число будет делиться на 5.

Точно! Значит, все что нам "светит" - это дальнейшее исследование $S(p)=34$, начиная с $p=109897$ (оканчивающиеся на девятку можно не проверять, там тоже всюду дележка на пять)

[lel0lel]

Проверка на малые делители оставила среди подходящих кандидатов следующие $p$:

169783, 179827, 188953, 227797, 266983, 271897, 281887, 285757, 
329677, 349477, 363967, 366397, 366973, 369673, 377557, 378583, 
382867, 388483, 389527, 390877, 393577, 397357, 399067, 399283, 
409993, 429973, 437587, 438667, 451897, 467197, 468493, 472993, 
475297, 476683, 476737, 478483, 488743, 488833, 506887, 519487, 
523987, 531997, 535957, 537847, 539863, 549097, 558457, 560977, 
564667, 567493, 569077, 571867, 577483, 577573, 580687, 581857, 
582937, 584377, 586087, 589453, 595717, 596257, 597823, 608857, 
617677, 621997, 630997, 634597, 637297, 646873, 649087, 653893, 
656737, 661777, 666727, 673837, 678463, 686437, 694087, 695293, 
697093, 699037, 706597, 707767.

Может быть кто-то захочет проверить своё железо и выполнит тест Ферма для некоторых из них. Будет интересно узнать результат, а также время выполнения и базу, по которой проведена проверка.

[Booker48]

Ktina в сообщении #1333210 писал(а):

Обозначим через $S(n)$ сумму десятичных цифр целого неотрицательного числа $n$.

В таких задачах Ктины всегда любопытно преодолеть ограничение, связанное со системой счисления.
Понятно, что во всех позиционных системах счисления с нечётным основанием таких чисел нет: в них, если число нечётно, то и сумма его цифр нечётна, а значит

$$p^{S(p)}+S(p)^{p}$$

чётно(-а?). В двоичной же сразу натыкаемся на $2$ и $3$ — но, м.б. это исключения? В четверичной проверка до $67$ включительно тех простых, у которых $S(n)$ чётна тоже ничего не дало.
М.б. поискать в системах с чётным основанием, меньшим $10$? Если даже в двоичной больше ничего не найдётся, то, по ощущениям, таких простых чисел и вовсе нет (за указанным исключением).
Хотя это, разумеется, абдуктивный вывод.