Симметричные кортежи из последовательных простых чисел

[Begemot82]

Элементарно же:
распишите числа из паттерна по первой формуле $859+30030n$.
Для элемента 90 формула примет вид $(859+90)+30030n$.
Делится на 13?

[Nataly-Mak]

Формализовала известное решение

23653934725904299: 0 12 22 34 48 60 70 82 90 102 112 124 138 150 160 172

Обозначим:

$z=12829+30030x$, (х - натуральное число)

Обозначим далее элементы следующей последовательности

0, 12, 22, 34, 48, 60, 70, 82, 90, 102, 112, 124, 138, 150, 160, 172 

$a_i $

Требуется решить следующую систему уравнений:

$z+a_1=y_1$
$z+a_2=y_2$
$z+a_3=y_3$
. . . . .
$z+a_{14}=y_{14}$
$z+a_{15}=y_{15}$
$z+a_{16}=y_{16}$

так, чтобы все $y_i$ были простыми числами.
По крайней мере одно решение у этой системы точно существует (это известное решение).
Может быть, есть и другие решения, надо их найти, если они есть.
Теперь уже в суть задачи совсем не надо вникать, задача формализована.
Пишем программу, например, для Mathematica и - вперёд.

-- Сб сен 19, 2015 20:11:53 --

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

Элементарно же:
распишите числа из паттерна по первой формуле $859+30030n$.
Для элемента 90 формула примет вид $(859+90)+30030n$.
Делится на 13?

Делится.
Формулы выдал WA, я их не проверяла. Значит, формулы WA надо проверять, не все выдаваемые им формулы годные.
Впрочем, могла ошибиться и в вычислении остатков, считала вручную.
А, точно ошиблась: по модулю 13 остаток 12 есть, поэтому дополнения 1 не будет. Ну вот они - три неправильных решения.
WA не виноват. Банальная оплошность на листе бумаги.

-- Сб сен 19, 2015 20:24:48 --

Не, что-то не то.
У меня свободные остатки по модулю 13: 1,2,6,10. Надо просто проверить.
Всё равно: 1 тут в любом случае не будет как дополнения, а она у меня записана, машинально записала. Всего дополнений должно быть 4, а у меня их 5.
Ну, главное, что формула, соответствующая известному решению, правильная получилась. Остальные вообще не при деле.

[Nataly-Mak]

Перепроверила формулы, напортачила с остатками по модулю 13.
Теперь, надеюсь, правильно:

$17029+30030n$
$14719+30030n$
$12409+30030n$
$10099+30030n$
$3379+30030n$
$1069+30030n$
$28789+30030n$
$26479+30030n$
$19759+30030n$
$17449+30030n$
$15139+30030n$
$12829+30030n$

Тогда ведь вполне возможны и решения по остальным 11 формулам.
В формализации задачи вместо

$z=12829+30030x$

можно подставить 11 других значений. Шансы найти решения возрастут.

[Nataly-Mak]

Мини-исследование

Единственный паттерн с минимально возможным диаметром для составления квадратов:

0, 10, 12, 18, 22, 28, 30, 40, 42, 52, 54, 60, 64, 70, 72, 82

Первые три решения по этому паттерну были найдены Jarek давно

Цитата:

There exist exactly 3 numbers n below 192*47# such that all the 16 numbers n+d where d = 0 10 12 18 22 28 30 40 42 52 54 60 64 70 72 82 are prime:

Цитата:

78830573871633653539 (20 digits)
94505039351105832919 (20 digits)
110732011215202177249 (21 digits)

Обратите внимание на значения первых чисел кортежей.
Когда появилось описание конкурса, Jarek прислал мне ещё несколько решений:

5782290971330101557799
86626497666472385701549
148519612556430230871589
252817794258769146656719
255297836561152277222779
365906478100144127235559
372892284538006573920049
374541929668867924737859
603426671076333364284109
608439236788260892144579
666857307384943839104389
689309475375265586661289

Примечательно, что для Jarek поиск таких кортежей совсем не проблема, он может искать их быстро, в больших количествах.
В чём же дело? Полагаю, что в умении работать с очень большими простыми числами.

