Гипотеза о паттернах кортежей

[Nataly-Mak]

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

Предыстория

В программе поиска кортежей whitefox допустил маленькую ошибку: все элементы паттерна выводились удвоенными.
Недавно тестировала поиск кортежа длины 15.

Пример

Правильное решение:

3945769040698829: 0 12 18 42 102 138 180 210 240 282 318 378 402 408 420

Программа выводит (неправильное решение):

3945769040698829: 0 24 36 84 204 276 360 420 480 564 636 756 804 816 840

Мы говорим о паттерне, когда кортеж нормализован. То есть вот это

(0 12 18 42 102 138 180 210 240 282 318 378 402 408 420)

– паттерн следующего реального кортежа из последовательных простых чисел:

(3945769040698829 3945769040698841 3945769040698847 3945769040698871 3945769040698931 3945769040698967 
3945769040699009 3945769040699039   3945769040699069 3945769040699111 3945769040699147 3945769040699207 
3945769040699231 3945769040699237 3945769040699249)

Первый элемент паттерна обычно равен нулю, а остальные элементы – чётные числа.
Далее рассматриваем паттерны.

На этом сервисе проверки паттернов
http://primes.utm.edu/glossary/includes/ktuple.php
написано условие теоретической допустимости паттерна:

Цитата:

Recall that a sequence of integers
(a0, a1, ... ak-1)
is an admissible k-tuple as long as it does not include a complete set of residues for any prime less than or equal to k.

Замечание: здесь паттерн назван k-tuple, то есть кортежем, но это дела не меняет.

Из показанного примера у меня родилась следующая гипотеза:
пусть
($a_1, a_2, a_3,…, a_k$)
теоретически допустимый паттерн длины $k$.
Тогда
($ma_1, ma_2, ma_3,…, ma_k$), $m=2,3,…$
тоже теоретически допустимый паттерн длины $k$.

Это правильная гипотеза?
Если да, как доказать? Я даже не знаю, как подступиться.

Для поиска потенциальных паттернов это очень важная гипотеза.
Например, найден такой потенциальный паттерн для кортежа длины 25:

0  10  24  34  48  60  66  70  76  84  90  94  100  108  114  120  126  130  136  144  150  154  160  168  174

Удваиваю элементы паттерна:

0 20 48 68 96 120 132 140 152 168 180 188 200 216 228 240 252 260 272 288 300 308 320 336 348

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

[tolstopuz]

Представьте себе, что у вас есть $5$ коробочек и вы раскладываете по ним ваши числа в зависимости от остатка при делении на $5$:

в коробочку $0$ попадут числа $0$, $10$, $60$, $70$, $90$, $100$, $120$, $130$, $150$, $160$,
в коробочку $1$ - числа $66$, $76$, $126$, $136$,
в коробочку $3$ - числа $48$, $108$, $168$,
в коробочку $4$ - числа $24$, $34$, $84$, $94$, $114$, $144$, $154$, $174$.

А коробочка $2$ останется пустой. Если бы все коробочки были заполнены, у паттерна не было бы шансов, потому что, с какого бы числа его ни приложи, хотя бы одно число будет делиться на $5$. А сейчас, если мы приложим паттерн с числа $5n-2$, то все числа, делящиеся на $5$, мы аккуратно обойдем.

Теперь удвоим все элементы паттерна. Очевидно, что содержимое коробочки $0$ останется на месте, коробочки $1$ - переселится в коробочку $2$, коробочки $4$ - в коробочку $3$ и так далее. То есть кучек как было четыре, так и останется, а коробочек все равно пять, поэтому опять минимум одна будет пустой.

То есть если паттерн был допустим по модулю $p$, то и после умножения на любое число он останется допустимым. Значит, если он был полностью допустим, то таким и останется.

[Nataly-Mak]

tolstopuz
огромное спасибо. Понятно, доступно.
А если доказать строго математически, а не на пальцах? Можно?

Отлично, что гипотеза верна! Мне это очень поможет в поиске потенциальных паттернов.

[tolstopuz]

Nataly-Mak в сообщении #1043738 писал(а):

А если доказать строго математически, а не на пальцах? Можно?

Строго математически это практически очевидно :)

[Nataly-Mak]

Ну да, практически очевидно. И всё же... Очевидно то, что строго доказано. Так меня учили

Кстати, я на пальцах-то тоже пыталась доказывать.
Брала остатки при делении на некоторое простое число. Потом удваивала элементы паттерна и снова вычисляла остатки при делении на это простое число. Да, практически очевидно.

Теоретически, однако, не доказано.

-- Пн авг 10, 2015 01:05:21 --

Да, спасибо whitefox за гениальную ошибку

Гипотеза тривиальная (мне тут и в личку так написали), но без этого примера с удвоенными элементами паттерна она мне в голову не пришла.

[Nataly-Mak]

tolstopuz в сообщении #1043735 писал(а):

А сейчас, если мы приложим паттерн с числа $5n-2$, то все числа, делящиеся на $5$, мы аккуратно обойдем.

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

0  4  6  10  12  22  24  34  36  40  42  46

у меня получается такая формула для первого члена кортежа:
$1447+2310n$

