2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5 ... 215  След.
 
 Пентадекатлон мечты
Сообщение06.02.2022, 06:29 
Аватара пользователя


29/04/13
8187
Богородский
Продолжение обсуждения из темы «И еще раз считаем всем миром...»

Поскольку пошла конкретика, обсуждение в теме со столь общим названием представляется далее неуместным.

Итак, ищем $15$ натуральных чисел подряд, имеющих ровно по $12$ делителей.

То бишь дюжинный пентадекатлон. Какова же его структура?

VAL в сообщении #1548056 писал(а):
Yadryara в сообщении #1548053 писал(а):
То есть в искомом пентадекатлоне должно быть строго $7$ чётных, где степени двойки должны быть строго такими:

$ 1 \quad 2 \quad 1 \quad 5 \quad 1 \quad 2 \quad 1  $

Правильно?
Совершенно верно.


Некоторое неудобство для дальнейшего анализа структуры получается из-за того, что в статье и в программе на PARI различные обозначения.

Поняв, как работает лемма $6$ и разобравшись почему в состав искомой 15-шки не может входить $2^3$, решил обратить внимание и на правую $2^2$.

И выяснилось, что это число, которое в статье обозначено как $n_4$, а в программе как $n+11$ (?) должно делиться строго на $12$.

То есть представление $$n_4 = 2^2q^3$$ не подходит, а возможно только $$n_4 = 2^2 \cdot3r$$
Обоснование довольно-таки длинное, посему пока что не привожу.

Здесь и далее предлагаю не использовать универсальную букву $p$, поскольку ею традиционно обозначаются все простые, включая $2$. Но мы ведь всё знаем про двойки. Так что у меня здесь $q$ и $r$ — нечётные простые, причём $r=8k+3$.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение06.02.2022, 07:38 
Аватара пользователя


29/04/13
8187
Богородский
Yadryara в сообщении #1548115 писал(а):
Так что у меня здесь $q$ и $r$ — нечётные простые, причём $r=8k+3$.

Можно усилить до $r=16k+3$ и отсюда следует, что $q=6k+1$ для натуральных $k$.

-- 06.02.2022, 08:32 --

Да, вижу, что делимость на $12$ в программе уже используется. Только для $n+10$.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение08.02.2022, 00:24 
Заслуженный участник


27/06/08
4062
Волгоград
Yadryara в сообщении #1548115 писал(а):
И выяснилось, что это число, которое в статье обозначено как $n_4$, а в программе как $n+11$ (?) должно делиться строго на $12$.

То есть представление $$n_4 = 2^2q^3$$ не подходит, а возможно только $$n_4 = 2^2 \cdot3r$$
Обоснование довольно-таки длинное, посему пока что не привожу.

Насколько я понимаю, это вовсе не обязательно. Вид $12$ должно иметь одно из двух чисел: либо четвертое от начала цепочки, либо четвертое с конца. (Поскольку обозначения в статье и в самом деле не совпадают с используемыми в программе, решил обойтись и без тех, и без этих :-) )

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение08.02.2022, 14:22 
Аватара пользователя


29/04/13
8187
Богородский
VAL в сообщении #1548248 писал(а):
Насколько я понимаю, это вовсе не обязательно. Вид $12$ должно иметь одно из двух чисел: либо четвертое от начала цепочки, либо четвертое с конца.

Да, я позже заметил, но писать уже не стал, ибо чего ж с самим собой разговаривать.

Задача напоминает мне знаменитую задачу Киркмана о 15-ти деятельницах, которую удалось-таки решить(спустя много лет как о ней впервые узнал).

Я придумал более-менее удобные(омаховские) обозначения:

$. \; h_7$
$.  \;  \;  h_6$
$.  \;  \;  \;  h_5$
$.  \;  \;  \;   \;  h_4$
$.  \;  \;  \;   \;   \;  h_3$
$.  \;  \;  \;   \;   \;   \;  h_2$
$.  \;  \;  \;   \;   \;   \;   \;  h_1$
$.  \;  \;  \;  \;    \;   \;   \;   \;  bs$
$.  \;  \;  \;   \;   \;   \;   \;  l_1$
$.  \;  \;  \;   \;   \;   \;  l_2$
$.  \;  \;  \;   \;   \;   l_3$
$.  \;  \;  \;   \;     l_4$
$.  \;  \;  \;     l_5$
$.  \;  \;      l_6$
$.  \;   l_7$