Нашла все теоретические формулы для данного паттерна; их у меня нашлось всего четыре:

$19489+30030n$
$24109+30030n$
$5839+30030n$
$10459+30030n$

Далее проверила все 15 решений - по каким формулам они получаются. Интересно: работают все четыре формулы.
Вот результаты проверки:

$78830573871633653539=19489+30030 \cdot 2625060734986135$
$94505039351105832919=19489+30030 \cdot 3147020957412781$
$110732011215202177249=10459+30030 \cdot 3687379660845893$
$5782290971330101557799=19489+30030 \cdot 192550481895774277$
$86626497666472385701549=19489+30030 \cdot 2884665256958787402$
$148519612556430230871589=5839+30030 \cdot 4945708043837170525$
$252817794258769146656719=19489+30030 \cdot 8418840967657980241$
$255297836561152277222779=10459+30030 \cdot 8501426458912829744$
$365906478100144127235559=19489+30030 \cdot 12184697905432704869$
$372892284538006573920049=19489+30030 \cdot 12417325492441111352$
$374541929668867924737859=24109+30030 \cdot 12472258730232032125$
$603426671076333364284109=24109+30030 \cdot 20094128240970142000$
$608439236788260892144579=10459+30030 \cdot 20261046846095933804$
$666857307384943839104389=10459+30030 \cdot 22206370542289172131$
$689309475375265586661289=19489+30030 \cdot 22954028484024828060$

Все приведённые решения не подходят для конкурса, так как не удовлетворяют ограничению по магической константе.

[Dmitriy40]

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

Примечательно, что для Jarek поиск таких кортежей совсем не проблема, он может искать их быстро, в больших количествах.
В чём же дело? Полагаю, что в умении работать с очень большими простыми числами.

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

Непонятно почему вы выбрали множитель $30030$, ведь для других множителей число формул может быть и другим, более удобным, например для множителя $210$ формула всего одна: $169+210n$, а для множителя $510510$ формул уже 12шт.

[Nataly-Mak]

Давно обратила внимание на число, присутстсующее во фразе:

Цитата:

There exist exactly 3 numbers n below 192*47# such that all the 16 numbers n+d ...

Что означает в этой фразе число
$192 \cdot p_{15}\#$


Это наводит на мысль, что Jarek использует какое-то правило для поиска границ интервала и/или для поиска формулы первого элемента кортежей. Какое?

Вычислила:

$192 \cdot p_{15}\#=118058838256990350720$

В приведённых кортежах первый элемент действительно меньше этого числа. Значит, некая граница интервала? Откуда она взялась?

-- Пн сен 21, 2015 09:40:53 --

И ещё одна фраза:

Цитата:

I have verified: for this set of d's this is the only n below 64*43# = 837296725226881920 = 8.37*10^17, for which all n+d are prime.

И опять аналогичное число! И опять вроде граница, так как впереди написано "ниже".

-- Пн сен 21, 2015 09:45:20 --

Проверила в Wolfram Alpha, действительно

$64 \cdot p_{14}\#=837296725226881920$

[Nataly-Mak]

Что же я всё о квадратах и о квадратах
Поговорим о задаче #2.

Для кортежей длины 17 с минимальным диаметром 240 существует три потенциальных паттерна:

0  6  24  36  66  84  90  114  120  126  150  156  174  204  216  234  240 
0  12  18  30  42  72  78  102  120  138  162  168  198  210  222  228  240 
0  12  30  42  60  72  78  102  120  138  162  168  180  198  210  228  240

Беру первый паттерн, вычисляю остатки по модулям 2,3,5,7,11,13,17:

2: свободные (1), дополнения (1)
3: (1,2) (2,1)
5: (2,3) (3,2)
7: (4,5) (3,2)
11: (1,8) (10,3)
13: (2,4) (11,9)
17: (8,9,10,11) (9,8,7,6)

Формул получается аж 128 штук.
Нашла первые 12 штук:

$480307+510510n$
$420247+510510n$
$360187+510510n$
$300127+510510n$
$139967+510510n$
$79907+510510n$
$19847+510510n$
$470297+510510n$
$276103+510510n$
$216043+510510n$
$155983+510510n$
$95923+510510n$

