2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6, 7 ... 67  След.
 
 Re: Prime Sums
Сообщение16.10.2012, 12:57 
Аватара пользователя


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

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

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

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

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

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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение16.10.2012, 12:58 
Заблокирован
Аватара пользователя


22/03/08

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

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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение16.10.2012, 13:05 
Аватара пользователя


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #631551 писал(а):
Значит, вы уже нашли новый рекорд?


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

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

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

Nataly-Mak в сообщении #631559 писал(а):
теоретизируете?


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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение16.10.2012, 13:29 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Pavlovsky в сообщении #631563 писал(а):
Интригую. Могу сказать, что числа для N=5 498 и для N=6 888 взяты не с потолка. Это скорее всего теоретический минимум для этих N. Надеюсь, что достижимый минимум.

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

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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение16.10.2012, 13:35 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Nataly-Mak в сообщении #631551 писал(а):
Если мы делаем, например, перестановку строк, вы же сами сказали, что это может изменить количество простых сумм. А это нам и нужно.


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

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

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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение16.10.2012, 13:39 
Заблокирован
Аватара пользователя


22/03/08

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

Мудрый вывод :D

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

Цитата:
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

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

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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение16.10.2012, 13:42 
Аватара пользователя


21/02/10
1594
Екатеринбург
Nataly-Mak Я не Зоя Космодемьянская, меня пытать долго не надо. :D

Nataly-Mak в сообщении #631579 писал(а):
Как я понимаю, вы нашли набор простых сумм


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

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

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

Изображение

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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение16.10.2012, 13:52 
Заблокирован
Аватара пользователя


22/03/08

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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение16.10.2012, 14:08 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Pavlovsky в сообщении #631558 писал(а):
Утверждение. Если N четно. Тогда линии из семейств "строки", "колонки" пересекаются с линиями из других семейств ровно в одной точке. Линии из семейств "диагонали" и "обратные диагонали" пересекаются между собой ровно в двух точках.

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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение16.10.2012, 14:13 
Аватара пользователя


21/02/10
1594
Екатеринбург
whitefox в сообщении #631602 писал(а):
Главные диагонали не пересекаются.


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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение16.10.2012, 14:45 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Кстати, я выше сообщала, что все простые суммы для 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) :D

-- Вт окт 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


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

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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение16.10.2012, 15:32 
Заслуженный участник


31/12/05
1530

(Оффтоп)

Nataly-Mak в сообщении #631617 писал(а):
найдено без кластера? :D Всего за три дня!
Вот этим и плоха данная задача, что решается она, в основном, не умом, а машиной.

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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение16.10.2012, 15:47 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
tolstopuz в сообщении #631629 писал(а):
На ProjectEuler есть немало задач, которые можно решить за неделю/месяц/год на кластере, а можно несколько часов подумать и решить за минуту на домашнем компьютере. Этим такие задачи и хороши - они решаются умом, а машина служит только усилителем ума.

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

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

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

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

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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение16.10.2012, 19:55 
Аватара пользователя


21/02/10
1594
Екатеринбург
Забавная задача. Мне нравится. :D

 Профиль  
                  
 
 Re: Prime Sums
Сообщение17.10.2012, 04:45 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Полку россиян прибыло

Цитата:
29 Pavel Burdanov 6.395480 10-17-2012 @ 02:18:48

(Оффтоп)

tolstopuz, это вы?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1005 ]  На страницу Пред.  1, 2, 3, 4, 5, 6, 7 ... 67  След.

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



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

Сейчас этот форум просматривают: Dmitriy40


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

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