Симметричные кортежи из последовательных простых чисел

[Yadryara]

Yadryara в сообщении #1661397 писал(а):

Конечно группы, где такое крошечное количество чужих чисел (4, 5, 6, ... , 15), да ещё и проверенные по всем модулям до 71, жутко перспективные в плане поиска 19\19.

Ну про окончание на 15-й группе, это я навскидку сказал. А теперь попытался экстраполировать. У меня получились такие доли от общего количества, то есть от $15\, 257\, 671\, 388\, 312\, 371\, 200$ кандидатов.

71#   Sum(G0..G15)  Sum(G0..G16)   Sum(G0..G17)
              1.7%          5.2%          12.9%

Лично я пока верю что наша 19-ка найдётся не позднее чем будет проверена 16-я группа.

Программа:

(PARI)

{print();
t0=getwalltime();
v = vector(67,i,[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]);

v[19]=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 8, 44, 70, 118, 78, 48, 16];\\, sum=384
v[23]=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 40, 146, 348, 584, 608, 392, 134, 36, 6];
v[29]=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 24, 230, 838, 2338, 4714, 6666, 6444, 4068, 1754, 456, 106, 10];
v[31]=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 24, 488, 2932, 11536, 30144, 56382, 76846, 74250, 48694, 21812, 6850, 1578, 230, 10];
v[37]=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 98, 1006, 9158, 51810, 195582, 520066, 1011204, 1438786, 1476074, 1086646, 566290, 210120, 56684, 10712, 1230, 50];
v[41]=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 102, 1814, 19784, 166006, 947414, 3653662, 10108734, 20713944, 31541838, 35384680, 29035512, 17298152, 7439094, 2319814, 528748, 84560, 8294, 324];
v[43]=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 118, 2578, 36174, 371608, 2856156, 15702392, 62086738, 180749476, 395325934, 654302846, 815927422, 761493746, 527859342, 269672194, 101106766, 27941146, 5714732, 832744, 74658, 2748];
v[47]=[0, 0, 0, 0, 0, 0, 0, 0, 0, 24, 1406, 34278, 520308, 5590512, 44192112, 255924622, 1087592188, 3438714568, 8217471808, 14998221970, 20942301992, 22275622040, 17925228472, 10827430718, 4874885124, 1630911948, 406659102, 75530368, 9994728, 810792, 27480];
v[53]=[0, 0, 0, 0, 0, 0, 0, 0, 178, 16902, 460544, 7121330, 78869428, 657860428, 4116175026, 19280190180, 68067144514, 183171836012, 379227347730, 605935215088, 745332928752, 702113842442, 503399988380, 272878823040, 111161557082, 33924337564, 7758154760, 1318925414, 158040254, 11479392, 348600];
v[59]=[0, 0, 0, 0, 0, 0, 0, 2342, 169500, 4949320, 86498046, 1072162912, 9922991574, 69015165402, 361555473588, 1436573713066, 4372104902192, 10287665248786, 18821195521110, 26789470532208, 29566950432394, 25162208168768, 16402877618224, 8134573376362, 3050946438594, 862382999288, 183204299616, 28827888442, 3171808930, 210338416, 5822520];
v[61]=[0, 0, 0, 0, 0, 0, 12100, 1162530, 43545580, 938309020, 13701704430, 145057883078, 1140235233920, 6730737725168, 30146142503066, 103563762588810, 275651199964114, 572695946364630, 932086506180384, 1187990207594756, 1181845637240896, 912977750382936, 544254528859674, 248727163776468, 86638382762746, 22910146137790, 4577709549962, 678625326646, 70209898488, 4365719848, 113480160];
v[67]=[0, 0, 0, 0, 0, 54760, 6792018, 325858198, 8732689082, 153606059908, 1913747177340, 17483063702860, 119249071095310, 615440511892708, 2432725989818718, 7447022885574328, 17813512167763926, 33491264807265158, 49603797522180000, 57819061781785358, 52856050981018074, 37699907542234036, 20848732917709526, 8879811423403526, 2895245491002764, 719253136438230, 135295969437234, 18878969508802, 1836531247768, 107619357728, 2666478240];

