2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 203, 204, 205, 206, 207, 208, 209 ... 215  След.
 
 Re: Пентадекатлон мечты
Сообщение20.01.2023, 19:32 
Аватара пользователя


29/04/13
7126
Богородский
EUgeneUS в сообщении #1578115 писал(а):
Насколько понимаю, речь о конкретном паттерне. В котором 11 и 13 в квадратах.

Да, тот самый, b1165. 7 и 11 в квадратах.

Yadryara в сообщении #1578041 писал(а):
Так вот, есть надежда, что таких комплектов из 3-4 куаров будет не шибко много и удастся быстро проверить все мультипустые паттерны.
Dmitriy40 в сообщении #1578117 писал(а):
Как-то она не очень оправдывается: для этого (b1165) паттерна с qr<60000 есть 584 варианта расстановки таких qr по 4-м пустым местам.

Так 584 это же мало! Тут ещё насчёт порога надо подумать. Я дальше 300 тысяч пока не заходил.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение20.01.2023, 22:11 


05/06/22
292
Ah, I was not quite accurate. For every prime $p$ other than 2, exactly half of the values coprime to $p$ will be residues; and we will want to skip semiprimes that divide one of our small primes, so the count of those needs a more complicated expression: $|qr \le n: 13 < q < r| = n \ln{\ln{n}} / \ln{n} - \sum_{p \le 13}{ (n/p) / (\ln{n/p}) }$. Of those, I would expect exactly one in $2^7$ to be valid with respect to the first 6 primes in any given position.

With those refinements, I get a break-even point of just over $10^7$ for $D(12,12)$ rising to just over $10^{11}$ for $D(12,15)$. In the latter case, that means $4 \cdot 10^9$ primes, and choosing 1/128 of $515 \cdot 10^9$ semiprimes.

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


20/08/14
11058
Россия, Москва
Yadryara в сообщении #1578125 писал(а):
Так 584 это же мало! Тут ещё насчёт порога надо подумать. Я дальше 300 тысяч пока не заходил.
Да не так уж и мало вроде ...
Но дело даже не в количестве (оно несколько уменьшится при учёте qr на местах с простыми), а в скорости роста, вот значения по этому паттерну для qr<10000,20000,30000,40000,50000,60000: 0,7,29,86,247,584. Смахивает на квадратичность ... А ведь qr<60000 это всего лишь -p1e11, что всё ещё слишком много.

EUgeneUS в сообщении #1578119 писал(а):
ИМХО. А дальше применять при расчете конкретных паттернов. А-ля, увеличить скорость "W-стадии". Нет?
Это я тоже сделал, ну почти, до стадии замера примерной скорости (сама проверка при этом не полная). Как раз в виде той своей идеи быстро на асме отфильтровывать те большие $p$, которые дают начальное число для паттерна выше 6e26. И скорость ну совсем не радует: если обратный элемент вычисляется со скоростью 25e6/с, то вычисление его для всех комбинаций LCM идёт лишь 1e6/c, а добавление проверок мест в паттернах по КТО (ещё недописано до конца) уже замедляет до 1e5/c. С такой скоростью ползти до 1e11 (с нуля) две недели (и скорее несколько больше, ведь надо ещё допроверку в PARI дописать). Правда радует что тут время проверки приблизительно линейно (для больших $p$, где-то от $\sqrt{10\cdot6\cdot10^{26}/LCM}$), ни от каких qr оно уже не зависит, а зависит лишь от LCM паттерна (как много простых дают начальное число меньше 6e26).

-- 20.01.2023, 23:08 --

За 7.2ч порог для -p уменьшил с 4.2e12 до 1.5e12, при этом нашлась лишь одна цепочка длиной 6 (остальные короче). И до 1e12 собирается работать ещё 6ч, но реально раза в два дольше (пока проверяются лишь треть qr, те что меньше 267).

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


