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

[Nataly-Mak]

Возможно, новый участник конкурса уже нашёл КПППЧ длины 19. У него уже много решений задачи #1.
Интересно бы узнать, откуда участник. Россия?

А я вот сочинила КПППЧ длины 19 с одной "дыркой":

p: 0, 12, 30, 42, 60, 72, 78, 100*, 102, 120, 138, 140, 162, 168, 180, 198, 210, 228, 240

Первый элемент кортежа p пока не показываю.
Это решение получено из бракованой 17-ки Jarek с минимальным диаметром 240.
Число, соответствующее элементу паттерна 100, не простое, это и есть "дырка".
Если выбросить из кортежа комплементарную пару (100, 140), получится 17-ка с минимальным диаметром 240, но... она не будет состоять из последовательных простых чисел, ибо простое число, соответствующее элементу паттерна 140, выброшено. В этом и заключается брак 17-ки.
Ну, и 19-ка, конечно, бракованая; во-первых, в ней есть "дырка" - не простое число; во-вторых, КПППЧ длины 19 не может иметь диаметр 240, для таких КПППЧ минимально возможный диаметр равен 252.
Хотя бы на приближение к решению можно посмотреть

Есть у меня и ещё одно приближение к КПППЧ длины 19, тоже с одной "дыркой"; оно получено продолжением хорошей 17-ки Jarek до 19-ки.

[Jarek]

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

У-р-р-р-а-а-а-а!
На конкурсе новый участник!

Цитата:

Цитата:

Pos User Points T1 T2 T3 Last Improvement

1 Jarek 235 15 5 215 24/09/2015
2 Volja 28 28 25/09/2015
3 Natalia Makarova 4 3 1 16/09/2015

28 решений в задаче #1. Здорово!

Very nice. But where is this competitor now?

Цитата:

Pos User Points T1 T2 T3 Last Improvement

1 Jarek 235 15 5 215 24/09/2015
2 Natalia Makarova 4 3 1 16/09/2015

[Nataly-Mak]

Jarek в сообщении #1056696 писал(а):

But where is this competitor now?

Объясняю.
Попросила ice00 посмотреть его решения.
Выяснилось, что все его решения неправильные - они состоят не из последовательных простых чисел.
Как мне объяснил ice00, этот участник вводил решения по "Submit An Entry", что привело к ошибке, так как решения не проверялись. Я не совсем поняла, как они могли пройти в таком случае.
Поэтому все решения удалены, участнику было отправлено письмо с разъяснением его ошибки.
В описании конкурсной задачи ясно написано, что мы рассматриваем кортежи из последовательных простых чисел

Цитата:

We consider the k-tuple, where p + a1, p + a2, p + a3, …, p + ak are consecutive primes.

[Jarek]

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

Как мне объяснил ice00, этот участник вводил решения по "Submit An Entry", что привело к ошибке, так как решения не проверялись. Я не совсем поняла, как они могли пройти в таком случае.

I do not know how it happened, but I can easily imagine the following: If "Submit An Entry" was not disabled while API query for primality testing used up the 2000 primality tests limit, the primality tester could give an error message in a format which was not predicted at the time the scorer was written and the scorer could behave unpredictably in that case. Of course I do not know whether this is exactly what happened, but such a scenario looks possible to me.

[Nataly-Mak]

Формализовала задачу поиска симметричного кортежа длины 15 с минимальным диаметром 180 из последовательных простых чисел.
Взяла пока первую формулу из 32 возможных, составила систему линейный уравнений:

10163+30030x=6y1-1
10163+30030x+6=6y2-1
10163+30030x+24=6y3-1
10163+30030x+30=6y4-1
10163+30030x+54=6y5-1
10163+30030x+66=6y6-1
10163+30030x+84=6y7-1
10163+30030x+90=6y8-1
10163+30030x+96=6y9-1
10163+30030x+114=6y10-1
10163+30030x+126=6y11-1
10163+30030x+150=6y12-1
10163+30030x+156=6y13-1
10163+30030x+174=6y14-1
10163+30030x+180=6y15-1

Здесь x, yi - натуральные числа, причём значения выражений

$6y_1-1$, $6y_2-1$, ..., $6y_{15}-1$

должны представить последовательные простые числа.
[Они могут и не представить, это должно проверяться в программе.]

Далее решаю эту систему линейных уравнений в онлайн-решателе, получаю следующее решение:

{x = (y1-1694)/5005, 
y10 = y1+19, 
y11 = y1+21, 
y12 = y1+25, 
y13 = y1+26, 
y14 = y1+29, 
y15 = y1+30, 
y2 = y1+1, 
y3 = y1+4, 
y4 = y1+5, 
y5 = y1+9, 
y6 = y1+11, 
y7 = y1+14, 
y8 = y1+15, 
y9 = y1+16}

Интересное решение.
Всё ну очень просто! Всего одна свободная переменная $y_1$, все остальные переменные зависимые.
Программка, матпакет... короб решений...

Затем есть ещё 31 формула, значит, ещё 31 система. Их тоже решаем, получаем ещё 31 короб решений

[Nataly-Mak]

Покажу аналогичную систему уравнений и её решение для другого известного симметричного кортежа из 15 последовательных простых чисел:

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

(решение найдено Dmitriy40 в рамках проекта распределённых вычислений)
Этот кортеж минимальный по значениям составляющих его простых чисел, но имеет большой диаметр 420.
Составляю для этого кортежа аналогичную систему линейных уравнений:

