2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Гипотеза о паттернах кортежей
Сообщение09.08.2015, 16:16 
Аватара пользователя
Речь пойдёт о кортежах, все необходимые определения в Википедии.

Предыстория

В программе поиска кортежей 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

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

 
 
 
 Re: Гипотеза о паттернах кортежей
Сообщение09.08.2015, 23:46 
Представьте себе, что у вас есть $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$, то и после умножения на любое число он останется допустимым. Значит, если он был полностью допустим, то таким и останется.

 
 
 
 Re: Гипотеза о паттернах кортежей
Сообщение09.08.2015, 23:52 
Аватара пользователя
tolstopuz
огромное спасибо. Понятно, доступно.
А если доказать строго математически, а не на пальцах? Можно?

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

 
 
 
 Re: Гипотеза о паттернах кортежей
Сообщение09.08.2015, 23:56 
Nataly-Mak в сообщении #1043738 писал(а):
А если доказать строго математически, а не на пальцах? Можно?
Строго математически это практически очевидно :)

 
 
 
 Re: Гипотеза о паттернах кортежей
Сообщение10.08.2015, 00:00 
Аватара пользователя
Ну да, практически очевидно. И всё же... Очевидно то, что строго доказано. Так меня учили :?

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

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

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

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

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

 
 
 
 Re: Гипотеза о паттернах кортежей
Сообщение10.08.2015, 06:33 
Аватара пользователя
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

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

Проверка:
Код:
Select[Range[0,90],PrimeQ[8101777+#]&]
{0, 4, 6, 10, 12, 22, 24, 34, 46, 54, 82, 90}

 
 
 
 Re: Гипотеза о паттернах кортежей
Сообщение10.08.2015, 06:38 
Nataly-Mak в сообщении #1043796 писал(а):
[Никак не найду, как тут набирать в формуле праймориал, 2310 это как раз 11#]
primorial(5)

 
 
 
 Re: Гипотеза о паттернах кортежей
Сообщение10.08.2015, 06:56 
Аватара пользователя
DanilovV
спасибо, но у меня не получается.
$1447+primorial(11)$

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

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

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

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

 
 
 
 Re: Гипотеза о паттернах кортежей
Сообщение10.08.2015, 07:02 
Nataly-Mak в сообщении #1043799 писал(а):
DanilovV
спасибо, но у меня не получается.
$1447+primorial(11)$

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

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

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

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

 
 
 
 Re: Гипотеза о паттернах кортежей
Сообщение10.08.2015, 07:07 
Аватара пользователя
Я придерживаюсь такого определения праймориала:
Цитата:
Иногда праймориалом называют число n# , определяемое как произведение всех простых чисел, не превышающих заданное n.

Из Википедии

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

Begemot82 в сообщении #1043800 писал(а):
У паттерна и второе решение - $817+2310n$. Первое правильное.

То есть моё решение правильное?
Я получила своё решение так:
Код:
ChineseRemainder[{1,1,2,5,6},{2,3,5,7,11}]

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

 
 
 
 Re: Гипотеза о паттернах кортежей
Сообщение10.08.2015, 07:15 
Так там так и написано
пятый примориал равен 2310

 
 
 
 Re: Гипотеза о паттернах кортежей
Сообщение10.08.2015, 07:17 
Аватара пользователя
Begemot82 в сообщении #1043802 писал(а):
Так там так и написано
пятый примориал равен 2310

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

 
 
 
 Re: Гипотеза о паттернах кортежей
Сообщение10.08.2015, 07:21 
Nataly-Mak в сообщении #1043799 писал(а):
$1447+primorial(5)$
Что вы хотите получить?
$1447+primorial(5)$=3757

 
 
 
 Re: Гипотеза о паттернах кортежей
Сообщение10.08.2015, 07:24 
Аватара пользователя
Begemot82

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

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

 
 
 
 Re: Гипотеза о паттернах кортежей
Сообщение10.08.2015, 07:26 
Nataly-Mak в сообщении #1043804 писал(а):
Произведение всех простых чисел не превосходящих 11 чему равно :?:

Читаем же по-русски
Цитата:
Праймориал или примориал (англ. primorial) числа n обозначается $p_5\#$ и определяется как произведение n первых простых чисел. Например,$
p_5\# = 2 \times 3 \times 5 \times 7 \times 11 = 2310.$
В WA пользуються таким же определением примориала. Или они не правы?

 
 
 [ Сообщений: 17 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group