20/08/14
11058
Россия, Москва
Yadryara
Объясните пожалуйста, вот в паттерне b1165 на 32p+6 минимально может быть qr=502 (без учёта qr на других местах), значит в эту позицию можно подставлять простые до $\sqrt{6\cdot10^{26}/502}=1.1\cdot10^{12}$, как минимальный qr=3131 на месте 32p-5 (ограничивающий p до 4.38e11) может помешать подставить 5e11<p<1e12 на место 32p+6? Ведь при этом на 32p-5 вполне может быть офигенно большой qr с очень маленьким $p^2$, разве нет? И тогда выходит что для ограничения сверху простого в квадрате для каждого паттерна имеет значение лишь наименьший qr для всех мест (502, а не 3131 и не 1411), а не некая их комбинация. Нет, если бы можно было перебрать все qr до $6\cdot10^{26}/17^2=2\cdot10^{24}$ (или все комбинации qr и $p^2$, вон Хуго прикинул сколько их может быть) вопросов не было бы, но это очевидно невозможно. И тогда непонятно зачем искать допустимые комбинации qr на разных местах. Можете это пояснить?

-- 21.01.2023, 04:27 --

Проверил, во всех 3408 паттернах на одном из мест существует qr<2967, так что никакой из них не получится проверять сразу ниже 4.5e11.

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


29/04/13
7126
Богородский
EUgeneUS в сообщении #1578119 писал(а):
О!
Эту идею можно распространить и на другие модули.
Например, проверять не по модулю $9$, а по модулю $27$.

Ента идея была высказана VAL ещё в самом начале темы, в феврале. Неслучайно же шаг уже тогда брался равным 6-кратному LCM:

Yadryara в сообщении #1549491 писал(а):
$$2^63^3\prod_{i=3}^{12}p_i^2=Step = ma$$

Видите, здесь уже 64 и 27 стоят особняком.

Может и Хьюго про то же самое говорил:

Huz в сообщении #1578097 писал(а):
already give a 6-fold improvement.)

Для 15-к это работает. Потому что понятно не только где стоит число кратное именно 18-ти, а ещё и где кратное именно 9-ти, так что и про 27 всё понятно.

Huz в сообщении #1578144 писал(а):
Of those, I would expect exactly one in $2^7$ to be valid with respect to the first 6 primes in any given position.

Ok. It's equals my results.

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

Dmitriy40 в сообщении #1578160 писал(а):
Ведь при этом на 32p-5 вполне может быть офигенно большой qr с очень маленьким $p^2$, разве нет?

Да, конечно. Позже отвечу подробнее.

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


29/04/13
7126
Богородский
Dmitriy40 в сообщении #1578160 писал(а):
И тогда непонятно зачем искать допустимые комбинации qr на разных местах. Можете это пояснить?

Вот мы расставили $qr$ на 4-х местах. Проверка такого паттерна займёт доли секунды. Так? И 584 расстановки тоже проверятся весьма быстро. Правильно?

По мере увеличения $qr$, их можно будет расставлять не на 4 места, а на 3 или даже на 2. Такие паттерны всё равно будут проверяться быстро.

Затем, с какого-то момента, нужно будет перейти от расстановки $qr$ к нашей обычной расстановке $p^2$(их будет уже намного меньше) или к каким-то ещё гибридным вариантам...

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


