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

[gris]

Досадная, но несущественная оппечатка вкралась во вчерашний текст. Конечно, надо было написать
45% кортежей имеют valids 2.
35% кортежей имеют valids 3.
15% кортежей имеют valids 4.
Исследования продолжаются!

[Yadryara]

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

несущественная оппечатка вкралась во вчерашний текст

Это не так называется. Больше подходит вот это:

natalya_1 в сообщении #1599811 писал(а):

Опять описок налепила...

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

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

Здесь остатки по модулю 3 ? Очепятка? Или по каким-то причинам удобно считать остатками и 0, и 3?

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

То есть, 100000 кортежей 15/228 разместились на интервале(a,b) длиной a-b.

А разве не $b - a$? Очепятка?

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

Последняя строка - количество кортежей с валидсами от 0 до 15.

С учётом нынешней поправки — от 2 до 15? И два нуля справа лишние?

Я и сам порой говорил паттерны вместо кортежи. И/или наоборот.

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

Исследования продолжаются!

У меня тоже. Но пока лень рассказывать.

[gris]

самая коварная накладка в прямом смысле произошла с определением числа повторений паттернов в сплошном массиве кортежей 15-228. не обнаружено повторений среди 4 млн кортежей. а это значит, что вероятность встретить кортеж с любым допустимым по 17# паттерном не так уж сильно зависит от паттерна. от диапазона поиска о, да! но при заданном интервале количества найденных кортежей не зависит и от диапазона. поэтому коды увы бесполезны

[Yadryara]

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

Ничегошеньки пока не понял.

Начинаю более детально знакомиться с той прогой.

Взять хотя бы вот эту строчку:

am=vecextract(vector(p-1,i,fromdigits(Vecrev(apply(t->(t+i)%p>0,a)),2)),m);

Ну вот ни одной из 5 команд (функций) я не знал! Пришлось раскручивать в обратную сторону: от apply к vecextract...

Заметил, что в самом начале не сходится с формулой:

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

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

Поправил $c \to len$.

Так что у Вас лишние элементы:

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

Программа:

ww=vector(v[#v]/2,i,Map());

А надо бы

ww=vector(v[#v]/2+2-#v,i,Map());

[Dmitriy40]

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

Так что у Вас лишние элементы:

Да, но короткие или пустые Map отрабатываются моментально, так что на скорость работы не влияют. А уж на правильность тем более. Зато не будет проблем что где-то не так округлил или забыл добавить единицу или ещё какие тонкости, всегда проще выделить память с запасом (если не слишком много и не тормозит). Можно было даже на два не делить.

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

Ну вот ни одной из 5 команд (функций) я не знал!

Да ладно, уж vector точно знали, да и Vecrev наверняка, и fromdigits мелькала уже сколько раз.
А так да, они и писались с конца, получал правильный промежуточный результат, потом оборачивал в следующую конструкцию, снова добивался правильности, и так по кругу.

-- 03.05.2024, 13:11 --

Кстати следующая конструкция mapput(ww[#ww],2^#a-1,1); тоже неправильная если размер #ww больше минимально необходимого. Но так как 3# гарантированно снижает загрязнённость, то этот элемент гарантированно станет пустым и тогда без разницы куда именно сунуть затравку, главное не слишком низко чтобы не пересечься с новыми элементами при обработке 3#. Конец массива выглядит подходящим, хоть и неправильным, правильнее было бы в ww[#a+1] сунуть (собственно такого размера ww[] и надо).

[Yadryara]

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

Да, но короткие или пустые Map отрабатываются моментально, так что на скорость работы не влияют.

Ну вот я думал-думал, и так и решил, что это на всякий случай добавлено. То самое неудобство вникания в чужой код.

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

Да ладно, уж vector точно знали, да и Vecrev наверняка, и fromdigits мелькала уже сколько раз.

Обычный vector знал, а про тот, который с 3 аргументами только смутно что-то припоминал.

Много что много где мелькает... Но вроде бы не у меня в коде.

Ну вроде разобрался что к чему:

(Немало цифр)

p = 2

Невозможный остаток по модулю 2 для 0-й позиции паттерна [0, 12, 24] :

        0, 12, 24
+       0,  0,  0
_________________
        0  12  24
mod 2   0   0   0


Единственный годный остаток по модулю 2 для 0-й позиции этого паттерна:

m = [0, 1] - [0]   =                                               [1]


Все возможные позиции грязных чисел для этого же паттерна:

a = [2, 4, 6, 8,10,14,16,18,20,22]

              2, 4, 6, 8,10,14,16,18,20,22
+   1   
__________________________________________
              3  5  7  9 11 15 17 19 21 23
mod 2 > 0 ?   1  1  1  1  1  1  1  1  1  1 --> revers --> 1023

Одна расстановка грязных чисел: am = [1023]



p = 3

Невозможный остаток по модулю 3 для 0-й позиции паттерна [0, 12, 24] :

        0, 12, 24
+       0,  0,  0
_________________
        0  12  24
mod 3   0   0   0


Все годные остатки по модулю 3 для 0-й позиции этого паттерна:

m = [0, 1, 2] - [0]   =                                [1, 2]

              2, 4, 6, 8,10,14,16,18,20,22
+   1   
__________________________________________
              3  5  7  9 11 15 17 19 21 23
mod 3 > 0 ?   0  1  1  0  1  0  1  1  0  1 --> revers --> 726

              2, 4, 6, 8,10,14,16,18,20,22
+   2   
__________________________________________
              4  6  8 10 12 16 18 20 22 24
mod 3 > 0 ?   1  0  1  1  0  1  0  1  1  0 --> revers --> 429

Две расстановки грязных чисел: am = [726, 429]



p = 5

Невозможные остатки по модулю 5 для 0-й позиции паттерна [0, 12, 24] :

        0, 12, 24
+       0,  3,  1
_________________
        0  15  25
mod 5   0   0   0


Все годные остатки по модулю 5 для 0-й позиции этого паттерна:

m  = [0, 1, 2, 3, 4] - [0, 1, 3]        =        [2, 4]

              2, 4, 6, 8,10,14,16,18,20,22
+   2   
__________________________________________
              4  6  8 10 12 16 18 20 22 24
mod 5 > 0 ?   1  1  1  0  1  1  1  0  1  1 --> revers --> 887


              2, 4, 6, 8,10,14,16,18,20,22
+   4   
__________________________________________
              6  8 10 12 14 18 20 22 24 26
mod 5 > 0 ?   1  1  0  1  1  1  0  1  1  1 --> revers --> 955

Две расстановки грязных чисел: am = [887, 955]


                  2, 4, 6, 8,10,14,16,18,20,22
______________________________________________
+ 1 mod 3 > 0 ?   0  1  1  0  1  0  1  1  0  1 --> revers --> 726  
bitand
+ 2 mod 5 > 0 ?   1  1  1  0  1  1  1  0  1  1 --> revers --> 887
______________________________________________
                  0  1  1  0  1  0  1  0  0  1 -------------> 598

Только пока не понял для чего реверс нужен. На виндовском калькуляторе в режиме "Программист" проверял bitand. Там это просто кнопка "And".

[Yadryara]

Хммм...

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

В строке с am=... остатку m[11]=24 соответствует число/маска am[11]=324517315718368994658257656078335, в котором нулевых битов всего 4шт: 13, 39, 64, 90, что соответствует числам 34, 92, 150, 208 в a[], именно эти числа могут вырезаться (если они там ещё оставались) из массива a[] при обработке остатка 24.

И это делается вот этой командой?

apply(t->(t+i)%p>0,a)

То бишь для всех 108 битов делается суммирование и проверка по модулю $p=29$ вместо того, чтобы обнулить всего лишь 4 или 5 битов с шагом $2p=58$ ? Неужели так быстрее ??

[Dmitriy40]

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

Только пока не понял для чего реверс нужен. На виндовском калькуляторе в режиме "Программист" проверял bitand. Там это просто кнопка "And".

bitand это и есть and, только именно побитовый, не абы какой ещё (например & или &&).
Vecrev нужен вот почему: apply выдаёт элементы в порядке следования, слева направо, так что первому элементу массива соответствует первая цифра 0/1 в массиве для fromdigits, но для него первая цифра это старшая, а для vecextract за первый элемент отвечает младший бит (младшая цифра числа). Но биты в числе переставить сложнее чем развернуть массив, потому и Vecrev.
На самом деле Vecrev тут похоже не нужен - пока не используется vecextract от результата fromdigits (маски), например для проверки или вывода списка или ещё чего. Видимо остался как раз от отладки, когда сравнивал списки фильтрованного a[] по маске и правильного.

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

То бишь для всех 108 битов делается суммирование и проверка по модулю $p=29$ вместо того, чтобы обнулить всего лишь 4 или 5 битов с шагом $2p=58$ ? Неужели так быстрее ??

Нет, разумеется это не быстрее. Но во первых это выполняется лишь раз для каждого простого и делает лишь p*#a итераций (p в vector и #a в apply), это суммарно всего сотня-две тысяч раз, что слёзы. Во вторых с постоянным шагом можно сделать если бы массив a[] был регулярный, однако это совсем не так, оттуда выкинуты часть чисел (весь v[]), что учитывать в шаге можно, но сложно и лень. В третьих, да, можно сделать ему setminus со списком x,x+2p,x+4p,x+6p и так далее, но для 3# этот список будет из 41-42 элементов, что в общем тоже не проблема (vector(v[#v]/6,i,x+(i-1)*2*p) или bitand(...,2^(v[#v]/6)-1-vecsum(2^vector(v[#v]/6,i,x+(i-1)*2*p))) если маской), но блин а если ошибусь, да и как начальное число x вычислять, да и сомневаюсь что такие конструкции окажутся понятнее, а конструкция ((t+i)%p понятна и надёжна.
К тому же тут делается немало лишнего - сначала вычисляются все маски по всем вообще остаткам (vector до p-1) и лишь потом из них отбираются (vecextract) лишь допустимые, понятно что выгоднее наоборот, вычислять маски только для допустимых остатков, но видимо думать и тут было лень (потому что 2e5 итераций это доли секунды и на них плевать).
Так что тут соображения скорее понятности (и соответственно надёжности) и удобства, чем скорости. Сделать же можно по разному.

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

То самое неудобство вникания в чужой код.

Я предлагал подробно рассказать что и как.

[Yadryara]

Ура! Я таки прорвался через дебри и объединил свой ещё один способ вычисления cg с Вашей прогой и удивительно быстро посчитал много cg !

Вот пока суммы cg и времена для последних этапов:

--> 37# : sum =        15396480, time:                 6,459 ms

--> 41# : sum =       242352000, time:                28,789 ms

--> 43# : sum =      6015544704, time:         1 min,  5,941 ms

--> 47# : sum =    237908880000, time:         4 min,  1,077 ms

--> 53# : sum =   2299785840000, time:                13,666 ms

--> 59# : sum = 368802020160000, time:         6 min, 22,960 ms

По-прежнему прошу не сообщать мне новых результатов! Я как раз обсчитываю 11-144. Грядёт сверка. Для 53# во времени опечатки нет!

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

это суммарно всего сотня-две тысяч раз, что слёзы.

Ну да, я уже позже заметил, что команда-то во внешнем цикле.

[Yadryara]

Досчитал:

--> 37# : sum =             15396480, time:                 6,459 ms

--> 41# : sum =            242352000, time:                28,789 ms

--> 43# : sum =           6015544704, time:         1 min,  5,941 ms

--> 47# : sum =         237908880000, time:         4 min,  1,077 ms

--> 53# : sum =        2299785840000, time:                13,666 ms

--> 59# : sum =      368802020160000, time:         6 min, 22,960 ms

--> 61# : sum =    12690740943720000, time:         2 min, 28,247 ms

--> 67# : sum =   801520480656000000, time:         8 min,  7,800 ms

--> 71# : sum = 75243403055315880000, time:        13 min,  9,380 ms

--> 73# : sum =                    0 

Неприятной особенностью найденного алгоритма является счёт с нуля для каждого p#. То есть до 71# я добрался примерно за 2 с половиной часа, перезапуская прогу каждый раз для всех финальных значений 37#, 41#, ... , 71# , с различными включениями в паттерн.

Только с нуля до 71# комп справился почти ровно за час.

Dmitriy40 у Вас сколько считался 1-й паттерн 11-144 в пересчёте на 1 поток?

[Dmitriy40]

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

Грядёт сверка.

Вот только у меня нет vecsum(cg) и сверить его не можем, у меня есть только vecsum(vc) (и конечно сам массив vc), которая и называется sum.

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

Только с нуля до 71# комп справился почти ровно за час.
Dmitriy40 у Вас сколько считался 1-й паттерн 11-144 в пересчёте на 1 поток?

Они и считались в один поток, на PARI, времена на каждое простое (не с начала):
29#: 1,595 ms
31#: 15,624 ms
37#: 1min, 50,439 ms
41#: 6min, 36,976 ms
43#: 15min, 24,531 ms
47#: 24min, 4,339 ms
53#: 30min, 33,017 ms
59#: 34min, 37,949 ms
61#: 35min, 28,376 ms
67#: 37min, 26,759 ms
71#: 37min, 24,168 ms
73#: 37min, 54,155 ms
Общее время 4ч22м (3ч44м по 71#). В принципе расчёт любого одного последнего значения (например 73#) можно и ускорить (вместо модификации ww[] считать сразу vc[]), но смысла не вижу.
Очень интересно как это у Вас та же программа досчитала до 71# всего за час. Или что-то у меня с PARI явно не то в плане скорости (бесит т.к. не понимаю причины).

[Yadryara]

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

Вот только у меня нет vecsum(cg) и сверить его не можем, у меня есть только vecsum(vc) (и конечно сам массив vc),

Вот сам массив vc и предлагаю сверить. Но пока застрял немного. Пару ошибок у себя нашёл, одну исправил, со 2-й разбираюсь...

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

Очень интересно как это у Вас та же программа досчитала до 71# всего за час. Или что-то у меня с PARI явно не то в плане скорости (бесит т.к. не понимаю причины).

Видимо потому, что я укоротил массив a[] на единицу. Стартовая длина 61, а не 62. Соответственно, для 19-252 не 108, а 107.

[Dmitriy40]

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

я укоротил массив a[] на единицу. Стартовая длина 61, а не 62. Соответственно, для 19-252 не 108, а 107.

Это максимум проценты, уж точно не трёхкратно.
Почему-то у меня страшно тормозят любые операции с памятью (выделение и освобождение массивов и переменных), а тут их полно.

[Yadryara]

Ну вот в этом месте уже можно сверить. Пока не устранённое расхождение:

v=[0, 12, 30, 42, 54, 72, 90, 102, 114, 132, 144];

lmax = 31

31# --> 37#                                                           Sum

vc = [   5617466,  3288286,  1227208,  252110,  24342,   980 ]   27648000 
                                                           *
                                                           6
                                                           +
cg = [   3035144,  1785372,   694194,  150118,  14628,   560 ]   15396480
                                                           +
g2 = [   4423660,  2784734,  1138406,  263552,  30854,  1540 ]   19258752
                                                          <> 
vc = [ 118359724, 58406136, 18258392, 3198032, 274818, 10080 ]  718848000

Чтобы получить $10080$ надо ещё раз прибавить $560+1540$. И $1540-560=980$ Совпадение?

А у Вас какие значения здесь?

[Dmitriy40]

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

А у Вас какие значения здесь?

31#: 0, 0, 0, 0, 0, 0, 10, 396, 6868, 69358, 387838, 1378512, 3278384, 5495890, 6620352, 5617466, 3288286, 1227208, 252110, 24342, 980, sum=27648000
37#: 0, 0, 0, 0, 0, 64, 3608, 69060, 758646, 4941602, 20479682, 57342942, 112866628, 160128298, 163750288, 118359724, 58406136, 18258392, 3198032, 274818, 10080, sum=718848000