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

[Dmitriy40]

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

В смысле, с исключениями? Я вижу только одно исключение — самый крошечный кортеж.

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

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

А есть ли мысли по теоретической части?

Таких мыслей только одна: так как для 19-252 простые 59-113 могут уменьшить длину a[] максимум на два, значит и зависимость vc[] может быть только от предыдущих максимум трёх элементов. А для простых 43-53, уменьшающих длину a[] максимум на 3, от максимум четырёх предыдущих элементов. Можно попробовать составить систему линейных (для начала, вряд ли там высшие степени) уравнений и посмотреть имеет ли она решение. Благо точные данные есть по 67# (и частичные по 127#) и можно упроверяться.

[Yadryara]

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

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

Да почему они-то? Оно одно в самом начале. Сравните:

— Существуют ли кортежи 2-2?
— Да, конечно: 3, 5, 7.
— А где ещё хотя бы один?
— Есть только этот, в самом начале.

Обоснование уже привёл. Всё ли понятно про гнездование?

gris, откуда дровишки?

[Dmitriy40]

Проверил левые части переходов 41#->43# и 43#->47# и 61#->67# для 19-252, что-то там коэффициенты везде какие-то ну совсем не целые.
Делаю вывод что линейной комбинации vc[] от предыдущих vc[] для не окейных строк не существует.
На этом теоретические мысли и закончились.

Удивительная ситуация: оценить вероятность появления цепочки на порядки сложнее чем её найти.

-- 05.04.2024, 19:08 --

Впрочем нет, похоже я неправильно составил систему уравнений и вывод выше некорректен.

[Yadryara]

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

На этом теоретические мысли и закончились.

У меня пока не закончились

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

Проверил левые части переходов

А что такое левые части?
Это самые чистые кортежи для данного периода.
А где располагаются самые чистые кортежи?
Там, где меньше всего малопростых.
А где меньше всего малопростых?
Например, в самом конце периода и в начале следующего.

Показал проверку, действительно ли это так.

Обратите внимание, что рядом с пустотами, по обе стороны, наоборот, имеется очень много малопростых:

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

223092847 на 48-м                   99 03 09 11 17 23 27 29 33 39 41 47   12  c1

223092893 на  0-м                   93 99 01 07 11 13 17 23 29 31 37 41   12  c1

Видите: по 12 малопростых в кортежах при максимуме в 13. Все 12 перечислены. Указаны две последние цифры.

Но это отрывочные наблюдения. Системных я пока не делал.

Так вот, я предлагаю составить что-то типа карты расположения (гнездования) самых чистых кортежей для разных симметричных нечётных паттернов.

[vicvolf]

Чистые кортежи возникают в конце. А появление нужных кортежей происходит на более ранних шагах, когда они имеют наибольшую загрезненность. Другое дело убедиться, что нужный кортеж не один. Например, для кортежа длиной 42 это стало ясно уже при $\#5$.

[Yadryara]

vicvolf, Вы нарочно так говорите, чтобы ничего не понятно было?

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

Чистые кортежи возникают в конце.

В конце чего? Периода?

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

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

И опять "загрЕзненность". Речь идёт о каких-то грёзах?

Что за нужные кортежи? Приводите, пожалуйста, численные примеры, иначе ну решительно ничего не понятно.

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

Другое дело убедиться, что нужный кортеж не один. Например, для кортежа длиной 42 это стало ясно уже при $\#5$.

Это что ж за кортеж такой, длиной 42 ? Или Вы, как и gris перепутали длину и диаметр?

Опять-таки нет точного примера. А разве бывают нечётные симметричные кортежи диаметром 42 ? Нет, он у них кратен 12-ти. А стоит ли нам отвлекаться на другие кортежи, ежели мы с нашими ещё не разобрались?

Подытожу для кортежа 19-252.

Начиная со строчки ближайшей снизу к половине диаметра, 113#, мы знаем как считать по точным формулам.

Для того, чтобы попытаться посчитать, начиная с предыдущей строки, 109#, приходится вводить ещё одну переменную $c1g1$.

Для того, чтобы попытаться посчитать, начиная с ещё более ранних строк, от 107# и меньше, приходится вводить и ещё одну переменную $g2$.

Количество таких переменных не увеличивается вплоть до строчки ближайшей снизу к четверти диаметра, то есть 61#.

Мои соображения заключаются в сокращении перебора. В идеале: не лазить по всему периоду, а посмотреть в крошечные области и определить значения этих двух переменных. Как это сделать, я только что показал на примерах.

А дальше, если мы уже знаем значения $c1g1$ и $g2$, посчитать способом, который показан здесь.

