Prime Sums

[Pavlovsky]

Строки, колонки, диагонали (прямые и обратные) будем называть линиями. У нас есть 4 семейства линий. В каждом семейестве N линий. Очевидно линии из одного семейства не пересекаются.

Утверждение. Если N нечетно, то линии из разных семейств пересекаются ровно в одной точке.

Утверждение. Если N четно. Тогда линии из семейств "строки", "колонки" пересекаются с линиями из других семейств ровно в одной точке. Линии из семейств "диагонали" и "обратные диагонали" пересекаются между собой ровно в двух точках.

Задавая различные условия пересечений легко посчитать возможность заполнения этих линий натуральными числами.

Например.
1) Если две линиии не пересекаются, то эти линии, минимальным образом, можно заполнить числами от 1 до 2N.
2) Если две линии пересекаются в одной точке. То минимальное заполнение будет выглядеть так. Общее число 1. Остальные числа различны от 2 до 2N-1.
3) Если три линии попарно пересекаются в одной точке. Тогда числа 1,2,3 будут присутствовать дважды. Остальные числа различны от 4 до 3*(N-2)+3.

Ну и так далее.

[Nataly-Mak]

А я сейчас решила попробовать программу для N=6. Запустила, немного покрутила, 12 простых сумм найдены, результат: min=1302, max=1308. Фи
Никакого удовлетворения! Ну, программа генерирует квадрат, ну преобразовывает его во все лопатки, ну ищет простые суммы. И что? А я совсем не при деле тут

Pavlovsky
теоретизируете? Это в вашем стиле.
А я не люблю теоретизировать, люблю практически задачу решать. Ну вот и не решается ни черта. Без теории куда ж?

[Pavlovsky]

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

Значит, вы уже нашли новый рекорд?

Это ничего не значит. Так мысли вслух. Приглашение к обсуждению.

PS Если у женщины на руке кольцо, значит, она скорее всего замужем. Если бусы, то это ничего не значит. Если кольцо и бусы, - она замужем, но это ничего не значит. (С) Жванецкий

-- Вт окт 16, 2012 15:09:00 --

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

теоретизируете?

Интригую. Могу сказать, что числа для N=5 498 и для N=6 888 взяты не с потолка. Это скорее всего теоретический минимум для этих N. Надеюсь, что достижимый минимум.

[Nataly-Mak]

Pavlovsky в сообщении #631563 писал(а):

Интригую. Могу сказать, что числа для N=5 498 и для N=6 888 взяты не с потолка. Это скорее всего теоретический минимум для этих N. Надеюсь, что достижимый минимум.

Надеяться всегда хорошо. Главное, чтобы надежды сбывались

Как я понимаю, вы нашли набор простых сумм (причём практически возможных сумм!), которые дают минимальную сумму 498 (и 888). Но это ещё не значит, что суммы эти могут быть получены в реально существующем квадрате. Вот получить-то эти реальные квадратики - в этом и вся задача
Я склонна думать, что конкурсанты с кластерами нашли уже минимумы для N=5, N=6. И дальше минимизировать эти результаты бесполезно. Возможно, я ошибаюсь.

[dimkadimon]

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

Если мы делаем, например, перестановку строк, вы же сами сказали, что это может изменить количество простых сумм. А это нам и нужно.

Если в настоящем решении уже нужное количество простых сумм (2N) тогда преобразование которое меняет ето количество для нас бесполезное. Если же в настоящем решении количество сумм неправильное тогда мы хотим такие преобразования.

Ех ладно, загружу пару решений :)

Нашел максимальное решение N=5:790 где два простых числа повторяются. Забавно.

[Nataly-Mak]

dimkadimon в сообщении #631584 писал(а):

Если в настоящем решении уже нужное количество простых сумм (2N) тогда преобразование которое меняет ето количество для нас бесполезное. Если же в настоящем решении количество сумм неправильное тогда мы хотим такие преобразования.

Мудрый вывод

Нас уже четверо:

Цитата:

5 Alex Chernov 49.404700 10-15-2012 @ 21:10:44
16 Artem Ripatti 32.963800 10-14-2012 @ 11:53:28
28 Konstantin Porozov 5.601920 10-14-2012 @ 04:07:57
32 Natalya Makarova 2.815220 10-16-2012 @ 14:32:48

Остальные что-то стесняются

