касательно кортежей из простых чисел

[gris]

Рассматриваются симметричные кортежи нечётной длины из последовательных простых чисел.
Паттерны кортежей имеют несколько вариантов записи
[0, 12, 30, 36, 42, 60, 72] в виде отклонения от первого элемента;
[-36, -24, -6, 0, 6, 24, 36] в виде отклонения от среднего элемента;
[12, 18, 6, 6, 18, 12] в виде вектора разностей соседних элементов.
По этому паттерну есть много кортежей, например
97967: [-36, -24, -6, 0, 6, 24, 36]
Но есть и недопустимые паттерны, по которым не существует соответствующих им кортежей.
Например, [-30, -24, -6, 0, 6, 24, 30].
Проверка на допустимость паттерна проводится известным способом

{p= [-30, -24, -6, 0, 6, 24, 30]; print(p);
v=vector(#p,i,p[i]-p[1]); print(v);
wm=43;
wt=1;
forprime( w=2,wm, ws=w-1;
   for (s=1,w-1,
      for ( i=2,#p, if( (s+v[i])%w==0, ws--; break ) );
   ); wt=wt*ws; if(wt==0, wf=w; break);
);
if( wt!=0, print("good"),print("bad on ", wf));}

[-30, -24, -6, 0, 6, 24, 30]
[0, 6, 24, 30, 36, 54, 60]
bad on 7

Проверка производится на первые простые числа от 2 до wm. Проверка закончилась на 7. Это значит, что любой кортеж по этому паттерну будет содержать составное число, кратное 7, что делает паттерн негодным.
Бытует мнение, что проверку можно производить до простого числа wm, не большего длины паттерна.
Вероятно, есть какие-то теоретические обоснования.
Пока же я провёл лишь испытания на случайно сгенерированных симметричных паттернах с отклонениями от центрального элемента, кратными 6. Известно, что кортежи рассматриваемого вида имеют такое свойство непреодолимой силы.
Вот некоторые результаты:

            2  3     5      7     11    13   17  19
03 [1000000]
05 [652547, 0, 0, 347453]
07 [330281, 0, 0, 607085, 62634]
09 [149348, 0, 0, 769361, 81291]
11 [ 62458, 0, 0, 864839, 70715, 1988]
13 [ 23992, 0, 0, 921521, 51518, 2580, 389]
15 [  8654, 0, 0, 954173, 34496, 2178, 499]
17 [  2909, 0, 0, 973184, 22230, 1314, 359,  4]
19 [   963, 0, 0, 984378, 13688,  756, 209,  5, 1]
 

Хотелось бы отыскать такой паттеpн длины p, у которого проверка отрицательно срабатывает на wf > p.

[EUgeneUS]

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

Вероятно, есть какие-то теоретические обоснования.

Похоже на то.

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

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

Рассмотрим вот такую нотацию:

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

[0, 12, 30, 36, 42, 60, 72] в виде отклонения от первого элемента;

Остаток от деления первого элемента на некое нечетное число $p$ будет пробегать все натуральные числа $[0, p-1]$.
Остатки от деления остальных элементов на тоже самое число $p$ будут определяться остатком первого элемента и "сдвигом".
Требование - чтобы существовало такое счетное множество первых элементов, чтобы остаток никакого элемента не был равен нулю. В противном случае, паттерн "бракованный".
Если $p$ больше длины паттерна, то это требование выполняется автоматически.

[Dmitriy40]

Рассмотри для примера кортеж $[x,x+a,x+b,x+c,x+d]$ с паттерном $[0,a,b,c,d]$. По модулю $7$ он при любом $x$ может дать не более 5-ти запрещённых остатков из 7-ми: если какое-то из чисел разделится на $7$. Это прекрасно видно если взять кортеж $[x,x+1,x+2,x+3,x+4]$, или в любом другом порядке заменить числа $x+\{0,a,b,c,d\}$ на $x+(\{0,a,b,c,d\} \bmod 7)$. Всегда обязательно останется минимум 2 варианта остатка $x \bmod 7$, при которых ни одно из чисел кортежа не делится на 7 - т.е. кортеж (и соответствующий паттерн $[0,a,b,c,d]$) допустим по модулю $7$.
Аналогично и с любым другим простым модулем больше длины паттерна/кортежа.
Соответственно паттерн не может быть недопустимым по любому простому модулю больше длины паттерна. Так что контрпримера не найдёте.

[gris]

я люблю наглядность
вот тот паттерн с распечаткой подробностей
[-30, -24, -6, 0, 6, 24, 30]
[0, 6, 24, 30, 36, 54, 60]

w=5
s=1: 2, 0, 1, 2, 0, 1
s=2: 3, 1, 2, 3, 1, 2
s=3: 4, 2, 3, 4, 2, 3
s=4: 0, 3, 4, 0, 3, 4

w=7
s=1: 0, 4, 3, 2, 6, 5
s=2: 1, 5, 4, 3, 0, 6
s=3: 2, 6, 5, 4, 1, 0
s=4: 3, 0, 6, 5, 2, 1
s=5: 4, 1, 0, 6, 3, 2
s=6: 5, 2, 1, 0, 4, 3

w=11
s=1: 7, 3, 9, 4, 0, 6
s=2: 8, 4, 10, 5, 1, 7
s=3: 9, 5, 0, 6, 2, 8
s=4: 10, 6, 1, 7, 3, 9
s=5: 0, 7, 2, 8, 4, 10
s=6: 1, 8, 3, 9, 5, 0
s=7: 2, 9, 4, 10, 6, 1
s=8: 3, 10, 5, 0, 7, 2
s=9: 4, 0, 6, 1, 8, 3
s=10: 5, 1, 7, 2, 9, 4

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

[Dmitriy40]

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

вот здесь разгадка?

Ну, и здесь тоже:
вот по модулю 5 допустимы два остатка, остальные дают составные числа в паттерне (0 в строке);
по модулю 7 допустимых остатков нет, каждый даёт составное число в паттерне (0 в строке);
по модулю 11 допустимы 4 остатка (без 0 в строке).
Плюс Вы почему-то забыли остаток s=0 - да, он недопустим ни по какому простому потому что тогда составным будет прямо первое же число паттерна (или центральное, смотря где у вас ноль в паттерне), однако для полноты картины он нужен.

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

а почему паттерны проверяют до гораздо больших значений? или проверяют что-то другое?

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

Но вообще говоря не паттерны проверяют на допустимость по большим модулям, а начальные числа проверяют на допустимость, могут ли с них начинаться паттерны, ведь далеко не любой остаток по простому модулю допустим для начального числа, например из всего семи разных остатков допустимыми может оказаться скажем 2 или 3. Или вообще 1, если паттерн длиннее 5.
А для простых больше диаметра паттерна недопустимыми оказываются всегда ровно #pat (длина паттерна) остатков - на какое число паттерна попадёт сито из повтором этого простого.
А в промежутке от длины паттерна до его диаметра ситуация может быть весьма разнообразной, вплоть до "инверсии", когда для большего простого допустимы меньшее количество остатков. Всё зависит от конкретного паттерна.
Возможно Вы несколько спутали допустимость паттернов (достаточно проверить по простым только до длины паттерна) и допустимость начального числа кортежа/цепочки/решения (можно проверять по простым вплоть до корня из конца проверяемого диапазона).

[gris]

Провёл небольшой эксперимент. Из 10 млн 19-паттернов набралось 16, которые проявляют свою недопустимость только при проверке по модулю 19.
Вот один из них с подробностями проверки.

[-282, -258, -210, -180, -138, -120, -78, -42, -12, 0, 
12, 42, 78, 120, 138, 180, 210, 258, 282]
[0, 24, 72, 102, 144, 162, 204, 240, 270, 282,
294, 324, 360, 402, 420, 462, 492, 540, 564]
w= 17
s=  0:  7  4  0  8  9  0  2 15 10  5  1  3 11 12  3 16 13  3
s=  1:  8  5  1  9 10  1  3 16 11  6  2  4 12 13  4  0 14  4
s=  2:  9  6  2 10 11  2  4  0 12  7  3  5 13 14  5  1 15  5
s=  3: 10  7  3 11 12  3  5  1 13  8  4  6 14 15  6  2 16  6
s=  4: 11  8  4 12 13  4  6  2 14  9  5  7 15 16  7  3  0  7
s=  5: 12  9  5 13 14  5  7  3 15 10  6  8 16  0  8  4  1  8
s=  6: 13 10  6 14 15  6  8  4 16 11  7  9  0  1  9  5  2  9
s=  7: 14 11  7 15 16  7  9  5  0 12  8 10  1  2 10  6  3 10
s=  8: 15 12  8 16  0  8 10  6  1 13  9 11  2  3 11  7  4 11
s=  9: 16 13  9  0  1  9 11  7  2 14 10 12  3  4 12  8  5 12
s= 10:  0 14 10  1  2 10 12  8  3 15 11 13  4  5 13  9  6 13
s= 11:  1 15 11  2  3 11 13  9  4 16 12 14  5  6 14 10  7 14
s= 12:  2 16 12  3  4 12 14 10  5  0 13 15  6  7 15 11  8 15
s= 13:  3  0 13  4  5 13 15 11  6  1 14 16  7  8 16 12  9 16
s= 14:  4  1 14  5  6 14 16 12  7  2 15  0  8  9  0 13 10  0
s= 15:  5  2 15  6  7 15  0 13  8  3 16  1  9 10  1 14 11  1
s= 16:  6  3 16  7  8 16  1 14  9  4  0  2 10 11  2 15 12  2

w= 19
s=  0:  5 15  7 11 10 14 12  4 16  9  1 18  3  2  6 17  8 13
s=  1:  6 16  8 12 11 15 13  5 17 10  2  0  4  3  7 18  9 14
s=  2:  7 17  9 13 12 16 14  6 18 11  3  1  5  4  8  0 10 15
s=  3:  8 18 10 14 13 17 15  7  0 12  4  2  6  5  9  1 11 16
s=  4:  9  0 11 15 14 18 16  8  1 13  5  3  7  6 10  2 12 17
s=  5: 10  1 12 16 15  0 17  9  2 14  6  4  8  7 11  3 13 18
s=  6: 11  2 13 17 16  1 18 10  3 15  7  5  9  8 12  4 14  0
s=  7: 12  3 14 18 17  2  0 11  4 16  8  6 10  9 13  5 15  1
s=  8: 13  4 15  0 18  3  1 12  5 17  9  7 11 10 14  6 16  2
s=  9: 14  5 16  1  0  4  2 13  6 18 10  8 12 11 15  7 17  3
s= 10: 15  6 17  2  1  5  3 14  7  0 11  9 13 12 16  8 18  4
s= 11: 16  7 18  3  2  6  4 15  8  1 12 10 14 13 17  9  0  5
s= 12: 17  8  0  4  3  7  5 16  9  2 13 11 15 14 18 10  1  6
s= 13: 18  9  1  5  4  8  6 17 10  3 14 12 16 15  0 11  2  7
s= 14:  0 10  2  6  5  9  7 18 11  4 15 13 17 16  1 12  3  8
s= 15:  1 11  3  7  6 10  8  0 12  5 16 14 18 17  2 13  4  9
s= 16:  2 12  4  8  7 11  9  1 13  6 17 15  0 18  3 14  5 10
s= 17:  3 13  5  9  8 12 10  2 14  7 18 16  1  0  4 15  6 11
s= 18:  4 14  6 10  9 13 11  3 15  8  0 17  2  1  5 16  7 12

[Dmitriy40]

Можно и короче (но медленнее):

? pat=[0, 24, 72, 102, 144, 162, 204, 240, 270, 282, 294, 324, 360, 402, 420, 462, 492, 540, 564];
? forprime(p=2,19, v=setminus(vector(p,i,i-1),Set(-pat%p)); print(p,": ",v););
2: [1]
3: [1, 2]
5: [2, 4]
7: [1, 2]
11: [1, 7]
13: [10, 11]
17: [3, 11]
19: []

Сначала вычисляем сколько надо добавить к начальному числу чтобы попасть точно в каждое из чисел паттерна — -pat.
Потом берём это расстояние по модулю проверяемого простого — -pat%p — получаем список запрещённых остатков для начального числа по данному простому.
Сортируем его и удаляем повторы — Set(-pat%p).
Ну и удаляем запрещённые остатки из всех возможных оставляя только допустимые.

-- 24.07.2023, 12:31 --

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

-- 24.07.2023, 12:36 --

Да, насчёт проверки паттерна на допустимость: условие наличия допустимых остатков по модулю простого имеет исключение: если начальное число кортежа/цепочки столь мало, что в кортеж попадает само это проверяемое простое (и ровно один раз). Проверка по модулю выдаст запрет, ведь число будет делиться само на себя, но такой паттерн и кортеж допустимы, но лишь ровно один раз, в начале числового ряда.
К счастью в начале натуральных чисел нет симметричных решений достаточно большой длины и потому на это исключение можно забить.
Примером такого исключения является паттерн [0,2,4] с кортежем/цепочкой 3:[0,2,4] — нет допустимых остатков по модулю 3, зато оно само есть в кортеже (причём ровно один раз) и потому это допустимый паттерн, хоть решений/цепочек по нему и всего ровно одна.

[gris]

красивое, спасибо.
Про длины и диаметры и нахождение формул/добавок либо по китайской теореме, либо тупым перебором я помню.
+++ Прочту внимательно и постараюсь понять