Вариантов море. Если работают все 128 формул, это сколько ж можно найти решений
Напомню, что участникам проекта за год не удалось найти ни одного решения этой задачи.
Jarek решение уже нашёл.

[Nataly-Mak]

А теперь о кортеже длины 15 с минимальным диаметром 180, единственный возможный паттерн:

0 6 24 30 54 66 84 90 96 114 126 150 156 174 180

Вычисляю отстатки по модулям 2,3,5,7,11,13:

2: свободные (1) дополнения (1)
3: (1,2) (2,1)
5: (2,3) (3,2)
7: (1,4) (6,3)
11: (1,3) (10,8)
13: (3,8) (10,5)

Получается 32 теоретические формулы, нахожу первые 8 штук (показываю вместе с командами в Wolfram Alpha):

ChineseRemainder[{1,2,3,6,10,10},{2,3,5,7,11,13}]
10163+30030n
ChineseRemainder[{1,2,3,6,10,5},{2,3,5,7,11,13}]
5543+30030n
ChineseRemainder[{1,2,3,6,8,10},{2,3,5,7,11,13}]
7433+30030n
ChineseRemainder[{1,2,3,6,8,5},{2,3,5,7,11,13}]
2813+30030n
ChineseRemainder[{1,2,3,3,10,10},{2,3,5,7,11,13}]
23033+30030n
ChineseRemainder[{1,2,3,3,10,5},{2,3,5,7,11,13}]
18413+30030n
ChineseRemainder[{1,2,3,3,8,10},{2,3,5,7,11,13}]
20303+30030n
ChineseRemainder[{1,2,3,3,8,5},{2,3,5,7,11,13}]
15683+30030n

Вариантов тоже предостаточно.
Участники проекта не нашли кортеж длины 15 с минимальным диаметром по той причине, что после нахождения минимального кортежа (по значениям элементов кортежа) этой длины по моей просьбе поиск таких кортежей whitefox убрал из программы. Тогда ещё мы не рассматривали задачу поиска кортежей с минимальным диаметром, а рассматривали только задачу поиска минимальных кортежей по значению p.
Ну вот, задача со временем возникла, и теперь уже она решена Jarek.
Белое пятно ликвидировано
Jarek нашёл много решений этой задачи, но пока неизвестно, есть ли среди них решение с минимальным значением p.

Из кортежей нечётной длины на очереди кортеж длины 19 с минимальным диаметром 252, для которого имеется тоже единственный теоретический паттерн:

0  6  12  30  42  72  90  96  120  126  132  156  162  180  210  222  240  246  252

Эта задача - крепкий орешек!

-- Пн сен 21, 2015 15:50:46 --

Несколько теоретических формул для этого паттерна я приводила здесь.
Там же есть решение с 10 простыми числами, найденное в Wolfram Alpha.
Ну, найти кортеж длины 19 в онлайн WA, по-моему, нереально.
А вот если бы написать программку на языке Wolfram Language, тогда был бы толк несомненно.

Кстати, вот ссылку дали на документацию по этому языку
http://reference.wolfram.com/language/

Желающие приобщиться к этому замечательному сервису - это для вас

[Dmitriy40]

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

Если работают все 128 формул,

Формулы не могут не работать, обязательно будут кортежи по каждой формуле. Но неизвестно в каком порядке они встретятся с увеличением величины простых чисел. Но что встретятся абсолютно все - это 100%.
Что формул море - это понятно, вы ещё множитель $47\#=614889782588491410$ вместо $510510$ возьмите, формул станет чуть больше 600 миллиардов. И все обязательно когда-нибудь встретятся.

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

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

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

[Vovka17]

Сижу такой, "выдумал" формулу с праймориалами для поиска кортежей. Доволен! Дай-ка посмотрю, чем на форуме народ делится...
А оказывается слишком велосипедистый велосипед у меня . Все кому не лень уже давно разобрались с этим.
Ну если у Jareka не подобный алгоритм, то я уж не знаю, что и подумать...

[Nataly-Mak]

Vovka17 в сообщении #1055610 писал(а):

А оказывается слишком велосипедистый велосипед у меня