$h$ и $l$ от слов "high" и "low" соответственно. Очень удобно, что чётные индексы соответствует чётным числам и к тому же числа $h_4$ и $l_4$ обязательно делятся как раз на $4$. И только одно из них ещё и на $3$.

Каковы нынешние рекорды? 13 чисел или 14? И сколько найдено 13-к и/или 14-к? Есть ли среди рекордов результат, где использованы оба числа $h_6$ и $l_6$?

Я сделал свою программу, но она пока уверенно генерит только 6-ки чисел.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение08.02.2022, 19:13 
Заслуженный участник


27/06/08
4062
Волгоград
Yadryara в сообщении #1548294 писал(а):
Задача напоминает мне знаменитую задачу Киркмана о 15-ти деятельницах, которую удалось-таки решить(спустя много лет как о ней впервые узнал).
Полагаю сходство ограничивается тем, что и там, и там фигурирует число 15 :-)
Цитата:
Каковы нынешние рекорды? 13 чисел или 14? И сколько найдено 13-к и/или 14-к?
Сразу после нахождения цепочки из 13 чисел я переключился на 15. Разумеется, по ходу может найтись и 14, но если бы 14 было целью, поиск можно было бы оптимизировать. Так что, 14 пока не найдено.
Цитата:
Есть ли среди рекордов результат, где использованы оба числа $h_6$ и $l_6$?
В цепочке, начинающейся с 6854625212387082380472670696886398002841, 13 подходящих чисел. В том числе и $h_6$, и $l_6$

 Профиль  
                  
 
 Re: И еще раз считаем всем миром...
Сообщение10.02.2022, 10:03 
Заслуженный участник