Всего участников пока 41.

[Pavlovsky]

Nataly-Mak Я не Зоя Космодемьянская, меня пытать долго не надо.

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

Как я понимаю, вы нашли набор простых сумм

Таких наборов я могу найти много. Но есть еще вот это:


Схема размещения 10 линий в квадрате 5х5. Число в ячейке - количество зачетных линий, проходящих через ячейку. Если в ячейках помеченных 3, поместить числа от 1 до 8. В ячейках помеченных 2, поместить числа от 9 до 21. Сумма получается 498. Пока не вижу причин, почему это невозможно.

-- Вт окт 16, 2012 15:48:25 --



Схема размещения 12 линий для N=6. Итого получается 887. Сумма должна быть четной, поэтому берем 888.

[Nataly-Mak]

Pavlovsky
я вас не пытаю, просто высказала своё мнение о ваших сообщениях.
В ваши теории пока не вникаю. Не уверена, что они мне пригодятся.
Ну, может, пригодятся кому-нибудь ещё, кто в теме.

[whitefox]

Pavlovsky в сообщении #631558 писал(а):

Утверждение. Если N четно. Тогда линии из семейств "строки", "колонки" пересекаются с линиями из других семейств ровно в одной точке. Линии из семейств "диагонали" и "обратные диагонали" пересекаются между собой ровно в двух точках.

Главные диагонали не пересекаются.

[Pavlovsky]

whitefox в сообщении #631602 писал(а):

Главные диагонали не пересекаются.

Точно забыл. Если раскрасить квадрат в шахматном порядке. То семейства линий "Диагонали", "обратные диагонали" можно разбить на подсемейства "Черные" и "Белые".
1) Одноцветные диагонали пересекаются с обратными диагоналями в двух точках.
2) Разноцветные диагонали не пересекаются с обратными диагоналями.

[Nataly-Mak]

Кстати, я выше сообщала, что все простые суммы для N=5 практически возможны (проверено программой).
Для N=6 тоже все простые суммы практически возможны, если я не ошиблась в программе.
Этих сумм 38 штук:

23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199

Например, в решении S=1280 для N=6 у меня получился такой набор простых сумм:

97  113  101  107  103  73  89  131  67  139  151  109

Ох, как далеко мне до минимума (894)

-- Вт окт 16, 2012 16:18:09 --

Кто-то может поверить, что вот это всё

(Оффтоп)

Цитата:

8 5568 Robert Gerbicz @ 07:47:18 on 10-14-2012 1
9 8434 Robert Gerbicz @ 07:34:39 on 10-14-2012 1
10 13536 Robert Gerbicz @ 09:21:46 on 10-14-2012 1
11 18770 Robert Gerbicz @ 07:29:19 on 10-14-2012 1
12 28008 Robert Gerbicz @ 07:06:25 on 10-14-2012 1
13 36558 Robert Gerbicz @ 07:23:39 on 10-14-2012 1
14 51816 Robert Gerbicz @ 09:21:01 on 10-14-2012 1
15 64738 Robert Gerbicz @ 07:27:31 on 10-14-2012 1
16 88320 Robert Gerbicz @ 07:09:23 on 10-14-2012 1
17 106734 Robert Gerbicz @ 10:04:48 on 10-14-2012 1
18 141384 Robert Gerbicz @ 09:23:41 on 10-14-2012 1
19 166466 Robert Gerbicz @ 10:06:58 on 10-14-2012 1
20 215400 Robert Gerbicz @ 08:34:06 on 10-14-2012 1
21 248338 Robert Gerbicz @ 10:10:08 on 10-14-2012 1
22 315264 Robert Gerbicz @ 09:24:45 on 10-14-2012 1
23 357246 Robert Gerbicz @ 17:59:09 on 10-14-2012 1
24 446400 Robert Gerbicz @ 08:50:56 on 10-14-2012 1
25 498578 Robert Gerbicz @ 20:32:02 on 10-14-2012 1
26 614736 Robert Gerbicz @ 09:25:44 on 10-14-2012 1
27 678206 Robert Gerbicz @ 22:06:12 on 10-14-2012 1
28 826728 Robert Gerbicz @ 09:02:51 on 10-14-2012 1
29 902498 Robert Gerbicz @ 13:38:06 on 10-15-2012 1


