Prime Sums

[dimkadimon]

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

dimkadimon
Вы обещали объяснить, что за подсказка в картинке.

Хехе. Подсказка там совсем мелкая. Возмем хорошое решение (минимальное или максимальное) и раскрасим клетки с маленькими цифрами одним цветом, а клетки с большими цифрами другим цветом. Тогда получится раскраска похожая на шахматную доску. То есть большие цифры чередуются с маленькими по рядам и по колонкам. В картинке трава раскрашена имено таким образом. Почему получается такая раскраска мы (организаторы) не знаем, но решили что будет возможно получить неплохие решения если использовать етот факт.

[Pavlovsky]

Ed в своей программе, использует хитрую расскраску ячеек.

Цитата:

Odd cells are diplayed in blue. The higher the number the lighter the blue.
Even cells are colored in red.

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

[whitefox]

Забавно

И это справедливо для всех решений близких к оптимальным?

-- 04 янв 2013, 14:12 --

Увы, это не верно.

Вот решение 790 для N=5:
1, 3, 25, 13, 6, 7, 11, 18, 19, 16, 10, 8, 14, 2, 15, 20, 5, 9, 4, 12, 17, 22, 23, 21, 24;

Указанная закономерность не прослеживается.

-- 04 янв 2013, 14:28 --

Заменим 0 все числа от 1 до 13, и заменим 1 все остальные числа.
Получим:

0 0 1 0 0
0 0 1 1 1
0 0 1 0 1
1 0 0 0 0
1 1 1 1 1

Даже близко не похоже на шахматную доску.

[Pavlovsky]

Для четных N (N>=8) шахматный порядок имеет место быть. Объясняется это легко. Маленькие числа концентрируются на зачетных диагоналях.
N=10


Шахматный порядок немного нарушают числа 48,49,51,52

-- Пт янв 04, 2013 16:50:50 --

N=28

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

-- Пт янв 04, 2013 17:18:33 --

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

Пусть у нас есть набор 2N простых чисел, упорядоченных по возрастанию.
Специфика оптималных конфигураций для четных N такова что:
1) Суммы зачетных диагоналей заметно меньше сумм зачетных строк и колонок. Наверно можно придумать пример, когда максимальная сумма зачетных диагоналей больше чем минимальная сумма зачетных строк и колонок. Но это вряд ли. То есть можно считать что в наборе простых чисел, первые N чисел это суммы диагоналей. Остальные это суммы строк и колонок.
2) Зачетных прямых диагоналей должно быть N/2, зачетных обратных диагоналей тоже должно быть N/2. Если квадрат раскрасить в черно-белые цвета, как шахматную доску. То зачетные диагонали должны быть одноцветными (либо черными, либо белыми). Отсюда сумма зачетных прямых диагоналей должна равняться сумме зачетных обратных диагоналей. То есть в нашем наборе простых чисел первые N чисел должны разбиваться на две группы по N/2 чисел в каждой с одинковой суммой.

В тему о распредлении чисел в шахматном порядке. Кстати пункт 1) для N=6 оказался неверным.

[Gerbicz]

"Indeed I could. However, once I realized how to do it, it took me a single day to code and find the solutions for N>7."

That isn't really matter. You needed much more time than ten days, and the help of this forum.

Out of 100 programmers (with average knowledge) probably 80 could code this task if somebody writes down the algorithm. I would not call this a challenge or contest.

[mertz]

down to 9 schemes for 887/1777. my weight counts are reversed, the first number is 0, the last number is 4.

"887/1777 (4,10,9,8,5) 020313202131131424202131131424313242" 
"887/1777 (4,10,9,8,5) 020313202131131424313242131424202131" 
"887/1777 (4,10,9,8,5) 020313313242131424202131131424202131" 
"887/1777 (4,10,9,8,5) 021213203031132324314142021213314142" 
"887/1777 (5,8,9,10,4) 020313202131020313313242131424313242" 
"887/1777 (5,8,9,10,4) 020313202131131424313242020313313242" 
"887/1777 (5,8,9,10,4) 020313313242020313202131131424313242" 
"887/1777 (5,8,9,10,4) 021213203031132324203031132324314142" 
"887/1777 (5,8,9,10,4) 021213314142132324203031132324203031" 

I get the correct number of schemes for 891/1173.

"891/1773 (3,12,9,6,6) 021213314142021213314142021213314142" 
"891/1773 (3,12,9,6,6) 021312314241021312314241021312314241" 
"891/1773 (6,6,9,12,3) 020313313242020313313242020313313242" 
"891/1773 (6,6,9,12,3) 021303314232021303314232021303314232" 

I get 13 instead of 8 for 896/1768.

I take the weight matrix, translate it so each cell that is in the first group is at the origin and record the result. Then I apply seven matrix transforms and run each one. For (4,10,9,8,5) this creates 4 * 8 =32 different results and I take the "minimum".