20/08/14
11797
Россия, Москва
VAL в сообщении #1548034 писал(а):
А пока думаете, комп может посчитать, используя мои фильтры.
Вообще-то не получается: я ведь не исключительно на бумажке или в голове думаю, а проверяю свои предположения, а это перебор, занимающий часы и дни.
Пока лучшее чего достиг - нашёл несколько последовательностей длиной 10 величиной до $10^{19}$ за два дня счёта (в одном потоке). Беда. :-(

Появилось ощущение что ломлюсь в открытую дверь и то что пытаюсь проверять - уже давно исследовано и отброшено. В связи с этим можете подсказать пару моментов?
Первый. Проверяли ли Вы варианты с квадратом искомого большого простого числа? Например вида $10p^2=26\pmod{32}$, $14p^2=30\pmod{32}$, $15p^2=31\pmod{32}$, $21p^2=5\pmod{32}$, $22p^2=6\pmod{32}$? Т.е. не оставлять это на откуп numdiv, а проверять сразу самому. Я всё это время пытаюсь найти такие решения, но допустимых вариантов $p$ странно мало (меньше десятка на сотню триллионов), наибольшее $p\approx4\cdot10^{11}$. Возможно я что-то недопонимаю и такие варианты априори не подходят и я страдаю фигнёй? Просто странно почему младшие простые могут появляться в квадрате, а большие практически нет.

Второй. Правильно ли я понимаю что модуль $m=3660987554487982120802400$ (который равен $\operatorname{lcm}(2^5, p_i^2), 19\ne p_i\le37$) выбран несколько произвольно? В части что туда обязательно должны входить квадраты простых больших 3? Ведь в принципе ничто не мешает быть лишь квадратам простых скажем больше 1000, а из меньших только степени 2 и 3 выше первой. Т.е. это сознательный выбор такого ограничения или на то есть некие предпосылки? Соображение что младшие простые должны встречаться немного чаще - понятно, вопрос о более сильных.

Не вопросы, просто размышления. Перебирать линейно (вида $n=p_0+im$) как у Вас не интересно, это медленно (и понятно что и как и главное на сколько тут можно ускорить), хочется резко сузить количество подходящих вариантов. Но пока не понимаю как, все перепробованные варианты или не дают решений вообще, или дают их аномально мало (подозрительно мало). При том что в принципе можно до 5 из 15-ти больших простых иметь в квадратах, но даже пара уже практически не встречается.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение10.02.2022, 11:16 
Аватара пользователя


29/04/13
8187
Богородский
Да, между словами "обозначение" и "мучение" не такая уж большая разница. Трудно придумать во всех отношениях удобные обозначения. Попробовал обозначить номера искомых чисел с 1-го по 15-е с помощью 16-ричной CC. То есть наименьшее — 1, наибольшее — F.

Если придерживаться схемы, которую я назвал концепцией минимальных квадратов, то один из вариантов можно изобразить так:

$\text{Малые}\hspace{3.7cm}1\; 1\; 1\; 1\; 2\; 2\; 3\; 3 \hspace{1.7cm} 5$
$\text{квадраты}\hspace{1.8cm} 3\; 3\hspace{0.46cm}  5\; 7\; 1\; 3\; 7\; 9\; 3\; 9\; 1\; 7 \hspace{0.76cm} 2\; 2\hspace{0.36cm}  2$

$\text{Позиции}\hspace{1.91cm} 1\, \text{A} \hspace{0.45cm} 6\; 2\; 5\; 3\; 7\; 9 \; \text{B} \text{D} \text{E} \text{F}\hspace{0.73cm} 4 \,\text{C}\hspace{0.36cm}   8$

$\text{Множитель раз}\hspace{0.8cm}       5\; 2\hspace{0.45cm}   2\; 2\; q\; q\; 3\; 7\; 5\; 3\; 2\; q \hspace{0.77cm}         3\; q \hspace{0.36cm}  q$
$\text{Множитель два}\hspace{0.8cm}       r\; r \hspace{0.48cm}   r\; r\; r\; r\; r\; r\; r\; r\; r\; r           \hspace{0.8cm} r\; r$

Единственный не квадрат в верхней строке это $2^5$. 12-значный код расстановки здесь 1A625379BDEF.

Если поставить на первое место то самое число $6854625212387082380472670696886398002841$, то схема будет выглядеть так:

$\text{Малые}\hspace{3.7cm}1\; 1\; 1\; 1\; 2\; 2\; 3\; 3 \hspace{1.7cm} 5$
$\text{квадраты}\hspace{1.8cm} 3\; 3\hspace{0.46cm}  5\; 7\; 1\; 3\; 7\; 9\; 3\; 9\; 1\; 7 \hspace{0.76cm} 2\; 2\hspace{0.36cm}  2$

$\text{Позиции}\hspace{1.91cm} 6\, \text{F} \hspace{0.4cm} \text{A}\text{B}\; 7\; \text{D}\; 1\; 5 \; 9\; \text{E} \;3 \;2\hspace{0.65cm} 4 \,\text{C}\hspace{0.36cm}   8$

$\text{Множитель раз}\hspace{0.8cm}       2\; 5\hspace{0.45cm}   2\; q\; q\; q\; q\; 5\; 3\; 2\; 3\; 2 \hspace{0.77cm} 7\; 3 \hspace{0.36cm}  q$
$\text{Множитель два}\hspace{0.8cm}       r\; r \hspace{0.48cm}   r\; r\; r\; r\; r\; r\; r\; r\; r\; r           \hspace{0.8cm} r\; r$

И код этой расстановки 6FAB7D159E32.

Как видим, в обоих случаях здесь аж 19 неизвестных нечётных простых. Это различные $q$ и $r$, пока обозначенные лишь двумя буквами. Для второй расстановки 15 неизвестных были найдены.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение10.02.2022, 12:21 
Аватара пользователя


29/04/13
8187
Богородский
Как пользоваться схемой. Допустим, надо узнать 14-е по величине число нашей 15-шки. Во втором случае мы его знаем:

$6854625212387082380472670696886398002841 + 13 = $
$6854625212387082380472670696886398002854$

А сколько у него делителей?

$14_{16}$$E$. Ищем, где $E$ в строке "Позиции". И находим под числом $29$. Идём вниз по этому столбцу. Видим множители $2$ и $r$. Значит нам надо перемножить три числа: $29^2\cdot2\cdot r$

Отсюда $r=4075282528173057301113359510634005947$. И оно простое. Значит, необходимые нам $12$ делителей найдены.

А если мы хотим узнать 13-е по величине число той же самой нашей 15-шки? Да, мы его тоже знаем:

$6854625212387082380472670696886398002841 + 12 = $
$6854625212387082380472670696886398002853$

А сколько у него делителей?

$13_{16}$$D$. Ищем, где $D$ в строке "Позиции". И находим под числом $13$. Идём вниз по этому столбцу. Видим множители $q$ и $r$. Значит нам надо перемножить три числа: $13^2\cdot q\cdot r$

Но вот беда: вместо двух различных простых сомножителей находятся целых пять. Так что это число вида $13^2qrstv$, а не $13^2qr$ и имеет $96$ делителей вместо требуемых $12$.

И те же $96$ делителей у числа в позиции $B$.

А зачем вообще нужна эта схема?

VAL в сообщении #1203960 писал(а):
координировать действия нескольких участников

Вот я как раз и хочу подробно разобраться, какие варианты уже проверены и какие результаты достигнуты. Например, может оказаться, что варианты, начинающиеся с "1A" проверять не нужно, а направление "6F", напротив, перспективно.

Собственно, в рамках концепции минимальных квадратов, другие варианты и невозможны. Даже точнее: невозможно начать не с "1A6" или "6FA".

 Профиль  
                  
 
 Re: И еще раз считаем всем миром...
Сообщение10.02.2022, 12:57 
Заслуженный участник


27/06/08
4062
Волгоград
Dmitriy40, мне кажется, на все Ваши вопросы я уже отвечал :-)
Попробую еще раз.

