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

[vicvolf]

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

И что же нам делать? Звать спецов по ТЧ? Лично я уже звал. Или самим разбираться...

Конечно взять учебник и посмотреть. Вы же здесь в теме занимаетесь теорией. А как же заниматься теорией, не зная основ

gris в сообщении #1636726 писал(а):

vicvolf, мы можем начать перебор кортежей с [0,1,2].
У кортежа полная система вычетов по модулю 3: [0,1,2].
При переходу к следующему кортежу вида (2,2) происходит сдвиг на 1, при этом система вычетов остаётся полной. Так что 0 обязательно присутствует.Я это и имел в виду.
Хотя я, например, слабо разбираюсь в ТЧ и поэтому не лезу

Мы рассматриваем кортежи, которых бесконечное количество, поэтому кортежи, начинающиеся с числа $2$ мы не рассматриваем.

gris в сообщении #1636752 писал(а):

Например, $ S_3([3,5,7])=[0,1,3]; S_3([3,5,11])$

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

gris в сообщении #1636752 писал(а):

Например
$S_7([5,7,13,19, 31, 43, 61])= [0,1,2,3,4,5,6] $

Таких кортежей тоже конечное количество и их надо исключать. Я для начала хотел рассмотреть кортежи длиной 5. Дело в том, что все тройки простых, входящих в такой кортеж надо тоже проверять сначала не образуют ли они ПСВ по модулю 3.

[Dmitriy40]

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

то программы будут считать быстрее.

Это вряд ли: не знаю как у gris, у меня же перебор идёт всегда только по разрешённым остаткам для каждого простого. А для ПСВ таковых нет и потому перебор не просто не ускоряется, он вообще даже не запускается:

T:\>echo x:5 7 13 19 31 43 61|patterns_check18.exe
n=7, max=56, x: 0 2 8 14 26 38 56
3:2, n=1, d=1 / 6
5: n=0, d=0 / 30
ERROR! Not avaible modules.

По модулю 5 уже не проходит.
Начальные решения меня не интересуют, их легко найти тупым перебором.

[vicvolf]

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

T:\>echo x:5 7 13 19 31 43 61|patterns_check18.exe
n=7, max=56, x: 0 2 8 14 26 38 56
3:2, n=1, d=1 / 6
5: n=0, d=0 / 30
ERROR! Not avaible modules.

По модулю 5 уже не проходит.
Начальные решения меня не интересуют, их легко найти тупым перебором.

Это можно сделать только с помощью программы. Иначе надо вручную проверять $C_7^5=42$ кортежа длиной 5. А до этого надо проверить $C_7^3=840$ кортежей длиной 3.

[Dmitriy40]

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

Это можно сделать только с помощью программы.

Что именно "это"?
Если полноту системы вычетов, то достаточно n (длина кортежа) делений (точнее взятия остатка от деления) для каждого простого числа максимум до половины диаметра паттерна, иногда хватит и меньшего количества делений.
Для кортежа (или паттерна) из цитаты длиной 7 достаточно 7 делений на 3 и 5 делений на 5, всего 12 делений, и 12 операций вычёркивания чисел из короткого списка. Кортежи (паттерны) перебрать не обязательно.

[vicvolf]

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

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

Это можно сделать только с помощью программы.

Что именно "это"?
Если полноту системы вычетов, то достаточно n (длина кортежа) делений (точнее взятия остатка от деления) для каждого простого числа максимум до половины диаметра паттерна, иногда хватит и меньшего количества делений.
Для кортежа (или паттерна) из цитаты длиной 7 достаточно 7 делений на 3 и 5 делений на 5, всего 12 делений, и 12 операций вычёркивания чисел из короткого списка. Кортежи (паттерны) перебрать не обязательно.

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

[Dmitriy40]

(Оффтоп)

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

но все равно для длинных кортежей вручную это невозможно.

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

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

Это называется определением "проходимости" кортежа данной структуры,

Так чем знание правильного названия поможет в программах если в них и так это уже реализовалось само собой? Или это лишь подводка к какому-то красивому эффективному результату из ТЧ? Не томите.

[Yadryara]

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

Иначе надо вручную проверять $C_7^5=42$ кортежа длиной 5. А до этого надо проверить $C_7^3=840$ кортежей длиной 3.

А что такое у вас $C_7^5=42$ и $C_7^3=840$ ?? Числа сочетаний?

Но число сочетаний из 7 по 3 равно всего лишь $35$ , а никак не $840$ !!

А число сочетаний из 7 по 5 равно $21$ , а не $42$.

[Yadryara]

Сегодня тоже день прекрасных новостей по теме.

Я таки научился вычислять и c1g1[], и g2[]. Пока вычислял и проверял для самых простых паттернов. Но уже понятно, как вычислять и для более сложных.

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

