2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 9, 10, 11, 12, 13, 14, 15 ... 67  След.
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение07.07.2013, 13:38 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Как я уже писала, очень трудно было выявить закономерности в примитивном квадрате 9-го порядка, чтобы из него можно было получить пандиагональный квадрат с помощью преобразования Россера.

В Теореме 5.5 (случай 3) Россер рассмотрел построение классического пандиагонального квадрата 9-го порядка из примитивного квадрата, построенного по определённой схеме, то есть это очень специальный примитивный квадрат.
К этому специальному примитивному квадрату применяется следующее преобразование:

$A(i,j) = B(i + j, 2i + 3j)$

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

Циатата из статьи:

Цитата:
Итак, мы установили, что методом Россера для построения классического пандиагонального квадрата 9-го порядка с применением примитивного квадрата можно построить и нетрадиционные пандиагональные квадраты. Теперь надо определить, какими же могут быть примитивные квадраты, чтобы можно было применить метод Россера.

Начались поиски закономерностей.
Кому интересно, читайте статью.
Приведу только один пример из произвольных (различных) натуральных чисел:

Специальный примитивный квадрат:

Код:
5 62 72 81 38 45 90 150 57
4 61 71 80 37 44 89 149 56
1 58 68 77 34 41 86 146 53
30 87 97 106 63 70 115 175 82
27 84 94 103 60 67 112 172 79
7 64 74 83 40 47 92 152 59
165 222 232 241 198 205 250 310 217
181 238 248 257 214 221 266 326 233
159 216 226 235 192 199 244 304 211

Полученный из него пандиагональный квадрат:

Код:
56 90 165 216 248 67 106 40 146
63 152 53 89 5 222 226 221 103
199 257 60 175 59 86 4 62 232
61 72 205 235 214 172 82 92 1
115 7 58 71 45 241 192 326 79
304 233 112 30 64 68 44 81 198
80 38 310 211 266 27 87 74 41
97 47 77 37 150 217 244 181 84
159 238 94 70 83 34 149 57 250

Несмотря на то, что мне удалось выявить закономерности в примитивном квадрате для построения нетрадиционного пандиагонального квадрата 9-го порядка, найти такой квадрат из простых чисел я не смогла. Это сделал в рамках проведённого на этом форуме конкурса alexBlack. Полученные им пандиагональные квадраты из простых чисел имели очень большие константы. Позже он занялся построением идеальных квадратов 9-го порядка и ему удалось построить такой квадрат из различных простых чисел с магической константой 24237. Это лучшее решение для N=9 известное на начало конкурса.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение07.07.2013, 16:20 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Что у нас для N=10?
Мне известны два алгоритма построения нетрадиционных пандиагональных квадратов 10-го порядка из простых чисел. Оба они уже изложены в теме.

Алгоритм №1. Построение по решёткам Россера.

Для построения пандиагонального квадрата порядка 10 достаточно найти 4 пандиагональных квадрата порядка 5 с одинаковой магической константой, но составленных из различных чисел, и разместить их в матрице 10х10 по решёткам Россера.
Как размещать в решётках, показано выше на примере N=8.