Я проверяю наборы (по 15 чисел), в которых среднее число обязательно кратно 32, но не 64 (соответствующие числа любых наборов сравнимы по модулю 64).

Ровно два числа в каждом наборе стоят кратны 9. Это могут быть либо 1-е и 10-е число, либо 6-е и 15-е. Соответственно либо 6-е, либо 10-е число кратно 25 (см. таблицы, которые я присылал).

По одному числу в каждом наборе кратно 49, 121, 169, 289, 361, 529, 841, 961, 1369. При этом в наборах нет третьего числа, кратного 7, и вторых чисел, кратных 11 и 13 (последние теоретически могли бы присутствовать, но их допущение резко снижает эмпирическую вероятность успеха, поскольку в интересующем нас диапазоне произведения двух простых встречаются гораздо чаще, чем простые).

Таким образом, в проверяемых наборах заведомо не будет чисел, делящихся на квадраты простых чисел, больших 37. Разумеется, в интересующих нас цепочках таковые могут встречаться. Но в целях ускорения поиска выгоднее искать цепочки без них.

С учетом указанных ограничений возникает несколько десятков тысяч идентичных начальных условий для программы поиска. У меня автоматически сгенерированы порядка 2000 таких программ. Их-то я и собирался рассылать волонтерам, коих, к сожалению, почти нет :cry:

Для каждой цепочки сначала идет 11 проверок с помощью ispseudoprime (они быстрее и положительный ответ менее вероятен), а затем 4 проверки c помощью numdiv.

Отмечу, что каждая программа перебирает цепочки с одним и тем же шагом $2^63^3\prod_{i=3}^{12}p_i^2$.
Является ли он произвольным? Думаю, он оптимален. Произвольным, скорее, является выбор конкретных начальных условий из нескольких тысяч равновозможных.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение10.02.2022, 16:54 
Аватара пользователя


29/04/13
8187
Богородский
VAL в сообщении #1548506 писал(а):
При этом в наборах нет третьего числа, кратного 7, и вторых чисел, кратных 11 и 13 (последние теоретически могли бы присутствовать, но их допущение резко снижает эмпирическую вероятность успеха, поскольку в интересующем нас диапазоне произведения двух простых встречаются гораздо чаще, чем простые)