Вот здесь, например, новый метод может помочь:

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

53# посчиталось, файл обновил.

Это для паттерна [0, 30, 60, 90, 120]. Но добраться-то надо было хотя бы до 59#. Так вот, я теперь знаю как на периоде 53# вычислить c1g1[] и g2[], а затем подставить эти массивы в мою программу и моментально вычислить 59#.

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

Короче пока прорыв не ощущается, надо вникать то ли это что нужно и если да, то что как считается.

А я ощущаю прорыв. Потому что понимаю, что и как считается.

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

Сейчас у меня гораздо более продвинутый вариант. И с перемножением флагов и с учётом не только обычной, но и широкой вилки. Теперь я могу вычислять c1g1[] и g2[] аж от $\frac16$ диаметра.

И именно на их вычислении я был сосредоточен, а vc[] вычислял совсем примитивным способом. А Вы многократно совершенствовали способы вычисления vc[].

Так что можно зайти и с другого конца: не Вы будете пытаться вникнуть в мои проги, а я попытаюсь вникнуть в Вашу и в неё встроить новые. Вы говорили, что есть реализация на PARI. Ну так в студию её, лучше тот вариант, что для [0, 30, 60, 90, 120].

[Yadryara]

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

А как же заниматься теорией, не зная основ

Ну так а кто не знает основ-то?

Ну вы что так и не видите, что люди говорят об одном и том же? Разве же обязательно каждый раз говорить КТО и ПСВ, чтобы понимать друг друга? Арифмост, система сравнений, система вычетов, запреты по модулям — это всё об одном и том же.

VAL в сообщении #1548967 писал(а):

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

VAL в сообщении #1548056 писал(а):

 i%37!=17

Что сие значит?

$i$ не сравнимо с 17 по модулю 37

Меня учили делению с остатком во 2-м, кажется, классе. То же самое можно ведь сказать другими словами:

Не подходят числа, которые дают остаток 17 при делении на 37. То есть $17, 54, 91, ...$

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

Всё, внутренний цикл вообще не нужен, как и КТО.

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

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

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

Ну так а вы тему-то читаете? Эта проверка выполняется элементарно, на коленке:

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

В принципе несложно программку на PARI написать по генерации таких паттернов: начинаем от центра и расставляем числа с шагом 6 симметрично, проверяем по остаткам. Вот, буквально на коленке:

