2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.



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


22/03/08

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

Предыстория

В программе поиска кортежей 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 
Заслуженный участник


31/12/05
1517
Представьте себе, что у вас есть $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 
Заблокирован
Аватара пользователя


22/03/08

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

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

 Профиль  
                  
 
 Re: Гипотеза о паттернах кортежей
Сообщение09.08.2015, 23:56 
Заслуженный участник


31/12/05
1517
Nataly-Mak в сообщении #1043738 писал(а):
А если доказать строго математически, а не на пальцах? Можно?
Строго математически это практически очевидно :)

 Профиль  
                  
 
 Re: Гипотеза о паттернах кортежей
Сообщение10.08.2015, 00:00 
Заблокирован
Аватара пользователя


22/03/08

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

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

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

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

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

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

 Профиль  
                  
 
 Re: Гипотеза о паттернах кортежей
Сообщение10.08.2015, 06:33 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
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 


17/04/15
46
Nataly-Mak в сообщении #1043796 писал(а):
[Никак не найду, как тут набирать в формуле праймориал, 2310 это как раз 11#]
primorial(5)

 Профиль  
                  
 
 Re: Гипотеза о паттернах кортежей
Сообщение10.08.2015, 06:56 
Заблокирован
Аватара пользователя


22/03/08

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

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

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

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

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

 Профиль  
                  
 
 Re: Гипотеза о паттернах кортежей
Сообщение10.08.2015, 07:02 


10/07/15
286
Nataly-Mak в сообщении #1043799 писал(а):
DanilovV
спасибо, но у меня не получается.
$1447+primorial(11)$

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

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

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

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

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


22/03/08

7154
Саратов
Я придерживаюсь такого определения праймориала:
Цитата:
Иногда праймориалом называют число 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 


10/07/15
286
Так там так и написано
пятый примориал равен 2310

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


22/03/08

7154
Саратов
Begemot82 в сообщении #1043802 писал(а):
Так там так и написано
пятый примориал равен 2310

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

 Профиль  
                  
 
 Re: Гипотеза о паттернах кортежей
Сообщение10.08.2015, 07:21 


10/07/15
286
Nataly-Mak в сообщении #1043799 писал(а):
$1447+primorial(5)$
Что вы хотите получить?
$1447+primorial(5)$=3757

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


22/03/08

7154
Саратов
Begemot82

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

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

 Профиль  
                  
 
 Re: Гипотеза о паттернах кортежей
Сообщение10.08.2015, 07:26 


10/07/15
286
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