here are the transforms.

   for( int  i = 0; i < m_size; i++ )
      {
      for( int  j = 0; j < m_size; j++ )   // 35
         m_rot[0][i][j] = m_nc[i][j];
      }
   for( int  i = 0; i < m_size; i++ )      // 23
      {
      for( int  j = 0; j < m_size; j++ )
         m_rot[1][i][j] = m_nc[j][i];
      }
   for( int  i = 0; i < m_size; i++ )      // 21
      {
      for( int  j = 0; j < m_size; j++ )
         m_rot[2][i][j] = m_nc[i][m_size-j-1];
      }
   for( int  i = 0; i < m_size; i++ )      // 15
      {
      for( int  j = 0; j < m_size; j++ )
         m_rot[3][i][j] = m_nc[m_size-i-1][j];
      }
   for( int  i = 0; i < m_size; i++ )      // 13 
      {
      for( int  j = 0; j < m_size; j++ )
         m_rot[4][i][j] = m_nc[m_size-i-1][m_size-j-1];
      }
   for( int  i = 0; i < m_size; i++ )      // 10 
      {
      for( int  j = 0; j < m_size; j++ )
         m_rot[5][i][j] = m_nc[m_size-j-1][m_size-i-1];
      }
   for( int  i = 0; i < m_size; i++ )      // 10
      {
      for( int  j = 0; j < m_size; j++ )
         m_rot[6][i][j] = m_nc[j][m_size-i-1];
      }
   for( int  i = 0; i < m_size; i++ )      // 9
      {
      for( int  j = 0; j < m_size; j++ )
         m_rot[7][i][j] = m_nc[m_size-j-1][i];
      }

Is there a transform missing or an invalid one?

[whitefox]

mertz

Выше я давал ссылку на статью Россера.
Если Вы её пропустили -- приведу снова:
http://narod.ru/disk/63172284001.aef0b88b340ad842227ae19facc6cf78/Rosser1939.rar.html
Статья на английском.

Вам нужны теоремы 3.3 и 3.4 в которых вводится группа преобразований Россера.
Эти преобразования переставляют линии квадрата, при этом множество элементов каждой линии не изменяется (а потому не изменяется и сумма элементов линии).

В теореме 3.4 доказывается, что для чётного $n$ существует точно $4n^2\varphi(n)$ преобразований Россера. В частности, для $n=6$ их будет 4х36х2=288.

То есть алгоритм должен быть примерно таким:

Перечислить все возможные весовые матрицы, при этом для каждой матрицы выполнить все 288 преобразований Россера и взять наименьшую из полученных, если она не была выбрана раньше.

[mertz]

Thanks for your help. I am uneducated so I could not understand the paper. I will make some minor changes and release program without the configurations generator working correctly.

[svb]

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

Организаторы конкурса ето один человек (Нейл), которому если честно не до етих глупых скандалов, у него и так работы завались.

Да, похоже у организатора "работы завались" - сегодня 6-е, а результатов конкурса до сих пор нет

Может кто-нибудь выложит сюда квадраты 1802 и 3090, хотя бы?

(Оффтоп)

На тему

[Pavlovsky]

49, 48, 21, 16, 4, 3, 40, 47, 37, 35, 17, 6, 23, 28, 32, 44, 45, 43, 33, 38, 34, 18, 20, 39, 46, 41, 25, 8, 7, 9, 27, 42, 31, 11, 1, 10, 24, 30, 22, 15, 14, 13, 36, 29, 26, 5, 2, 12, 19

1, 2, 32, 23, 11, 45, 43, 12, 4, 15, 7, 37, 17, 21, 34, 31, 3, 10, 42, 26, 5, 14, 13, 33, 6, 8, 25, 40, 28, 22, 46, 18, 16, 39, 48, 44, 41, 9, 20, 47, 36, 27, 30, 24, 29, 19, 49, 38, 35

[svb]

Pavlovsky
Спасибо.

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

При $N=5$ я обычно использовал схемы 484, но вот решил проверить случайную схему 482:

Цитата:

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

Похоже, что имело бы смысл продолжить анализ.

[Pavlovsky]

svb в сообщении #667943 писал(а):

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

Какая схема и какое распределение чисел по группам лучше? Над этой темой много думал и даже задавал вопросы в этой ветке. Однозначного ответа так и не получил. Почему использовал схему с теоретической оценкой 1802 это понятно. Для нее распределение чисел по группам единственно. А так как нашел рекордное решение, то схемы с оценкой 1800 и 1798 не рассмтаривал.

[Nataly-Mak]

Решила посмотреть, что даст программа whitefox для конкретной схемы-разбиения (по результату Pavlovsky N=7, S=1802). Я такую схему не проверяла, мучила другую схему.
Однако разложение 1802 на 14 простых у меня было точно такое, как у Pavlovsky.
Но это у меня. Как я уже отмечала, программа whitefox не ориентируется на конкретное разложение на 14 простых. В результате программа выставляет много зачётных линий, но! Даже при правильных 13 зачётных линиях решение не получается, так как значение 14-ой зачётной линии не простое число.
Покрутила программу часок, привожу один из выданных программой результатов:



В программе whitefox используется отжиг.
Во входной файл загнала случайным образом заполненный квадрат, в соответствии со схемой.

whitefox
как я поняла, у вас пропал интерес к задаче напрочь.
Очень жаль!
Теперь, когда точно известна схема, дающая результат, можно было бы проверить на ней вашу программу. Почему она так и не даёт результат? Чего в ней не хватает? Или чтобы получить результат, программу надо покрутить сутки-двое?
---

Последние страницы темы читала не очень внимательно, может быть пропустила. Было ли что-то сказано о решении 1752 для N=6?
Я писала в ЛС Vovka17 по поводу этого решения, а также решения 506 для N=5, но, увы, ответа не получила.
Похоже, про задачу и про конкурс уже все забыли, кроме разве что svb.

(Оффтоп)

Впрочем, на форуме конкурса сетуют, что победители не заботятся об описании своих алгоритмов.
Ха! А почему администратор конкурса даже не удосужился поздравить победителей?
Может быть, конечно, у него какие-нибудь неприятности, проблемы и ему не до конкурса. Но хоть какую-то финишную черту он просто обязан провести. На то он и администратор!
А тут получается полное игнорирование победителей.
И какого чёрта они (победители) должны в таком случае заботиться об описании своих алгоритмов? Они описание сделали здесь, там дали ссылки. Этого больше чем достаточно.
Не понимают по-русски? Есть переводчик. Есть, в конце концов, один из организаторов конкурса (по крайней мере, он себя таковым здесь представляет), который прекрасно знает русский язык и мог бы сделать хороший перевод этих описаний.

[Nataly-Mak]

При поиске минимума для N=7 я проверяла две структуры:

1. 2,16,13,16,2 с оценкой Q=1798 (разбиение естественное при оценке 1798; для оценки Q=1802 немного изменяла разбиение);

2. 1,17,16,11,4 с оценкой Q=1802 (здесь разбиение естественное и изменять его не надо).

Схема для второй структуры была выбрана такая:

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

Эту схему мучила долго и по своей программе, и по программе whitefox.
Выше было подробно рассказано о работе моей программы, приведено окно программы с большим количеством 12 выставленных линий. Увы! На 12 линиях всё и закончилось
13-ая и 14-ая зачётные линии так и не найдены (конечно, полный перебор не выполнен).

Существует ли решение в этой схеме
Очень хотелось бы узнать.

А потом брала решения с 12 выставленными зачётными линиями, выданные моей программой, и обрабатывала их программой доработки (whitefox); здесь используется отжиг. И тоже ничего!

-- Пн янв 07, 2013 07:10:18 --

Покажу одно из решений, выданное программой whitefox:



Несколько побочных зачётных линий. По схеме выставлено 13 правильных зачётных линий (то есть эти линии имеют значения - различные простые числа), а значение 14-ой зачётной линии равно 115.
Где-то, кажется, писала, что почти во всех решениях, полученных по этой программе, присутствует простое число 149, а его не должно быть. Никак программа не может обойтись без этого числа

В своей программе я задавала конкретное разложение 1802 на 14 простых:

97,101,103,107,109,113,127,131,137,139,151,157,163,167

Числа 149 в этом разложении нет.

-- Пн янв 07, 2013 07:16:59 --

В подтверждение ещё раз покажу окно моей программы с выведенными 12 выставленными зачётными линиями:

Цитата:

На экран вывожу теперь решения с 12 правильными зачётными линиями, их выводится море. Как бы в них не утонуть

Обидно, если решение в этой схеме "сидит", но я его так и не нашла
Говорят: "Если долго мучиться, что-нибудь получится"
Не всегда верно! Я долго мучилась, но ничего не получилось.

[Vovka17]

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

Последние страницы темы читала не очень внимательно, может быть пропустила. Было ли что-то сказано о решении 1752 для N=6?
Я писала в ЛС Vovka17 по поводу этого решения, а также решения 506 для N=5, но, увы, ответа не получила.

Наверное пропустили. Вот было:

Vovka17 в сообщении #666068 писал(а):

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

Итоги по БД:
для "пятёрки" не найдено решение 506; для "шестёрки" не найдено решение 1752; для "семёрки" БД полная.

Решение 1752 для N=6 существует - 100%. Можете считать БД для шестерки тоже полной.
Решения 506 для N=5 не существует с вероятностью $\approx100$%.

Я, после ответов на вопросы по алгоритму, не заходил на форум и не видел вашего сообщения в личке. Это решение (1752 для N=6) я находил раньше, но не сохранял, как, впрочем, и решение 3088 для N=7. Но без проблем найду их снова, если надо для БД. Только моя программа на работе, смогу найти для вас эти решения и выложить здесь 8-го января.