Да, это полезное наблюдение. Но тогда надо присмотреться и, например, к единственной 7-ке(числу кратному ровно 7). Для неё возможны только места 4, 7, 9, 12. И если разместить её на 4-й(как у Вас в примере) или 12-й позициях, то набор $4\cdot7r$, и приходится искать огромное простое r.

А если она на 7-й или 9-й позициях, то набор, например $19^2\cdot7r$ и ищем простое уже на два порядка меньше.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение10.02.2022, 18:08 
Заслуженный участник


20/08/14
11797
Россия, Москва
VAL
Возможно и отвечали ранее, но или я не понял, или ответ был про чуть другое. Сейчас вот это увидел
VAL в сообщении #1548506 писал(а):
(последние теоретически могли бы присутствовать, но их допущение резко снижает эмпирическую вероятность успеха, поскольку в интересующем нас диапазоне произведения двух простых встречаются гораздо чаще, чем простые).

Таким образом, в проверяемых наборах заведомо не будет чисел, делящихся на квадраты простых чисел, больших 37. Разумеется, в интересующих нас цепочках таковые могут встречаться. Но в целях ускорения поиска выгоднее искать цепочки без них.
и стало понятно почему и простые взяли наименьшие, и от проверки квадратов отказались.
Спасибо за разъяснения.

Что же, с работой Ваших программ понятно, вопрос лишь как выбираете начальные числа, типа этого $p_1=5028162941065848674776261$, как строится всё их множество тоже понятно (по китайской теореме об остатках). Но это уже детали, на скорость перебора цепочек (но не величину числа $n$) это слабо влияет. А заниматься мелкими оптимизациями кода на PARI неохота.


Мне интереснее не просто запустить ваш код, а пытаться его ускорить, или в самом PARI, или вынесением части проверок наружу (в прогу на асме, да ещё и AVX прикрутить). Причём ускорить не в разы, а на пару-тройку порядков. ;-) Поэтому и хотел сменить формулы на содержащие квадраты простых. Например выложенная Вами выше программа использует следующую комбинацию коэффициентов:
Используется синтаксис Text
\\      n+0     n+1     n+2     n+3     n+4     n+5     n+6     n+7     n+8     n+9     n+10    n+11    n+12    n+13    n+14
\\      -       2pq^2   3pq^2   4pq     5pq^2   18p     847p    32p     3pq^2   50p     -       12p     169pq   98p     45p
в которой в числа $q^2$ подставлены квадраты простых 19,31,23,37 соответственно слева направо:
Используется синтаксис Text
\\      n+0     n+1     n+2     n+3     n+4     n+5     n+6     n+7     n+8     n+9     n+10    n+11    n+12    n+13    n+14
\\      -       722p    2883p   4pq     2645p   18p     847p    32p     4107p   50p     -       12p     169pq   98p     45p
Понятно что все $p$ и $q$ тут и далее разные.
В результате остались лишь первые степени неизвестных простых $p$, которые Вы и ищете перебором с постоянным шагом по одному из них. А все $q$ и пропущенные позиции найдутся сами, через numdiv.

(Зачем вообще подставлять квадраты)

Тут есть непонятная тонкость: зачем вообще подставили квадраты маленьких простых. Понятно чтобы увеличить модуль/шаг, но ведь тогда пропускаете огромную тучу вариантов где на этих местах стоят простые чуть больше 37. А количество проверок цепочек ровно то же, одна на модуль/шаг. Зато числа больше и PARI их проверить чуть труднее. Это полезно делать ради распараллеливания, но у вас и так достаточно разных вариантов чтобы загрузить хоть тысячи потоков. Зато если не подставлять квадраты первых простых, то и числа будут меньше, и подходящих под них вариантов будет больше, при фактически том же объёме проверок. Да, чуть чаще будут "ложные срабатывания" (уход на проверку numdiv вместо более быстрых ispseudoprime), но ведь и до подстановки есть 7 чисел лишь с $p$, одно перебираем, на 6 вместо 10 проверяем, частота уходов заметно не повысится и тормоза от numdiv влиять не будут (доли и единицы процентов замедления как обычно нагло игнорирую).
В качестве обоснования приведу сравнение: ваша десятка начинается с числа $n=1545780028345667311380575449$, я же аналогичным линейным поиском на PARI без подстановки этих вот квадратов малых простых нашёл $n=385202062351588441$ той же длины 10, в 4млрд раз меньше. Да, мериться размером чисел, тем более для длины 10, смысла мало, просто иллюстрация что и без подстановки поиск достаточно эффективен.

