кортежи последовательных простых. ключ к 19-252

[Yadryara]

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

И потому следить нужно не только за общим количеством вариантов (vc[] и ваши массивы), но и за каждым отдельно (ww[]). И по моему это принципиально.

Пока не возражаю. Делать-то что будем?

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

Где-то тут у Вас пробел в логике.

У меня? Я лишь сказал, что может быть есть какая-то инверсия. Какая-то, понимаете? Ведь есть же огромная разница между смутной идеей и цельным логическим построением.

Вы лучше знаете Вашу программу, Вы видели как cg считается у меня. А как посчитать cg у Вас?

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

Точнее я не понимаю чего Вы хотите.

Я хочу посчитать cg для перехода $41\# \to 43\#$ для 19-252. То есть память нужна всё-таки для счёта до $41\#$.

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

Вы пытаетесь свернуть всё множество вариантов ww[l] в два-три массива, но простите по моему это невозможно.

В три. Жаль, если это невозможно.

[Dmitriy40]

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

Вы лучше знаете Вашу программу, Вы видели как cg считается у меня. А как посчитать cg у Вас?

Да что Вы привязались к моей программе то?! Посчитайте всё нужное на бумажке вообще без программ. В терминах списков чисел (v[], a[], vc[], ещё любых).

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

Я хочу посчитать cg для перехода $41\# \to 43\#$ для 19-252. То есть память нужна всё-таки для счёта до $41\#$.

И в чём с этим проблема? По 41# всего лишь 159млн вариантов комбинаций допустимых остатков, перебрать их на PARI достаточно десятков минут (не перебирать же все 41#/2=1.5e14 вариантов как у Вас сейчас), просто заменить циклы forstep(i=1,mor,2,for(j=1,#v, на нормальные циклы по всем остаткам с КТО, как для формирования таблиц (формул) в соседней теме. И вычисляйте для каждого из 159млн свои массивы ... Это уже не минуты, а часы, и много, но всё равно, никакой проблемы не вижу.
Даже ладно, могу наверное Вам посчитать c1g1[] и g2[] по ww[] для 41#, тех 31млн, это полчаса их генерить и потом несколько часов считать ваши массивы (потому что я пока плохо понимаю что за массив fl[] и нельзя ли его считать сильно быстрее).
Но мне интересно - а что дальше то? Ну вот посчитали Вы c1g1[] и g2[] для 41#->43# - и? Ну убедитесь что можно по vc[], c1g1[], g2[] для 41# получить vc[] для 43# - и что? Как Вы собираетесь считать c1g1[] и g2[] для 43#, уже не имея 3.8млрд (159млн*(43-19)) грязных вариантов для 43#? Т.е. на два шага дальше, не на один.
И зачем лезть в 19-252 и 41# если можно проводить опыты над сильно проще паттернами? Считать c1g1[] и g2[] на один шаг вперёд Вы научились, прекрасно. А на два шага? А на 16 шагов? Ведь это нужно.
Вот Вы выложили программу для 5-120, считающую по списку грязных для 19# массивы c1g1[] и g2 для расчёта по ним vc[] для 23# за несколько минут, прекрасно. А теперь, не увеличивая в ней mor (и не добавляя цикла перебора остатков по модулю 23), посчитайте vc[] для 29#. Когда посчитаете - будем думать как это перенести на 19-252 для 41# и дальше.

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

Жаль, если это невозможно.

По моему тут идёт потеря критично важной информации. Малой части от всей, но потеря. Т.е. если новый грязный вариант уже есть в списке - ок, потери информации нет, можно просто счётчик увеличить, но вот если появляется новый грязный вариант, которого раньше не было - с чего Вы взяли что его можно просто подсуммировать к уже имеющимся?! На один шаг дальше да, можно, потому что в таком случае нас не интересуют индивидуальные варианты, только их общее количество, но на два шага - очень даже интересуют, они же по разному себя ведут при дальнейшем очищении от грязи даже одним и тем же допустимым остатком. Далеко не все, лишь некоторые, многие дальше чистятся одинаково, но не все же одинаково! Потому что тогда бы размер ww[] больше не рос, а это наблюдается только для окейных строк (половина диаметра), не раньше. Можно улучшить оценку до примерно трети диаметра если новые грязные варианты хранить и считать отдельно, после трети диаметра их количество почти не растёт, но это всё равно треть диаметра, не 1/6. Для 19-252 треть диаметра это минимум 83#, дотуда грязных вариантов (размер ww[]) будут триллионы, не влезут ни в память, ни на диск.


