2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 Re: Существует ли такое простое число?
Сообщение18.08.2018, 18:44 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
kotenok gav в сообщении #1333323 писал(а):
Запускал wrest.
Я понял так, что это как раз список не отсеянных.
wrest в сообщении #1333302 писал(а):
На них мозгов не хватает на проверку простоты. Остальные проверены и не подходят.
Конечно, интересно, какие тесты выполнялись.

 Профиль  
                  
 
 Re: Существует ли такое простое число?
Сообщение18.08.2018, 23:20 


05/09/16
11468
Someone в сообщении #1333324 писал(а):
Конечно, интересно, какие тесты выполнялись.

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

 Профиль  
                  
 
 Re: Существует ли такое простое число?
Сообщение18.08.2018, 23:56 
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Существует ли такое простое число?
Сообщение19.08.2018, 00:44 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
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$.

 Профиль  
                  
 
 Re: Существует ли такое простое число?
Сообщение19.08.2018, 01:16 
Аватара пользователя


01/12/11

8634
kotenok gav в сообщении #1333309 писал(а):
Потому что он никогда раньше не ошибался.

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

 Профиль  
                  
 
 Re: Существует ли такое простое число?
Сообщение19.08.2018, 02:16 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
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


 Профиль  
                  
 
 Re: Существует ли такое простое число?
Сообщение19.08.2018, 03:16 
Аватара пользователя


07/01/16
1426
Аязьма
Someone в сообщении #1333361 писал(а):
Ключ -f означает, что сначала выполняется поиск малого простого делителя (в каком интервале, программа определяет сама).
При этом, алгоритм выдает наименьший простой делитель (если находит), или один из малых? Если первое, попытка разгадать в нем какую-либо структуру, видимо, обречена

 Профиль  
                  
 
 Re: Существует ли такое простое число?
Сообщение19.08.2018, 04:00 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
waxtep в сообщении #1333366 писал(а):
алгоритм выдает наименьший простой делитель (если находит), или один из малых?
Наименьший. Просто последовательным делением.

 Профиль  
                  
 
 Re: Существует ли такое простое число?
Сообщение19.08.2018, 08:46 


05/09/16
11468
Someone в сообщении #1333353 писал(а):
Она, скорее всего, делимость на небольшие простые числа не проверяет.

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

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

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

 Профиль  
                  
 
 Re: Существует ли такое простое число?
Сообщение19.08.2018, 10:04 


21/05/16
4292
Аделаида
wrest в сообщении #1333377 писал(а):
Не нашел гуглом что такое pfgw64.exe -- она есть в исходных кодах (или готовое binary для arm)?

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

 Профиль  
                  
 
 Re: Существует ли такое простое число?
Сообщение19.08.2018, 11:19 
Аватара пользователя


07/01/16
1426
Аязьма
Someone в сообщении #1333353 писал(а):
Это безнадёжно. Придётся ограничиться $S(p)=34$.
А! Ну да, наибольшее известное простое $2^{77232917}-1\approx10^{10^{7.37}}$ имеет раза в полтора меньше цифр, т.е. это самый передний край

-- 19.08.2018, 11:42 --

waxtep в сообщении #1333347 писал(а):
наименьшего красивого числа $19999999^{64}+64^{19999999}$
Ну оно-то делится на $5$

 Профиль  
                  
 
 Re: Существует ли такое простое число?
Сообщение19.08.2018, 13:42 


20/04/10
1776
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.

 Профиль  
                  
 
 Re: Существует ли такое простое число?
Сообщение19.08.2018, 16:07 
Аватара пользователя


07/01/16
1426
Аязьма
lel0lel в сообщении #1333420 писал(а):
По этой причине $S(p)=64$ можно не рассматривать, у него есть делитель $4$, значит итоговое число будет делиться на 5.
Точно! Значит, все что нам "светит" - это дальнейшее исследование $S(p)=34$, начиная с $p=109897$ (оканчивающиеся на девятку можно не проверять, там тоже всюду дележка на пять)

 Профиль  
                  
 
 Re: Существует ли такое простое число?
Сообщение19.08.2018, 19:15 


20/04/10
1776
Проверка на малые делители оставила среди подходящих кандидатов следующие $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.

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

 Профиль  
                  
 
 Re: Существует ли такое простое число?
Сообщение19.08.2018, 21:18 


07/06/17
983
Ktina в сообщении #1333210 писал(а):
Обозначим через $S(n)$ сумму десятичных цифр целого неотрицательного числа $n$.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 39 ]  На страницу Пред.  1, 2, 3  След.

Модератор: Модераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group