По этому алгоритму Pavlovsky построил квадрат с магической константой 3594.
Интересен вопрос: можно ли построить по данному алгоритму квадрат с меньшей магической константой :?:
Я пыталась это сделать, не получилось. Два пандиагональных квадрата 5-го порядка с одинаковой магической константой находятся быстро; три квадрата тоже найти не проблема, а вот четвёртый к найденным трём никак не хочет находиться :-(

Алгоритм №2. Построение ассоциативного примитивного квадрата 10х10, удовлетворяющего дополнительным условиям, и превращение его в пандиагональный квадрат с помощью матричного преобразования.
Этот алгоритм я не реализовала.

Могу добавить
Алгоритм №3. Строим ассоциативный магический квадрат 10х10 из различных простых чисел. Превращаем этот квадрат в пандиагональный с помощью преобразования 3-х квадратов.

Замечу, что ассоциативный магический квадрат строится из пар комплементарных чисел.
Вообще ассоциативный квадрат построить намного проще, чем пандиагональный: степеней свободы в ассоциативном квадрате меньше. Например, ассоциативный квадрат 6-го порядка из различных простых чисел построился у меня мгновенно.
Ассоциативный квадрат 10-го порядка из простых чисел я не пробовала строить, поскольку было найдено Pavlovsky довольно хорошее решение для N=10.

О построении пандиагональных квадратов 10-го порядка читайте статью.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение08.07.2013, 05:46 
Аватара пользователя


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #743452 писал(а):
Как я понимаю, здесь речь идёт о парах комплементарных простых чисел (пары с постоянной суммой).
Хорошая идея!


Так это ваша идея для N=4K. Строить квадрат из K^2 квадратов 4х4. В этом случае квадрат порядка N=4K будет составляться из 8K^2 комплеменатрных пар чисел.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение08.07.2013, 05:56 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Эта идея (построение из пар комплементарных чисел) применима ещё в двух алгоритмах (см. алгоритмы №2 и №3 для N=10).

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение08.07.2013, 08:25 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
О-о-о! Вот как сегодня хорошо начали :D

Цитата:
1 15.00 Jarek Wroblewski Wroclaw, Poland 8 Jul 2013 05:16
2 7.42 Wes Sampson La Jolla, California, United States 8 Jul 2013 03:49
3 7.12 Dmitry Kamenetsky Adelaide, Australia 8 Jul 2013 05:16

dimkadimon
а я уж думала, что вы совсем сдались :wink:
Оказывается, не всё безнадёжно. Рада за вас.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение08.07.2013, 10:44 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Nataly-Mak в сообщении #744296 писал(а):
а я уж думала, что вы совсем сдались :wink:
Оказывается, не всё безнадёжно. Рада за вас.


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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение08.07.2013, 12:10 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
dimkadimon в сообщении #744332 писал(а):
У меня открылось второе дыхание благодаря вашим подсказкам.

Мои подсказки - для всех, это те алгоритмы, о которых я здесь рассказываю.

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

Да, именно так. Магические квадраты с характером, каждый требует своего подхода :-)

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение08.07.2013, 12:35 
Аватара пользователя


21/02/10
1594
Екатеринбург
Тяжело идет работа. Впрочем ни в одном из конкурсов я быстро не начинал.

Завис на поиске регулярных решений для N=13,17,19. Накачал алгоритм эвристиками. Вроде вот вот должны появиться решения и всегда чуть чуть не хватает.

Неспешо обдумываю следующие этапы работы. Можно попробовать построить решения по алгоритму Наталии для N=4K. Правда заметные улучшения можно получить только для N=12,16. Для N=8 Наталия достаточно плотно поработала. А для N=20 Наталия построила по компементарным парам найденым Jarek Wroblewski. Так что вряд ли можно значительно улучшить решение.

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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение08.07.2013, 12:46 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Цитата:
А для N=20 Наталия построила по компементарным парам найденым Jarek Wroblewski.

Pavlovsky
вы что-то путаете.
Пандиагональный квадрат 20-го порядка из различных простых чисел я построила из пар комплементарных чисел, найденных мной, а не Jarek Wroblewski.
Вот цитата из моей статьи:

Цитата:
Уже дописав статью, решила попробовать построение пандиагонального квадрата 20-го порядка из различных простых чисел по решёткам Россера. Поскольку пандиагональные квадраты 4-го порядка строятся быстрее, чем 5-го порядка, начала с поиска 25 пандиагональных квадратов 4-го порядка. Сначала нашла подходящий набор комплементарных пар простых чисел. Понятно, что для построения 25 пандиагональных квадратов 4-го порядка требуется не менее 200 комплементарных пар. Выбрала набор, содержащий 241 пару комплементарных чисел, сумма чисел в паре равна 6510. Квадраты 4-го порядка, составленные из чисел этого набора, имеют магическую константу 13020. Набор оказался хорошим, построилось ровно 25 пандиагональных квадратов! 26-ой квадрат уже не составился, ну, он нам и не нужен.

Статья написана два года назад.
Кстати, построение этого квадрата выполнено по решёткам Россера. Найдено 25 пандиагональных квадратов 4-го порядка. Интересно, что 26-ой квадрат уже не построился. Ровно 25 квадратов! На квадрат 20-го порядка как раз хватило.
Магическая константа квадрата равна 65100. Единственное известное решение для N=20 на начало конкурса.
Почти уверена, что решение не оптимальное.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение08.07.2013, 12:55 
Аватара пользователя


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #744357 писал(а):
вы что-то путаете.