Короче всё выше можно и не читать, главное в другом: как посчитать c1g1[] и g2[] для 41# для 19-252 - вообще не вопрос. Вопрос как их посчитать на два шага вперёд не имея полного списка грязных вариантов на шаг вперёд и не перебирая все комбинации разрешённых остатков двух шагов. И это можно и нужно разбирать на более простых примерах.

-- 23.04.2024, 17:08 --

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

Делать-то что будем?

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

Я как бы наверное могу посчитать самый левый элемент vc[] (т.е. чистые) для 113# для 19-252 (не так уж много вариантов комбинаций остатков могут дать столь чистый вариант), может даже и следующий слева, но это мало что даёт, точность оценки для 1e25 будет около порядка величины (потому что мы знаем примерный максимум в vc[] для 113#, но не знаем в какой он позиции и что в остальных элементах vc[]), это слишком много.

[Yadryara]

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

Да что Вы привязались к моей программе то?!

Как-то это грубовато звучит. Разве у нас тут не дружелюбный обмен мнениями?

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

Но мне интересно - а что дальше то?

Да мне самому интересно что дальше. Совсем недавно писал, что именно такие задачи порой весьма интересны. Есть решение или нет, непонятно пока.

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

Считать c1g1[] и g2[] на один шаг вперёд Вы научились, прекрасно. А на два шага? А на 16 шагов? Ведь это нужно.

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

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

Т.е. если новый грязный вариант уже есть в списке - ок, потери информации нет, можно просто счётчик увеличить, но вот если появляется новый грязный вариант, которого раньше не было - с чего Вы взяли что его можно просто подсуммировать к уже имеющимся?!

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

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

И это можно и нужно разбирать на более простых примерах.

Ну так я это и делаю. Но 41# тоже интересно. Пробовал посчитать g2, памяти не хватило. При этом 37# — меньше чем за минуту.

И кэфы превышения тоже считать интересно, хотя они прямо сейчас не нужны.

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

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

Погорячился. Не прорыв, продвижение. Раньше-то я вообще не умел считать эти массивы. Кстати, это я пока ограничился 3 массивами. Вполне допускаю, что надо ещё шире смотреть.

[Yadryara]

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

Все 3 массива понадобятся,

Ну вот, для этих массивов на примере правого края удалось изобразить как работает формула при путешествии от одной шестой почти до половины диаметра. На следующем шаге g2[] обнулится.

v=[0, 36, 72]   11# -------> 31#

11# --> 13#                                     p - lmax              Sum
                                               13 - 18  = -5
                                                           *
vc = [         0,        0,       18,      56,     46,     8 ]        128
                                                           +
cg = [         0,        0,       20,     100,    108,    24 ]        168
                                                           +
g2 = [         0,        0,       48,     162,    138,    26 ]        374
                                                           =
vc = [        48,      262,      474,     380,    106,    10 ]       1280
                                                           *
                                               17 - 18  = -1
                                                           +
cg = [        46,      356,      660,     518,    166,    18 ]       1764
                                                           +
g2 = [        62,      314,      496,     462,    134,    12 ]       1480
                                                           =
vc = [,     2694,     5954,     5736,    2422,    408,    20 ]      17920
                                                           *
                                                19 - 18  = 1
                                                           +
cg = [,      734,     1966,     1714,     596,     86,     6 ]       5292
                                                           +
g2 = [,     2658,     6720,     7558,    3974,    888,    54 ]      22464
                                                           =
vc = [,    77202,    94432,    56046,   15740,   1976,    80 ]     286720
                                                           *
                                                23 - 18 =  5
                                                           +
cg = [,    40986,    53430,    35158,   11478,   1712,    80 ]     163800
                                                           +
g2 = [,    47558,    67552,    44420,   13506,   1962,   104 ]     193536
                                                           =
vc = [,  1755202,  1532930,   696038,  157296,  16442,   584 ]    5734400
                                                           *
                                                29 - 18 = 11
                                                           +
cg = [,   671538,   580902,   255558,   53630,   4756,   112 ]    2134080
                                                           +
g2 = [,   880712,   866864,   421280,   93628,   8920,   360 ]    2903040
                                                           =
vc = [, 44604362, 31789682, 12234252, 2400058, 218908,  6896 ]  149094400
                                                           *
                                                31 - 18 = 13
                                                           +