for(i=8,19,
do1=round(vecsum(v[prime(i)][1..35-i])/vecsum(v[prime(i)])*1000);
do2=round(vecsum(v[prime(i)][1..36-i])/vecsum(v[prime(i)])*1000);
do3=round(vecsum(v[prime(i)][1..37-i])/vecsum(v[prime(i)])*1000);

print();
print(prime(i),"#   G",35-i,"   G",36-i,"   G",37-i);
print("tys   ",do1,"   ",do2,"   ",do3);

);

print();
print(strtime(getwalltime()-t0));
print();
}

Выдача:

19#   G27   G28   G29
tys   323   630   833

23#   G26   G27   G28
tys   490   753   924

29#   G25   G26   G27
tys   536   769   916

31#   G24   G25   G26
tys   538   761   908

37#   G23   G24   G25
tys   486   709   873

41#   G22   G23   G24
tys   422   644   826

43#   G21   G22   G23
tys   343   557   756

47#   G20   G21   G22
tys   262   458   666

53#   G19   G20   G21
tys   180   346   551

59#   G18   G19   G20
tys   114   243   427

61#   G17   G18   G19
tys   68   162   314

67#   G16   G17   G18
tys   36   97   211

Переход к 71#:

19#   323   630   833
23#   490   753   924
29#   536   769   916
31#   538   761   908
37#   486   709   873     1.11   1.07   1.04
41#   422   644   826     1.15   1.10   1.06      4     3     2
43#   343   557   756     1.23   1.16   1.09      8     6     3
47#   262   458   666     1.31   1.22   1.14      8     6     5
53#   180   346   551     1.46   1.32   1.21     15    10     7
59#   114   243   427     1.58   1.42   1.29     12    10     8
61#    68   162   314     1.68   1.50   1.36     10     8     7
67#    36    97   211     1.89   1.67   1.49     21    17    13

71#    17    52   129     2.12   1.87   1.64     23    20    15
71#   G15   G16   G17

[Dmitriy40]

Yadryara в сообщении #1661397 писал(а):

Я понимаю, что хитрый, но не, я не парился пока. Я просто остановил ту прогу, что привёл, когда она перевалила через 8 миллионов.

Тогда у Вас остатки по старшим простым были всегда первые допустимые. Не знаю, но как-то не слишком хорошо. Лучше было бы сделать перебор какого-то количества младших простых, скажем до сотни тысяч итераций, а старшие каждый раз выбирать случайно из допустимых. А можно и все выбирать случайно (ага, из двух возможных для малых простых). Всё же при случайном выборе меньше вероятность артефактов.

Yadryara в сообщении #1661397 писал(а):

В августе я спрашивал и о проверке всего диапазона $0-71\#$, то есть о поиске vc[]. И самый оптимистичный срок был назван Вами — 25 дней.

Логично, если 67# считался 37ч, а растёт в 15-17 раз на каждое простое. Надо было переписывать асм программу чтобы она или сама использовала Map(), или подхватывала из PARI число из Map() и лишь продолжала счёт по большим простым. Но смысла в этом я не видел. Да и сейчас не вижу. Пока не придуман механизм перебора именно юнитов из 71#, а не из 71#/13...31 (а его не придумать чтобы считался с разумной скоростью).

Yadryara в сообщении #1661397 писал(а):

Я уже не помню точно алгоритмы, но вроде бы самые чистые группы можно посчитать гораздо быстрей, совершенно необязательно считать все.

Нет, это про самые грязные. Самые чистые зависят от множества групп уровнем выше (по меньшим простым), а в них чудовищное количество юнитов и хранить их негде, а вычислять долго.
Например, G4@71# зависит от G4...6@67#, G6@67# (6792018шт) зависит от G6...8@61#, G8@61# (43545580шт) зависит от G8...10@59#, G10@59# (86498046шт) зависит от G10..12@53#, G12@53@ (78869428шт) зависит от G12...G14@47 (и так далее до 43#, для 41# и менее зависимость будет уже от 4-х групп меньшего простого), которые тоже уже меньше, только поэтому и получилось на PARI посчитать G4@71#, что в процессе количество всех юнитов на каждом уровне было не слишком большим (порядка сотни миллионов) и влезли в память (с огромным трудом). Попытка точного вычисления G5@71# приведёт к смещению всех зависимых групп на одну вправо, а это на порядок больше юнитов в каждой, миллиард же юнитов на PARI в память точно не влезет. Конечно этот процесс можно разбить на части и оптимизировать (и на асм переписать), но это время, без особой практической пользы.

