Prime Sums

[dimkadimon]

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

dimkadimon
вы ведь сами писали, что все рекорды побиваемы
Или Gerbicz уже нашёл все непобиваемые рекорды? Я что-то пропустила этот момент.

Ето я так раньше думал. Теперь могу сказать что побиваемых рекордов осталось мало, может только для N=6 и 7.

[Nataly-Mak]

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

Ето я так раньше думал. Теперь могу сказать что побиваемых рекордов осталось мало, может только для N=6 и 7.

Для всех остальных результатов строго доказана их оптимальность?

[Pavlovsky]

whitefox в сообщении #636367 писал(а):

Пусть $A$ меньшее из чисел.
Включим в множество $AA$ все числа от $1$ до $K$.
Пусть $A$ больше суммы этих чисел, и пусть избыток равен $D$.
Представим $D$ в виде: $D=N\cdot K+M$, где $0\leqslant M < K$.
Заменим в множестве $AA$ число $L=K+1-M$ числом $K+1$.
Выберем $N$ чисел в множестве $AA$, отличных от $L$ и $1$, и заменим каждое из них числом большим на $K$.

Хороший алгоритм, мне нравится. А над общим случаем разбиения на m подмножеств думали?
Мне он как раз сейчас нужен. Если вы не поможете, придется самому думать.

[Nataly-Mak]

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

Если вы не поможете, придется самому думать.

О-ха-ха! А кто говорил, что творческие мучения полезны?

Думаем, думаем, все сами думаем

[Nataly-Mak]

Немножко в сторону от конкурса, но с очень похожей задачей...

Я уже писала об этой задаче - это задача построения наименьших магических пандиагональных квадратов из простых чисел.
A179440
Сейчас готовлю небольшой файл с описанием задачи, возможно, завтра выложу его на сайте конкурса.

Задача действительно очень похожа на задачу текущего конкурса.
Поэтому я приглашаю всех конкурсантов (и даже тех, кто в конкурсе не участвует, но интересуется задачей) принять участие в решении моей задачи.

Покажу любопытную картинку. Это я ввела в программу Эда свой уникальный пандиагональный квадрат 7-го порядка из простых чисел с наименьшей на сегодня магической константой. Интересно то, что магическая константа квадрата является простым числом. Таким образом, квадрат имеет 28 простых линий, но все они с одинаковой суммой
Интересно, что программа Эда не показала числа большие 49, но суммы все посчитала.



Иллюстрация подтверждает большое сходство этих двух задач.

[dimkadimon]

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

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

Раскажите побольше про ету задачу. Что значит пандиагональные? Могут ли простые числа повторяться? Какие сейчас лучшие результаты?

-- 28.10.2012, 07:36 --

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

Для всех остальных результатов строго доказана их оптимальность?

Теоретически не доказано, но практически доказано. Для N>=8 результаты оптимальные.

[whitefox]

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

Хороший алгоритм, мне нравится. А над общим случаем разбиения на m подмножеств думали?
Мне он как раз сейчас нужен. Если вы не поможете, придется самому думать.

Думаю, что предложенный алгоритм можно обобщить и на случай $m>2$.
Но доказать это не пытался.

[Nataly-Mak]

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

Раскажите побольше про ету задачу. Что значит пандиагональные? Могут ли простые числа повторяться? Какие сейчас лучшие результаты?

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

Цитата:

Теоретически не доказано, но практически доказано. Для N>=8 результаты оптимальные.

Не поняла. Что значит: практически доказано?
Вот, например, я построила пандиагональный квадрат 7-го порядка из простых чисел с магической константой 1597, с меньшей константой у меня никак не получается. Но это не значит, что я доказала минимальность этой магической константы. Теоретического доказательства нет. Переборного доказательства (полным перебором) тоже нет. Поэтому минимальноcть этой константы считается недоказанной.

[dimkadimon]

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

Не поняла. Что значит: практически доказано?

Ето значит что каждый раз когда я запускаю программу по поиску лучших конфигураций линий я получаю тот же самый результат. Тот же результат получают еще как минимум два человека для всех N>=8.

[Herbert Kociemba]

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

Тот же результат получают еще как минимум два человека для всех N>=8.

At least three people. And in almost all cases the complete solution was found in about 1-2 seconds. The larger the square, the faster. It seems, that the restriction to have exactly 2N different prime numbers is quite week. Even omitting this restriction completely can not produce better results for N>=8.