[Никак не найду, как тут набирать в формуле праймориал, 2310 это 11#]
Не ошиблась?

В Wolfram Alpha эта формула даёт, например, такие решения:

matrix(table[Select[Range[0,200],PrimeQ[(n*2310+1447)+#]&],{n,1,4}])
n | 
1 | {4, 10, 12, 22, 36, 40, 46, 64, 66, 76, 90, 94, 96, 106, 120, 124, 132, 150, 154, 160, 162, 166, 172, 174, 186, 190}
2 | {0, 6, 12, 22, 24, 34, 46, 54, 64, 66, 76, 84, 96, 106, 130, 132, 136, 144, 150, 154, 162, 180, 190, 196}
3 | {0, 10, 12, 42, 46, 52, 54, 66, 70, 84, 90, 124, 136, 144, 150, 160, 162, 166, 186, 196}
4 | {0, 4, 22, 24, 36, 42, 46, 52, 66, 84, 94, 102, 112, 144, 150, 160, 166, 172, 174, 180, 196}

Ещё:

matrix(table[Select[Range[0,150],PrimeQ[(n*2310+1447)+#]&],{n,900,908}])
903 | {0, 4, 6, 10, 12, 22, 42, 66, 76, 84, 90, 106}

Интересное решение: хорошо уже паттерну соответствует.

По формуле для данного случая получаем:
$1447+2310 \cdot 903=2087377$

Проверяю:

Select[Range[0,106],PrimeQ[2087377+#]&]
{0, 4, 6, 10, 12, 22, 42, 66, 76, 84, 90, 106}

Вроде всё правильно. Или только вроде?

Ну, в WA у меня не получилось найти что-то более близкое к решению.
Тогда написала свою программку. По программе удалось найти такое неполное решение:

8101777  8101781  8101783  8101787  8101789  8101799  8101801  8101811  0  0  0  0

Программа у меня плохая, проверила до 50 миллионов, полное решение не нашла.
Генерировала простые числа порциями в интервалах длины 5 миллионов и проверяла, могла что-то пропустить, полуавтоматическая работа.

А интересное решение получилось: вставить в конце три не простых числа, а последнее число будет простое:

8101777  8101781  8101783  8101787  8101789  8101799  8101801  8101811  8101813*  8101817*  8101819*  8101823

Соответствие паттерну точное, но в решении три не простых числа (они отмечены звёздочкой).
Решение с тремя "дырками"

Проверка:

Select[Range[0,90],PrimeQ[8101777+#]&]
{0, 4, 6, 10, 12, 22, 24, 34, 46, 54, 82, 90}

[DanilovV]

Nataly-Mak в сообщении #1043796 писал(а):

[Никак не найду, как тут набирать в формуле праймориал, 2310 это как раз 11#]

primorial(5)

[Nataly-Mak]

DanilovV
спасибо, но у меня не получается.
$1447+primorial(11)$

ещё так:
$1447+\primorial(11)$

где знак праймориала?

Хорошо, так:
$1447+primorial(5)$
или так:
$1447+ \primorial(5)$
или так:
$1447+/primorial(5)$

Ничего не получается

[Begemot82]

Nataly-Mak в сообщении #1043799 писал(а):

DanilovV
спасибо, но у меня не получается.
$1447+primorial(11)$

ещё так:
$1447+\primorial(11)$

где знак праймориала?

primorial(5) это 11# , так как 11 - пятое простое число

У паттерна и второе решение - $817+2310n$. Первое правильное.

[Nataly-Mak]

Я придерживаюсь такого определения праймориала:

Цитата:

Иногда праймориалом называют число n# , определяемое как произведение всех простых чисел, не превышающих заданное n.

Из Википедии

-- Пн авг 10, 2015 08:15:23 --

Begemot82 в сообщении #1043800 писал(а):

У паттерна и второе решение - $817+2310n$. Первое правильное.

То есть моё решение правильное?
Я получила своё решение так:

ChineseRemainder[{1,1,2,5,6},{2,3,5,7,11}]

А вы как получили ваше решение?
Значит, решение может быть и не одно?

[Begemot82]

Так там так и написано
пятый примориал равен 2310

[Nataly-Mak]

Begemot82 в сообщении #1043802 писал(а):

Так там так и написано
пятый примориал равен 2310

Так, а у меня что написано?
Произведение всех простых чисел не превосходящих 11 чему равно

[Begemot82]

Nataly-Mak в сообщении #1043799 писал(а):

$1447+primorial(5)$

Что вы хотите получить?
$1447+primorial(5)$=3757

[Nataly-Mak]

Begemot82

Я хочу получить формулу, в которой будет знак праймориала (11#)
или же чтобы показали, как правильно это набрать.
Что, я плохо с утра выражаю свои мысли? Или это вы ещё спите?

Это правильный набор формулы
$1447+primorial(5)$

[Begemot82]

Nataly-Mak в сообщении #1043804 писал(а):

Произведение всех простых чисел не превосходящих 11 чему равно

Читаем же по-русски

Цитата:

Праймориал или примориал (англ. primorial) числа n обозначается $p_5\#$ и определяется как произведение n первых простых чисел. Например,$ p_5\# = 2 \times 3 \times 5 \times 7 \times 11 = 2310.$

В WA пользуються таким же определением примориала. Или они не правы?