2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 5, 6, 7, 8, 9, 10, 11 ... 18  След.
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение25.09.2015, 19:42 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Возможно, новый участник конкурса уже нашёл КПППЧ длины 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-ки.

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение25.09.2015, 22:27 


18/11/10
75
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

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение25.09.2015, 22:36 
Заблокирован
Аватара пользователя


22/03/08

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

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение26.09.2015, 07:02 


18/11/10
75
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.

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение28.09.2015, 11:15 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Формализовала задачу поиска симметричного кортежа длины 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$, все остальные переменные зависимые.
Программка, матпакет... короб решений... :wink:

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

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение28.09.2015, 13:43 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Покажу аналогичную систему уравнений и её решение для другого известного симметричного кортежа из 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
Все остальные переменные вычисляются по значению этой свободной переменной.
Проверяйте!

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

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение28.09.2015, 13:54 


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

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение28.09.2015, 14:05 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Begemot82 в сообщении #1057290 писал(а):
Вопрос один:
как искать y_1? Перебором? Или из известных решений? :D

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

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение28.09.2015, 14:15 


10/07/15
286
Nataly-Mak в сообщении #1057296 писал(а):
Всего одна свободная переменная! Одна! Всё остальное вычисляется, с проверкой на простоту.
Я правильно понимаю, что перебором, с шагом 1.

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение28.09.2015, 14:24 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
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$ для этого решения пока не сообщаю. Впрочем, его можно посмотреть в известной головоломке :-)

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение28.09.2015, 14:36 


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

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение28.09.2015, 14:44 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
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$? :lol:

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение28.09.2015, 15:19 


10/07/15
286
Nataly-Mak в сообщении #1057309 писал(а):
Но если вам не нравится, не навязываю же этот подход. Решайте по алгоритмам, которые вам нравятся.
Зачем он нужен?
Лучше поиска по формулам? Нет, много ненужных вычислений.
Чтоб было много и разных и неважно каких?
Nataly-Mak в сообщении #1057309 писал(а):
Опять ничего не сказала про $y_1$?
Про $y_1$ сказали, определив её через еще одну лишнюю переменную.

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение28.09.2015, 15:33 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Begemot82 в сообщении #1057323 писал(а):
Про $y_1$ сказали, определив её через еще одну лишнюю переменную.

Это
$y_1=35k, k>1$
"определив её через ещё одну лишнюю переменную"? :mrgreen:
Это шаг перебора :!: Вы же спрашивали про шаг перебора:
Begemot82 в сообщении #1057298 писал(а):
Я правильно понимаю, что перебором, с шагом 1.

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

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

 Профиль  
                  
 
 Re: Симметричные кортежи из последовательных простых чисел
Сообщение28.09.2015, 15:46 


10/07/15
286
Nataly-Mak в сообщении #1057327 писал(а):
Это
$y_1=35k, k>1$
"определив её через ещё одну лишнюю переменную"?
Зачем определили $k$, чтобы запутать?
Nataly-Mak в сообщении #1057327 писал(а):
Объясняю: в данном примере шаг перебора 35. Теперь понятно?
Для $k$ или для $y_1$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 257 ]  На страницу Пред.  1 ... 5, 6, 7, 8, 9, 10, 11 ... 18  След.

Модераторы: maxal, Toucan, PAV, Karan, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group