Но я хотел поискать по формулам типа такой:
Используется синтаксис Text
\\      n+0     n+1     n+2     n+3     n+4     n+5     n+6     n+7     n+8     n+9     n+10    n+11    n+12    n+13    n+14
\\      9pq     10p^2   11pq^2  12p     13pq^2  14p^2   15p^2   32p     -       18p     -       20p     21p^2   22p^2   -
Тут можно предварительно найти все возможные комбинации 5-ти простых $p$, чтобы выполнялись одновременно все равенства $10p^2-1=14p^2-5=15p^2-6=32p-7=21p^2-12=22p^2-13\pmod{m}$ по некоторому достаточно большому модулю $m$. Тогда можно перебирать лишь несколько (или вообще один если повезёт) вариантов $p$ по этому модулю (т.е. с таким шагом). А так как условие на совпадение квадратов сильнее условия совпадения произведений, то и модуль тут должен быть на много порядков больше - а значит проверять на простоту и количество делителей на те же порядки меньше. Но проблема оказалась в нахождении и такого модуля, похоже он кардинально огромный, и подходящих вариантов $p$. Про символ Лежандра только пытаюсь осознать.
Кроме того, извлечение квадратного корня намного быстрее проверки на простоту, во всяком случае на обычном языке типа С или асма (но не PARI), что тоже можно использовать, даже на PARI (предварить проверку на простоту проверкой извлекаемости корня, плюс числа в ispseudoprime будут сильно меньше что тоже поможет PARI их проверить). А если организовать проверку на извлекаемость корня внешней прогой, что в общем несложно, то можно получить и хорошую скорость проверки (порядка сотен миллионов цепочек в секунду).
Такова была общая идея, вот её и обсасываю в разных вариантах. Пока безуспешно.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение11.02.2022, 01:08 
Заслуженный участник


27/06/08
4062
Волгоград
Dmitriy40 в сообщении #1548533 писал(а):
Такова была общая идея, вот её и обсасываю в разных вариантах. Пока безуспешно.
Возможно, я не все понял в предлагаемом Вами подходе. Но с позиции моего понимания он кажется бесперспективным. Вероятность того, что цепочка из Вашей схемы окажется искомой по грубой прикидке в $10^{17}$ раз меньше, чем для цепочек, проверяемых у меня. Это с лихвой убьет все преимущества, связанные с меньшим размером проверяемых чисел. (Хотя... вдруг повезет :D )

Откуда оценка?
Давайте, например, сравним вероятности того, что числа стоящие на 11-м месте в Вашей и моей цепочках будут иметь по 12 делителей.
В моем случае оно гарантированно делится на квадрат простого числа. Поэтому достаточно, чтобы частное было произведением двух простых. Эмпирическая вероятность этого события (для 40-значных чисел) примерно 0.24.
В Вашей же схеме это число должно быть произведением квадрата простого числа, большего 13, и еще двух простых сомножителей (вероятность того, что оно будет 11-й степенью простого или произведением 5-й и 1-й степеней простых, пренебрежимо мала).
Эмпирическая вероятность этого события (для 40-значных чисел) примерно в 60 раз меньше.
И это только для одного числа.

-- 11 фев 2022, 01:17 --

Yadryara в сообщении #1548522 писал(а):
Да, это полезное наблюдение. Но тогда надо присмотреться и, например, к единственной 7-ке(числу кратному ровно 7). Для неё возможны только места 4, 7, 9, 12. И если разместить её на 4-й(как у Вас в примере) или 12-й позициях, то набор $4\cdot7r$, и приходится искать огромное простое r.

А если она на 7-й или 9-й позициях, то набор, например $19^2\cdot7r$ и ищем простое уже на два порядка меньше
Это мелочи. Разумеется, вероятность наткнутся на простое среди 38-значных выше, чем среди 40-значных (а поиск идет примерно в таком диапазоне). Но разнятся они несущественно.