Может и путаю.

-- Пн июл 08, 2013 14:58:26 --

Все смешалось в доме Облонских. :D Не простые числа, а числа Смита. И не Jarek Wroblewski, а М. Алексеев.
Цитата:
Вспомнила о наборе комплементарных пар смитов, найденном М. Алексеевым.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение08.07.2013, 13:01 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Ага, это другое дело :-)
Есть такой зачечательный набор пар комплементарных чисел Смита, найденный maxal.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение09.07.2013, 13:55 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Сегодня тоже хорошо начали :-)

Цитата:
1 15.00 Jarek Wroblewski Wroclaw, Poland 9 Jul 2013 10:24
2 7.41 Dmitry Kamenetsky Adelaide, Australia 9 Jul 2013 02:47
3 7.40 Wes Sampson La Jolla, California, United States 8 Jul 2013 03:49

Уже есть борьба за второе место, что делает соревнование намного интереснее.

-- Вт июл 09, 2013 15:03:26 --

Что у нас для N=11?
Этот порядок является простым числом. Значит, прежде всего - регулярное решение, получаемое из наименьшего квадрата Стенли 11-го порядка. Но это всего только известное решение S=18191.
Как искать нерегулярные решения :?: Задача века :wink:

Попробовать искать идеальный квадрат (пандиагональный, обладающий свойством ассоциативности)? Единственное, что пришло в голову.
Кстати, здесь тоже будут пары комплементарных чисел, кроме элемента, расположенного в центральной ячейке квадрата. Но есть большое сомнение, что этот способ даст лучшее решение (меньше 18191).

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение09.07.2013, 15:33 


16/08/05
1146
Nataly-Mak в сообщении #744081 писал(а):
Несмотря на то, что мне удалось выявить закономерности в примитивном квадрате для построения нетрадиционного пандиагонального квадрата 9-го порядка, найти такой квадрат из простых чисел я не смогла. Это сделал в рамках проведённого на этом форуме конкурса alexBlack. Полученные им пандиагональные квадраты из простых чисел имели очень большие константы. Позже он занялся построением идеальных квадратов 9-го порядка и ему удалось построить такой квадрат из различных простых чисел с магической константой 24237. Это лучшее решение для N=9 известное на начало конкурса.

Ссылки (http://alexblack.wallst.ru/article.php?content=116 и http://alexblack.wallst.ru/article.php?content=120) на соответствующие статьи alexBlack в настоящий момент не действуют. Если статьи сохранились, то выложите их куда-нибудь, пожалуйста.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение09.07.2013, 16:25 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Статьи alexBlack о построении пандиагональных квадратов:

Пандиагональные 9х9:
http://alex-black.ru/article.php?content=116

Идеальные 9х9 из простых чисел:
http://alex-black.ru/article.php?content=120

Пандиагональные 6х6:
http://alex-black.ru/article.php?content=121

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение10.07.2013, 06:11 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Цитата:
1 15.00 Jarek Wroblewski Wroclaw, Poland 9 Jul 2013 19:23
2 7.43 Dmitry Kamenetsky Adelaide, Australia 10 Jul 2013 01:21
3 7.36 Wes Sampson La Jolla, California, United States 8 Jul 2013 03:49
4 6.18 Valery Pavlovsky Ekaterinburg, Russia 22 Jun 2013 20:28

О решениях Jarek у меня уже нет слов. Какой-то у него супералгоритм работает. Улучшения так и сыпятся, как из рога изобилия. Вчера наблюдала весь день; как ни открою турнирную таблицу - опять новый результат.

Хорошо получается у dimkadimon. Результат за известные решения (6.18) он уже увеличил на 1.25. Значительные найдены улучшения.
Как ответит Wes?
Что-то пока не складывается у Pavlovsky. Будем надеяться.
Участников на сегодня 28. Прибудут ли новые? Жду :-)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1005 ]  На страницу Пред.  1 ... 9, 10, 11, 12, 13, 14, 15 ... 67  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group