Prime Sums

[Vitaly12]

Pavlovsky

Цитата:

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

Как это заменить, что имеется ввиду?

[dimkadimon]

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

Теперь о нашей задаче. 2N простых чисел дают нам рекордные суммы S. Естественно рассмотреть возможные представления S в виде суммы простых чисел. Этих представлений очень много, но при малых N вполне обозримо. Если эти представления расположить в убывающем порядке, то получается любопытная картина. Поясню: рассматриваем разложения $S = P_1 + P_2 + ... + P_{2N} $, где $P_{i + 1} < P_i $ располагаем в порядке убывания (можно и наоборот, просто так их легче было генерировать). Наблюдается следующая вещь: рекордные разложения оказались в конце списка, не в самом конце, но рядом.

Можете привести примеры? Я думаю рекордные разложения должны быть в конце списка, ведь на то они рекордные.

[svb]

dimkadimon

Вот два примера:

2752:
229 223 211 199 197 193 181 179 167 163 151 149 139 131 127 113 рекордный
223 211 199 197 193 191 181 173 167 163 157 151 149 139 131 127 последний

4850:
331 313 311 307 293 283 281 277 271 269 263 257 251 241 239 229 223 211

Для 4850 рекордное разложение совпадает с последним. Можно, конечно, предположить, что и для последнего разложения из списка для 2752 существует рекорд.

[Pavlovsky]

Vitaly12 в сообщении #641878 писал(а):

Как это заменить, что имеется ввиду?

В квадрате NxN всего 4N различных линий (строки, колонки, диагонали, обратные диагонали). Конфигурацией будем называть некоторое множество 2N зачетных линий. Для конфигурации можно посчитать нижнюю оценку суммы сумм этих зачетных линий. Как считается оценка описывалось ранее. Линии не вошедшие в конфигурацию будем называть свободными.

Берем произвольную конфигурацию. Выбираем в конфигурации некоторую зачетную линию. Так же выбираем некоторую свободную линию(не входящую в конфигурацию). Удаляем из конфигурации выбранную зачетную линию и добавляем в конфигурацию выбранную свободную линию. У нас получилась новая конфигурация из 2N линий для которой можно посчитаь оценку и сравнить ее с оценкой исходной конфигурации.

-- Пт ноя 09, 2012 08:55:26 --

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

Наблюдается следующая вещь: рекордные разложения оказались в конце списка, не в самом конце, но рядом.

Всегда беру последнее из списка. Обснование этому простое. Чем меньше разность между первым простым числом и последним тем лучше.

[Pavlovsky]

Не всякий набор простых чисел дает решение. Есть дополнительные условия.

Пусть задана конфигурация и распределение чисел по группам.
Пусть у нас есть последовательность простых чисел $(P_1,...,P_{2N})$ $P_i < P_{i+1}$
Пусть $(a_1,...,a_{2N})$ номера линий из конфигурации. Линии $a_i$ поставим в соответсвие простое число $P_i $
Посчитаем суммы $S_i$ - минимально возможная сумма первых i линий $(a_1,...,a_i)$. Если их заполнять минимальными числами в соответствии с распределением чисел по группам.

Тогда очевидно неравенство
$S_j \le \sum_{i=1}^{j}{P_i}$ для всех j $1 \le j \le 2N$

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

До кучи, еще верно равенство.
$S_{2N}=\sum_{i=1}^{2N}{P_i}$

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

-- Пт ноя 09, 2012 10:09:33 --

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

229 223 211 199 197 193 181 179 167 163 151 149 139 131 127 113 рекордный
223 211 199 197 193 191 181 173 167 163 157 151 149 139 131 127 последний

Посчитаем нарастающую сумму этих наборов простых чисел

2752   2523   2300   2089   1890   1693   1500   1319   1140   973   810   659   510   371   240   113
2752   2529   2318   2119   1922   1729   1538   1357   1184   1017   854   697   546   397   258   127

Если первый набор удовлетворяет неравенствам
$S_j \le \sum_{i=1}^{j}{P_i}$ для всех j $1 \le j \le 2N$
Тогда и второй набор удовлетворяет этим неравенствам.

-- Пт ноя 09, 2012 10:27:10 --

