fixfix
2014 dxdy logo

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

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




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


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

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


05/09/16
12406
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
1654
Аязьма
Мне почему-то* кажется, что $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
18035
Москва
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
18035
Москва
Someone в сообщении #1333353 писал(а):
Я запустил проверку ваших кандидатов на PFGW.
Проверка закончена. Все составные.
Файл с данными (abba.txt):

(Оффтоп)

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

(Оффтоп)


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


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

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


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

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


05/09/16
12406
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
1654
Аязьма
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
1993
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
1654
Аязьма
lel0lel в сообщении #1333420 писал(а):
По этой причине $S(p)=64$ можно не рассматривать, у него есть делитель $4$, значит итоговое число будет делиться на 5.
Точно! Значит, все что нам "светит" - это дальнейшее исследование $S(p)=34$, начиная с $p=109897$ (оканчивающиеся на девятку можно не проверять, там тоже всюду дележка на пять)

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


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