20/08/14
11058
Россия, Москва
Yadryara в сообщении #1578161 писал(а):
ля 15-к это работает. Потому что понятно не только где стоит число кратное именно 18-ти, а ещё и где кратное именно 9-ти, так что и про 27 всё понятно.
Нет, там это работает потому что в паттерне есть два числа кратные 9, потому точно известно где кратное 27. Для цепочек короче это уже не всегда так, потому вариантов для остатка по модулю 27 может быть и два - именно поэтому у меня компилятор паттернов не всегда может вытащить тройку из списка проверок и ускорить работу ускорителя вдвое.
EUgeneUS, кстати поэтому же и Ваш расчёт про модуль 27 не совсем корректен: при проверке по модулю 9 есть ровно один разрешённый остаток, т.е. проверка 1/9, для модуля 27 разрешённых остатков может быть и 1 (при двух девятках в паттерне) и 2 (при только одной) и проверка соответственно 1/27 или 2/27, в три или полтора раза быстрее. Это для линейного перебора, если перебирается простое под квадратом, то допустимых его остатков в разы (обычно вдвое) больше, например для qr=106 в одном из вариантов допустимы p%9=2,7 и p%27=7,11,16,20.

Yadryara
Я всё же не понимаю зачем вообще проверять такие паттерны: даже при расстановке всего двух qr>1e5 шаг паттерна становится гарантированно больше 6e26 и такой паттерн действительно можно проверить за микросекунды даже без Пелля. И что с того? Мы же искать такие qr будем на порядки дольше их проверки. И при расстановке больше одного qr мы этой проверкой никак не уменьшим порог перебора простых в квадрате, ради чего всё и измышлялось. Так зачем всё же искать и проверять эти 584 паттернов? А на самом деле гораздо больше чем 584, ведь 584 это всего лишь p>1e12, что ну очень много и таких решений с очень высокой вероятностью нет.
Другое дело если найти список qr для каждого места, объединить их и для каждого паттерна пытаться подставлять не любые вообще допустимые qr, а допустимые конкретно для него, но строго по одному qr и таким образом уменьшить ему порог -p. Но такой список довольно длинный (для больших qr, больше тысяч) и париться с ним для каждого из 3000 паттернов ... Не вижу здесь выигрыша перед проверкой просто всех вообще допустимых qr для любого паттерна. Хотя надо бы поточнее прикинуть ...

Dmitriy40 в сообщении #1578145 писал(а):
За 7.2ч порог для -p уменьшил с 4.2e12 до 1.5e12, при этом нашлась лишь одна цепочка длиной 6 (остальные короче). И до 1e12 собирается работать ещё 6ч, но реально раза в два дольше (пока проверяются лишь треть qr, те что меньше 267).
Уменьшение порога до 1e12 заняло 18.6ч, нашлись три цепочки длиной 7 и две длиной 6, остальные короче.

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


29/04/13
7126
Богородский
Dmitriy40 в сообщении #1578176 писал(а):
Нет, там это работает потому что в паттерне есть два числа кратные 9, потому точно известно где кратное 27.

А почему "нет"? Это же просто альтернативная формулировка. Или кому-то непонятно что число, которое делится на 18, делится и на 9 :-)

Кстати решил проверить 15-ки по тому же принципу. Из 488 бесквадратных паттернов:

120 с одним пустым местом;
300 — с двумя;
68 — с тремя.

Взял один из паттернов с тремя пустым местами и самым маленьким LCM=554954400.

Проверил сначала по модулю 18, затем по модулю 27. Результат идентичен: подходящим в среднем является каждое 121-е число.

Dmitriy40 в сообщении #1578176 писал(а):
Другое дело если найти список qr для каждого места, объединить их и для каждого паттерна пытаться подставлять не любые вообще допустимые qr, а допустимые конкретно для него, но строго по одному qr и таким образом уменьшить ему порог -p.

Да, я это уже сделал для 2-х паттернов. Правда списки пока крошечные, куары меньше 100 тысяч.

До куда их составлять? Я думаю, надо продолжить тестить тот же паттерн b1165.

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


11/12/16
13195
уездный город Н
Dmitriy40 в сообщении #1578176 писал(а):
EUgeneUS, кстати поэтому же и Ваш расчёт про модуль 27 не совсем корректен:


Да, я там чушь написал спросонья :roll: Но опять не понимаю, почему переход от модуля 32 к модулю 64 даёт выигрыш в 2 раза. :roll:

Вот примеры расчетов:
32. Для $p^2qr$ подходит только один остаток (определяется смещением места с $p^2qr$ относительно $32p$). У $p^2$ имеем четыре возможных нечётных остатка. У $qr$ - 16 возможных нечётных остатков. Итого коэффициент фильтрации - $\frac{1}{4}$

64. Для $p^2qr$ опять подходит только один остаток (определяется смещением места с $p^2qr$ относительно $32p$). У $p^2$ имеем восемь возможных нечётных остатка. У $qr$ - 32 возможных нечётных остатков. Итого коэффициент фильтрации опять - $\frac{1}{4}$

9. Для $p^2qr$ подходит только один остаток (определяется смещением места с $p^2qr$ относительно $18p$). У $p^2$ имеем четыре возможных остатка, ноль не подходит - итого три возможных остатка. У $qr$ - 6 возможных остатков, которые не делятся на 3. Итого коэффициент фильтрации - $\frac{3}{6} = \frac{1}{2}$

27. Для $p^2qr$ подходит уже два остатка ($9$ или $18$ плюс смещением места с $p^2qr$ относительно $18p$). Но это не имеет значения, так как запрещаются и разрешаются $qr$ с теми же самыми остатками. У $p^2$ имеем 11 возможных остатков, ноль и 9 не подходят - итого 9 возможных остатков. У $qr$ - $18$ возможных остатков, которые не делятся на 3. Итого коэффициент фильтрации опять $\frac{9}{18} = \frac{1}{2}$

-- 21.01.2023, 15:49 --

Если же речь не о фильтрации вариантов $qr$, а о фильтрации вариантов комбинаций $p^2 \times qr$, то

а) переход от модуля 32 к модулю 64 улучшает коэффициент фильтрации в 2 раза.
б) переход от модуля 9 к модулю 27 улучшает коэффициент фильтрации в 1.5 раза.

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


20/08/14
11058
Россия, Москва
EUgeneUS в сообщении #1578190 писал(а):
Но опять не понимаю, почему переход от модуля 32 к модулю 64 даёт выигрыш в 2 раза.
Выигрыш при линейном переборе получается потому что из 64-х последовательных чисел по модулю 32 будет два допустимых, а по модулю 64 только одно.
Для перебора под квадратом выигрыш тоже ровно вдвое:
Код:
? for(p=1,32, x=(106*p^2+6)%32;if(x==0, print1(p,", ")))
3, 5, 11, 13, 19, 21, 27, 29,
? for(p=1,64, x=(106*p^2+6)%64;if(x==32, print1(p,", ")))
5, 11, 21, 27, 37, 43, 53, 59,
? for(p=1,32, x=(129*p^2-1)%32;if(x==0, print1(p,", ")))
1, 15, 17, 31,
? for(p=1,64, x=(129*p^2-1)%64;if(x==32, print1(p,", ")))
15, 17, 47, 49,
? for(p=1,32, x=(551*p^2-7)%32;if(x==0, print1(p,", ")))
1, 15, 17, 31,
? for(p=1,64, x=(551*p^2-7)%64;if(x==32, print1(p,", ")))
1, 31, 33, 63,
Количество допустимых остатков то же, зато они приходятся на вдвое разный интервал.

Yadryara в сообщении #1578178 писал(а):
Правда списки пока крошечные, куары меньше 100 тысяч.
До куда их составлять? Я думаю, надо продолжить тестить тот же паттерн b1165.
А давайте их сравним? Вот мои (qr<15000 чтобы побыстрее считалось):
Код:
b1165:
#qr[-5]=7: [3131,5891,9731,9899,10931,12371,14099]
#qr[-3]=11: [3013,5893,6613,7453,8557,8797,8917,9253,10573,11413,12997]
#qr[+3]=11: [1411,3859,5371,5611,6931,7291,8299,8611,10411,11419,12499]
#qr[+5]=6: [1821,3189,4341,6861,7149,13701]
#qr[+6]=6: [502,838,1942,9862,10342,14038]
#qr[+7]=5: [2567,3503,5207,8903,9287]
Учитывая что среди них почти не встречается повторов в разных позициях, то их объединение будет суммарной длины 46шт qr.