MIN
8 2752 Robert Gerbicz @ 11:45:16 on 10-14-2012 1
9 4850 Robert Gerbicz @ 11:38:41 on 10-14-2012 1
10 6664 Robert Gerbicz @ 11:43:44 on 10-14-2012 2
11 10754 Robert Gerbicz @ 11:49:56 on 10-14-2012 1
12 13752 Robert Gerbicz @ 11:58:40 on 10-14-2012 1
13 20902 Robert Gerbicz @ 12:00:43 on 10-14-2012 1
14 25408 Robert Gerbicz @ 12:02:20 on 10-14-2012 1
15 36962 Robert Gerbicz @ 12:13:29 on 10-14-2012 1
16 43264 Robert Gerbicz @ 11:37:43 on 10-14-2012 1
17 60886 Robert Gerbicz @ 15:12:45 on 10-14-2012 1
18 69216 Robert Gerbicz @ 12:08:39 on 10-14-2012 1
19 94898 Robert Gerbicz @ 15:09:32 on 10-14-2012 1
20 105400 Robert Gerbicz @ 12:10:20 on 10-14-2012 1
21 141506 Robert Gerbicz @ 15:02:06 on 10-14-2012 1
22 154216 Robert Gerbicz @ 12:11:59 on 10-14-2012 1
23 203494 Robert Gerbicz @ 15:34:02 on 10-14-2012 1
24 218304 Robert Gerbicz @ 12:14:55 on 10-14-2012 1
25 283922 Robert Gerbicz @ 17:06:42 on 10-14-2012 1
26 300568 Robert Gerbicz @ 12:16:23 on 10-14-2012 1
27 386186 Robert Gerbicz @ 18:14:50 on 10-14-2012 1
28 404152 Robert Gerbicz @ 12:18:12 on 10-14-2012 1
29 513746 Robert Gerbicz @ 13:36:59 on 10-15-2012 1

найдено без кластера? Всего за три дня!
Вот этим и плоха данная задача, что решается она, в основном, не умом, а машиной.

Хотя... некоторые рассуждают совсем по-другому.
На форуме конкурса, например, andrews выступил как раз с противоположным мнением: ах, какая замечательная задача! Тут вот мы и увидим, кто самый лучший программист (вольный перевод его сообщения).

[tolstopuz]

(Оффтоп)

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

найдено без кластера? Всего за три дня!
Вот этим и плоха данная задача, что решается она, в основном, не умом, а машиной.

На ProjectEuler есть немало задач, которые можно решить за неделю/месяц/год на кластере, а можно несколько часов подумать и решить за минуту на домашнем компьютере. Этим такие задачи и хороши - они решаются умом, а машина служит только усилителем ума. Robert Gerbicz в прошлые годы решал задачи с ProjectEuler очень быстро, так что сейчас вполне мог справиться и без кластера. Хотя с кластером он тоже управляться умеет :)

[Nataly-Mak]

tolstopuz в сообщении #631629 писал(а):

На ProjectEuler есть немало задач, которые можно решить за неделю/месяц/год на кластере, а можно несколько часов подумать и решить за минуту на домашнем компьютере. Этим такие задачи и хороши - они решаются умом, а машина служит только усилителем ума.

Задача задаче рознь. Я тоже решала много переборных задач и немного имею об этом представление.

Цитата:

Robert Gerbicz в прошлые годы решал задачи с ProjectEuler очень быстро, так что сейчас вполне мог справиться и без кластера. Хотя с кластером он тоже управляться умеет :)

Скорее всего, вполне не мог справиться без кластера

Ну, ежели только он гений и для любой задачи может придумать за пару часов супер-алгоритм, за несколько минут реализовать этот алгоритм, то есть написать и отладить программу, ещё за несколько часов прогнать эту программу для N=5-29, тогда, конечно, вполне мог.

Заметьте, я привела здесь таблицу рекордов, то есть он нашёл почти для всех N самые лучшие результаты. Остальные конкурсанты, видимо, совсем без ума. Так получается?
А, нет, не так. Они с умом, но без усилителя

[Pavlovsky]

Забавная задача. Мне нравится.

[Nataly-Mak]

Полку россиян прибыло

Цитата:

29 Pavel Burdanov 6.395480 10-17-2012 @ 02:18:48

(Оффтоп)

tolstopuz, это вы?