Prime Sums

[Nataly-Mak]

Да, точнее мне надо было спросить так: возможен ли такой набор сумм?

-- Пн окт 15, 2012 14:11:57 --

Сейчас программа выдала ещё одно маленькое улучшение, теперь для минимальной суммы, было 556, нашлось 554. Вот какой набор сумм соответствует этому результату:

23  37  43  47  53  61  67  71  73  79

Если в этом наборе заменить 71 на 19, то получится минимальная сумма 502.

[Pavlovsky]

Набрать сумму 502 из 10 простых чисел, существует огромное количество вариантов.

[svb]

Первые эксперименты для знакомства с задачей.
Попробовал обыкновенную случайную генерацию квадратов с последующей их проверкой.

N=5: 780, 526
N=6: 1514, 1138
N=7: 2734, 2124
N=8: 4532, 3706
N=9: 7174, 6218
N=10: 10550, 10410

Для больших N, конечно, не стал пробовать.
Похоже, что достаточно эффективным может оказаться метод "отжига". Не плохо бы проверить и специальную начальную генерацию случайного квадрата, например, с наперед заданными линиями, но только для ускорения процесса при больших N.

[Nataly-Mak]

Ввела то, что получилось сегодня для квадрата 5х5 (программа работала целый день).
Плохие результаты, но всё-таки улучшение некоторое имеется:
556 -> 534
710 -> 742

А между тем уже 6 участников из 37 имеют 49 баллов с хвостиком, в том числе и alexBlack. Это что же они будут 3 месяца улучшать? Не наскучит ли им это занятие примерно через неделю? Мне наскучило за три дня, хотя сегодня собственно этой задачей и не занималась, просто программа у меня крутилась, а я занималась книгой.

[dimkadimon]

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

А между тем уже 6 участников из 37 имеют 49 баллов с хвостиком, в том числе и alexBlack. Это что же они будут 3 месяца улучшать?

Скорее всего это проблема с расчётом очков - не должно быть так много людей рядом. Может надо брать в четвёртой степени, например (S/T)^4? Задача точно сложная, посмотрите на N=6 max, только недавно нашли рекорд. Но не уверен что задача достаточно интересная и захватит внимание участников на все 3 месяца...

[Pavlovsky]

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

Скорее всего это проблема с расчётом очков - не должно быть так много людей рядом. Может надо брать в четвёртой степени, например (S/T)^4? Задача точно сложная, посмотрите на N=6 max, только недавно нашли рекорд. Но не уверен что задача достаточно интересная и захватит внимание участников на все 3 месяца...

Да все нормально, ничего не надо менять. Что из того, что результаты будут достаточно плотными. Вероятность того, что большая группа участников наберут одинаковые баллы - маловероятна. Некоторые участники активно стартовали, но есть и те кто поддянутся позже. Неспешно изучаю задачу. В задаче есть глубина! Есть над чем поломать голову!

[Nataly-Mak]

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

В задаче есть глубина! Есть над чем поломать голову!

Счастливые люди, глубину видят
А я ни черта не вижу.
Вот от чего зависит, что сумма некоторой группы попарно различных натуральных чисел будет простым числом
Есть тут какие-то закономерности, математические зависимости? Или всё это зависит только от Господина Случая? Если последнее, то нисколько не интересно!

(Оффтоп)

Возьмите, к примеру, построение пандиагональных магических квадратов. Там есть математика, там есть красивые алгоритмы. Чего стоят одни алгоритмы Россера! А алгоритм svb для пандиагональных квадратов 6-го порядка! Россер до этого не додумался. Он доказал, что классических пандиагональных квадратов 6-го порядка не существует, а нетрадиционные обошёл стороной.
Даже вообразить трудно, насколько было интересно svb получить этот алгоритм и программно реализовать его! Наименьший пандиагональный квадрат 6-го порядка из простых чисел - его произведение. Отличное произведение математического искусства!

