2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2, 3, 4, 5 ... 67  След.
 
 Prime Sums
Сообщение13.10.2012, 04:19 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Стартовал новый конкурс программистов - Prime Sums
http://infinitesearchspace.dyndns.org/primesums

Ввела первый попавшийся квадрат 5х5. Суммы посчитались, выдалось сообщение: слишком мало простых сумм.
Оказывается, простых сумм в квадрате NxN должно быть ровно 2N, и не больше, и не меньше :-)
Это сделать непросто. Надо писать программу.

Однако алгоритмов, кроме тупого перебора, пока никаких в голову не пришло :D

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


22/03/08

7154
Саратов
Пример

немного изменила квадрат, приведённый в качестве примера в описании задачи:

Код:
1 10 7 4 15
11 17 19 9 16
21 12 13 14 5
20 3 25 8 24
6 22 23 2 18

Посчитала по программке суммы:

Код:
37  72  65  80  71  59  64  87  37  78  57  73  63  67  65  46  73  71  57  78

Попробовала ввести этот квадрат. Конкурсная программа выдала 5 простых сумм:

Код:
37 59 67 71 73

Всё верно, только 5 простых сумм.
У меня получилось две одинаковые простые суммы - 73. Дубликат не в счёт.

А надо получить 10 простых сумм. Потом найти сумму этих сумм. С одной стороны искать максимальную сумму, а с другой стороны - минимальную.

В этом квадрате

Код:
1 9 12 4 15
11 17 19 10 16
21 7 13 14 5
20 3 25 8 24
6 22 23 2 18

уже 6 простых сумм.
Это все суммы, посчитанные программой:

Код:
41  73  60  80  71  59  58  92  38  78  57  72  69  67  60  47  68  76  56  78

Конкурсная программа выдаёт простые суммы:

Код:
41 47 59 67 71 73

Всё правильно :D
В этом примере нет одинаковых простых сумм.

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


22/03/08

7154
Саратов
Написала простенькую программку - случайная генерация квадрата 5х5.
В этом квадрате:

Код:
1  3  8  13  18
23  2  7  11  17
22  6  15  20  5
10  14  19  24  9
12  16  4  21  25

8 простых сумм:

Код:
43  41  53  89  67  61  59  73

Это нашлось за несколько секунд.
Сейчас попробую искать с 10 простыми суммами :D

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


22/03/08