Да пуcть велосипедный велосипед, главное, вы сами додумались. А это в любом случае здорово!

Цитата:

Ну если у Jareka не подобный алгоритм, то я уж не знаю, что и подумать...

Может, и подобный, а может, и ещё какой.
Я вот в его сообщениях какие-то хитрые числа увидела, тоже с праймориалами (выше написала об этом). А чего эти числа значат, ну вообще без понятия Вроде как верхняя граница интервала.

[Nataly-Mak]

Задача #2 для кортежей чётных длин начинается с длины $k=12.$
Это минимальное решение по значению элементов кортежа:

137: 0 2 12 14 20 26 30 36 42 44 54 56

Потенциальный паттерн для минимального диаметра 46 всего один:

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

Хотя решение давно известно, думаю, что каждому участнику конкурса интересно найти его самостоятельно – для разминки.
Именно начать с самого простого решения, чтобы войти в задачу, понять, что и как надо делать.
К тому же, не обязательно искать решение с минимальным p, достаточно найти любое решение с минимальным диаметром.

Вычисляем остатки по модулям 2,3,5,7,11:

2 свободные (1), дополнения (1)
3 (2) (1)
5 (3) (2)
7 (2) (5)
11 (5,8) (6,3)

Получается всего две формулы:

$817+2310n$
$1447+2310n$

Известное решение получается по второй формуле

$41280160361347=1447+2310 \cdot 17870199290$

Я пробовала найти решение этой простенькой задачки в онлайн Wolfram Alpha, по второй формуле, например, с ходу получилось решение с шестью правильными элементами:

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}

Пробовала и по своей программке искать решение. Нашла решение с тремя “дырками”, то есть в кортеже три не простых числа (помечены звёздочкой):

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

Ну и, разумеется, по программе whitefox это решение находится легко.

[Nataly-Mak]

Единственный теоретический паттерн для симметричного кортежа длины 14 с минимальным диаметром 56

0  2  6  12  14  20  26  30  36  42  44  50  54  56

Вычисляем остатки по модулям 2,3,5,7,11,13:

2: свободные (1) дополнения (1)
3: (1) (2)
5: (3) (2)
7: (3,4) (4,3)
11: (5,7) (6,4)
13: (8,9) (5,4)

Получается 8 формул; показываю все вместе с соответствующей командой Wolfram Alpha:

ChineseRemainder[{1,2,2,3,4,4},{2,3,5,7,11,13}]
27317+30030n
ChineseRemainder[{1,2,2,3,4,5},{2,3,5,7,11,13}]
4217+30030n
ChineseRemainder[{1,2,2,3,6,4},{2,3,5,7,11,13}]
17+30030n
ChineseRemainder[{1,2,2,3,6,5},{2,3,5,7,11,13}]
6947+30030n
ChineseRemainder[{1,2,2,4,4,4},{2,3,5,7,11,13}]
23027+30030n
ChineseRemainder[{1,2,2,4,4,5},{2,3,5,7,11,13}]
29957+30030n
ChineseRemainder[{1,2,2,4,6,4},{2,3,5,7,11,13}]
25757+30030n
ChineseRemainder[{1,2,2,4,6,5},{2,3,5,7,11,13}]
2657+30030n

Известное решение получается по последней формуле:

$10421030292115097=2657+30030 \cdot 347020655748$

По программе whitefox это решение найти, конечно, можно, но уже не так быстро, как решение для $k=12$.

-- Вт сен 22, 2015 12:15:36 --

Цитата:

1 Jarek 218 15 3 200 22/09/2015

200 квадратов!!

Jarek
Браво!

[Nataly-Mak]

Для симметричных кортежей длины 16 с минимальным диаметром 74 существует два теоретических паттерна:

0 6 8 14 18 24 26 36 38 48 50 56 60 66 68 74
0 6 8 14 20 24 26 36 38 48 50 54 60 66 68 74

Интересно: паттерны отличаются всего одной комплементарной парой, в первом паттерне пара (18, 56), во втором – (20, 54).
Поскольку известное решение найдено по первому паттерну, для него и буду искать формулы.
Вычислим остатки по модулям 2,3,5,7,11,13:

2: свободные (1) дополнения (1)
3: (1) (2)
5: (2) (3)
7: (2) (5)
11: (9,10) (2,1)
13: (2,7) (11,6)

Получается всего 4 формулы:

ChineseRemainder[{1,2,3,5,1,6},{2,3,5,7,11,13}]
19493+30030n
ChineseRemainder[{1,2,3,5,1,11},{2,3,5,7,11,13}]
24113+30030n
ChineseRemainder[{1,2,3,5,2,6},{2,3,5,7,11,13}]
5843+30030n
ChineseRemainder[{1,2,3,5,2,11},{2,3,5,7,11,13}]
10463+30030n

Известное решение получается по первой формуле:

$996689250471604163=19493+30030 \cdot 33189785230489$

По программе whitefox это решение тоже можно найти, но за год работы в проекте участники его не нашли, потому что до таких значений простых чисел ещё не проверили.

[Nataly-Mak]

Для симметричного кортежа длины 18 с минимальным диаметром 82 существует единственный теоретический паттерн:

0  4  10  12  18  22  28  30  40  42  52  54  60  64  70  72  78  82

Интересно: из этого паттерна получается паттерн с минимальным диаметром 74 для кортежа длины 16:

0 6 8 14 18 24 26 36 38 48 50 56 60 66 68 74

Ну, паттерн-то получается, а вот решение для $k=18$ из решения для $k=16$, увы, не получается.

Вычисляем остатки по модулям 2,3,5,7,11,13,17:

2: свободные (1) дополнения (1)
3: (2) (1)
5: (1) (4)
7: (6) (1)
11: (2,3) (9,8)
13: (6,11) (7,2)
17: (7,15,16) (10,2,1)

Получается 12 формул, показываю шесть:

ChineseRemainder[{1,1,4,1,8,2,1},{2,3,5,7,11,13,17}]
379849+510510n
ChineseRemainder[{1,1,4,1,8,2,2},{2,3,5,7,11,13,17}]
319789+510510n
ChineseRemainder[{1,1,4,1,8,2,10},{2,3,5,7,11,13,17}]
349819+510510n
ChineseRemainder[{1,1,4,1,8,7,1},{2,3,5,7,11,13,17}]
144229+510510n
ChineseRemainder[{1,1,4,1,8,7,2},{2,3,5,7,11,13,17}]
84169+510510n
ChineseRemainder[{1,1,4,1,8,7,10},{2,3,5,7,11,13,17}]
114199+510510n

Участники проекта нашли много симметричных кортежей длины 18 из последовательных простых чисел, но с минимальным диаметром не нашли.
Задачу уже решил Jarek. Он нашёл два решения; числа в одном решении 24-значные, а в другом 25-значные.
Я определила, какой формуле соответствуют эти решения, но пока не оглашаю эти результаты.

-- Вт сен 22, 2015 16:55:31 --

О, чудо!
По привычке проверять все решения на продолжение до следующей длины k, проверила оба решения Jarek для $k=18$.
Одно из них продолжилось до кортежа длины 20 с минимальным диаметром 94
Смотрю, смотрю - не ошиблась ли; вроде всё правильно, в Wolfram Alpha проверила.
Написала Jarek, он ещё проверит. Жду от него подтверждения.
Неужели 20-ка с минимальным диаметром найдена?

-- Вт сен 22, 2015 17:02:56 --

Кстати, покажу и теоретические паттерны для $k=20$ с минимальным диаметром 94:

0  4  6  10  16  18  24  28  30  34  60  64  66  70  76  78  84  88  90  94 
0  4  6  10  16  18  24  28  34  36  58  60  66  70  76  78  84  88  90  94 
0  4  6  10  16  18  24  28  36  46  48  58  66  70  76  78  84  88  90  94 
0  4  6  10  16  18  24  30  34  46  48  60  64  70  76  78  84  88  90  94 
0  4  6  10  16  18  24  34  36  46  48  58  60  70  76  78  84  88  90  94 
0  6  10  16  18  24  28  34  36  46  48  58  60  66  70  76  78  84  88  94

По одному из этих паттернов получается решение из решения Jarek для $k=18$, если я ничего не напутала.