А в этой задаче пока не вижу ни одной приличной идеи. Вижу только идею случайной генерации.

Испытала на квадрате 5х5 почти все преобразования: полную перестановку строк одновременно с перестановкой элементов в первой строке, это 14400 вариантов.
Потом добавила М-преобразования, потом добавила поворот на 90 градусов, ещё преобразование "взятие дополнения". И ничего хорошего! Например, М-преобразованиями удалось найти результат 532 к имеющемуся уже 534. Это всё! Преобразование "взятие дополнения" не дало вообще ничего.

[dimkadimon]

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

Потом добавила М-преобразования, потом добавила поворот на 90 градусов, ещё преобразование "взятие дополнения"

Поворот на 90 градусов ничего нового не даст. А вот поменять две строки местами даст, так как некоторые диагонали поменяются.

[Nataly-Mak]

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

Поворот на 90 градусов ничего нового не даст.

У меня даст
Дело в том, что я ещё к перестановкам всех строк добавляю одновременную перестановку элементов в первой строке (о чём ведь написано в моём сообщении!). А если повернуть квадрат на 90 градусов, то уже будут переставляться элементы не в строке, а в столбце, что совсем не одно и то же.

Вообще-то я на преобразованиях магических квадратов собаку съела
Статьи у меня об этом подробнейшие написаны, на одну из них Pavlovsky дал ссылку чуть выше. Правда, это было написано 4 года назад, половину уже забыла.

Есть, например, очень симпатичное преобразование 3-х квадратов, я его сама придумала. Правда, оно применимо только к квадратам чётного порядка.

[dimkadimon]

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

Вообще-то я на преобразованиях магических квадратов собаку съела

Но тут не магический квадрат...

[Pavlovsky]

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

Сумму 502 для N=5 можно получить, например, так:17+23+31+37+53+59+61+67+71+83

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

Думаю нельзя одновремено иметь 17 и 23

Для N=5.
1) первое число должно быть не меньше 15.
2) Сумма первых двух не меньше 46
3) Сумма первых трех не меньше 84
4) Сумма первых четырех не меньше 126

17 + 23 = 40 < 46 одновременно быть не могут.

А вот такой набор 29+31+37+43+47+53+59+61+67+71 = 498 вполне допустим.

[Nataly-Mak]

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

Но тут не магический квадрат...

А какая разница?! Преобразования-то всё равно применимы и к этим квадратам.

[Pavlovsky]

Набор для N=6
47,53,59,61,67,71,73,79,83,89,97,109 = 888

[dimkadimon]

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

Для N=5.
1) первое число должно быть не меньше 15.
2) Сумма первых двух не меньше 46
3) Сумма первых трех не меньше 84
4) Сумма первых четырех не меньше 126

17 + 23 = 40 < 46 одновременно быть не могут.

А вот такой набор 29+31+37+43+47+53+59+61+67+71 = 498 вполне допустим.

Здорово. А как вы ето нашли?

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

А какая разница?! Преобразования-то всё равно применимы и к этим квадратам.

Ну я так понимаю преобразования для магических квадратов превращали магический квадрат в другой магический квадрат? А тут нужны такие преобразования которые не меняют количество простых линий.

[Nataly-Mak]

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

Набор для N=6
47,53,59,61,67,71,73,79,83,89,97,109 = 888

А квадрат 6х6 с таким набором есть?
На форуме найден для N=6 минимум 894. Значит, вы уже нашли новый рекорд?

-- Вт окт 16, 2012 13:53:06 --

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

Ну я так понимаю преобразования для магических квадратов превращали магический квадрат в другой магический квадрат? А тут нужны такие преобразования которые не меняют количество простых линий.

Почему же это не меняют? Наоборот надо, чтобы меняли!
Если мы делаем, например, перестановку строк, вы же сами сказали, что это может изменить количество простых сумм. А это нам и нужно.