Для четных N (включая N=6) есть еще дополнительные требования к набору простых чисел. Если Gerbicz будет не против могу рассказать.

[Pavlovsky]

Молчание знак согласия.
Пусть у нас есть набор 2N простых чисел, упорядоченных по возрастанию.
Специфика оптималных конфигураций для четных N такова что:
1) Суммы зачетных диагоналей заметно меньше сумм зачетных строк и колонок. Наверно можно придумать пример, когда максимальная сумма зачетных диагоналей больше чем минимальная сумма зачетных строк и колонок. Но это вряд ли. То есть можно считать что в наборе простых чисел, первые N чисел это суммы диагоналей. Остальные это суммы строк и колонок.
2) Зачетных прямых диагоналей должно быть N/2, зачетных обратных диагоналей тоже должно быть N/2. Если квадрат раскрасить в черно-белые цвета, как шахматную доску. То зачетные диагонали должны быть одноцветными (либо черными, либо белыми). Отсюда сумма зачетных прямых диагоналей должна равняться сумме зачетных обратных диагоналей. То есть в нашем наборе простых чисел первые N чисел должны разбиваться на две группы по N/2 чисел в каждой с одинковой суммой.
Похоже набор 223 211 199 197 193 191 181 173 167 163 157 151 149 139 131 127 не удовлетворяет именно этому критерию. Руками быстро проверить не смог. А проверочной программы у меня нет. Я генерирую наборы простых чисел уже с учетом этих критериев.

-- Пт ноя 09, 2012 12:18:34 --

Офигеть!!! Новый лидер.

1  Vladimir Chirkov 50.000000 11-09-2012 @ 12:21:09 

Кстати Vladimir Chirkov неплохо выступил и на прошлом конкурсе. Когда выясняли ники участников конкурса на этом форуме, он не отозвался. Видать этот форум не посещает?!
Ссылка на ники:
post591960.html#p591960

-- Пт ноя 09, 2012 12:47:03 --

Пожалуй продублирую список ников (с добавлениями). Первая колонка ник в конкурсе, вторая колонка ник на этом сайте.

Alex Chernov - alexBlack 
Artem Karavaev - Zealint 
Valery Pavlovsky - Pavlovsky 
Natalya Makarova - Nataly-Mak 
Anton Voropaev - ???
Vladimir Chirkov - ???
Artem Ripatti  - ???
Alexu007 - Alexu007 
Konstantin Porozov - ???
Ivan Kazmenko - ???
Sergey Zorkin - 12d3
Serg Belyaev - svb
Pavel Burdanov  - tolstopuz
??? - whitefox
??? - Vitaly12
Dmitry Kamenetsky (Австралия) - dimkadimon
Jim Gillogly (США) - Scryer
Jarek Wroblewski (Польша) - Jarek
Robert Gerbicz(Венгрия) - Gerbicz
Ed Mertensotto(США) - mertz
Herbert Kociemba(Германия) - Herbert Kociemba

[Nataly-Mak]

Ещё один баг в программе Эда - программа не проверяет наличие одинаковых элементов в квадрате. Вот минимальное решение для N=6 (890), но оно неверное, так как в квадрате повторяется число 15.



Может быть, есть уже новая версия программы? Я редко просматриваю форум конкурса, вполне могла пропустить.

Ещё очень хотелось бы иметь "живую" гляделку
Ну, чтобы она работала (как в прошлых конкурсах), а не просто картинку показывала.
Для моего алгоритма "свободных электоронов" очень нужна такая работающая гляделка.
То есть в программе надо сделать возможность заменять числа в ячейках на другие, и чтобы программа мигом выдала новую картинку со всеми посчитанными суммами и новым результатом.
Сейчас я делаю это в Ворде.

-- Сб ноя 10, 2012 08:43:31 --

Кстати, хорошая головоломка для гениев
Показанное выше неверное решение - это моё решение с результатом 900 слегка преобразованное.
Вопрос: можно ли, не заморачиваясь программами и переборами, получить из этого решения правильное решение с результатом 890
У меня не получается, потому что я не гений

-- Сб ноя 10, 2012 09:08:16 --

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

Цитата:

Your project can probably be published at http://primepuzzles.net/