А кроме того, у меня много (порядка двух тысяч) программок. И в большинстве 7-ка стоит на 7-м или 9-м местах :-)

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение12.02.2022, 17:32 
Заслуженный участник


20/08/14
11797
Россия, Москва
VAL в сообщении #1548563 писал(а):
Вероятность того, что цепочка из Вашей схемы окажется искомой по грубой прикидке в $10^{17}$ раз меньше, чем для цепочек, проверяемых у меня. Это с лихвой убьет все преимущества, связанные с меньшим размером проверяемых чисел. (Хотя... вдруг повезет :D )
Что-то оценка мне кажется сильно завышенной, но так сходу аргументов не приведу. Потому вчера полдня собирал статистику чтобы разобраться, собрал, теперь надо её обдумать, как-то она неоднозначная (и решить каков критерий оптимальности). Подробно про это напишу позже, как обдумаю. На первый взгляд Вы правы, преимущество в подстановках есть, но максимум на порядок, да и то смотря как сформулировать критерий.

Пока же мои идеи эффекта не дают решил переписать линейный перебор, вынести проверку псевдопростоты из PARI во внешнюю прогу (на любимом асме, да), причём не одного числа (что невыгодно, интерфейс съест весь выигрыш скорости), а сразу перебор $k$ из формулы $n=n_0+km$ (он в точности эквивалентен перебору простого у Вас, вопрос лишь в выборе $k$, у Вас оно $k=722p$, я же заморачиваться с такой оптимизацией для простоты пока не стал и перебираю сразу $k$) с проверкой что псевдопростыми оказываются одновременно все числа $(n+5)/18$, $(n+7)/32$, $(n+8)/363$, $(n+9)/50$, $(n+11)/12$, $(n+13)/98$, $(n+14)/45$. В вашей программе эта оптимизация частично тоже есть, утроением модуля (о сколько я ломал бошку почему у вас там в $m$ три в кубе вместо квадрата! :facepalm:) и проверками $i$ по нескольким модулям (в которых кстати у Вас неточность для модулей больше $11$, там надо не по одному $i$ исключать, а по 7 разных), но я пошёл дальше и проверяю делимость всех чисел на большее число малых простых (да, оптимизацию этих проверок тоже оставил на потом). Плюс всё написано на асме (с дополнительной заменой медленных делений на быстрые умножения), что тоже существенно быстрее PARI. Если конкретное $k$ подходит, т.е. даёт все вышеуказанные числа не кратные малым простым, то такое $k$ возвращается обратно в PARI для полной проверки.
В итоге скорость перебора увеличилась с примерно миллиона цепочек в секунду, что ограничивается скоростью самой первой ispseudoprime, до почти 30 миллионов в секунду ($10^{11}$ в час) и ограничивается уже моей прогой, в которой на удивление нет зависимости от величины чисел (в отличие от PARI, ispseudoprime в котором резко тормозит с увеличением чисел). Коэффициент фильтрации составил примерно 250-500 (регулируется в исходнике проги), из миллиона $k$ в PARI на проверку уходит менее 2...4 тысяч, которые он проверяет примерно впятеро быстрее моей проги (т.е. его тормоза от величины чисел на итоговую скорость влияют уже не сильно).
С утра за 6ч перебрались $6\cdot10^{11}$ цепочек и нашлись 6 штук длиной 10 (но все в первой трети диапазона). Числа $n$ при этом до $8\cdot10^{19}$ (я ради поиска всех возможных вариантов и попадания под ограничения своей проги не подставлял простых в квадратах), т.е. совсем небольшие. Более длинных цепочек пока не нашлось.
Прогу не выкладываю по двум причинам:
а) она заточена под конкретную группу паттернов (формул, список привёл выше) и для переделки под другую нужны не слишком тривиальная правка ассемблерного исходника и перекомпиляция;
б) она имеет сильные ограничения на величину чисел: в $n=n_0+km$ все три числа $n_0, k, m <2^{64}$, что ограничивает $n$ величиной менее примерно $10^{38}$, и то достижимой только при очень специально подобранном паттерне, с обычными предел на порядки ниже, Вы за эти рамки уже вышли.
Собственно получился пока ещё далеко не конечный продукт на годы счёта, а скорее полуфабрикат для дальнейших исследований. Так что это скорее отчёт о промежуточной вехе. :-)

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение12.02.2022, 18:10 
Заслуженный участник