15359+30030x=6y1-1
15359+30030x+12=6y2-1
15359+30030x+18=6y3-1
15359+30030x+42=6y4-1
15359+30030x+102=6y5-1
15359+30030x+138=6y6-1
15359+30030x+180=6y7-1
15359+30030x+210=6y8-1
15359+30030x+240=6y9-1
15359+30030x+282=6y10-1
15359+30030x+318=6y11-1
15359+30030x+378=6y12-1
15359+30030x+402=6y13-1
15359+30030x+408=6y14-1
15359+30030x+420=6y15-1

Онлайн-решатель выдаёт такое решение этой системы уравнений:

{x = (y1-2560)/5005, 
y10 = y1+47, 
y11 = y1+53, 
y12 = y1+63, 
y13 = y1+67, 
y14 = y1+68, 
y15 = y1+70, 
y2 = y1+2, 
y3 = y1+3, 
y4 = y1+7, 
y5 = y1+17, 
y6 = y1+23, 
y7 = y1+30, 
y8 = y1+35, 
y9 = y1+40}

Всё чётко.
И вот решение, дающее приведённый кортеж:
y_1=657628173449805
Все остальные переменные вычисляются по значению этой свободной переменной.
Проверяйте!

Пример наглядно демонстрирует, что данный алгоритм работает.
Числа большие, да. Ну, с маленькими числами эту задачу можно было бы в седьмом классе задавать на уроках информатики
Никак, значит, не получается с большими числами... Увы и ах! У меня точно ничего не получается, не умею
А другие тоже что ли не умеют? Или просто лень?

[Begemot82]

Вопрос один:
как искать y_1? Перебором? Или из известных решений?

[Nataly-Mak]

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

Вопрос один:
как искать y_1? Перебором? Или из известных решений?

Из каких известных? У вас есть известные кортежи длины 15 с минимальным диаметром 180?
У Jarek их тоже не было к моменту начала конкурса, а сейчас уже 20 штук.
И кортежей длины 17 у него не было (ни с каким диаметром), а сейчас уже 15 штук, в том числе и с минимальным диаметром 240. Как-то же он их нашёл. Значит, задача решения имеет!
Сделайте оценку для $y_1$, с какого примерно значения начинать поиск.
Дальше - программа для матпакета и вперёд.
Всего одна свободная переменная! Одна! Всё остальное вычисляется, с проверкой на простоту.

[Begemot82]

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

Всего одна свободная переменная! Одна! Всё остальное вычисляется, с проверкой на простоту.

Я правильно понимаю, что перебором, с шагом 1.

[Nataly-Mak]

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

Я правильно понимаю, что перебором, с шагом 1.

Смотрите на формулу:
$x = (y_1-2560)/5005$
1. x, y1 - натуральные числа;
2. чтобы x было числом натуральным, y1 должно удовлетворять определённым условиям.

Решите, наконец, такую совсем простенькую систему для КПППЧ длины 7 с минимальным диаметром 60:

209+210x=6y1-1
209+210x+12=6y2-1
209+210x+18=6y3-1
209+210x+30=6y4-1
209+210x+42=6y5-1
209+210x+48=6y6-1
209+210x+60=6y7-1

Решение системы в онлайн-решателе:

{x = (y1-35)/35, 
y2 = y1+2, 
y3 = y1+3, 
y4 = y1+5, 
y5 = y1+7, 
y6 = y1+8, 
y7 = y1+10}

Найдите кортеж с минимальным первым элементом кортежа.
Решение я нашла давно по своей программе, в которой реализован алгоритма поиска в лоб (безо всяких систем).
Значение $y_1$ для этого решения пока не сообщаю. Впрочем, его можно посмотреть в известной головоломке

[Begemot82]

1. Вы написали алгоритм, но ничего не сказали про $y_1$.
2. Чем такой подход лучше чем перебором по формуле $10163+30030k$? Это одно и тоже, но в формуле все прозрачно, без лишних и ненужных действий.

[Nataly-Mak]

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

1. Вы написали алгоритм, но ничего не сказали про $y_1$.

Сказала

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

Смотрите на формулу:
$x = (y_1-2560)/5005$
1. x, y1 - натуральные числа;
2. чтобы x было числом натуральным, y1 должно удовлетворять определённым условиям.

Цитата:

2. Чем такой подход лучше чем перебором по формуле $10163+30030k$? Это одно и тоже, но в формуле все прозрачно, без лишних и ненужных действий.

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

-- Пн сен 28, 2015 15:57:30 --

А здесь
$x = (y_1-35)/35$
вообще всё замечательно: чтобы x было натуральным, $y_1$ должно быть кратно 35. Перебор будет очень быстрый!
$y_1=35k, k>1$

Опять ничего не сказала про $y_1$?

[Begemot82]

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

Но если вам не нравится, не навязываю же этот подход. Решайте по алгоритмам, которые вам нравятся.

Зачем он нужен?
Лучше поиска по формулам? Нет, много ненужных вычислений.
Чтоб было много и разных и неважно каких?

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

Опять ничего не сказала про $y_1$?

Про $y_1$ сказали, определив её через еще одну лишнюю переменную.

[Nataly-Mak]

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

Про $y_1$ сказали, определив её через еще одну лишнюю переменную.

Это
$y_1=35k, k>1$
"определив её через ещё одну лишнюю переменную"?
Это шаг перебора Вы же спрашивали про шаг перебора:

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

Я правильно понимаю, что перебором, с шагом 1.

Или вам непонятно, что это шаг перебора?

Объясняю: в данном примере шаг перебора 35, начиная с $y_1=70$, на что указывает $k>1$.
Теперь понятно?

[Begemot82]

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

Это
$y_1=35k, k>1$
"определив её через ещё одну лишнюю переменную"?

Зачем определили $k$, чтобы запутать?

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

Объясняю: в данном примере шаг перебора 35. Теперь понятно?

Для $k$ или для $y_1$.