Prime Sums

[Nataly-Mak]

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

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

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

[Nataly-Mak]

Пример

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

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

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

[Nataly-Mak]

Написала простенькую программку - случайная генерация квадрата 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 простыми суммами

[Nataly-Mak]

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

[Nataly-Mak]

А что-то все стесняются здесь говорить?
Я стала 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 разных простых сумм, а одинаковые просто не учитываются.

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

[dimkadimon]

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

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

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

[Nataly-Mak]

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

Поздравляю с первым решением.

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

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

79  43  0  41  53  89  0  47  61  59  67  71

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

[dimkadimon]

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

Мой результат примерно посредине Ни к максимуму, ни к минимуму не тяготеет.

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

[Nataly-Mak]

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

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

[Nataly-Mak]

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

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

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

[Nataly-Mak]

Да, активность очень хорошая на конкурсе, не в пример активности в данной теме
Лидирует 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 пристроить строку и столбец, пока ни черта не получилось. Надо писать хорошую программу, не тяп-ляп, как у меня сейчас.

[Nataly-Mak]

Цитата:

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

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

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

[svb]

Интересный рывок Robert Gerbicz.
Это он?

[dimkadimon]

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

[Nataly-Mak]

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

Ну что как задачка?

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

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

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

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

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