27/06/08
4062
Волгоград
Dmitriy40 в сообщении #1548653 писал(а):
...кстати у Вас неточность для модулей больше $11$, там надо не по одному $i$ исключать, а по 7 разных
Почему?

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение12.02.2022, 22:24 
Заслуженный участник


20/08/14
11797
Россия, Москва
VAL
Я неточно выразился, не "надо", а "можно".
Потому что в этом случае $i$ попадают в список чисел гарантированно не более одного раза, а при этом разрешены все позиции (все смещения) и любое из них может стать запретным. Если же попадают два и более раз, то появляются ограничения на допустимые позиции (смещения) и количество вариантов уменьшается (или увеличивается). Это если очень "на пальцах", корректнее мне трудно сформулировать, я поступил проще - программку написал:
код: [ скачать ] [ спрятать ]
Используется синтаксис Text
\\      n+0     n+1     n+2     n+3     n+4     n+5     n+6     n+7     n+8     n+9     n+10    n+11    n+12    n+13    n+14
\\%32:  %25     %26     %27     %28     %29     %30     %31     %0      %1      %2      %3      %4      %5      %6      %7
{v=[    1,      1,      1,      1,      1,      18,     1,      32,     363,    50,     1,      12,     1,      98,     45      ];
pp=Mod(0,1); for(i=1,#v, pp=chinese(pp,Mod(-i+1,v[i]))); print(pp);
forprime(m=3,37,
        mm=2^64-1;\\Изначально разрешено всё, маска из всех 1
        for(i=0,m-1,
                n=lift(pp)+i*pp.mod;
                for(d=0,14, if(v[d+1]>1 && ((n+d)/v[d+1])%m==0, mm-=2^i; break));\\Если разделилось в любой используемой позиции паттерна, то запрещаем
        );
        printf("%2d:", m,); for(i=0,m-1, print1(if((mm\2^i)%2>0, i%10, "-"))); print;
)}

\\Её вывод:
Mod(29157241, 42688800)
 3:--2
 5:-1234
 7:012-456
11:0-234567890
13:01-34-6-----2
17:0-----67890-23-56
19:---3-5--890123456-8
23:01-3456--901-345--89-12
29:0-2345-7890-2-456789-1234-67-
31:012345-78-012345678901-----7890
37:012345-78-01-34-67-9012-45678901-3456

\\Другой паттерн, из выложенной выше Вашей программы:
\\      n+0     n+1     n+2     n+3     n+4     n+5     n+6     n+7     n+8     n+9     n+10    n+11    n+12    n+13    n+14
\\%32:  %25     %26     %27     %28     %29     %30     %31     %0      %1      %2      %3      %4      %5      %6      %7
{v=[    1,      722,    2883,   1,      2645,   18,     847,    32,     4107,   50,     1,      12,     1,      98,     45      ];
\\Вывод программы (для простых по 53):
Mod(8460769000242914041, 10725156955673344800)
 3:0--
 5:0123-
 7:0-23456
11:0-234567890
13:-1---5-----1-
17:01--4--7-----3--6
19:0123-56789012345678
23:-1234567890123456789012
29:0-234-67--012-45-789-12--5--8
31:0123456789-12345678901234567890
37:01234567890123456-8901234567890123456
41:-123--678-01234-678-0123--6789-1234-6789-
43:012-45678---2345---90123-567890--34567-9012
47:01--45678--12345--8901--456789-123456789012--56
53:01-34-67-90123-56-8901234567890-23-56789-12345-78-01-
Обратите внимание на количество прочерков в масках, как только закачиваются использованные числа, так сразу же количество прочерков становится постоянным и равным количеству использованных позиций в паттерне.
Как видно это маски для индексов в $n$, если хотите для индексов в $p=(n+1)/722$, то придётся пересчитать по модулям, но вроде бы от этого количество прочерков не меняется, только положения.

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

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



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

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


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

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