? for(a=1,8, for(b=a+1,8, vv=[-b,-a,0,a,b]*6; forprime(p=5,13, if(#setminus(vector(p,i,i-1), Set(vv%p))==0, next(2))); print(vv); ));
[-24, -6, 0, 6, 24]
[-30, -6, 0, 6, 30]
[-36, -6, 0, 6, 36]
[-18, -12, 0, 12, 18]
[-30, -12, 0, 12, 30]
[-42, -12, 0, 12, 42]
[-48, -12, 0, 12, 48]
[-30, -18, 0, 18, 30]
[-42, -18, 0, 18, 42]
[-48, -18, 0, 18, 48]
[-30, -24, 0, 24, 30]
[-36, -24, 0, 24, 36]
[-36, -30, 0, 30, 36]
[-42, -30, 0, 30, 42]
[-48, -30, 0, 30, 48]
[-48, -42, 0, 42, 48]

И так далее. Простые проверять надо лишь до длины паттерна, не диаметра (впрочем можно и до диаметра, тут же всё быстро).
Если хочется паттерн в обычном виде, то печатаем не vv, а vv+vector(#vv,i,-vv[1]).

И не только проверка выполнена безо всякого упоминания ПСВ, но ещё и полный список подходящих кортежей до 100 выдаётся.

Так что это не мы основ не знаем, это вы в тему никак не въедете.

[gris]

Ничего, что я невтему
Посмотрел, что там с центральными подпаттернами 19-252.
Интересно с 9-108. Нашёл все приближения с прибитыми краями. Коды тем же способом в pt[2..8]. Их 128 штук, valids изменяется от 2 до 9.
Спектр:
[0 2 5531; 34 4 5903; 2 3 7349; ... 119 8 445455169; 95 8 623911909; 127 9 909894593]
(code, valids, первое появление)
Интересно, что последний код появляется последним и с большим отрывом. Вот график появления кодов.



По горизонтали очерёдность очередного кода, а по вертикали — логарифм места его появления.
Да там же линейная зависимость Ожидаемо более раннее появление кодов с маленькими valids (цвет меняется о красненького к синенькому).
А вот бы код считать по-другому, чтобы valids монотонно (нестрого, ессно) возрастал(а,о). Помечтаю об этом. Идей много

[vicvolf]

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

А что такое у вас $C_7^5=42$ и $C_7^3=840$ ?? Числа сочетаний?

Да, это в уме подсчитал с ошибкой.

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

Ну вы что так и не видите, что люди говорят об одном и том же? Разве же обязательно каждый раз говорить КТО и ПСВ, чтобы понимать друг друга? Арифмост, система сравнений, система вычетов, запреты по модулям — это всё об одном и том же.

Можно конечно говорить на разных языках, но Вавилонскую башню не построишь https://ru.wikipedia.org/wiki/%D0%92%D0 ... 0%BD%D1%8F

[vicvolf]

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

Ну так а вы тему-то читаете?

Нет. Это не очень интересно. Может быть только с точки зрения вычислений и тема явно должна быть в другом разделе. Общих математических вопросов здесь точно нет.

[Dmitriy40]

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

Вы говорили, что есть реализация на PARI. Ну так в студию её, лучше тот вариант, что для [0, 30, 60, 90, 120].

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

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

Теперь я могу вычислять c1g1[] и g2[] аж от $\frac16$ диаметра.

Как я понимаю это позволяет вычислить 43# и далее для 19-252? Так расскажите что Вам для этого нужно, ведь 41# вычислить можно, с трудом (PARI надо до 7ГБ памяти), но реально. А вот следующие - уже только перебором (что на асме сильно быстрее).
Возможно рассказать мне про формулы чтобы я их встроил в свою прогу будет быстрее чем Вам разбираться в моей, хотя по моему там всё несложно, просто идея немного другая (причём на неё натолкнули Вы же, хоть и косвенно). И на самом деле прога вычисляет вовсе не vc[], а аккуратно всё множество всех встретившихся комбинаций содержимого массива a[] (грязных кортежей) - суммирование этого множества и даёт искомый vc[].

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

Так вот, я теперь знаю как на периоде 53# вычислить c1g1[] и g2[], а затем подставить эти массивы в мою программу и моментально вычислить 59#.

Вопрос можете ли Вы вычислить столь же моментально (или хотя бы не полным перебором по остаткам на 61) следующий 61# (и следующий, и следующий). Добавка лишь одного шага проблему вычисления 19-252 не снимает, я на асме могу добавить 4-5-6 шагов за разумное время, а надо добавить 11 шагов (от vc[] для 67#) или 17 шагов (от ww[a[]] для 41#).

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

и тема явно должна быть в другом разделе. Общих математических вопросов здесь точно нет.

Мне не удалось убедить в этом модератора.

[Yadryara]

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

Добавка лишь одного шага проблему вычисления 19-252 не снимает

Да я в курсе.

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

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

Так что это именно вычисление на шаг раньше. Пока так.

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

Можно ли досконально рассчитать по формулам кортеж малопростых по чистоте, начиная за шаг до четверти диаметра? Непонятно.

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

Ответа, на первый вопрос всё ещё нет.

А вот на второй — да, можно. Проверено уже на разных паттернах.

С разных точек стартовал и получал на следующем шаге правильные vc[]. В последний раз для того самого паттерна 5-120 сделал шаг от 19# (в 6 раз меньше диаметра!) до 23#.

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

Как я понимаю это позволяет вычислить 43# и далее для 19-252?

Смотря какой смысл Вы в это вкладываете.

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

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

Так какие формулы-то?

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

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

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

Так вот, я теперь знаю как на периоде 53# вычислить c1g1[] и g2[], а затем подставить эти массивы в мою программу и моментально вычислить 59#.

Объединил две проги в одну. Могу показать, да. Но Вы же ругаться опять будете.

Широкую вилку с шагом между зубцами $4p$, а не $2p$ нужно дополнительно обсчитывать как раз, когда $p<\frac{d}4$. И это в ней реализовано.

Прежде чем 19-252, предлагаю всё же сделать шаг $51\#\to53\#$ для 5-120, ещё раз проверить, а затем уже $53\#\to59\#$.

[Dmitriy40]

Yadryara
Я чего-то не понимаю.
Вы говорите имея некие данные для 41# можно вычислить vc[] для 43# быстрее чем перебором 24 разрешённых остатков, так?
И это (более быстрое вычисление одного шага) работает для любых простых с 43# по 113#, так?
Тогда у меня вопрос сколько надо данных (количество и размеры массивов) для каждого простого, может они все влезут в память? И можно будет вычислять по простым подряд, не перебором вглубь. Последняя моя программа это и делает, но быстро утыкается в память (больше 30млн элементов в 9ГБ Map() и PARI дохнет).
Чтобы Вам не разбираться в моей программе возможно будет проще объяснить мне как считать ваши массивы. Хоть реальным кодом, хоть рассказом идеи. Ругаться может и буду, но если прога позволит посчитать давно искомое - то и прекрасно, сам приведу в нормальный вид (и оптимизирую если увижу возможности). А может там всё так просто что на асм хорошо ложится, тогда вообще счастье.