Yadryara в сообщении #1661397 писал(а):

Да и 5(?) самых чистых групп и 7 самых грязных уже посчитаны.

Грязных да, чистых нет. Причина абзацем выше.

Yadryara в сообщении #1661397 писал(а):

Может надо не просто находить количество vc[], то есть юнитов, но и сразу же на лету проверять их по простым больше 71 ...

Можно, но это же вычисление КТО, что не быстро. Или куча таблиц. И есть подозрение что при оптимизации в итоге приду к уже работающему коду, ведь он и сейчас перебирает только более чистые группы от выданной (и её саму). Но в силу второго абзаца выше - не полностью каждую группу, лишь те юниты, что получаются очищением конкретного переданного юнита из указанной группы.
Я пожалуй даже могу прикинуть скорость если отказаться от оптимизации и перебирать юниты в 71# по одному. Скорость будет почти равна скорости проверки по простым 128-256 сейчас, а она для разбиения 71#/13...31 составила 150e6/с, при том что запуская эту проверку после первой (проверки по простым 73-128) в 10 раз реже скорость двух проверок 600e6/с. Реально скорость будет ещё ниже, сейчас же там не вычисляется номер группы. Простите, но на замедление в 4 и более раз ради непонятно какого выигрыша от проверок как можно более чистых групп я не готов. Тем более что 47#/13...31 и так уже практически работает (не хватает лишь оболочки на PARI).

Yadryara в сообщении #1661397 писал(а):

Вот про это:

А, я просто не понял, ведь до этого её кажется нигде не показывал, а Вы всё равно её взяли. Ладно, не суть, хоть понятно про что именно говорите.
Но тогда я не понимаю в каком именно смысле 71#/13...31 с 7.36e14 юнитами "гораздо лучше" разбиения 47#/13...31 с 5.16e16 юнитами. Покрывает большую долю юнитов в самых чистых группах 71#? Насколько большую? На 3% или в 7 раз? Может невнимательно посмотрел и Вы это уже показали?

[Yadryara]

Dmitriy40 в сообщении #1661434 писал(а):

Но тогда я не понимаю в каком именно смысле 71#/13...31 с 7.36e14 юнитами "гораздо лучше" разбиения 47#/13...31 с 5.16e16 юнитами.

Только в том, что чистые группы стартуют с 20 чужих чисел, а не с 25. Но vc-шки-то вообще стартуют с 4-х.

Я уже подзабыл как vc-шки считаются. Если они считаются точно медленнее в 4 раза, то да, непонятно какой выигрыш, ведь в самых чистых группах очень мало чисел, трилионные и миллиардные доли от всех.

Так Вы к какому разбиению склоняетесь?

Dmitriy40 в сообщении #1661434 писал(а):

Лучше было бы сделать перебор какого-то количества младших простых, скажем до сотни тысяч итераций, а старшие каждый раз выбирать случайно из допустимых. А можно и все выбирать случайно (ага, из двух возможных для малых простых). Всё же при случайном выборе меньше вероятность артефактов.

А это сейчас актуально? Нужно ли вообще выяснять эти доли, если разбиение будет другим?

[Dmitriy40]

Yadryara в сообщении #1661440 писал(а):

А это сейчас актуально? Нужно ли вообще выяснять эти доли, если разбиение будет другим?

Так в этом и вопрос, стоит ли его делать другим или таким, если скорости будут отличаться в разы. Но вдруг вероятность нахождения тоже сильно в разы выше будет, тогда плевать на скорость ... Правда непонятно как программу переписывать, но если на скорость совсем наплевать, то в общем можно ... Вопрос где та граница где уже плевать (или ещё не плевать).

Yadryara в сообщении #1661440 писал(а):

Так Вы к какому разбиению склоняетесь?