[Nataly-Mak]

Пока выложила файл в формате doc с кратким описанием задачи построения наименьших пандиагональных квадратов из простых чисел на своём сайте:
http://www.natalimak1.narod.ru/ProjectPandSq.doc

Сделала перевод текста на английский язык в Google. Прошу простить за корявость перевода, старалась редактировать много раз, лучше не получается.
Позже выложу файл на сайте конкурса в формате pdf.

[Nataly-Mak]

Выложила файл в формате pdf на сайте конкурса:
http://infinitesearchspace.dyndns.org/c ... prime-sums

Ещё раз предлагаю всем форумчанам (как участвующим, так и не участвующим в конкурсе) помочь в решении поставленной проблемы.
Последовательность минимальных магических констант в OEIS для данного вида пандиагональных квадратов состоит всего из трёх членов.
maxal разрешил опубликовать статью в связи с уникальностью этой последовательности, несмотря на то, что в ней всего три члена.
Каждый из трёх наименьших пандиагональных квадратов имеет своего автора. Квадрат порядка 4 найден мной. Квадрат порядка 5 построил В. Павловский, квадрат порядка 6 принадлежит С. Беляеву.

[dimkadimon]

Nataly-Mak

Я решил заняться магическими квадратами - наконец вы меня уговорили. Какие рекорды существуют на даный момент? Какие N еще не найдены? Можете в нескольких предложениях описать ваши методы?

[Nataly-Mak]

dimkadimon
я очень рада, что вы решили заняться магическими квадратами.
Тема вечная, неисчерпаемая.

Вы прочли мой файл, выложенный на сайте конкурса?
Я в нём кратко описала только одну из проблем - построение пандиагональных квадратов из простых чисел. Описание понятно? Эта задача очень близка конкурсной задаче. Тоже строятся квадраты NxN, тоже считаются суммы чисел в строках, в столбцах и во всех диагоналях. Только эти суммы, в отличие от конкурсной задачи, должны быть равными. И ещё одно отличие: в моей задаче квадраты надо заполнять попарно различными простыми числами. И в пандиагональных квадратах надо минимизировать магическую константу.
О рекордах в данной задаче я уже говорила: они в статье OEIS A179440.
В статье указаны все найденные верхние границы. Например, для квадрата порядка 7 верхняя граница равна 1597. Значит, надо искать пандиагональные квадраты с меньшей магической константой.

Мои методы в нескольких предложениях описать не могу
У меня много разных методов. Но вы можете найти их все в моих статьях. Ссылки на статьи я указала в файле с описанием задачи. Это далеко не все статьи о магических квадратах. Вот здесь, внизу, вы видите ссылку на главную страницу о магических квадратах. Заходите, не стесняйтесь. Там вы найдёте очень много статей не только о магических, но и о латинских квадратах, ими я тоже довольно много занималась.

Отмечу, что фундаментальная статья по пандиагональным квадратам - это статья Россера.
Наименьшие пандиагональные квадраты порядков 5 и 7 из простых чисел построены по алгоритму Россера, который годится для квадратов порядков, являющихся простыми числами. Однако уже для порядков 11, 13 и выше построить пандиагональные квадраты из простых чисел по этому алгоритму сложно. Мне удалось построить квадраты порядков 11 и 13, но наверняка не наименьшие. Квадрат порядка 17 я не построила.
Ссылку на эту статью вы найдёте в моих статьях или ещё в темах-конкурсах, проведённых мной на этом форуме. Ссылки на эти темы в том же файле с описанием задачи.

[Nataly-Mak]

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

Но есть еще вот это:


Схема размещения 10 линий в квадрате 5х5. Число в ячейке - количество зачетных линий, проходящих через ячейку.

Таких схем, как я понимаю, можно сочинить вагон и маленькую тележку.
Вчера нашла решение для N=5 - 786 (чуть-чуть не хватило до максимума), схема в этом решении оказалась такой:

2 0 1 1 3
2 0 2 1 2
2 3 3 2 2
3 2 4 1 2
3 2 2 2 3

Может быть, потому у меня решение не максимальное, что эта схема не оптимальна?
Может ли данная схема дать результат 790

Собираюсь написать программу именно по данной схеме. Интересная схема: в ней есть числа, входящие в зачётную сумму 1, 2, 3, 4 раза. И два "свободных электрона", то есть два числа не входят в зачётную сумму ни разу.