2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 15, 16, 17, 18, 19, 20, 21 ... 72  След.
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение29.03.2024, 10:44 
Аватара пользователя


29/04/13
8013
Богородский
Yadryara в сообщении #1634363 писал(а):
Да, на 99% с чем-то уверен: не может такая красота не работать для всех нечётных симметричных паттернов и кортежей.

Ура! Я просёк почему она работает. Но рассказ будет довольно долгим.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение29.03.2024, 11:30 


23/02/12
3335
Yadryara в сообщении #1634670 писал(а):
Ну как же оно стремится к 0, когда оно наоборот с ростом $p\#$ увеличивается в разы и это прекрасно видно, в том числе в нынешнем примере ???
А значение $c_{max}$ в нынешнем случае устаканилось на 7. То есть тройка простых 12-12 может быть загрязнена другими простыми в количестве до 4-х штук.
Извините, может я неправильно Вас понимаю. Допустим есть кортеж $p,p+4$. Таких кортежей, состоящих из двух простых чисел, бесконечное количество. Вы хотите добавить в этот кортеж одно простое число и получить кортеж, состоящий из трех простых чисел $p,p+2,p+4$. Я правильно понимаю? Таких кортежей может быть только конечное количество, так как входящие в него числа образуют полную систему вычетов по модулю 3. Теперь допустим есть кортеж $p,p+6$. Таких кортежей, состоящих из двух простых чисел, тоже бесконечное количество. Вы хотите добавить в этот кортеж одно простое число и получить кортеж, состоящий из трех простых чисел $p,p+2,p+6$ или кортеж $p,p+4,p+6$. Таких кортежей будет бесконечное количество, так как входящие в него числа не образуют полную систему вычетов по модулю 3. Но если попытаться добавить в последние кортежи второе простое число и получить кортеж $p,p+2,p+4,p+6$, то таких кортежей вообще будет 0 (вариант конечного количества) и.т.д.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение29.03.2024, 13:48 
Заслуженный участник


20/08/14
11670
Россия, Москва
Yadryara в сообщении #1634677 писал(а):
виганием вершины я уже занимался, кстати. Удавалось добиться, что относительная погрешность для всех чисел строки стала меньше одного процента.
Э, т.е. Вы можете посчитать вектор vc[] для 127# для 19-252 с погрешностью процента?! :shock: Так чего же молчите то, давайте скорее его! Хоть так оценим. Или погрешность растёт с каждым шагом (по p) и ничего оценить не получится?


У меня рано утром (за 11.5ч) посчиталось 61# для 19-252, следующее 67# будет считаться до недели, так покажу пока имеющиеся:
Код:
v=[0, 6, 12, 30, 42, 72, 90, 96, 120, 126, 132, 156, 162, 180, 210, 222, 240, 246, 252]
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, sum=3638600663040
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, sum=145544026521600
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, sum=6112849113907200
Предыдущие и показывал, и на PARI легко считаются.

Dmitriy40 в сообщении #1634568 писал(а):
например можно подумать как ускорить проход более глубоких уровней если в a[] остался ровно один элемент (ровно один единичный бит в aa, hammingweight(aa)=1) (это похоже на идею №2, только по другому аргументу), возможно получится вместо более глубоких вложенных циклов пройти их просто подряд, линейно, и что-то там на что-то домножить. Т.е. ускорить выбор между cmin и cmin+1, точнее даже не выбор, а сразу подсчёт обоих в таком вот случае, а он вроде бы весьма не редок.
Хороший пример бесполезного ускорения: для малых простых элементы cmin и cmin+1 ничтожно малы по сравнению с sum, следовательно ускорение их вычисления ничего не даст в плане скорости. Вот вроде и хорошая идея оптимизации, но бессмысленная.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение29.03.2024, 14:15 
Аватара пользователя


29/04/13
8013
Богородский
Dmitriy40 в сообщении #1634702 писал(а):
Так чего же молчите то, давайте скорее его!

Так я не молчал, я сразу сказал:

Yadryara в сообщении #1633669 писал(а):
Самый показательный пока паттерн 42-42, в котором 18 лишних простых. В паттерне 19-252 30 лишних простых и его предпоследняя строка, видимо, гораздо более регулярна. Но одно дело спрогнозировать строку с погрешностью не более 1% и совсем другое — точно.

Для паттерна 42-42 — не более 1%.

Dmitriy40 в сообщении #1634702 писал(а):
Или погрешность растёт с каждым шагом (по p) и ничего оценить не получится?