Чёткого плана действий у меня нет. Если Демис быстро всё насчитает и пора будет запускать 71#, то остановлюсь на 47#/11...31 как уже готовом и не требующем правки асм кода (по крайней мере в плане порядка перебора, так то кое-что хочу подправить), плюс в gp файле сделаю более удобный перезапуск и объединение логов. Если же время будет, то думаю как можно уменьшить загрязнение перебираемых групп (увеличить простое в разбиении), и тогда вон в принципе понятно как можно перебирать 59#/13...31, хотя особого преимущества не вижу, что от G23@59#/13...31 к G4...23@71# спускаться, что от G27@47#/13...31 к G4...27@71#. Вот если и правда будет большая разница в покрытии групп @71#, то да, лучше программу заметно переписать.

Yadryara в сообщении #1661440 писал(а):

Я уже подзабыл как vc-шки считаются. Если они считаются точно медленнее в 4 раза,

vc[] считается на порядки быстрее вычисления номеров всех юнитов 71# (или 67#, не суть). Потому что на каждом простом (ну скажем после 23) немало юнитов не уменьшают номер группы (не меняют список оставшихся простых в паттерне) и соответственно на всех больших простых они считаются только один раз, а не сколько их было на каждом простом. Соответственно их номера при этом теряются. Только это и позволило посчитать весь vc[] для 67# за полтора дня, разумеется перебрать 3e17 юнитов за столь малое время невозможно.

[Dmitriy40]

Dmitriy40 в сообщении #1661196 писал(а):

Yadryara в сообщении #1661194 писал(а):

Уж не клоните ли Вы к тому, что вероятность успеха будет увеличиваться с каждым неудачным броском?

А это не очевидно? Обоснование:
Пусть абсолютно точно есть ровно один кортеж 19-252 (или любой другой, даже не обязательно из простых чисел, вообще какой угодно) до $10^{1000}$. Тогда тыкая в случайное число и если не попали, выкидывая его, будем уменьшать количество оставшихся непроверенными чисел, т.е. увеличивать вероятность тыкнуть в решение (как 1/M, где M - сколько чисел осталось, для последнего вероятность станет равна 1).
Мы же проверив вариант выкидываем его из оставшейся части проверки.

Забавно что мат.ожидание при этом наоборот падает, вот для интервала начиная с 1e9 (считаем ниже кортежей нет):
$67\#: 0.5111988876929923316538381625 \pm 0.7149817394122680191163511625$
$71\#: 10.96988070724654071679861094 \pm 3.312081023653639533167194857$
А вот для интервала начиная с 1.7e24 (докуда было тотально проверено старой программой):
$67\#: 0.3381044484268848041959258385 \pm 0.5814674955892932835812774267$
$71\#: 10.79678626778375803674839221 \pm 3.285846354865631576636873462$
И оценка вероятности по стандартному отклонению для 67# тут вдвое ниже, 13% вместо 25%.

Причина понятна: уменьшается (оставшийся) интервал.
И это не противоречит возрастанию вероятности обнаружить любой из $W$ точно присутствующих кортежей (специально процитировал больше) $P=\frac{W}{M}$ каждой следующей проверкой (а не $n$ проверок!) при уменьшении оставшегося интервала $M$ (до $W$) потому что вероятность и мат.ожидание вещи сугубо разные. Такие дела ...

-- 15.11.2024, 08:28 --

Вероятность $n \le M_0-W$ ($M_0$ - начальное значение $M$) неудачных попыток подряд составит по идее $P=\prod\limits_{i=0}^{n-1} (1-\frac{W}{M_0-i})$, что при $\max(n,W) \ll M_0$ можно аппроксимировать выражением $P=(1-\frac{W}{M_0})^n$. Как здесь поменять местами $n$ и $W$, чтобы получить ту самую формулу $1-(1-\frac{n}{M_0})^W$, я не знаю.

[Dmitriy40]