Я попробовала опубликовать, но у меня ничего не получилось. Обратилась за помощью к двум друзьям, они тоже попробовали, и у них тоже не получилось.

Весьма странно

Это текст сообщения, который я пыталась там запостить:

(Оффтоп)

This project began long ago, my colleagues and I have devoted much problem.
Be required pan-diagonal magic squares of prime numbers.

Definition: A square table NxN, filled with natural numbers, called pan-diagonal magic square of order N, if the sum of the numbers in all rows, columns, main and broken diagonals are equal.

The value of these equal sums called magic constant of the square.

If the table is filled with a variety of natural numbers from 1 to N ^ 2, then this square is called classical or traditional. To construct the classical pan-diagonal squares are several algorithms.

Now we will complete table NxN pair wise distinct primes. Such magic squares pan-diagonal called unconventional. The challenge is to build pan-diagonal magic squares of prime numbers with a minimum of magic constant.
Today, we find the smallest pan-diagonal squares of prime numbers for the three orders: 4, 5, 6. This sequence is the minimum magic numbers can be found here:
https://oeis.org/A179440

Pan-diagonal built many magic squares of other orders of the prime numbers, but found the squares with a minimum of magic numbers. Even for a square 7x7 problem is not solved. I built square for order 7 with a magic constant 1597, but no evidence that this is the minimum magic constant. In Figure 1 shows pan-diagonal square 7x7 of prime numbers with the magic constant 1597:

191 89 397 409 43 157 311
379 103 101 491 17 313 193
317 241 109 163 439 47 281
223 383 227 107 541 37 79
331 337 7 139 167 563 53
83 347 389 277 127 307 67
73 97 367 11 263 173 613

Figure 1

***
Link
http://www.natalimak1.narod.ru/panpr.htm

Никто не может мне в этом помочь? Так и не поняла, что я делаю не так, почему выдаётся ошибка. При этом у меня и у друга ошибки выдались разные.
У меня выдалась ошибка 500 HTTP Общая ошибка сервера.
У друга выдалась ошибка:
an error occurred while processing this directive

[whitefox]

Nataly-Mak
И снова я не вижу Вашу картинку.

Все прочие молчат, значат видят.

Никто не знает почему так? Ведь раньше все картинки выложенные Nataly-Mak
я тоже прекрасно видел. Но сейчас они все пропали. Почему?

[Nataly-Mak]

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

Nataly-Mak
И снова я не вижу Вашу картинку.

Я, право, не знаю, почему вы не видите мои картинки. Наверное, козни международных агентов
Попробуйте посмотреть последнюю картинку по прямой ссылке:
http://www.natalimak1.narod.ru/prim6x6a.jpg

Так видите?

[whitefox]

По ссылке картинку вижу, а на форуме нет.

-- 10 ноя 2012, 08:31 --

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

Наверное, козни международных агентов

Скорее уж инопланетных

-- 10 ноя 2012, 08:38 --

Nataly-Mak
У меня версия программы Эда от 25 октября.
Она позволяет вносить изменения, и обнаруживает ошибку, указанную Вами.

Но баг, отмеченный мной, в ней не исправлен.

[Nataly-Mak]

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

У меня версия программы Эда от 25 октября.
Она позволяет вносить изменения, и обнаруживает ошибку, указанную Вами.

Но баг, отмеченный мной, в ней не исправлен.

А где её скачать? На главной странице конкурса? Или в другом месте?

[whitefox]

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

А где её скачать? На главной странице конкурса? Или в другом месте?

Скачиваете по той же ссылке, что и первую версию. Там уже новая программа.

[Nataly-Mak]

Спасибо большое! Сейчас скачаю.

[Nataly-Mak]

И новый рекорд!

Цитата:

7 3088 Vladimir Chirkov @ 10:17:13 on 11-10-2012 1

Вперёд, Россия!

Кстати, Vladimir Chirkov вроде форум этот не посещает, идеи в этой теме не видел.
А вот же в лидеры вышел.

[mertz]

I have a new version of the app almost ready. I will add the check to make sure all the numbers are in the solution once.

The new version shows configurations and sets. I need to ask Neil before I release it. I might have to disable the configuration generator and the grid filling.

ed