[Yadryara]

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

Запишу проще: vc[#v+1]=2*vc[#v+2]-if((v[#v]-p)%5==0,0,2).

И если вычет для симметричных троек считается просто и равен 0 или 2, то для симметричных пятёрок уже вон сколько значений:

        d   36   48   60   60   60   60   72   72   72   84   84   84

first gap    6   18    6   12   18   24    6   12   30   12   24   30

   vychet    6    8    0   96   98   48    0    0   20  888 3168 2750

Пример расчёта вычета для паттерна [0, 30, 42, 54, 84] :

len:    5      6      7

37#:    4,   372, 23978, 

41#:  508, 58226,

372*(41-6) + 2*23978 - 58226 = 2750

[vicvolf]

Поздно было, поэтому перепутал. Имел в виду диаметр кортежа - 42. Но Вы же поняли!

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

В конце чего? Периода?

Мы двигаемся по шагам, увеличивая размер праймориала $p\#$ в приведенной системе вычетов.

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

Что за нужные кортежи? Приводите, пожалуйста, численные примеры, иначе ну решительно ничего не понятно.

Разве мы говорили о других кортежах диаметром 42?

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

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

v=[0, 6, 12, 30, 42];
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
[/code]

Кортеж имеют диаметр 42. Как понять, что в $5\#=30$ умещается 2 таких кортежа?

Здесь я задавал вопрос на эту тему. Уже на шаге $5\#$ обнаружилось 2 нужных кортежа. Естественно они не чистые. Это не так важно. Ведь задача - отыскать требуемые кортежи за минимальное количество шагов.

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

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

Стоит, так как эта общая тенденция.

-- 06.04.2024, 10:26 --

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

И опять "загрЕзненность". Речь идёт о каких-то грёзах?

Убавьте свой пыл. Могу не участвовать. У меня своих дел хватает.

[Yadryara]

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

Но Вы же поняли!

Вроде да, просто досадно, ведь прикладывались усилия специально чтобы именно эти слова не путали, причём совсем недавно.

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

Уже на шаге $5\#$ обнаружилось 2 нужных кортежа.

Ну как же два, когда 4 ?

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

Ведь задача - отыскать требуемые кортежи за минимальное количество шагов.

Разве??

Хотя, может мы говорим об одном и том же сильно разными словами? Приведите, пожалуйста, цитату с такой постановкой задачи.

Или это Вы от себя вот прям сейчас такую задачу поставили?

[vicvolf]

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

v=[0, 6, 12, 30, 42];
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

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

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

А здесь в строке $23\#$ 3234 кортежа длиной 8, 88314 кортежа длиной 7, 423378 кортежа длиной 6, 672776 кортежа длиной 5, 427231 кортежа длиной 4, 114591 кортеж длиной 3, 11960 кортеж длиной 2 и 340 кортежей длиной 1.

Здесь на 4 ошиблись, причём уже в другую сторону: максимум здесь 12, а не 8. 3234 кортежа длиной 12.

Значит первая колонка количество чистых кортежей. А в 8 колонке количество кортежей максимальной длины - 12. Теперь возьмем строку $5\#$ - там в 8 колонке стоит 2. Как Вы писали выше это количество кортежей максимальной длины - 12.
Теперь Вы пишите:

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

Ну как же два, когда 4 ?

Как понимать?

[Dmitriy40]

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

Вот прога с тремя наборами векторов. Значение нового vc выводится в самом конце.

Ужасно непонятно пишете код ... Стал разбираться, оказалось массив y[] вообще не нужен: он сначала инициализируется в vc[]*cm, а потом используется ровно в одном месте, где тут же делится на cm, т.е. можно просто подставить vc[] вместо него (и убрать деление на cm) и всё. А массив kan[] до момента вычисления kan[#vc] просто равен vc[]*(p-cm). Да, в PARI можно умножать и делить массивы на скаляры, циклы для этого не нужны. Ещё удивительно что g2[cm] может быть и ненулевым, а вот g2[cm+1] обязан быть нулевым, иначе ненулевым станет vc[cm-1], чего быть не должно, уж лучше бы использовали g2[i+2] чем такую путаницу вводить (в конце последнего цикла, про kan[i-1]).
Основной цикл вычислений, начиная с вычисления kan[#vc], тоже вроде упрощается, но уже незначительно, слишком много разных индексов, детально разбираться не стал.
Потому что дошло: для каждого p используются свои массивы c1g1[] и g2[] и как их вычислять неясно. Мне неясно. Если Вам ясно - вычислите для 61# для 19-252, сравним что они дадут для 67#. Или хотя бы объясните как вычислять, напишу прогу. Несколько последних сообщений с "размещениями" непонятно чего не пойми где объяснениями не считаю уж простите, восстанавливать идею из кучи примеров муторно. Остаётся ждать пока сами разберётесь и или напишете код или сможете нормально объяснить идею как вычислять оба ваших массива для произвольного паттерна и произвольного простого.

[Yadryara]

vicvolf
Ну так граница максимальной загрязнённости на момент 5# ещё не устаканилась на 12-ти!

Для 2# она 22, для 3# она 15, для 5# она 13 и только для 7# и дальнейших она стабилизируется на 12-ти.

И формулы расчёта этой границы приводил:

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

$c_{max}(2\#)= \dfrac{d}{2} + 1$

$c_{max}(3\#)= \dfrac{d}{2} - \dfrac{d}{6}+ 1$

$c_{max}(5\#)= \dfrac{d}{2} - \dfrac{d}{6} - \lfloor\dfrac{d}{15}\rfloor + 1$

Вот оформил более наглядно:

v=[0, 6, 12, 30, 42];

        5   6   7   8   9  10  11  12  13  14  15            S

3#                                              2            2

5#                                  2   2                    4

7#                          1   9   2                       12

11#                 1   7  34  28   2                       72

13#             2  28 160 269 111   6                      576

Так что для 5# 4 кортежа из малопростых, по два длинами 12 и 13.

И совсем недавно ведь об этом же говорил:

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

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

[Yadryara]

Dmitriy40, конечно муторно, ещё бы не муторно, задача-то сложнейшая.

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

А 47# для паттернов 5-96 не стали считать? Слишком долго?

[Dmitriy40]

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

А 47# для паттернов 5-96 не стали считать? Слишком долго?

Диаметры 96 досчситал все до окейных строк (53#).
3-108 остановился на 43#, долго.
Диаметры 120 считать не стал, долго, остановился на 37# для 3-120 и на 47# для 5-120 (который кратный 30).
Сгенерил отсутствующие в списке 4шт 5-108, запустил их счёт, оказалось потратив раз в 100 больше времени (не секунды, а десяток минут) на инициализацию стомегабайтных таблиц дальше счёт ускоряется вчетверо и хватает часов 5. Как генерить гигабайтные таблицы вообще без понятия, PARI затыкается уже на трёх десятках миллионов записей (как раз примерно стомегабайтные таблицы) и хавает больше 6ГБ памяти (из 8ГБ физических).

Теперь всё думаю как бы сгенерить таблицу около 220млн записей для 43# для 19-252 и померить каково будет ускорение относительно 41# (которое с таблицей 31млн дало жалкие 10% ускорения от 37# с таблицей 2.8млн). 220млн по 20 байт это более 4ГБ и поддерживать сортированный список такой длины - слишком медленно, а хештаблицы не дают заполнения более 60% и приходится вместо 4ГБ выделять более 7ГБ, да плюс всё равно остаётся сколько-то данных сверх хештаблиц, которые тоже надо как-то хранить - и всё это писанина кода и отладка. Пока в раздумьях заняться или плюнуть, всё равно дальше 71# посчитать не удастся, а это не такой прям уж прорыв от имеющихся 67#.
Задача в принципе стандартная (список уникальных элементов с дополнительным числом повторов), но все методы её решения плохо подходят: один слишком медленный (поддержание сортированного списка в виде двоичного дерева поиска), второй принципиально не влезает в память (битовая карта всех использованных комбинаций), третий требует прилично лишней памяти и сложной функции хеширования (хештаблицы). Хештаблицы самые быстрые (время почти не зависит от заполненности), но нужна хорошая хеширующая функция, а простые и быстрые дают слишком частые дубли, что требует увеличения памяти. В общем гемор всё писать и подбирать параметры. И непонятно ради чего, один только 71# получить ... толку то от него.

Так же раздумываю будет ли польза от получения одного-двух левых значений для 113#, если их всё же получится вычислить каким-то чудом (а мысли по этому поводу есть, хотя пока и не слишком практичные). И выходит что пользы нет, нужны и остальные значения.

[vicvolf]

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

И формулы расчёта этой границы приводил:

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

$c_{max}(2\#)= \dfrac{d}{2} + 1$
$c_{max}(3\#)= \dfrac{d}{2} - \dfrac{d}{6}+ 1$
$c_{max}(5\#)= \dfrac{d}{2} - \dfrac{d}{6} - \lfloor\dfrac{d}{15}\rfloor + 1$

Можете доказать?