7154
Саратов
Для 10 сумм программа надолго задумалась :D
Из предыдущего квадрата 5х5, переставив в нём два числа, получила квадрат, в котором 9 простых сумм.
Десятую сумму из этого квадрата получить не удаётся :-(

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


22/03/08

7154
Саратов
А что-то все стесняются здесь говорить? :D
Я стала 10-ым участником этого конкурса

Цитата:
1 Mark Mammel 27.802900 10-13-2012 @ 08:39:53
2 Wes Sampson 16.000000 10-13-2012 @ 12:48:50
3 Chuck Grant 8.538670 10-13-2012 @ 13:07:19
4 Rick Hennig 8.186130 10-13-2012 @ 10:11:14
5 Alex Chernov 2.997800 10-13-2012 @ 10:54:16
6 Ed Mertensotto 1.976520 10-13-2012 @ 09:59:47
7 Tom Sirgedas 1.829250 10-13-2012 @ 05:18:12
8 patrick demichel 1.362180 10-13-2012 @ 15:33:16
9 Henrik Schmid 1.355240 10-13-2012 @ 14:06:28
10 Natalya Makarova 1.276500 10-13-2012 @ 15:33:08

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

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

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


01/06/12
1016
Adelaide, Australia
Nataly-Mak в сообщении #630304 писал(а):
А что-то все стесняются здесь говорить? :D
Я стала 10-ым участником этого конкурса


Поздравляю с первым решением. Конкурс быстро набирает обороты. Wes Sampson за несколько часов нашел очень хорошие решения.

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


22/03/08

7154
Саратов
dimkadimon в сообщении #630308 писал(а):
Поздравляю с первым решением.

Спасибо :D
Хиленькое решение у меня: S=610.
На конкурсе уже имеется по этому квадрату max=788, min=502.
Мой результат примерно посредине :? Ни к максимуму, ни к минимуму не тяготеет.

Вот какие у меня получились простые суммы (нулями программа заменила повторяющиеся суммы):

Код:
79  43  0  41  53  89  0  47  61  59  67  71

Вот такое хиленькое решение полдня искала :D

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


01/06/12
1016
Adelaide, Australia
Nataly-Mak в сообщении #630310 писал(а):
Мой результат примерно посредине :? Ни к максимуму, ни к минимуму не тяготеет.


Ну ничего, ето только начало.

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


22/03/08

7154
Саратов
Немножко улучшила результат для квадрата 5х5.
Теперь у меня есть и минимум, и максимум (локальные пока):
min=592 (502)
max=688 (790)
В скобках то, что найдено на конкурсе.

А чего я сижу на одном квадрате 5х5? :D
Надо другие квадраты попробовать.

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


22/03/08

7154
Саратов
Как я понимаю, у нас пока участников двое.
Остальные думают :D
Я вот тоже думаю: стоит ли продолжать? Что-то задача мне не очень нравится на первый взгляд, после одного дня конкурса.
Не вижу в ней никаких математических идей. Может, просто не могу видеть: зрение плоховато математическое :wink:

Даже не вижу пока, как, найдя, например, решение для квадрата 5х5, расширить его на квадрат 6х6. Подумать надо.
Возможно ли такое расширение? Чтобы не весь квадрат 6х6 заново строить, а как-нибудь нужные числа 26,27,...,36 в квадрат 5х5 добавить и получить вместо 10 простых сумм уже 12 простых сумм в квадрате 6х6. Алгоритм наращивания должен работать! Без него тоскливо.

А здесь что-то все молчат, как в рот воды набрали.

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


22/03/08

7154
Саратов
Да, активность очень хорошая на конкурсе, не в пример активности в данной теме :D
Лидирует Ed Mertensotto.

А я вот за целый день наскребла :?

Цитата:
5 710 790 0.807723 566 502 0.786637 1.594360
Total 710 790 0.807723 566 502 0.786637 1.594360

710 - мой максимум, 790 - текущий максимум на конкурсе; дальше стоит коэффициент за этот результат, то бишь баллы. Точно так же для минимума.

Ну, с квадратом 5х5 более-менее разобралась, уже сносно получились.
А с квадратом 6х6 вообще мрак. Пыталась к квадрату 5х5 пристроить строку и столбец, пока ни черта не получилось. Надо писать хорошую программу, не тяп-ляп, как у меня сейчас.

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


22/03/08

7154
Саратов
Цитата:
1 Alex Chernov 46.693100 10-13-2012 @ 22:48:21
2 Mark Mammel 41.913100 10-14-2012 @ 00:16:10
3 Ed Mertensotto 41.507000 10-13-2012 @ 23:56:43
4 Rick Hennig 25.438400 10-13-2012 @ 23:13:23
5 Wes Sampson 16.000000 10-14-2012 @ 00:21:48
. . . . . . . . . . . . .
14 Tom Sirgedas 1.824570 10-13-2012 @ 05:18:12
15 Il brigante Pennastorta 1.796900 10-14-2012 @ 00:18:34
16 Yirmy Yasovsky 1.713290 10-13-2012 @ 23:27:02
17 Natalya Makarova 1.622910 10-14-2012 @ 00:22:47
18 Henrik Schmid 1.414490 10-13-2012 @ 18:01:29

Браво, Алексей! Вот так шутя, в первый день - и почти максимальное количество баллов. Это надо уметь!

А я плетусь в самом хвосте :D
У меня только один результат - для квадрата 5х5.

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


20/01/10
766
Нижний Новгород
Интересный рывок Robert Gerbicz.
Это он?

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


01/06/12
1016
Adelaide, Australia
Ну что как задачка? Мы её долго жевали чтобы получилось что-то интересное. Если честно я не уверен что к этой задаче будет такой же интерес как к старым. Пока что я вижу только один метод для её решения и он не очень интересный. К тому же результаты полученые на этом конкурсе достаточно абстрактные и я не вижу как их применить к другим областям математики. Например количество различных простых сумм 2N было выбрано совершено от фонаря. Можно было потребовать чтобы все суммы были простые, но казалось что тогда меньше возможных решений. У меня были другие предложения (где не нужно 2N сумм) но их не приняли. Возможно если задача народу быстро надоест то конкурс кончится пораньше и начнётся новый небольшой конкурс, похожий но с другими правилами. Короче посмотрим, всё зависит от интереса участников. Пока что Robert Gerbicz сильно вырвался вперёд и ему нет равных. Может он нашёл новый метод который мы не ожидали. За несколько дней он побил почти все наши рекорды.

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


22/03/08

7154
Саратов
dimkadimon в сообщении #631096 писал(а):
Ну что как задачка?

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

Могу предложить параллельный конкурс :D
Это построение пандиагональных магических квадратов из простых чисел.
В этой задаче, по крайней мере, есть алгоритмы. Я её много решала, и коллеги мне помогали её решать. Здесь надо только минимизировать магические константы.
Задача довольно сложная, и для меня гораздо интереснее предложенной на конкурсе.

Вот эта уникальная последовательность наименьших магических констант пандиагональных квадратов из простых чисел в OEIS: A179440. В этой последовательности всего 3 члена, то есть найдены только пандиагональные квадраты порядков 4,5,6 из простых чисел с минимальной магической константой. Каждый из этих квадратов имеет своего автора.
Кстати сказать, я предлагала эту задачу на форуме конкурса.

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

P.S. Моя задача очень похожа на конкурсную. И квадраты NxN, и суммы в строках, столбцах и ломаных диагоналях. Только суммы эти должны быть не простыми, а равными!
И эти равные суммы (магические константы квадратов) надо минимизировать.
Ещё одно отличие: в моей задаче квадраты заполняются не натуральными числами от 1 до N^2, а простыми числами.

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

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



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

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


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

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