cg = [, 23909618, 19719044,  8544076, 1856860, 191388,  6896 ]   77805000
                                                           +
g2 = [,  4797170,  5461046,  3262092,  967104, 127816,  5552 ]   17611776
                                                           =
vc =[,1153892762,698314552,235091702,41448078,3469356,102096 ] 4174643200

[Yadryara]

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

Собственно Ваши формулы для окейных строк работают как раз потому что в тех уже не появляется новых комбинаций загрязнений, их множество стабилизировалось и потому формулы столь просты и не зависят от этого множества, только от количеств соответствующей длины (которые и лежат в vc[]).

А вот и нет. Например, для того же паттерна 3-72, формулы работают, как обычно с предойкейной 31#, тогда как новые расстановки появляются вплоть до 43# включительно.

37#:
Len Rasst   New
1       0   0
2      32   32
3     363   246
4    2236   894
5    8976   2107
6   24766   2834
7   48932   1786
8   71678   506
9   79240   118
10  66208   2
11  41304   0
12  18744   0
13   5932   0
14   1226   0
15    148   0
16      8   0

369793


41#:
1   1   1
2   34   2
3   379   16
4   2324   88
5   9136   160
6   24862   96
7   48946   14
8   71682   4
9   79240   0
10   66208   0
11   41304   0
12   18744   0
13   5932   0
14   1226   0
15   148   0
16   8   0

370174


43#:
1   1   0
2   34   0
3   381   2
4   2328   4
5   9140   4
6   24862   0
7   48946   0
8   71682   0
9   79240   0
10   66208   0
11   41304   0
12   18744   0
13   5932   0
14   1226   0
15   148   0
16   8   0

370184


47#:
1   1   0
2   34   0
3   381   0
4   2328   0
5   9140   0
6   24862   0
7   48946   0
8   71682   0
9   79240   0
10   66208   0
11   41304   0
12   18744   0
13   5932   0
14   1226   0
15   148   0
16   8   0

370184

[Dmitriy40]

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

А вот и нет. Например, для того же паттерна 3-72, формулы работают, как обычно с предойкейной 31#, тогда как новые расстановки появляются вплоть до 43# включительно.

О, ну тогда я опять ничего не понимаю. И мои соображения о потере информации и невозможности расчётов неверны.

-- 24.04.2024, 14:30 --

Могу лишь предположить что все эти новые варианты не порождают двухзубых вилок ни на одном из следующих шагов, т.е. уменьшают загрязнение не более чем на 1, что Вашими формулами отрабатывается правильно.
Но что делать с двухзубыми вилками я всё равно не знаю. Их ведь нельзя просто брать и суммировать как однозубые, в зависимости от конкретного варианта загрязнения они могут уменьшать загрязнение и на 1 и на 2 одним и тем же остатком и тут уже нельзя знать одно лишь количество грязных вариантов, надо знать как каждый из них будет очищаться конкретным остатком. Точнее достаточно знать сколько из них уменьшит грязь на 2, сколько на 1, сколько на 0, но этого явно нельзя получить только из таких же количеств для предыдущего простого, надо знать и сами варианты загрязнений (т.е. ww[]). Как мне продолжает упорно казаться.

-- 24.04.2024, 15:07 --

Вывел максимальное уменьшение грязи dk, добавив его вычисление в строку после
hy=hammingweight(y)+1;
dk=max(dk,k-hy);
и оказалось таки да, как строка окейная, так dk=1.
Но для паттернна 3-60 dk стал равен 1 уже для 29#, а это ещё не окейная строка (формулы не сработали). Как и для паттерна 3-48. Т.е. и этот критерий неполный.

Для 19-252:
5#: dk=17
7#: dk=10
11#: dk=6
13#: dk=6
17#: dk=4
19#: dk=4
23#: dk=4
29#: dk=3
31#: dk=2
37#: dk=3
41#: dk=2
43#: dk=2
Вообще было увеличение dk, совсем удивительно.

[Yadryara]

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

Но для паттернна 3-60 dk стал равен 1 уже для 29#, а это ещё не окейная строка (формулы не сработали).

Ну как же не сработали. Сработали. Они как раз с предокейной начинают работать. Я потому её стартовой и называл.

[Dmitriy40]

Я называю сработавшей ту строку, для которой формулы дают правильный ответ, т.е. окейную. А не предыдущую, от которой они отталкиваются.

Для 19-252 для всех p=43..113 максимальный dk=2 (такое реально встретилось, а больше двух быть и не может). Неприятно. Это отбрасывает одну из моих идей.