Yadryara
Про скорость vc[] я наверное не совсем понял что Вы спросили.
Сам vc[] вычислить можно относительно быстро, 71# за ~25 дней (в 64 потока!), потому что там лишь количества юнитов, но не их уникальные номера и за счёт этого ускоряется перебор больших простых (скажем от 31 и больше).
А вот для проверки юнитов нужны их номера, которые вычислять намного дольше. Даже грубая прикидка говорит что скорость перебора номеров юнитов не может быть выше 1e9/с на поток и значит только перебрать все номера юнитов займёт 1.53e19/1e9/86400/365=500 лет в одном потоке. А скорость проверки юнитов без вычисления их номеров (после оптимизации они уже не нужны) если проверять по одному вместо пакетом 32шт как сейчас и будет примерно вчетверо меньше текущей (150e6/с вместо 600e6/с на поток). В каком порядке при этом они будут перебираться - зависит от разбиения и метода его довычисления до 71# в программе. Если метод будет долгим, как с фильтрацией только подходящих под указанную группу и указанную её часть (для деления работы на куски), то и скорость снизится ещё.
Т.е. падение скорости вчетверо происходит не из-за перехода к вычислению юнитов по vc[] как похоже Вы предполагаете, а из-за вычисления юнитов по одному вместо одновременно пакетами по 32шт всех 11520 (или 20736 для 71#/13...31) для какого-то списка простых, при этом они скорее всего из очень разных групп (но не грязнее переданной программе для обработки). Объединить же юниты в пакет (хоть х32, хоть 11520/20736) только из одной группы не представляется возможным. Так что или быстрая пакетная обработка, или попытка обрабатывать только из одной группы с возможными дополнительными тормозами от метода довычисления номера группы юнита от переданной до 71#.

[Yadryara]

Dmitriy40, а разве не будет быстрее вычислить только vc[] до 16-й, это же всего 5% от всех? Остальные группы скорее всего не понадобятся.

[Dmitriy40]

Может и будет. Только как это сделать - вопрос.
G16@71# зависит от G16...18@67#, те от G16...20@61#, те от G16...22@59#, те от G16...24@53#, в которых суммарно уже 3.57e12 юнитов и все их надо где-то держать. Ну или запускать перебор ещё раньше. например с 37# с 6.6млн юнитов, ведь зависимость расширится до G16...30@41#, а это фактически все.
Т.е. надо для всех 159e6 юнитов 41# (или 6.6млн 37#) перебрать все возможные остатки по 43-71 (41-71), вычислить номер группы, если он 16 и меньше - отдать на проверку. Скорость проверки будем считать знаем, 150e6/с (все скорости буду указывать на мой образцовый один поток основного компа). Вычисление номера группы займёт такта 3-4, меньше ну никак, и так уже с оптимизацией по таблицам, это 1e9/с. Но в проверку будет уходить как сами говорите лишь 5% вычисленных номеров, т.е. примерно со скоростью 50e6/с (может чуть выше если группа оказалась слишком грязной и можно не продолжать перебирать большие простые, но тут мне кажется выигрыш не слишком велик). Т.е. вычисления займут 6мкс на проверку юнита и 20мкс на поиск подходящего юнита среди всех, это скорость 40e6/c. Уже в 15 раз медленнее текущей скорости. И основные тормоза в поиске юнитов из групп G4...16@71#, а не только в их вчетверо медленнее проверке.
Да, если будет перебираться лишь 5%, то небольшой выигрыш похоже есть. А если 7%? Уже нету. А если только группы G4...G13@71#, с 1% (навскидку) общего объёма? Уходить в проверку станут лишь 1% номеров и скорость поиска подходящего юнита упадёт до 10e6/c, в 60 раз медленнее. А если я ошибся в оценках и насколько ускорить вычисление номера группы не получится? Тоже вах. А если в 71# не 11 кортежей, а 7 или 4? Ведь вероятность этого приличная, далеко не 1%.
Слишком всё на грани. И слишком много накладных расходов (на поиск юнита из желаемых групп). Не нравится мне так.
Единственный плюс что если не найдём, то можно будет запустить дальше, более грязные группы, без дублирования уже проверенного, это да.
В принципе надо тесты писать, как быстро можно на асме получать номер группы для юнитов, затык в этом. Либо думать как из номера юнита группы Gx@37# попроще получать номер группы Gy@71# чтобы та фильтрация до 5% занимала сильно меньше 1/0.05=20 времени.

Но не запустить ли просто кусками с шагом скажем 1e25, ведь для меньших кусков мат.ожидание выше:
1e25: 0.6067726990662829723774131154 +- 0.7789561599129202421159010354
2e25: 0.3879249085969080003677955488 +- 0.6228361811880456261840342971
3e25: 0.3347196833913003866352469416 +- 0.5785496377937682078306960124
4e25: 0.3044434764733548726998443699 +- 0.5517639680817830212982993492
5e25: 0.2838287359745312384904967898 +- 0.5327557939380211362719180218
...
54e25: 0.1446770104602508437249629599 +- 0.3803643128110875279317740968
55e25: 0.1439625223575401657308063131 +- 0.3794239348769923946886423148
56e25: 0.1432646315572382378011228257 +- 0.3785031460334751798866188669
Это не с нуля, а для куска длиной 1e25 до указанного числа.
Смотрите, практически тот же выигрыш 2-3 раза что и от более чистых групп, зато гораздо проще перебор и практически без накладных расходов, все вычислительные ресурсы в деле (проверки кандидатов).

[Yadryara]

Dmitriy40 в сообщении #1661497 писал(а):

Смотрите, практически тот же выигрыш 2-3 раза что и от более чистых групп, зато гораздо проще перебор и практически без накладных расходов, все вычислительные ресурсы в деле (проверки кандидатов).

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

Если нет, тогда минусом этого способа я вижу именно скукоту. Обсуждать кто сколько посчитал и что нашёл, зная, что на следующем отрезке найдётся в среднем меньше.

А вот если идти от очень чистых крошечных групп, то там прям интересно: и длина будет возрастать от группы к группе и количество находок. А вот качество находок будет снижаться, но именно в среднем. Зато количество проверяемых кандидатов будет расти и это делает фаворитами 16-ю и 17-ю группы.

[Dmitriy40]

Yadryara в сообщении #1661502 писал(а):

Если Вы придумали как самих кандидатов перебирать по возрастанию, то это здорово конечно.

Нет, не в порядке возрастания, а сделав ограничение по величине чисел в заданном диапазоне (не слишком маленьком, больше нескольких процентов от полного).

Внутренний цикл проверяет числа (юниты) вида Z=x+Mx*(((y[]-x)*d)%My), при этом для 71# размер #y[]=20736 (сейчас 11520 для 67#). Эта формула вычисляется в виде Z=if(A[j]<B,x1,x2)+Mx*A[j] и здесь уже A[]=(y[]*d)%My перебирается в порядке возрастания. Соответственно цикл фактически перебирает числа по возрастанию в двух диапазонах, A[j]<B и A[j]>=B. Поэтому при ограничении с гранулярностью Mx (а это порядка 1e19) несложно перед запуском цикла быстро найти те куски A[], которые точно влезают в желаемый диапазон Z. Да, это можно делать и для каждого юнита, но можно и до запуска цикла, где это можно сделать не за 11520 (20736) проверок (по одной на юнит), а всего лишь за 15*2=30 (двоичным поиском в массиве), на те же 11-20 тысяч юнитов сразу, т.е. накладные расходы порядка 0.3%. Из-за уменьшения длины обработки будет расти доля других накладных расходов и потому скорость будет ниже, вопрос насколько. Попытка сделать пропуск 22% от 67# (посчитанных старой программой) в текущей программе привела к ускорению счёта на 14%, писал выше. Не к замедлению, а всё же к ускорению, пусть и не на 22%. И это было сделано без двоичного поиска, одной проверкой на каждые 32 юнита (т.е. имеет некий резерв ускорения, но разница 22%-14% не стоила трудов). Пропуск 95%-99% конечно замедлит намного сильнее, но тут есть с чем поиграться.

В августе сделал перебор в порядке загрязнения групп 29#/17 только потому что все изменения свелись лишь к другому перебору юнитов в PARI, 13824 по группам (раньше было 80640 юнитов, по простым 59...67), при этом их вычислил один раз и сохранил в n19d252.nums, т.е. при работе ничего лишнего не делалось и асм код менять не пришлось. Сейчас такой фокус могу провернуть с 47#/13...31, уже не 13824 юнитов, а 5.16млн (80М файл ещё терпимо). Но группы чище не станут, были G21...33, будут G25...37. В общем можно и ещё больше юнитов сделать, до 7e9 с разбиением 59#/13...31 и группами G21...37, часть перебора 43...59 в PARI сделать, но дальше тогда время запуска программы падает до неприемлемых величин в единицы секунд из-за чего доля накладных расходов на старт программы слишком растёт, плюс чаще будет происходить запись на диск (а RAM диск есть не у всех) что тоже не полезно (тем более SSD). Пока 5.16млн юнитов в группах G25...37 выглядит разумным компромиссом и главное почти готовым к запуску - желаемые доработки PARI кода не касаются разбиения и перебора, только объединения логов (на 5млн файлов я не согласен!) и удобства перезапуска, но это пару дней посидеть и сделать.

Вы же предлагаете существенно замедлить вычисления ради перебора лишь нескольких процентов всего объёма, но самых чистых групп. Если вероятность найти там кортеж высока и выигрыш времени заметно положителен (не проигрыш и не 0.1%), да, хорошо бы сделать. Но пока прикидки не показывают существенного выигрыша во всех ситуациях, только в самых оптимистичных. А это извините сомнительно и опираться на такие предположения ... не слишком хочется.
Если придумается как достаточно выигрышно считать не только оптимистичный сценарий, но и более-менее пессимистичные - да я с радостью. В августе же сменил обход, с пересчётом 6% готовых данных, но сказали лучше от чистых и получилось быстро сделать - сделал ведь.

[Yadryara]

Dmitriy40 в сообщении #1661526 писал(а):

Вы же предлагаете существенно замедлить вычисления ради перебора лишь нескольких процентов всего объёма, но самых чистых групп.

Да не предлагаю я существенно замедлить вычисления! Ну не получается сделать быстро обсчёт с самых чистых, значит будем считать быстро, но скучнее.

[Dmitriy40]

Если получится быстро - я только за! Но пока по прикидкам получается слишком медленно. И выигрыш если и есть, то зависит от плохо доказуемых предположений (вероятности, мат.ожидание, преимущество чистых). Это не нравится.
Но подумать не отказываюсь, вдруг получится сделать.

-- 15.11.2024, 18:45 --

Вот кстати, может и правда пока сделать разбиение на 6-11 кусков по величине чисел? С шагом 0.5-1e26? Если кортежей много, то они более вероятно в младших кусках. Но и чтобы сильно не дробить. Это можно сделать почти независимо от прочих доработок. Надеюсь скорость упадёт незначительно. Как думаете?

[Yadryara]

Перефразируя известный мультик:

Ладно, дробите на сколько хотите,
Только не очень-то их колотите.


Кстати, может это банальность, но скажу. С экранной клавы печатаю со вчерашнего дня. Не знаю, может и порт PS/2 отключился. Так вот, я неработающую клаву от компа отсоединил. И ночью был установлен рекорд скорости счёта одного юнита:

55 минут 18 секунд и до 3.96 ГГц
против старого рекорда
56 минут 20 секунд и до 3.88 ГГц

И не греется как раньше. Раньше руку подносишь к вент. отверстиям -- горяченький воздух. А сейчас едва тёплый.

Так что, если хотите быстрей считать, отключайте побольше ненужного. На следующую ночь ещё колонки попробую.

Yadryara в сообщении #1661502 писал(а):

А вот качество находок будет снижаться, но именно в среднем.

Под качеством я имею в виду долю valids от len. Уже думал, что может я зря начал обозначать кортежи через обратный слэш. Буду через прямой. Взять, например дро, то есть кортеж 18/19. Его качество видно из его обозначения — 0.947.

[Yadryara]

Возвращаюсь к 12-му августа, когда впервые пришла идея использовать деление на группы и проверять их по убыванию чистоты:

Yadryara в сообщении #1649575 писал(а):

Что если искать чистую 19-ку надо прежде всего среди самых чистых, то есть среди 54760 кандидатов, а затем уже среди 6792018 и так далее...

Кстати, я обычно стараюсь давать переменным осмысленные названия. Вроде бы ещё ни разу не пояснял: vc[] — Vector Chistoty. И он действительно Вектор Чистоты. Ещё раз смотрим на его начало для 67# :

  G4    G5      G6        G7         G8           
   0 54760 6792018 325858198 8732689082

Вот посчитали мы все 54760 самых чистых кандидатов для $0\cdot67\#-1\cdot67\#$. Ни одной цепочки длиннее 12-ти не нашлось.

А что мешает обсчитать те же самые кандидаты и на следующих периодах? То бишь на

$1\cdot67\#-2\cdot67\#$
$2\cdot67\#-3\cdot67\#$
...
$70\cdot67\#-71\cdot67\#$

И весь $0-71\#$ будет закрыт по этой группе. Да, вероятность найти более длинную цепочку падает, но зато попыток в 70 раз больше.

А вот для следующей группы из 6792018 кандидатов уже нашлись и более длинные цепочки, но ни одной длиннее 15-ти не нашлось. Тоже можно проверить много раз, необязательно 70. Ели конечно эти 6 млн ещё где-нибудь сохранились. Следующая группа уже превышает 325 млн, с ней сложнее.

Ну или генерить самые-самые левые группы для ещё больших периодов.

19/19 вряд ли найдём, но статистика интересна.

[Dmitriy40]

Yadryara в сообщении #1661596 писал(а):

Вот посчитали мы все 54760 самых чистых кандидатов для $0\cdot67\#-1\cdot67\#$. Ни одной цепочки длиннее 12-ти не нашлось.

А что мешает обсчитать те же самые кандидаты и на следующих периодах? То бишь на

$1\cdot67\#-2\cdot67\#$
$2\cdot67\#-3\cdot67\#$
...
$70\cdot67\#-71\cdot67\#$

И весь $0-71\#$ будет закрыт по этой группе.

Во-первых группа G5@71# закрыта не будет. Потому что она зависит от групп G5...7@67#, а не только от G5@67#. Для примера посмотрите как там считал G6...8@67#, в них перебралось меньше полного количества.
Во-вторых да, так можно посчитать. Но это в 70 раз дольше, не в 52, сколько разрешённых остатков по 71. Впрочем для пары-тройки самых чистых групп 71# вполне можно. Впрочем самую чистую G4@71# и большую часть G5..6@71# и так уже тогда же посчитал.
В-третьих, программа примерно так и делает, из юнита в переданной группе перебирает несколько простых, при этом номер группы может уменьшиться, и проверяет получившийся юнит @71#. Но перебирает только допустимые остатки, потому в 52 раза больше, не в 70. Зато по всему 71#. Т.е. проверяются переданная группа и все чище что могут из неё получиться. В текущей программе по 67# перебираются 17,31...67, соответственно номер группы может уменьшиться максимум аж на 25. Так что и из переданной G30@29#/17 тоже могут получиться юниты группы G5@67#.

Т.е. я не понял Вашего предложения.

Yadryara в сообщении #1661596 писал(а):

Ели конечно эти 6 млн ещё где-нибудь сохранились.

Конечно нет, вычислялись на лету и сразу проверялись, чего их хранить то. Но я там писал, их вычисление заняло 7.5минут, проще перевычислить чем хранить.

Yadryara в сообщении #1661596 писал(а):

Ну или генерить самые-самые левые группы для ещё больших периодов.

Да не получается это! Так бы быстро насчитал чистую группу для 127# с чем долго мучились до HL1. Потому что группы зависят не от одной выше, и даже не от двух, а минимум от трёх! Это для простых от 43 и больше, для меньших - от четырёх выше и более. Соответственно для спуска на уровень ниже надо иметь плюс две группы правее на текущем уровне (41# и ниже/больше). А на предыдущем уже плюс 4 группы. И так оно быстро вырастает до полного объёма. а полный объём можно хранить только для 37# с 3млн, уже 41# с 31млн (да, уникальных только 1/5 от 159млн всех) в PARI влезает с огромным трудом (до 10ГБ памяти требуется), в асм с трудом и я не знаю как простым способом его туда пропихнуть (компилятор отказывается работать с большими файлами), придётся вычислять (а это код писать).