-- 21.01.2023, 17:39 --

Некоторые паттерны имеют на местах с 5 весьма большой минимальный qr, например b94: #qr[-3]=2: [40445,43805]

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


29/04/13
7126
Богородский
Dmitriy40 в сообщении #1578197 писал(а):
А давайте их сравним? Вот мои (qr<15000

А вот мои ($qr<100\;000$):

(Оффтоп)

Код:
27-е место, 69 штук{[  10931, 19091, 37451, 47651, 60299, 84779, 9899, 16739, 19931, 51851, 57779, 92891, 14099, 20171, 36731, 56051, 18299, 53099, 77459, 94859, 3131, 60419, 66371, 9731, 58571, 81659, 35219, 52931, 69659, 5891, 26531, 42011, 46859, 79571, 51251, 35459, 73691, 51179, 15611, 63851, 98051, 34091, 83819, 25979, 35939, 95699, 12371, 54611, 30179, 20819, 65291, 99299, 40259, 74939, 58739, 26219, 37979, 38579, 86699, 85499, 91739, 84611, 94739, 71051, 98291, 60491, 78899, 72899, 99899  ]}

29-е место, 68 штук {[  6613, 32317, 49453, 54757, 57613, 71893, 85357, 89437, 8797, 9253, 20653, 27037, 40717, 82213, 3013, 25093, 41653, 45517, 67597, 74773, 86917, 94093, 7453, 34597, 41557, 53413, 83173, 98797, 8917, 15133, 28453, 12997, 56293, 95653, 8557, 44677, 83893, 47893, 68197, 76093, 72133, 43837, 18157, 93733, 5893, 16117, 30733, 51757, 17533, 49573, 10573, 52477, 11413, 21733, 58813, 33277, 76933, 62893, 63157, 52597, 97093, 44173, 90037, 60997, 44197, 77437, 62677, 66013  ]}

35-е место, 73 штуки {[  1411, 3859, 38131, 93619, 99331, 11419, 23731, 39691, 59299, 71611, 94411, 7291, 31579, 53659, 78499, 81811, 84571, 6931, 10411, 12499, 61219, 83491, 5611, 25699, 53971, 62899, 72571, 30451, 48211, 5371, 44731, 74251, 81139, 8299, 19651, 44419, 37459, 47611, 60019, 76939, 92731, 45739, 58459, 72451, 85171, 30739, 51979, 61891, 16531, 85339, 27619, 20659, 38179, 8611, 42739, 71131, 22339, 37291, 86419, 48379, 40891, 77179, 77851, 99691, 60691, 33499, 56851, 35011, 28891, 71779, 80371, 51811, 45571  ]}

39-е место, 68 штук {[  2567, 25007, 82127, 32927, 42047, 53903, 83543, 30383, 34247, 52463, 69023, 94967, 8903, 22823, 47183, 54143, 57623, 95903, 3503, 71207, 85343, 9287, 15503, 35927, 5207, 54407, 68183, 19823, 40463, 99287, 32807, 36623, 44663, 64487, 71567, 85727, 50447, 70943, 18023, 74303, 87167, 22223, 30743, 81863, 75263, 46847, 86663, 96143, 73247, 18527, 58103, 88367, 41303, 46247, 37343, 61367, 96647, 80303, 27263, 27383, 77423, 42167, 77927, 43847, 71063, 61823, 63143, 63383  ]}


Правда, пока не упорядочил по возрастанию.

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


20/08/14
11058
Россия, Москва
Совпадают, это хорошо.

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


20/08/14
11058
Россия, Москва
Проверил, в 3408 паттернах встречаются чуть больше трети от всех возможных 22<qr<60000 (которых 14307шт). Т.е. проверка каждого паттерна отдельно замедлит раз в 1200 (ну или 500 если учесть что разных списков примерно 1500 вместо 3400) по сравнению с проверкой просто $qr$ и $p^2$ ... :facepalm:

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


29/04/13
7126
Богородский
Dmitriy40 в сообщении #1578243 писал(а):
Т.е. проверка каждого паттерна отдельно замедлит раз в 1200 (ну или 500

Напомню, что я говорил в первую очередь именно о паттернах с самыми маленькими шагами. 554954400 — это 5-й LCM, 270 patterns.

Есть ещё

1-й LCM 7207200, 34 patterns;
2-й LCM 50450400, 114 patterns;
3-й LCM 79279200, 164 patterns;
4-й LCM 93693600, 124 patterns.

Этими паттернами тоже не стоит заниматься отдельно?


Dmitriy40 в сообщении #1577558 писал(а):
Макарова кажется почти все их уже проверила.

Теперь уже пишет, что все одноквадратные проверила. Отмечу пока так:

$\tikz[scale=.08]{
\fill[green!90!blue!50] (66,180) rectangle (155,210);
\fill[green!90!blue!50] (95,150) rectangle (125,180);
\fill[green!90!blue!50] (140,150) rectangle (155,180);
\draw  (66,210) rectangle  (80,220);
\draw  (80,210) rectangle  (95,220);
\draw  (95,210) rectangle  (110,220);
\draw  (110,210) rectangle  (125,220);
\draw  (125,210) rectangle  (140,220);
\draw  (140,210) rectangle  (155,220);
\draw  (66,200) rectangle  (80,210);
\draw  (80,200) rectangle  (95,210);
\draw  (95,200) rectangle  (110,210);
\draw  (110,200) rectangle  (125,210);
\draw  (125,200) rectangle  (140,210);
\draw  (140,200) rectangle  (155,210);
\draw  (66,190) rectangle  (80,200);
\draw  (80,190) rectangle  (95,200);
\draw  (95,190) rectangle  (110,200);
\draw  (110,190) rectangle  (125,200);
\draw  (125,190) rectangle  (140,200);
\draw  (140,190) rectangle  (155,200);
\draw  (66,180) rectangle  (80,190);
\draw  (80,180) rectangle  (95,190);
\draw  (95,180) rectangle  (110,190);
\draw  (110,180) rectangle  (125,190);
\draw  (125,180) rectangle  (140,190);
\draw  (140,180) rectangle  (155,190);
\draw  (66,170) rectangle  (80,180);
\draw  (80,170) rectangle  (95,180);
\draw  (95,170) rectangle  (110,180);
\draw  (110,170) rectangle  (125,180);
\draw  (125,170) rectangle  (140,180);
\draw  (140,170) rectangle  (155,180);
\draw  (66,160) rectangle  (80,170);
\draw  (80,160) rectangle  (95,170);
\draw  (95,160) rectangle  (110,170);
\draw  (110,160) rectangle  (125,170);
\draw  (125,160) rectangle  (140,170);
\draw  (140,160) rectangle  (155,170);
\draw  (66,150) rectangle  (80,160);
\draw  (80,150) rectangle  (95,160);
\draw  (95,150) rectangle  (110,160);
\draw  (110,150) rectangle  (125,160);
\draw  (125,150) rectangle  (140,160);
\draw  (140,150) rectangle  (155,160);
\node at (73,215){\text{D12}};
\node at (87.8,215){\text{Osn}};
\node at (103,215){\text{Sq=1}};
\node at (118,215){\text{Sq>1}};
\node at (133,215){\text{Total}};
\node at (148,215){\text{Done}};
\node at (73,205){\text{10}};
\node at (88,205){\text{78}};
\node at (103,205){\text{8}};
\node at (118,205){\text{17}};
\node at (133,205){\text{103}};
\node at (148,205){\text{103}};
\node at (73,195){\text{11}};
\node at (88,195){\text{1044}};
\node at (103,195){\text{67}};
\node at (118,195){\text{52}};
\node at (133,195){\text{1163}};
\node at (148,195){\text{1163}};
\node at (73,185){\text{12}};
\node at (88,185){\text{504}};
\node at (103,185){\text{38}};
\node at (118,185){\text{36}};
\node at (133,185){\text{578}};
\node at (148,185){\text{578}};
\node at (73,175){\text{13}};
\node at (88,175){\text{3408}};
\node at (103,175){\text{202}};
\node at (118,175){\text{94}};
\node at (133,175){\text{3704}};
\node at (148,175){\text{642}};
\node at (73,165){\text{14}};
\node at (88,165){\text{1044}};
\node at (103,165){\text{46}};
\node at (118,165){\text{26}};
\node at (133,165){\text{1116}};
\node at (148,165){\text{72}};
\node at (73,155){\text{15}};
\node at (88,155){\text{488}};
\node at (103,155){\text{23}};
\node at (118,155){\text{17}};
\node at (133,155){\text{528}};
\node at (148,155){\text{40}};
}$

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


20/08/14
11058
Россия, Москва
Dmitriy40 в сообщении #1578176 писал(а):
Уменьшение порога до 1e12 заняло 18.6ч, нашлись три цепочки длиной 7 и две длиной 6, остальные короче.
Тут я немного лажанулся и проверял примерно втрое больше вариантов простых чем необходимо, после исправления тот же результат достигнут за 7.4ч.
Запустил уменьшение порога до 5e11, в начале оценка 6ч, но реально думаю до суток будет.

Отдельно довёл до ума проверку по методу превышения начального числа в паттернах, запустил для уменьшения порога с 1e11 для паттернов с LCM=15850052618400, скорость примерно 400с/1e9, оценка требуемого времени 12ч, но подозреваю ниже 1e9 начнёт подтормаживаться так как будет достаточно много простых давать начальное число меньше 6e26 (пока около 1e11 их суммарно для всех этих паттернов в среднем порядка одного на 1e6, именно в этом и смысл такой фильтрации).
К сожалению этот метод неприменим к паттернам с малыми LCM, там почти каждое простое (меньше 1e10) будет давать начальное число меньше 6e26, т.е. фильтрация практически исчезнет.
Впрочем, если добавить прямо в асм проверку по модулям, то может какой-то эффект и останется, надо прикинуть.

Yadryara в сообщении #1578260 писал(а):
Этими паттернами тоже не стоит заниматься отдельно?
Ну смотрите, с LCM=7207200 все 34 списка 22<qr<60000 различны, их длина от 309 до 442, т.е. грубо каждый паттерн будет проверяться в 5200/309=17...5200/442=12 раз быстрее (5200 это примерно сколько разных qr из 14307шт реально встретились в одном общем для всех вообще паттернов списке), для всех 34-х будет в среднем в 14 раз быстрее, но все 34 уже вдвое медленнее Тем более что 34 паттерна по спискам ровно в 34 раза короче будут проверяться дольше чем один общий список (хотя бы потому что генерацию простых надо будет делать 34 раза вместо одного).
Для LCM=50450400 тоже все 114 списка 22<qr<60000 различны, длиной от 167 до 349, в среднем будут проверяться каждый раз в 20 быстрее, т.е. суммарно все 114 уже впятеро медленнее общей проверки ...
Где профит-то? :-(

Yadryara в сообщении #1578260 писал(а):
Теперь уже пишет, что все одноквадратные проверила. Отмечу пока так:
А Вы сверили что все проверки она делала без ключей -p и -W? Это важно.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3216 ]  На страницу Пред.  1 ... 203, 204, 205, 206, 207, 208, 209 ... 215  След.

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



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

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


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

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