2014 dxdy logo

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

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




На страницу Пред.  1 ... 236, 237, 238, 239, 240, 241  След.
 
 Re: Пентадекатлон мечты
Сообщение12.10.2025, 06:35 
Аватара пользователя
Ну вот не зря советовал не морочить голову. Попытался разобраться. И опять терминология мешает. Оказывается EUgeneUS называет большим ифом совсем не тот иф, который так называли мы с Дмитрием.

Это терапевтика. Следуя VALу. У меня это массив zap, а у Дмитрия — bad, правда с другой индексацией. Хорошее слово, короткое. Предлагаю так и говорить — о бэдах или терапевтике, но не о большом ифе.

В плане автоматизации вычислений очень неплохо бы разобраться какую добавку делать для остатка, который именуется p1. А то и 4/6*m и 5/6*m встречается. А другие невозможны?

 
 
 
 Re: Пентадекатлон мечты
Сообщение12.10.2025, 07:34 
Аватара пользователя
Dmitriy40 в сообщении #1705386 писал(а):
Параллельная программа:

Спасибо!
Раскомментировал строку, как указано:
Код:
default(nbthreads,1);\\Убрать комментарий для запуска в одном потоке даже под gpp.exe


Но не запустилось :roll:
Код:
  ***   at top-level: ...,i2,pows,p1,m,vp,npr,t0);parfor(th=0,nth-1,my(
  ***                                             ^---------------------
  *** parfor: mt: please use export(pr2).


Видимо, что-то недоставлено...

-- 12.10.2025, 07:35 --

Yadryara в сообщении #1705411 писал(а):
Оказывается EUgeneUS называет большим ифом совсем не тот иф, который так называли мы с Дмитрием.

А что Вы называете "большим ифом"?

-- 12.10.2025, 07:47 --

За ночь статистика посчиталась до $26660$ кандидатов.

результаты:

1. Расчетный $b(1)$ оказался опять меньше теоретического, не много - в третьем знаке, но опять.
2. Вчера, до сбора статистики, делал оценки и ошибся в каждой позиции всего-то в третьем значащем знаке. :lol:
Это не удивительно - все поправочные коэффициенты для "4-0-12-5 (9)" и должны быть такими же, как для "3-0-13-5 (9)" - так как используются те же самые простые.
Неприятно другое: ошибка в третьем знаке в вероятности в каждой позиции, приводит к ошибке в 1.5 раза в финальной вероятности найти цепочку.

3. Сделал сравнение для 1 и 300000 тысяч паттернов.
Стабильно: количество необходимых проверок для "4-0-12-5 (9)" в $5.3 ... 5.5$ больше, чем для "3-0-13-5 (9)".
Это уже точно не окупается быстрой проверкой одного места и дополнительной фильтрацией.

 
 
 
 Re: Пентадекатлон мечты
Сообщение12.10.2025, 08:05 
Аватара пользователя
EUgeneUS в сообщении #1705413 писал(а):
А что Вы называете "большим ифом"?

Потому и говорил, что надо тему читать. Вот, в самом начале 9-й страницы чуть укороченный большой иф:

Yadryara в сообщении #1549818 писал(а):
Я изменил некоторые настройки. В частности, обязательно проверяю обязательные числа:

Код:
if(
             !ispseudoprime((n+0)/v[1]) ||
      \\!       !ispseudoprime((n+1)/v[2]) ||
             !ispseudoprime((n+3)/v[4]) ||
             !ispseudoprime((n+5)/v[6]) ||
      \\!       !ispseudoprime((n+6)/v[7]) ||
             !ispseudoprime((n+7)/v[8]) ||
           !ispseudoprime((n+9)/v[10]) ||
      \\!   !ispseudoprime((n+10)/v[11]) ||
         !ispseudoprime((n+11)/v[12]) ||
      \\!   !ispseudoprime((n+12)/v[13]) ||
      \\!   !ispseudoprime((n+13)/v[14]) ||


Здесь не указана последняя позиция n+14.

 
 
 
 Re: Пентадекатлон мечты
Сообщение12.10.2025, 08:35 
Аватара пользователя
Yadryara в сообщении #1705415 писал(а):
Вот, в самом начале 9-й страницы чуть укороченный большой иф:

Понятно.

Однако, в обсуждениях с Дмитрием вот это
Код:
if(i%5!=4 && i%7!=3 && i%11!=3 && i%13!=6 && i%17!=11 && i%19!=15 && i%23!=17 && i%29!=1 && i%31!=18 && i%37!=19 && i%41!=21 && i%43!=22 && i%47!=3 && i%53!=23 && i%59!=27,

было названо "длинным if". И далее "большим ифом".

 
 
 
 Re: Пентадекатлон мечты
Сообщение12.10.2025, 08:48 
Аватара пользователя
Ну так вот именно что Дмитрий, используя слово "длинный" вместо "большой", пытался избежать путаницы. Если не нравится терапевтика или бэд, пишите тогда длинный, а не большой.

Понимаете как p1 автоматически вычислять для разных паттернов? Опять-таки, чтоб не запутаться предлагаю считать p1 так, чтобы значение этого остатка всегда было меньше модуля m.

 
 
 
 Re: Пентадекатлон мечты
Сообщение12.10.2025, 10:48 
VAL в сообщении #1703430 писал(а):
В отличие от предыдущего случая уверенности в требуемом результате нет. Но шанс есть.

(2 prime factors wanted)

Код:
33546...22657 (171 digits) = pq?
Проверяйте:

(Оффтоп)

NFS elapsed time = 991466.1178 seconds.
Total factoring time = 991466.5577 seconds


***factors found***
P58 = 4457348075198688736536891609724479123419815426237113698333
P113 = 75261571673884121247901189904670509301850905186441970307071820365756202423688774934231985476689286427616615987029

***factorization:***
335467021637015542203063713239394664830759606837240602304368187184044184636395585268811591514264236958244086767398370987467669170886552640776777766410907632680699346922657=4457348075198688736536891609724479123419815426237113698333*75261571673884121247901189904670509301850905186441970307071820365756202423688774934231985476689286427616615987029

 
 
 
 Re: Пентадекатлон мечты
Сообщение12.10.2025, 13:29 
Yadryara в сообщении #1705411 писал(а):
А то и 4/6*m и 5/6*m встречается. А другие невозможны?
Очевидно возможен любой из 6.
EUgeneUS в сообщении #1705413 писал(а):
Но не запустилось :roll:
Хм, похоже в сообщение вставил старый код, который потом поправил (добавил bad[] и его проверку вместо длинного if, а там и понадобился pr2[]), надо в export в строке перед parfor добавить и pr2: export(nth,th,v,i1,i2,pows,p1,m,vp,npr,t0,pr2,bad);.
Yadryara в сообщении #1705424 писал(а):
Ну так вот именно что Дмитрий, используя слово "длинный" вместо "большой", пытался избежать путаницы.
Нет, длинный он и есть длинный, про него и говорим сейчас, а про второй с 9-й страницы я давно забыл.
Yadryara в сообщении #1705424 писал(а):
Опять-таки, чтоб не запутаться предлагаю считать p1 так, чтобы значение этого остатка всегда было меньше модуля m.
Как бы ещё VAL в этом убедить ... Проще же лишние значения i учесть в i1,i2, а не в p1.

-- 12.10.2025, 13:56 --

Dmitriy40 в сообщении #1705498 писал(а):
Yadryara в сообщении #1705411 писал(а):
А то и 4/6*m и 5/6*m встречается. А другие невозможны?
Очевидно возможен любой из 6.
Расчёт подходящих значений (да, их может быть больше одного, смотря какой паттерн, примеры ниже):
Код:
\\   +0   +1   +2   +3   +4   +5   +6   +7   +8   +9   +10   +11   +12   +13   +14   +15   +16   +17   +18   +19   +20
v=[   54910,   529,   12,   1573,   2738,   75,   194936,   841,   18,   961,   20,   5043,   3698,   15463,   1056,   14045,   338,   153,   4,   361,   1470   ];
\\   p   pqrs   pqr   pqr   pqr   pqr   p   pqrs   pqr   pqrs   pqr   pqr   pqr   pqr   p   pqr   pqr   pqr   pqrs   pqrs   p

nd=48;\\Количество делителей
ip=0;\\Перебирать будем по месту +0

{vp=v[ip+1];
print("v=",v);
print("m= ",m=lcm(v)*6/vp);
p0=(lift((chinese([Mod(-j+1, v[j]) | j<-[1..#v]])))+ip)/vp;
for(d=0,5,
   p1=(p0+d/6*m)%m; x=p1*vp-ip; print1("d=",d,": ",y=[((x+j-1)/v[j])%6 | j<-[1..#v]]);
   if(#select(t->(t%2==0||t==3),y)==0, print(" OK, p1=",p1) , print);
);}
Примеры для разных паттернов:
Код:
v=[54910, 529, 12, 1573, 2738, 75, 194936, 841, 18, 961, 20, 5043, 3698, 15463, 1056, 14045, 338, 153, 4, 361, 1470]
m= 3231767500965347277306803383324509858720
d=0: [1, 5, 1, 1, 1, 5, 5, 5, 1, 1, 1, 1, 5, 5, 5, 5, 1, 3, 1, 5, 1]
d=1: [1, 5, 1, 1, 1, 5, 5, 5, 5, 1, 1, 1, 5, 5, 2, 5, 1, 1, 1, 5, 1]
d=2: [1, 5, 1, 1, 1, 5, 5, 5, 3, 1, 1, 1, 5, 5, 5, 5, 1, 5, 1, 5, 1]
d=3: [1, 5, 1, 1, 1, 5, 5, 5, 1, 1, 1, 1, 5, 5, 2, 5, 1, 3, 1, 5, 1]
d=4: [1, 5, 1, 1, 1, 5, 5, 5, 5, 1, 1, 1, 5, 5, 5, 5, 1, 1, 1, 5, 1] OK, p1=2585411135997416929526970922772099743927
d=5: [1, 5, 1, 1, 1, 5, 5, 5, 3, 1, 1, 1, 5, 5, 2, 5, 1, 5, 1, 5, 1]

v=[110050456444, 118587876497, 188286357654, 152587890625, 137438953472, 290667031221, 570623341222, 137858491849]
m= 1338375256605151451992612220415039155649246936761775172469391360000000000000000
d=0: [1, 1, 5, 1, 4, 1, 1, 5]
d=1: [1, 1, 3, 1, 1, 1, 1, 5]
d=2: [1, 1, 1, 1, 4, 1, 1, 5]
d=3: [1, 1, 5, 1, 1, 1, 1, 5] OK, p1=781307056480115170046422423379072803780506895787740190391322159238619287154913
d=4: [1, 1, 3, 1, 4, 1, 1, 5]
d=5: [1, 1, 1, 1, 1, 1, 1, 5] OK, p1=1227432142015165654043959830184085855663589208041665247881119279238619287154913

v=[119164, 4913, 4374, 15625, 1024, 1029, 2662, 28561]
m= 3362423200636572072000000
d=0: [1, 1, 5, 1, 5, 1, 1, 5] OK, p1=171428771240519412408673
d=1: [1, 1, 1, 1, 2, 1, 1, 5]
d=2: [1, 1, 3, 1, 5, 1, 1, 5]
d=3: [1, 1, 5, 1, 2, 1, 1, 5]
d=4: [1, 1, 1, 1, 5, 1, 1, 5] OK, p1=2413044238331567460408673
d=5: [1, 1, 3, 1, 2, 1, 1, 5]
Последние два - это тестовый паттерн [4*31^7,17^9,2*3^23,5^16,2^37,3*7^13,2*11^11,13^10] и он же с сокращенными степенями [4*31^3,17^3,2*3^7,5^6,2^10,3*7^3,2*11^3,13^4].
Разумеется p1 будет зависеть и от номера перебираемого места ip.

 
 
 
 Re: Пентадекатлон мечты
Сообщение12.10.2025, 14:36 
DemISdx в сообщении #1705458 писал(а):
VAL в сообщении #1703430 писал(а):
В отличие от предыдущего случая уверенности в требуемом результате нет. Но шанс есть.

(2 prime factors wanted)

Код:
33546...22657 (171 digits) = pq?
Проверяйте:
[..]
Свершилось!

$M(9720) \ge 8$

(Начало цепочки)

Код:
n = 58117033006612222511443428942026604846940828673460075010256156003804259003680299209346206868576956961731841584260646902946770765098538943517520932703078188222881213904854276262078508799999998
n + 2 =  2^14 × 5^8 × 107^2 × 109^2 × 199 × 4457348075198688736536891609724479123419815426237113698333 ×
75261571673884121247901189904670509301850905186441970307071820365756202423688774934231985476689286427616615987029
На момент запуска на счет числа 33546... найденная цепочка планировалась как рекордная. Но с $k=11664$ удалось разобраться значительно быстрее.

Зато то относительно небольшое число, которое я выкладывал на этой неделе, чревато неким рекордом. Ждем'c.

 
 
 
 Re: Пентадекатлон мечты
Сообщение12.10.2025, 16:19 
Yadryara
Интересно, Вы понимаете что задача поиска M48n21 до момента факторизации всех чисел кортежа в точности эквивалентна задаче поиска n19d252?
Потому что перебор в M48n21 идёт по i с запрещёнными остатками по модулю простых, которые однозначно пересчитываются в n, т.е. фактически перебираются n=n0+k*j с некоторыми n0=v[21]*p1-20 и k=v[21]*m и при этом n имеет ровно столько же запрещённых остатков по любому простому. Т.е. фактически можно считать что вместо M48n21 ищем n3d21 (ну или n4d21 для 4-х проверяемых мест), только запрещённые остатки считаются по другому, вот и всё. Соответственно можно применять методы ускорения от n19d252. В частности замену длинного if на цикл только по допустимым остаткам по произведению простых модулей (через КТО).

Конечно проверка мест $pq, pqr, pqrs$ сюда не укладывается и для чисел порядка 1e52 по паттерну M48n21p4 (с 4 проверяемыми местами) она улучшает фильтрацию вшестеро (из 40122 кандидата после длинного if-а оставляет 436 кандидатов без учёта в factor(,2^15) простоты оставшегося числа и до 106 при учёте (чего в ускорителях делать слишком муторно), против 2542 без проверки вообще), что конечно много, но какой ценой (в ускорителях) пока непонятно.

 
 
 
 Re: Пентадекатлон мечты
Сообщение12.10.2025, 17:13 
Аватара пользователя
Dmitriy40 в сообщении #1705551 писал(а):
Интересно, Вы понимаете что задача поиска M48n21 до момента факторизации всех чисел кортежа в точности эквивалентна задаче поиска n19d252?

Не уверен что в точности эквивалентна. Ну допустим, Вы правы. Но тогда тем более можно применить разбиение по чистоте?

 
 
 
 Re: Пентадекатлон мечты
Сообщение12.10.2025, 17:53 
Аватара пользователя
Dmitriy40 в сообщении #1705498 писал(а):
надо в export в строке перед parfor добавить и pr2: export(nth,th,v,i1,i2,pows,p1,m,vp,npr,t0,pr2,bad);.

Ещё попросило экспортировать $ip$, после чего запустилось. Спасибо!

-- 12.10.2025, 18:19 --

Интересный эффект, впрочем ожидаемый:

Если перебирать по простому, у которого самый большой множитель, это уменьшает $m$, что ведет к уменьшению $N$, а это повышает вероятность и уменьшает количество необходимых проверок.

Для паттерна
Код:
v=[54910, 529, 12, 1573, 2738, 75, 194936, 841, 18, 961, 20, 5043, 3698, 15463, 1056, 14045, 338, 153, 4, 361, 1470]


Если перебирать по простому в первом месте - это уменьшает количество проверок на 20-30% (в сравнении с перебором по последнему).
А если перебирать по 7 месту (+6), то ещё снижает. И проигрыш паттерну с 3 простыми уже не более чем в пять раз, а около 3.2 раза (во столько больше проверок нужно сделать).

-- 12.10.2025, 18:21 --

Но всё равно, паттерн с 4-мя простыми проигрывает, даже для условно бесплатной проверки на простоту.

-- 12.10.2025, 18:30 --

Можно ли сделать паттерны для $D(48,21)$ вида "3-0-13-5 (9)" и "4-0-12-5 (9)" такие, чтобы на месте с неизвестным простым стояло $19^2 \cdot 13 \cdot 11 \cdot 7 = 6865859$
?

Чтобы потом перебирать по этому простому. Это снизит сильно $m$, насколько понимаю.

-- 12.10.2025, 18:31 --

В общем, при прочих равных нужно снижать $m$, как только можно.

 
 
 
 Re: Пентадекатлон мечты
Сообщение12.10.2025, 18:50 
Yadryara в сообщении #1705581 писал(а):
Но тогда тем более можно применить разбиение по чистоте?
Например.

-- 12.10.2025, 18:53 --

EUgeneUS в сообщении #1705591 писал(а):
В общем, при прочих равных нужно снижать $m$, как только можно.
Тогда уж не только у перебираемого простого, но и на всех местах $p$.

 
 
 
 Re: Пентадекатлон мечты
Сообщение12.10.2025, 19:04 
Аватара пользователя
Dmitriy40 в сообщении #1705601 писал(а):
Тогда уж не только у перебираемого простого, но и на всех местах $p$.

не понял предложение :roll:

 
 
 
 Re: Пентадекатлон мечты
Сообщение12.10.2025, 19:37 
EUgeneUS
Максимизировать число в паттерне не только на перебираемом месте, но и на всех местах где осталось найти только одно простое, т.е. места $p$.

 
 
 
 Re: Пентадекатлон мечты
Сообщение12.10.2025, 19:46 
Аватара пользователя
Dmitriy40 в сообщении #1705616 писал(а):
Максимизировать число в паттерне не только на перебираемом месте, но и на всех местах где осталось найти только одно простое, т.е. места $p$.

а это снизит $m$?

Как понимаю, там:
Код:
m=lcm(v)*6/vp

То есть $m$ зависит от $vp$, а не от числа в паттерне для других простых...

-- 12.10.2025, 20:01 --

Чтобы перейти от вероятности найти цепочку $P(\text{win})=0.95$ к $P(\text{win})=0.99$ количество попыток (кандидатов) нужно увеличить в такое количество раз:
$\frac{\ln(0.01)}{\ln(0.05)} \approx 1.537$

Это выполняется всегда. Поэтому дальше буду оценивать только для $P(\text{win})=0.95$

 
 
 [ Сообщений: 3607 ]  На страницу Пред.  1 ... 236, 237, 238, 239, 240, 241  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group