2014 dxdy logo

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

Математика, Физика, Computer Science, 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
752
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
752
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
764
Нижний Новгород
Интересный рывок Robert Gerbicz.
Это он?

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


01/06/12
752
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  След.

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



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

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


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

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