-- 24.04.2024, 15:52 --

Даже интересно почему Ваши формулы дают ошибку когда dk уже равен 1 ... Например для 11# для 3-24 с #ww[]=14->46.

[Dmitriy40]

Ещё забавное наблюдение: если для 19-252 начиная с 37# проследить только за вариантами уменьшающими свою грязь всегда только на 2, то для 41# их 6млн (из 31млн всех), для 43# их 6.9млн, для 47# их 6.4млн, для 53# их 1.3млн, и потом быстро уменьшается и для 73# становится равным нулю, т.е. нет цепочек уменьшения грязи всегда на 2 далее 71#. При этом начиная с 61# количество грязи не падает ниже 7, т.е. влево они не уходят к достаточно чистым.
Напомню, есть варианты с уменьшением грязи на 2 даже при переходе 109#->113#.

[Yadryara]

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

Даже интересно почему Ваши формулы дают ошибку когда dk уже равен 1 .

Да ёлки ж зелёные... Это снова тот же самый вопрос, на который я уже дважды пытался ответить:

vicvolf в сообщении #1634928 писал(а):

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

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

Непонятно почему 47# для 9-96 не окейная, ведь a[]=[2,...,94] и 47 в него дважды попасть всё равно не может ... Как и 41# для диаметров 84.

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

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

Не понятно почему надо смотреть на весь паттерн, который не менее чем на 4 шире чем a[] ?

Вот формула, которая работает для $dk\leqslant2$

(p-i)*vc[i] + (i-cm+1)*vc[i+1]
+     cg[i] -          cg[i+1]
+     g2[i] -        2*g2[i+1] + g2[i+2]

Если массивы g2[] и cg[] обнулятся, это уже будет та самая формула, о которой Вы сейчас сказали во множественном числе:

(p-i)*vc[i] + (i-cm+1)*vc[i+1]

g2[] обнулится на том же шаге, на котором станет $dk\leqslant1$. Но cg[] ещё не обнулится! Потому что даже когда вилка станет настолько широкой, что уже не сможет попадать обеими зубцами в a[], она всё ещё сможет попадать в v[] ! И только на следующем шаге уже и в v[] попадать не сможет. cg[] планово обнуляется ровно на шаг позже чем g2[] .

Ещё в марте писал:

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

Если подать на вход vc для 13# и c1g1 для 17#, и нулевой g2, то на выходе получится vc для 17#.

Если подать на вход vc для 17# и нулевые c1g1 и g2,

cg[] планово обнуляется ровно на шаг позже чем g2[] . Потому что вилка попадает по крайнему чистому числу.

[Dmitriy40]

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

Потому что даже когда вилка станет настолько широкой, что уже не сможет попадать обеими зубцами в a[], она всё ещё сможет попадать в v[] !

Это непонятно: я всегда считал что все вилки, любые зубья которых попадают в v[], не попадают в список разрешённых остатков. А программа обрабатывает только разрешённые остатки (и соответственно вилки). Т.е. процитированной ситуации просто не должно возникать никогда. А реальный dk меньше количества зубьев лишь по причине что места попадания других зубьев уже были выбиты вилками раньше, но это никак не места v[].

-- 24.04.2024, 18:05 --

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

[Yadryara]

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

Это непонятно: я всегда считал что все вилки, любые зубья которых попадают в v[], не попадают в список разрешённых остатков.

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

Что такое cg (старое название c1g1) ? Это ситуация, когда вилкой выбивается ровно одно чистое(c) и ровно одно грязное(g). Но в a[] нет чистых чисел. Поэтому шире надо смотреть. Объединить v[] и a[].

Ну вот я ещё раз расписал. Паттерн 3-24. $3\#\to5\#$

   |              |              |
      |              |              |
         |              |              |                  
   c                 c                 c
  01    05 07    11 13    17 19    23 25           9             cg  4p

  05 07    11 13    17 19    23 25    29           9             cg  4p

   c                 c                 c
  07    11 13    17 19    23 25    29 31           9             g1  

  11 13    17 19    23 25    29 31    35           9             cg  2p

   c                 c                 c
  13    17 19    23 25    29 31    35 37           9             cg  2p

  17 19    23 25    29 31    35 37    41           9             g2  2p

   c                 c                 c
  19    23 25    29 31    35 37    41 43           9             g2  2p

  23 25    29 31    35 37    41 43    47           9             cg  2p

   c                 c                 c
  25    29 31    35 37    41 43    47 49           9             cg  2p

  29 31    35 37    41 43    47 49    53           9             g1