Увы. Хотя, давайте проверим. Совсем недавно считали 9-84 до 1е16, помните? Ну так вот, измените там 5-10 чисел в стартовой строке в пределах процента и запустите. Если не начнётся жуткий расколбас к 1е16, не говоря уж об 1е25, придётся мне съесть шляпу :-)

О другом позже.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение29.03.2024, 14:27 
Заслуженный участник


20/08/14
11670
Россия, Москва
Yadryara
Ваши формулы работают и для несимметричных паттернов:
Код:
v=[0, 6, 12, 30, 42];\\Несимметричный! левый из 19-252
3#: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, sum=2
5#: 0, 0, 0, 0, 0, 0, 0, 2, 2, sum=4
7#: 0, 0, 0, 0, 0, 1, 9, 2, sum=12
11#: 0, 0, 0, 1, 7, 34, 28, 2, sum=72
13#: 0, 0, 2, 28, 160, 269, 111, 6, sum=576
17#: 0, 4, 109, 830, 2468, 2621, 838, 42, sum=6912
19#: 4, 268, 3702, 18453, 37609, 29250, 7188, 294, sum=96768
23#: 340, 11960, 114591, 427231, 672776, 423378, 88314, 3234, sum=1741824, OK

v=[0, 6, 12, 18, 30, 36];\\Несимметричный!
3#: 0, 0, 0, 0, 0, 0, 0, 2, sum=2
5#: 0, 0, 0, 0, 1, 1, sum=2
7#: 0, 0, 0, 1, 0, 1, sum=2
11#: 0, 0, 1, 4, 4, 1, sum=10
13#: 0, 2, 17, 26, 21, 4, sum=70
17#: 2, 54, 226, 282, 178, 28, sum=770
19#: 80, 1100, 3332, 3532, 1742, 224, sum=10010, OK
Оба посчитал и дальше, по 59# (на 61# числа превысили 2^64), все остальные строки тоже окейные, заняло пару секунд.

-- 29.03.2024, 14:55 --