[Dmitriy40]

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

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

Говорили. Только это совсем непонятно, как именно их смотреть (например куда делись нечётные числа в a[]) и собственно почему. Чтобы посчитать Ваши массивы? Ну ок, смотрите. Но связь с vc[] остаётся непонятной, нет в нём v[], никаким макаром.
Короче если Вам всё понятно - прекрасно. А мне вникать в это пока неохота, всё равно применить не получается.

[Yadryara]

Ну так я специально расписал на совсем простом примере. 10 кортежей длиной 9 перед Вами.

Забыли пока про a[].

Видите, все числа уже прошли проверку по модулям 2 и 3. Результат проверки всех 10 кортежей по модулю 5 представлен. Но выбитые при проверке по 5 числа, а это конечно 05, 25 и 35 я пока оставил, чтобы было видно на каких они местах.

[gris]

Провёл серию экспериментов на тему "все паттерны равны, но некоторые равнее"
Производился сплошной отбор подряд 100 000 кортежей длиной 15 и диаметром 228, начиная с некоторого числа. Для каждого кортежа определялся его паттерн для которого определялся код и валидс на основании идеального паттерна 15-228. Результаты анализировались. Экземпляр:
6763 10 1092717173: [0,18,30,36,78,80,86,114,120,126,150,176,198,210,228]
Обобщённые результаты некоторых серий:
tested 100000 tuples in (3.000 E0, 7.736 E7) = 7.736 E7
codes: 100000/1077 patterns: 100000/100000
[45043, 34666, 14725, 4337, 1003, 188, 33, 5, 0, 0, 0, 0, 0, 0, 0, 0]
То есть, 100000 кортежей 15/228 разместились на интервале(a,b) длиной a-b.
Кодов столько-то/ из них различных. С этим всё нормально. Кодов всего 8192.
А вот с паттернами интереснее. Все паттерны различны.
Последняя строка - количество кортежей с валидсами от 0 до 15.
Чуть подальше
tested 100000 tuples in (9.820 E8, 1.145 E9) = 1.625 E8
codes: 100000/1064 patterns: 100000/100000
[45595, 34179, 14569, 4407, 1027, 191, 27, 4, 1, 0, 0, 0, 0, 0, 0, 0]

tested 100000 tuples in (5.269 E14, 5.269 E14)
codes: 100000/1065 patterns: 100000/100000
[45866, 34301, 14430, 4211, 970, 181, 34, 7, 0, 0, 0, 0, 0, 0, 0, 0]
Интервал размещения серии возрастает, как и время обработки. Кортежи диаметром 228 встречаются всё реже. И набрать миллион в диапазоне Е24 не каждый комп сможет и за пять часов
Интересно, что обобщённые характеристики серии не меняются. Различных кодов (в текущей серии) набирается 1%. Повторных паттернов вообще нет.
45% кортежей имеют валидс 0.
35% кортежей имеют валидс 1.
15% кортежей имеют валидс 2.
Остальные — мелочь.
tested 1000000 tuples in (3.315 E9, 5.757 E9) = 2.442 E9
codes: 1000000/10648 patterns: 100000/100000
[454543, 344165, 145538, 43471, 10075, 1878, 285, 40, 5, 0, 0, 0, 0, 0, 0, 0]
Миллиона мало. Только в серии в три миллиона кортежей обнаружились 40 повторных паттернов.
Предварительные предположения.
Существует binomial(113,13) = 38 393 094 575 497 956 паттернов, допустимых по 2# проверка на 17# уберёт много, но не слишком. Мы знаем, что допустимых (и реализованных) симметричных паттернов 15-228 всего два. А несимметричных? Много!
Теперь о приближениях. Паттерн с валидсом 15 всего один. С валидсом 14 — 184 штуки. С валидсом 0 огромное количество.
Мне кажется, что все допустимые паттерны имеют приблизительно равную и маленькую частоту появления в серии определённой длины, не зависящей от расположения. Хоть от Е12345. А вот частоты кодов, валидсов разительно отличаются. Поэтому в малых диапазонах легко найти приближения к 19-252 с валидсом 0 или 1. В больших диапазонах сплошным поиском найти просто кортеж диаметром 252 затруднительно. А уж найти саму 19-ку разве что по формулам можно отыскать. А ведь она есть