Yadryara в сообщении #1634704 писал(а):
Хотя, давайте проверим. Совсем недавно считали 9-84 до 1е16, помните? Ну так вот, измените там 5-10 чисел в стартовой строке в пределах процента и запустите. Если не начнётся жуткий расколбас к 1е16, не говоря уж об 1е25, придётся мне съесть шляпу :-)
Надеюсь шляпа у Вас вкусная ... ;-)
Код:
? c0\\Образцовый
%1 = [0, 0, 0, 0, 0, 0, 0, 0, 3075976, 172443036, 2982765864, 22582804840, 87976549320, 195008570124, 262408889876, 220882584188, 117236333144, 40358558480, 9629086752, 1478049120, 90478080]
? c1
%2 = [0, 0, 0, 0, 0, 0, 0, 0, 3175976, 173443036, 2982765864, 22582804840, 87976549320, 194008570124, 262408889876, 221882584188, 117236333144, 40358558480, 9629086752, 1477049120, 90378080]
? vecsum(c0)
%3 = 960810188800
? vecsum(c1)
%4 = 960810188800
? c1-c0
%5 = [0, 0, 0, 0, 0, 0, 0, 0, 100000, 1000000, 0, 0, 0, -1000000000, 0, 1000000000, 0, 0, 0, -1000000, -100000]
? for(k=1,8,c=c0*1.0;pr=pr0;forprime(p=47,10^k,for(i=cm,#c-1,c[i]=c[i]*(p-i)+c[i+1]*(i+1-cm));c[#c]*=p-#c;pr*=p);print("10^",k,": c",cm,"=",c[cm]);)
10^1: c9=3075976.0000000000000000000000000000000
10^2: c9=9700723135938319098329396524.0000000000
10^3: c9=1.0376559211320620230155745256956034679 E407
10^4: c9=9.0253029272976793965590757856321081266 E4288
10^5: c9=2.6851992474995041923249653671105627727 E43283
10^6: c9=1.8136762603118047528812914570381931279 E433626
10^7: c9=6.9304824582518476787558725783564086233 E4340840
10^8: c9=3.9260010206257956280639458393354973103 E43424108
? for(k=1,8,c=c1*1.0;pr=pr0;forprime(p=47,10^k,for(i=cm,#c-1,c[i]=c[i]*(p-i)+c[i+1]*(i+1-cm));c[#c]*=p-#c;pr*=p);print("10^",k,": c",cm,"=",c[cm]);)
10^1: c9=3175976.0000000000000000000000000000000
10^2: c9=9708520755979285826470396524.0000000000
10^3: c9=1.0365268446529459230315246466029030524 E407
10^4: c9=9.0166770873375700299742649346238816862 E4288
10^5: c9=2.6831012978468884509569167610255563427 E43283
10^6: c9=1.8124993087421271042885020636682031079 E433626
10^7: c9=6.9266616458067128559934142396562836380 E4340840
10^8: c9=3.9241251662545230396128576159190309857 E43424108
Разница конечно есть, но всего 0.05%.

-- 29.03.2024, 14:59 --

Yadryara
Так что таки показывайте 127# для 19-252.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение29.03.2024, 14:56 
Аватара пользователя


29/04/13
8013
Богородский
В курсе :-) Сюрприз у меня получился вот на этом чётном: 6-6-6-12-6-6-6. Или по две 6-ки с краёв.

Сейчас пишу обоснование сходимости с примером.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение29.03.2024, 15:11 
Заслуженный участник


20/08/14
11670
Россия, Москва
Yadryara в сообщении #1634713 писал(а):
Сюрприз у меня получился вот на этом чётном: 6-6-6-12-6-6-6.
О! А с ним хитрее:
Код:
v=[0, 6, 12, 18, 30, 36, 42, 48]
7#: 0, 0, 0, 0, 0, 2, sum=2
11#: 0, 0, 0, 0, 4, 2, sum=6
13#: 0, 0, 0, 10, 16, 4, sum=30
17#: 0, 0, 20, 112, 114, 24, sum=270
19#: 0, 40, 516, 1352, 918, 144, sum=2970, OK
23#: 34, 1448, 10332, 19920, 11232, 1584, sum=44550
29#: 2162, 49624, 256068, 403488, 198864, 25344, sum=935550, OK
31#: 99350, 1603864, 6587892, 8865216, 3905136, 456192, sum=21517650, OK
37#: 4485014, 58083976, 204468732, 246116160, 99909360, 10948608, sum=624011850, OK
41#: 206089438, 2267624696, 7076879172, 7783122240, 2952114480, 306561024, sum=20592391050, OK
43#: 9480755026, 91252998008, 256886379396, 260868369600, 93048354000, 9196830720, sum=720733686750, OK
47#: 461002444022, 3981386683096, 10287401146452, 9763454721600, 3302676543600, 312692244480, sum=28108613783250, OK
53#: 24726496664086, 195755816349128, 471648613462236, 423275804481600, 136973199510000, 12507689779200, sum=1264887620246250, OK
59#: 1456807146217514, 10731088044380872, 24380609473094364, 20865131413156800, 6500278825866000, 575353729843200, sum=64509268632558750, OK
61#: 87941866793909114, 606777797253994072, 1306006477367282964, 1069257685961304000, 321390431116650000, 27616979032473600, sum=3418991237525613750, OK
Смотрите, окейная 19# не унаследовалась в 23#. А вот после p>v[#v]/2=24 все окейные наследуются.

PS. И посмотрите в предыдущем сообщении добавление про шляпу и 127# для 19-252.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение29.03.2024, 15:47 
Аватара пользователя


29/04/13
8013
Богородский
Да, вижу, сошлось. Хорошо ещё что догадался не писать "свою" (шляпу). У куколки возьму. А если все числа заменить ?

Итак, что происходит при превышении радиуса?

Возьмём тот же паттерн [0, 12, 24]. И попробуем по-другому посчитать для него окейную строку 13#.

Числа для 11# мы знаем. На периоде 13# их поначалу, до всех проверок, будет ровно в 13 раз больше, чем на периоде 11#. Затем начнутся проверки по модулю 13 и числа уменьшатся.

Причём, уже для числа 13 общее количество простых в паттерне никак не удастся уменьшить сразу на 2. По той простой причине, что числа кратные 13 оба должны стоять на чётных позициях паттерна. Даже если одно число окажется на самом-самом левом краю, в позиции 0, то другое в позиции 26 что ли? Но в паттерне крайне правая позиция — 24.

Так что 7 простых (7-ка) может уменьшиться только до 6-ки, 6-ка только до 5-ки и т. д.

И расчёт упрощается. С учётом весов:

Код:
11#:     0,    2,   20,   48,   58,               sum =   128

x 13          26   260   624   754                       1664

3*128 = 384

1664 - 384 = 1280


26/1664 * 384 =    6

260/1664 * 384 =  60

624/1664 * 384 = 144

754/1664 * 384 = 174
____________________
                 384

  174*4/3 = 232
  144*3/3 = 144
   60*2/3 =  40
    6*1/3 =   2


          26   260   624   754                       1664
-
           6    60   144   174
______________________________
          20   200   480   580                       1280
-
                           232
______________________________
                           348
+
                     232
-
                     144
________________________
                     568
+
               144
-
                40
__________________             
               304
+
          40
-
           2
____________
          58
+
     2

Как видим, это как раз числа нашей строки:

13#: 2, 58, 304, 568, 348, sum = 1280, OK

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение29.03.2024, 16:53 
Заслуженный участник


20/08/14
11670
Россия, Москва
Yadryara в сообщении #1634721 писал(а):
А если все числа заменить ?
Думаю без разницы:
Код:
? x1=vector(#c0,i,[0.99,1.01][i%2+1]);printf("%0.2f",x1)
[1.01,0.99,1.01,0.99,1.01,0.99,1.01,0.99,1.01,0.99,1.01,0.99,1.01,0.99,1.01,0.99,1.01,0.99,1.01,0.99,1.01]
? c1=vector(#c0,i,c0[i]*x1[i])
%1 = [0, 0, 0, 0, 0, 0, 0, 0, 3106735.7600000000000000000000000000000, 170718605.64000000000000000000000000000, 3012593522.6400000000000000000000000000, 223569767
91.600000000000000000000000000, 88856314813.200000000000000000000000000, 193058484422.76000000000000000000000000, 265032978774.76000000000000000000000000, 2186737583
46.12000000000000000000000000, 118408696475.44000000000000000000000000, 39954972895.200000000000000000000000000, 9725377619.5200000000000000000000000000, 1463268628.
8000000000000000000000000000, 91382860.800000000000000000000000000000]
? for(k=7,8,c=c1*1.0;forprime(p=47,10^k,for(i=cm,#c-1,c[i]=c[i]*(p-i)+c[i+1]*(i+1-cm));c[#c]*=p-#c);print("10^",k,": c",cm,"=",c[cm]);)
10^7: c9=6.9304786302322495413528972666558715777 E4340840
10^8: c9=3.9259978772466231558206199904685204682 E43424108
3.92600102 vs 3.92599788, разница менее 1ppm (одной миллионной, десятитысячной процента).

Проверил и случайные изменения каждого числа:
Код:
? x1=vector(#c0,i,random(201)/10000+0.99);printf("%0.4f",x1)
[0.9950,1.0060,0.9992,1.0034,0.9936,0.9962,1.0018,1.0061,0.9931,1.0020,0.9900,0.9918,1.0048,0.9944,1.0047,1.0081,0.9906,1.0008,1.0052,0.9905,1.0051]
? c1=vector(#c0,i,c0[i]*x1[i]);
? for(k=7,8,c=c1*1.0;forprime(p=47,10^k,for(i=cm,#c-1,c[i]=c[i]*(p-i)+c[i+1]*(i+1-cm));c[#c]*=p-#c);print("10^",k,": c",cm,"=",c[cm]);)
10^7: c9=6.9359252577130764070573522996061332303 E4340840
10^8: c9=3.9293821397950451370971828614308031352 E43424108
3.926001 vs 3.929382, разница менее 0.1%.

Я Вам больше скажу, даже если до 1e4 посчитать точно, а потом до 1e8 считать только левые три элемента (но по правильным формулам), то разница будет всего 3.9260010 vs 3.2488276, меньше 21%. Sum разумеется не совпадёт, но она нам и не нужна. А если взять 4 элемента, то 3.7486150, меньше 5%.

Dmitriy40 в сообщении #1634708 писал(а):
Так что таки показывайте 127# для 19-252.
Чего-то я торможу: если можете посчитать примерные vc[] для 127# для 19-252, то что мешает посчитать сразу и cmin для 1e13# для него же? Или там всё же цикл по простым и потому медленно?

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение29.03.2024, 17:14 
Аватара пользователя


29/04/13
8013
Богородский
Занятно.

Dmitriy40 в сообщении #1634731 писал(а):
Чего-то я торможу: если можете посчитать примерные vc[] для 127# для 19-252,

Да с чего Вы взяли-то, что я могу? Я же написал для какого паттерна.

Да и как я мог писать о точности в 1 %, если не с чем сравнивать? Относительно уже обсчитанной строчки, да мог.

Но. Вы разобрались в моём обосновании и примере с 13#? Именно здесь ведь пахнет прорывом. И очень здорово, что Вы посчитали 61# для 19-252. Ибо следующее число 67# уже больше половины радиуса, а это важно.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение29.03.2024, 18:01 
Заслуженный участник


20/08/14
11670
Россия, Москва
Yadryara в сообщении #1634734 писал(а):
Вы разобрались в моём обосновании и примере с 13#?
По моему это совпадает с моей второй идеей, уже реализованной и на PARI, и на асме. Она (моя идея) потому и работает что простое больше половины диаметра попадает в a[] не более одного раза, я сразу об этом писал.
Прорыв тут уже произошёл (если про программы).
Но как оно связано с Вашими формулами - нет, не разбирался. Верю Вам, да и с опытами совпадает же.
Непонятно почему 47# для 9-96 не окейная, ведь a[]=[2,...,94] и 47 в него дважды попасть всё равно не может ... Как и 41# для диаметров 84.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение29.03.2024, 18:15 
Аватара пользователя


29/04/13
8013
Богородский
Dmitriy40 в сообщении #1634744 писал(а):
Непонятно почему 47# для 9-96 не окейная, ведь a[]=[2,...,94] и 47 в него дважды попасть всё равно не может ... Как и 41# для диаметров 84.

Это-то как раз понятно. Не только именно в a[] надо смотреть попадания, но и во весь паттерн [0,...,96]

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение29.03.2024, 18:37 
Заслуженный участник


20/08/14
11670
Россия, Москва
Я кажется понял про какой прорыв Вы хотели сказать: похоже имея vc[] и списки всех оставшихся комбинаций для каждого vc[] можно относительно легко посчитать vc[] по следующему простому. Без разницы окейная строка или нет, работает для всех.
Т.е. вложенные переборы заменяются последовательными, но понадобятся до 1e9 элементов (реально сильно меньше) суммарно в 31 векторе, для 19-252.
Буду думать, очень заманчиво.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение29.03.2024, 23:05 
Заслуженный участник


20/08/14
11670
Россия, Москва
Идея рабочая, действительно получается получать строки подряд. Только очень медленно: любимый тестовый паттерн v=[0, 24, 30, 36, 60] вместо 0.23с, 2.0с, 4.5с считается 30с, 68с, 84с (соответственно 23#, 29#, 31#), всё на PARI.

-- 29.03.2024, 23:56 --

О, а грамотное применение Map() ускорило тестовую программу до соответственно 1.4с, 0.7с, 0.55с, даже быстрее образцовой (выложенной в теме выше)! И даже ускоряется с ростом p, что вообще нонсенс! :-)

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение30.03.2024, 11:34 
Заслуженный участник


20/08/14
11670
Россия, Москва
Итак, после допиливания удалось на PARI посчитать паттерн 9-108 до конца, по 59#, менее чем за 3 минуты, при том что программа переборов на асме считала 1ч20м. Время распределилось по 29#-59# так: 1.6c, 7с, 17с, 25с, 28с, 31с, 35с, 38с. Уникальных вариантов комбинаций a[] после 59# осталось 546 тысяч (почти не росло уже с 37#, потому и время почти не росло).
Но считать надо всегда с самого начала, с 3#, переборы же могут считать любой праймориал.

Программа:
Код:
allocatemem(10^8);\\Память нужна, да
v=[0, 18, 24, 48, 54, 60, 84, 90, 108];\\9
a=setminus(vector(v[#v]/2,i,i*2),v); print("v=",v);
ww=vector(v[#v]/2,i,Map()); mapput(ww[#ww],2^#a-1,1);
{forprime(p=1,nextprime(v[#v]/2),
   tz0=getwalltime();
   m=setminus(vector(p,i,i-1),Set(-v%p));
   am=vecextract(vector(p-1,i,fromdigits(Vecrev(apply(t->(t+i)%p>0,a)),2)),m);
   for(k=1,#ww,
      rr=Map();
      foreach(ww[k],m,
         b=m[1][1]; qq=m[1][2]; qn=0;
         foreach(am,x,
            y=bitand(x,b);
            if(y==b, qn+=qq; next);
            hy=hammingweight(y)+1; nn=0;
            if(mapisdefined(ww[hy],y,&nn), nn+=qq , nn=qq);
            mapput(ww[hy],y,nn);
         );
         if(qn>0, mapput(rr,b,qn); );
      );
      ww[k]=rr;
   );
   vc=vector(#ww); for(k=1,#ww, foreach(ww[k],x, vc[k]+=x[1][2]; ); );
   vcmax=#vc; while(vcmax>1&&vc[vcmax]==0, vcmax--);
   print("",p,"#: ",strjoin(vc[1..vcmax],", "),", sum=",vecsum(vc),", time: ",strtime(getwalltime()-tz0));
);}
Принцип работы: работаем с битовыми масками наличия элементов в a[], инициализируем список всеми единичными битами с множителем 1, потом в порядке увеличения индекса vc[k] обрабатываем весь список уникальных комбинаций a[], для каждой (взятой в m) для каждого допустимого остатка удаляем его элементы из оставшихся a[] (делается bitand), вычисляем длину hy новой комбинации и обновляем её множитель в списке если есть или просто добавляем в список если такой там ещё нет. Сравнение y==и и пропуск модификации - если ничего не изменилось, то не будем вызывать много раз, а вызовем один раз в конце с увеличенным множителем количества. Так как проход по длине k идёт в сторону увеличения, а при обработке каждого остатка длина может или уменьшиться (тогда список ww сразу обновится) или остаться той же, то последние случаи накапливаются в новом списке rr и потом он перезаписывает обработанный в общем ww[k] (чтобы не менять текущий обрабатываемый список на лету).

Посчитать большие диаметры не получается, слишком быстро растёт количество уникальных комбинаций a[] (для простых примерно до четверти-трети диаметра, потом рост практически прекращается) и список их ww не влезает в память.

Зато смог посчитать правые 5 элементов в 19-252 до 127#:
Код:
61#: 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, 4577709549962, 678625326646, 70209898488, 4365719848, 113480160, sum
67#: 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, 135295969437234, 18878969508802, 1836531247768, 107619357728, 2666478240, sum
71#: 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, 4613157466381520, 614389502603580, 57035296901788, 3194803761712, 76015820160, sum
73#: 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, 163469887490363636, 20811088335231610, 1842711011866572, 98229862527152, 2225825159040, sum
79#: 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, 6712529533063117932, 820634405591898460, 69651551721091256, 3557606996239392, 77458121798400, sum
83#: 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, 295588436197324273224, 34763658542898459608, 2834250821896477544, 138942083362119936, 2905818137107200, sum
89#: 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, 14788623264348306478398, 1687193291761313729988, 133497335364676741912, 6354086741865734784, 129246846208300800, sum
97#: 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, 840804066512067515222744, 93048517713584964085964, 7141103807508254772636, 329920591582412971584, 6529000988722060800, sum
101#: 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, 51618145822460787277758590, 5566629017220937449677844, 416310093193238409538376, 18746496499210476706368, 362224462774777344000, sum
103#: 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, 3218267413612819577226083354, 337015942625338490947048616, 24465924058699731920786584, 1069813034763044135539968, 20109323045263947264000, sum
107#: 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, 214036202732873586950402243044, 21866715832495639117111528096, 1548900465991827788951954720, 66139032710912104732002048, 1217030127904303663104000, sum
109#: 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, 14543387499963069153193849853344, 1446051054386135437460983283016, 99652711658483082990715589360, 4140824467524594175759550976, 74238837802162523449344000, sum
113#: 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, 1056915263686593893844168443674496, 102892528884072156314253248592176, 6943611289142775998673865244208, 282684306303616742837495359488, 4974002132744889071106048000, sum
127#: 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, 89445149902170647515706650093297424, 8528715955705842389417381362804080, 563686748014226965436196584961792, 22481280261968069356295314839552, 387972166354101347546271744000, sum
Начиная с 61# (меньшие ещё быстрее) все считались секунд по 16-35, всего хватило 7 минут.
Можно посчитать и 7 правых элементов, за десяток часов, но на большее не хватает памяти - ww слишком разрастается, для 7 правых элементов он уже больше 11млн элементов (для 5-ти хватило 357 тысяч).
На асме по идее под элемент списка хватает 32 байта (16 под маску и 16 под счётчик повторов qq в коде выше), значит в 8ГБ влезет 260млн элементов, это всего лишь 9 правых элементов в vc[] из 31. Беда.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1076 ]  На страницу Пред.  1 ... 15, 16, 17, 18, 19, 20, 21 ... 72  След.

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

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