2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6, 7, 8 ... 16  След.
 
 Re: Антимагические квадраты
Сообщение27.05.2012, 15:41 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Здорово! Отличное решение!

И вы получили общую формулу квадрата Стенли 6-го порядка, а также и общую формулу примитивного квадрата 6-го порядка (ибо это два совпадающих множества квадратов).
В этой формуле, как я и сказала выше, 11 свободных неизвестных. Всё верно.
Большое спасибо вам!

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

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


22/03/08

7154
Саратов
По программе построения примитивного квадрата 6-го порядка с ходу получила квадрат Стенли из простых чисел с индексом 952:

Код:
3  7  139  19  157  349
13  17  149  29  167  359
37  41  173  53  191  383
103  107  239  119  257  449
43  47  179  59  197  389
97  101  233  113  251  443

В минимальности индекса пока не уверена.

Итак, уже имеем квадраты Стенли 6-го порядка из простых чисел с индексами: 984, 966, 952.

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


22/03/08

7154
Саратов
Someone
а систему из 4340 уравнений (50 неизвестных) ваша чудо-программа из пакета тоже возьмёт? :-)

Речь, как вы понимаете, о общей формуле квадрата Стенли 7-го порядка.

Такая формула, которая будет и общей формулой примитивного квадрата 7-го порядка, для меня весьма интересна.
Дело в том, что наименьший примитивный квадрат 7-го порядка из простых чисел даст нам наименьший пандиагональный (регулярный) квадрат, который мы так и не нашли.

Вспоминаю, сколько раз я переписывала программу построения примитивного квадрата 7-го порядка. Каждый раз оптимизация позволяла чуть ускорить выполнение программы.
При построении примитивного квадрата 7-го порядка, если не задана константа, имеем 13 свободных переменных и 37 зависимых.

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

Вот этот примитивный квадрат:

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

Это и квадрат Стенли с индексом 1597.

Итак, на повестке дня система линейных уравнений: 4340 уравнений, 50 неизвестных :wink:

P.S. Конечно, нет никакой гарантии, что общая формула позволит-таки выполнить полный перебор и решить задачу. Но попытаться можно.

-- Пн май 28, 2012 06:55:15 --

Программа построения примитивного квадрата 6-го порядка работает у меня дальше. Получен такой квадрат Стенли с индексом 918:

Код:
5  7  17  31  257  277
11  13  23  37  263  283
41  43  53  67  293  313
59  61  71  85  311  331
101  103  113  127  353  373
137  139  149  163  389  409

Улучшение от 952 до 918, неплохо, но вряд ли это минимум.

Выполнить полный перебор даже для квадратов 6-го порядка проблематично. Я уже хитрю :-) Поскольку с числа 3 долго ничего не находит программа, я взяла и начала перебор со следующего числа массива простых чисел - 5. И тут квадрат нашёлся мгновенно.

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


22/03/08

7154
Саратов
Стоп!
Где-то в программе прокол. Только сейчас увидела, что в квадрате есть не простое число 85 (сразу бросилось в глаза своей последней цифрой 5).
Квадраты Стенли с индексами 952 и 918 не составлены только из простых чисел. В квадрате с индексом 952 в той же позиции находится не простое число 119.
Пошла искать ошибку :-) Видимо, забыла проверить этот элемент на принадлежность массиву простых чисел.

-- Пн май 28, 2012 07:45:13 --

Исправила ошибку.
Такой пока квадрат Стенли получила с индексом 900:

Код:
5  7  47  73  157  227
11  13  53  79  163  233
29  31  71  97  181  251
41  43  83  109  193  263
59  61  101  127  211  281
269  271  311  337  421  491

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


22/03/08

7154
Саратов
Вот этот квадрат Стенли 6-го порядка из простых чисел с индексом 774 у меня пока наименьший:

Код:
13  19  43  109  139  223
31  37  61  127  157  241
41  47  71  137  167  251
53  59  83  149  179  263
67  73  97  163  193  277
101  107  131  197  227  311

Надо делать полный перебор, чтобы программа отработала полностью, но это очень долго.

Поколдую с общей формулой, полученной Someone. Может быть, удастся улучшить программу.

Ещё такая идея: попробую каждый примитивных квадрат 6х6 достроить до примитивного квадрата 7х7; вдруг удастся получить примитивный квадрат 7х7 с константой меньше 1597.
Маловероятно, но проверка не помешает.

-- Пн май 28, 2012 10:02:57 --

Someone
Конечно, наврала с числом уравнений для квадрата Стенли 7-го порядка :-)
Вместо 720 набрала на калькуляторе 620. Уравнений будет, разумеется, 5040, а не 4340.

(слишком быстро, на мой взгляд, лишают возможности редактировать сообщение!)

 Профиль  
                  
 
 Re: Антимагические квадраты
Сообщение28.05.2012, 14:42 
Заслуженный участник
Аватара пользователя


23/07/05
17734
Москва
Nataly-Mak в сообщении #577485 писал(а):
а систему из 4340 уравнений (50 неизвестных) ваша чудо-программа из пакета тоже возьмёт? :-)

Речь, как вы понимаете, о общей формуле квадрата Стенли 7-го порядка.
Nataly-Mak в сообщении #577508 писал(а):
Конечно, наврала с числом уравнений для квадрата Стенли 7-го порядка :-)
Вместо 720 набрала на калькуляторе 620. Уравнений будет, разумеется, 5040, а не 4340.
"Возьмёт". Специально сделал с измерением времени счёта.

Порядок 7:
составление списка перестановок - 0. Second;
составление системы уравнений - 0.265 Second;
составление списка неизвестных - 0. Second
решение системы - 0.344 Second.

(Результат:)

Код:
x1 = - x14 - x21 - x28 - x35 - x42 - x44 - x45 - x46 - x47 - x48 + 4 x49 + x50
x2 = - x14 - x21 - x28 - x35 - x42 - x43 - x45 - x46 - x47 - x48 + 4 x49 + x50
x3 = - x14 - x21 - x28 - x35 - x42 - x43 - x44 - x46 - x47 - x48 + 4 x49 + x50
x4 = - x14 - x21 - x28 - x35 - x42 - x43 - x44 - x45 - x47 - x48 + 4 x49 + x50
x5 = - x14 - x21 - x28 - x35 - x42 - x43 - x44 - x45 - x46 - x48 + 4 x49 + x50
x6 = - x14 - x21 - x28 - x35 - x42 - x43 - x44 - x45 - x46 - x47 + 4 x49 + x50
x7 = - x14 - x21 - x28 - x35 - x42 - x43 - x44 - x45 - x46 - x47 - x48 + 5 x49 + x50
x8 = x14 + x43 - x49
x9 = x14 + x44 - x49
x10 = x14 + x45 - x49
x11 = x14 + x46 - x49
x12 = x14 + x47 - x49
x13 = x14 + x48 - x49
x15 = x21 + x43 - x49
x16 = x21 + x44 - x49
x17 = x21 + x45 - x49
x18 = x21 + x46 - x49
x19 = x21 + x47 - x49
x20 = x21 + x48 - x49
x22 = x28 + x43 - x49
x23 = x28 + x44 - x49
x24 = x28 + x45 - x49
x25 = x28 + x46 - x49
x26 = x28 + x47 - x49
x27 = x28 + x48 - x49
x29 = x35 + x43 - x49
x30 = x35 + x44 - x49
x31 = x35 + x45 - x49
x32 = x35 + x46 - x49
x33 = x35 + x47 - x49
x34 = x35 + x48 - x49
x36 = x42 + x43 - x49
x37 = x42 + x44 - x49
x38 = x42 + x45 - x49
x39 = x42 + x46 - x49
x40 = x42 + x47 - x49
x41 = x42 + x48 - x49

Ну уж издеваться - так издеваться.

Порядок 8:
составление списка перестановок - 0.015 Second;
составление системы уравнений - 2.36 Second;
составление списка неизвестных - 0. Second
решение системы - 10.969 Second.

(Результат:)

Код:
x1 = - x16 - x24 - x32 - x40 - x48 - x56 - x58 - x59 - x60 - x61 - x62 - x63 + 5 x64 + x65
x2 = - x16 - x24 - x32 - x40 - x48 - x56 - x57 - x59 - x60 - x61 - x62 - x63 + 5 x64 + x65
x3 = - x16 - x24 - x32 - x40 - x48 - x56 - x57 - x58 - x60 - x61 - x62 - x63 + 5 x64 + x65
x4 = - x16 - x24 - x32 - x40 - x48 - x56 - x57 - x58 - x59 - x61 - x62 - x63 + 5 x64 + x65
x5 = - x16 - x24 - x32 - x40 - x48 - x56 - x57 - x58 - x59 - x60 - x62 - x63 + 5 x64 + x65
x6 = - x16 - x24 - x32 - x40 - x48 - x56 - x57 - x58 - x59 - x60 - x61 - x63 + 5 x64 + x65
x7 = - x16 - x24 - x32 - x40 - x48 - x56 - x57 - x58 - x59 - x60 - x61 - x62 + 5 x64 + x65
x8 = - x16 - x24 - x32 - x40 - x48 - x56 - x57 - x58 - x59 - x60 - x61 - x62 - x63 + 6 x64 + x65
x9 = x16 + x57 - x64
x10 = x16 + x58 - x64
x11 = x16 + x59 - x64
x12 = x16 + x60 - x64
x13 = x16 + x61 - x64
x14 = x16 + x62 - x64
x15 = x16 + x63 - x64
x17 = x24 + x57 - x64
x18 = x24 + x58 - x64
x19 = x24 + x59 - x64
x20 = x24 + x60 - x64
x21 = x24 + x61 - x64
x22 = x24 + x62 - x64
x23 = x24 + x63 - x64
x25 = x32 + x57 - x64
x26 = x32 + x58 - x64
x27 = x32 + x59 - x64
x28 = x32 + x60 - x64
x29 = x32 + x61 - x64
x30 = x32 + x62 - x64
x31 = x32 + x63 - x64
x33 = x40 + x57 - x64
x34 = x40 + x58 - x64
x35 = x40 + x59 - x64
x36 = x40 + x60 - x64
x37 = x40 + x61 - x64
x38 = x40 + x62 - x64
x39 = x40 + x63 - x64
x41 = x48 + x57 - x64
x42 = x48 + x58 - x64
x43 = x48 + x59 - x64
x44 = x48 + x60 - x64
x45 = x48 + x61 - x64
x46 = x48 + x62 - x64
x47 = x48 + x63 - x64
x49 = x56 + x57 - x64
x50 = x56 + x58 - x64
x51 = x56 + x59 - x64
x52 = x56 + x60 - x64
x53 = x56 + x61 - x64
x54 = x56 + x62 - x64
x55 = x56 + x63 - x64

Порядок 9:
составление списка перестановок - 0.14 Second;
составление системы уравнений - 23.438 Second;
составление списка неизвестных - 0. Second
решение системы - 1492.06 Second.

(Результат:)

Код:
x1 = - x18 - x27 - x36 - x45 - x54 - x63 - x72 - x74 - x75 - x76 - x77 - x78 - x79 - x80 + 6 x81 + x82
x2 = - x18 - x27 - x36 - x45 - x54 - x63 - x72 - x73 - x75 - x76 - x77 - x78 - x79 - x80 + 6 x81 + x82
x3 = - x18 - x27 - x36 - x45 - x54 - x63 - x72 - x73 - x74 - x76 - x77 - x78 - x79 - x80 + 6 x81 + x82
x4 = - x18 - x27 - x36 - x45 - x54 - x63 - x72 - x73 - x74 - x75 - x77 - x78 - x79 - x80 + 6 x81 + x82
x5 = - x18 - x27 - x36 - x45 - x54 - x63 - x72 - x73 - x74 - x75 - x76 - x78 - x79 - x80 + 6 x81 + x82
x6 = - x18 - x27 - x36 - x45 - x54 - x63 - x72 - x73 - x74 - x75 - x76 - x77 - x79 - x80 + 6 x81 + x82
x7 = - x18 - x27 - x36 - x45 - x54 - x63 - x72 - x73 - x74 - x75 - x76 - x77 - x78 - x80 + 6 x81 + x82
x8 = - x18 - x27 - x36 - x45 - x54 - x63 - x72 - x73 - x74 - x75 - x76 - x77 - x78 - x79 + 6 x81 + x82
x9 = - x18 - x27 - x36 - x45 - x54 - x63 - x72 - x73 - x74 - x75 - x76 - x77 - x78 - x79 - x80 + 7 x81 + x82
x10 = x18 + x73 - x81
x11 = x18 + x74 - x81
x12 = x18 + x75 - x81
x13 = x18 + x76 - x81
x14 = x18 + x77 - x81
x15 = x18 + x78 - x81
x16 = x18 + x79 - x81
x17 = x18 + x80 - x81
x19 = x27 + x73 - x81
x20 = x27 + x74 - x81
x21 = x27 + x75 - x81
x22 = x27 + x76 - x81
x23 = x27 + x77 - x81
x24 = x27 + x78 - x81
x25 = x27 + x79 - x81
x26 = x27 + x80 - x81
x28 = x36 + x73 - x81
x29 = x36 + x74 - x81
x30 = x36 + x75 - x81
x31 = x36 + x76 - x81
x32 = x36 + x77 - x81
x33 = x36 + x78 - x81
x34 = x36 + x79 - x81
x35 = x36 + x80 - x81
x37 = x45 + x73 - x81
x38 = x45 + x74 - x81
x39 = x45 + x75 - x81
x40 = x45 + x76 - x81
x41 = x45 + x77 - x81
x42 = x45 + x78 - x81
x43 = x45 + x79 - x81
x44 = x45 + x80 - x81
x46 = x54 + x73 - x81
x47 = x54 + x74 - x81
x48 = x54 + x75 - x81
x49 = x54 + x76 - x81
x50 = x54 + x77 - x81
x51 = x54 + x78 - x81
x52 = x54 + x79 - x81
x53 = x54 + x80 - x81
x55 = x63 + x73 - x81
x56 = x63 + x74 - x81
x57 = x63 + x75 - x81
x58 = x63 + x76 - x81
x59 = x63 + x77 - x81
x60 = x63 + x78 - x81
x61 = x63 + x79 - x81
x62 = x63 + x80 - x81
x64 = x72 + x73 - x81
x65 = x72 + x74 - x81
x66 = x72 + x75 - x81
x67 = x72 + x76 - x81
x68 = x72 + x77 - x81
x69 = x72 + x78 - x81
x70 = x72 + x79 - x81
x71 = x72 + x80 - x81

Для квадрата порядка 10 время решения системы уравнений вполне может составить несколько сотен часов. Это само по себе, может быть, и не страшно, но за это время с большой вероятностью может произойти отключение электроэнергии, и придётся начинать решение заново, так как никаких средств для сохранения промежуточных результатов не предусмотрено. Кроме того, для решения последней системы программа заняла 567 мегабайт в оперативной памяти, и я боюсь, что для решения в 10 раз большей системы просто не хватит места.

 Профиль  
                  
 
 Re: Антимагические квадраты
Сообщение28.05.2012, 15:29 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Грандиозно!
Ну, больше "издеваться" не будем :D

Собственно, можно было остановиться и на порядке 7.
Спасибо за решения.
Теперь осталось написать программу по общей формуле для примитивного квадрата 7-го порядка. Насколько она будет эффективнее программы построения примитивного квадрата просто по определению, как я делала раньше, - это пока неизвестно.

Вот сейчас реализовала уже последнюю формулу примитивного квадрата 6-го порядка (с 11 свободными переменными). Конечно, по сравнению с первой формулой (с 17 свободными переменными) эта программа работает намного быстрее. Но вот по сравнению с программой построения примитивного квадрата по определению вряд ли быстрее (тут тоже 11 свободных переменных). Что-то я не заметила пока убыстрения. Но... возможен ещё один подход (и даже не один!) к реализации этой же формулы. Впору писать ещё одну программу :-)

И задача нахождения
1. наименьшего квадрата Стенли из простых чисел 6-го порядка
2. то же для 7-го порядка
остаётся открытой.

Да, полученные общие формулы для квадратов Стенли порядков 6, 7, 8, 9 могут оказаться полезными в такой области, которую пока даже невозможно представить.
Я вот заинтересовалась этими квадратами; оказалось, что квадраты Стенли - это не что иное как примитивные квадраты, а примитивные квадраты очень нужны для построения пандиагональных магических квадратов. Вот такой неожиданный получился переход от квадратов Стенли к пандиагональным квадратам.

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


22/03/08

7154
Саратов
Зато примитивный квадрат 6-го порядка из массива, состоящего из 36 чисел, строится по новой программе мгновенно, если он существует.

Сейчас проделала эксперимент. Взяла совершенный квадрат 6-го порядка из простых чисел (из статьи "Нетрадиционные совершенные квадраты"):

Код:
149 9161 2309 6701 2609 8861
9067 1483 6907 3943 6607 1783
4139 5171 6299 2711 6599 4871
3229 7321 1069 9781 769 7621
5987 3323 8147 863 8447 3023
7219 3331 5059 5791 4759 3631

Магическая константа квадрата равна 29790, очень большая, возможно, существует квадрат с меньшей константой.
Квадрат этот я построила без применения примитивного квадрата, совсем по другому алгоритму (алгоритм описан в указанной статье).

Теперь ввела в программу массив чисел, из которых составлен этот квадрат и мгновенно получила примитивный квадрат:

Код:
9067  6607  8147  5987  8447  6907
7219  4759  6299  4139  6599  5059
9781  7321  8861  6701  9161  7621
3229  769  2309  149  2609  1069
3943  1483  3023  863  3323  1783
5791  3331  4871  2711  5171  3631

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

Итак, новая задача: найти наименьший квадрат Стенли 6-го порядка, составленный из комплементарных пар чисел для превращения его в совершенный квадрат.

В этой же статье есть интересный примитивный квадрат 8-го порядка из простых чисел, это собственно квадрат Стенли, который обладает свойством ассоциативности:

Код:
19 83 1019 1583 3229 3793 4729 4793
103 167 1103 1667 3313 3877 4813 4877
499 563 1499 2063 3709 4273 5209 5273
523 587 1523 2087 3733 4297 5233 5297
709 773 1709 2273 3919 4483 5419 5483
733 797 1733 2297 3943 4507 5443 5507
1129 1193 2129 2693 4339 4903 5839 5903
1213 1277 2213 2777 4423 4987 5923 5987

Индекс этого квадрата Стенли равен 24024. Можно на этом квадрате проверить общую формулу, полученную Someone.

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

 Профиль  
                  
 
 Re: Антимагические квадраты
Сообщение29.05.2012, 04:48 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Кстати, если приведённый выше квадрат Стенли 6-го порядка (из простых чисел) с индексом 29790 нормализовать (в нормализованном примитивном квадрате элементы первой строки и элементы первого столбца расположены в порядке возрастания; понятно, что и в любой другой строке (другом столбце) элементы располагаются тоже в порядке возрастания, ибо это определяется расположением элементов в первой строке и в первом столбце), получится квадрат Стенли, обладающий свойством ассоциативности:

Код:
149 769 1069 2309 2609 3229
863 1483 1783 3023 3323 3943
2711 3331 3631 4871 5171 5791
4139 4759 5059 6299 6599 7219
5987 6607 6907 8147 8447 9067
6701 7321 7621 8861 9161 9781

Ассоциативный квадрат Стенли 6-го порядка из простых чисел с меньшим индексом найдите-ка :wink:

Если не найдёте, приведённый квадрат будет наименьшим в данном классе квадратов.

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


22/03/08

7154
Саратов
Someone в сообщении #577600 писал(а):
Для квадрата порядка 10 время решения системы уравнений вполне может составить несколько сотен часов.

Ну, я, пожалуй, могу решить быстрее :D
Посмотрела на все решения, очень они похожи, как одна мать родила :-)
Прекрасно работает аналогия.
Вот общее решение для квадрата Стенли 5-го порядка, я написала его вручную по аналогии:

Код:
x1=-x10-x15-x20-x22-x23-x24+2 x25+x26
x2=-x10-x15-x20-x21-x23-x24+2 x25+x26
x3=-x10-x15-x20-x21-x22-x24+2 x25+x26
x4=-x10-x15-x20-x21-x22-x23+2 x25+x26
x5=-x10-x15-x20-x21-x22-x23-x24+3 x25+x26
x6=x10+x21-x25
x7=x10+x22-x25
x8=x10+x23-x25
x9=x10+x24-x25
x11=x15+x21-x25
x12=x15+x22-x25
x13=x15+x23-x25
x14=x15+x24-x25
x16=x20+x21-x25
x17=x20+x22-x25
x18=x20+x23-x25
x19=x20+x24-x25

Правильно решила? :?
Проверила решение в числах из известного квадрата Стенли 5-го порядка. Всё получилось. Могла только сделать описку при наборе.
В системе 120 уравнений, 26 неизвестных. Как и должно быть (по правилу примитивного квадрата), получилось 9 свободных неизвестных и 17 зависимых.

Ну, и таким же макаром можно написать общее решение для квадрата Стенли 10-го порядка. Думаю, что для этого мне потребуется гораздо меньше времени, чем несколько сотен часов. И памяти, надеюсь, хватит :-)
В системе 10! уравнений, 101 неизвестных.


И вот она - общая формула примитивного квадрата 5-го порядка.
Сколько мы потратили усилий на выбор лучшей тактики построения такого квадрата!
Программ я написала штук 7.
Наименьшие примитивные квадраты 5-го порядка из простых чисел (константа 395) и из чисел Смита (константа 8318) нам известны. Оба квадрата нашёл Pavlovsky.

У нас есть интересная задача, связанная с построением примитивных квадратов 5-го порядка: надо построить 4 таких квадрата (из простых чисел) с одинаковой константой, чтобы они все состояли из различных чисел. Тогда из этих квадратов можно составить пандиагональный квадрат 10-го порядка.

Задачу упорно решал Pavlovsky, я тоже немного решала. Но до конца задача так и не решена.

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


22/03/08

7154
Саратов
Эх, Pavlovsky похоже ушёл в отпуск :-)

У меня уже столько задач возникло, а решать некому.

Итак, порылась в старых файлах. Нашла два комплекта из трёх квадратов Стенли 5-го порядка из простых чисел с индексом 1765:

Код:
№ 1
5 23 53 137 347
41 59 89 173 383
179 197 227 311 521
431 449 479 563 773
569 587 617 701 911

№ 2
71 151 199 239 601
83 163 211 251 613
101 181 229 269 631
113 193 241 281 643
491 571 619 659 1021

№ 3
11 7 31 641 271
17 13 37 647 277
47 43 67 677 307
317 313 337 947 577
467 463 487 1097 727

Код:
№ 1
3 5 53 131 173
11 13 61 139 181
101 103 151 229 271
641 643 691 769 811
659 661 709 787 829

№ 2
7 17 31 167 607
19 29 43 179 619
73 83 97 233 673
433 443 457 593 1033
439 449 463 599 1039

№ 3
23 71 137 227 491
109 157 223 313 577
163 211 277 367 631
283 331 397 487 751
353 401 467 557 821

В каждом комплекте все три квадрата составлены из различных простых чисел.

Задача
в каждом из комплектов найти четвёртый квадрат Стенли с таким же индексом, составленный из простых чисел, не принадлежащих трём известным квадратам.

Таких комплектов из трёх квадратов было найдено очень много, есть и с другими индексами, меньше 1765.
Полный комплект из четырёх квадратов с индексом 1797 нашёл Pavlovsky, этот комплект и дал наименьший на сегодня пандиагональный квадрат 10-го порядка из простых чисел с магической константой 3594.

Запрограммировала свою общую формулу для квадратов Стенли 5-го порядка. Программа работает удовлетворительно. Сейчас запустила её на проверку: есть ли ещё квадрат Стенли с индексом 1765 (к первому комплекту из 3-х квадратов). При этом выбросила из массива все числа, входящие в три квадрата. Затем проверю второй комплект.

 Профиль  
                  
 
 Re: Антимагические квадраты
Сообщение30.05.2012, 03:32 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Да, даже для порядка 5 выполнить полный перебор не так просто, проверка константы 1765 для первого комплекта продолжается, пока четвёртый квадрат не найден. Скорее всего, он и не существует. В своё время я проверяла этот комплект и квадрат так и не нашла, хотя полный перебор, конечно, и тогда не выполнила.

Пока работает программа, посмотрела свою статью "Нетрадиционные пандиагональные квадраты (часть V)"
Вот интересная картинка из этой статьи по теме:

Изображение

Квадраты Стенли 5-го порядка из комплекта № 1 превращены в пандиагональные квадраты и вписаны в матрицу 10х10 по решёткам Россера.
Пандиагональный квадрат 10-го порядка из различных простых чисел почти готов, не хватает четвёртого квадрата. Если разрешить повторение чисел, то четвёртый квадрат найдётся мгновенно, так как квадратов Стенли 5-го порядка с индексом 1765 из простых чисел очень много.

Этот пандиагональный квадрат имел бы магическую константу 3530, что меньше известной на сегодня наименьшей константы 3594.

-- Ср май 30, 2012 05:10:29 --

Покажу ещё два комплекта из трёх квадратов Стенли с одинаковым индексом, составленных из различных простых чисел, эти комплекты из статьи "Построение пандиагональных квадратов по решёткам Россера".

Комплект № 3 с индексом 1579:

Код:
№ 1
3 5 29 53 269
11 13 37 61 277
17 19 43 67 283
347 349 373 397 613
857 859 883 907 1123

№ 2
7 23 79 89 313
31 47 103 113 337
151 167 223 233 457
157 173 229 239 463
757 773 829 839 1063

№ 3
59 71 101 383 401
97 109 139 421 439
137 149 179 461 479
199 211 241 523 541
367 379 409 691 709

Комплект № 4 с индексом 1599 (автор Pavlovsky, post348126.html#p348126 )

Код:
№ 1
29 47 179 257 389
41 59 191 269 401
131 149 281 359 491
293 311 443 521 653
349 367 499 577 709

№ 2
7 13 19 157 967
31 37 43 181 991
61 67 73 211 1021
271 277 283 421 1231
101 107 113 251 1061

№ 3
79 97 163 199 379
109 127 193 229 409
313 331 397 433 613
523 541 607 643 823
53 71 137 173 353

Pavlovsky сообщал, что ему не удалось найти к этому комплекту четвёртый квадрат.

Чем меньше константа квадратов, тем быстрее выполнится полный перебор. Обязательно проверю свой комплект квадратов с индексом 1579.

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

 Профиль  
                  
 
 Re: Антимагические квадраты
Сообщение29.12.2012, 09:30 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Nataly-Mak в сообщении #576531 писал(а):
Получила ещё ряд квадратов Стенли из чисел Смита, наименьший индекс пока у меня 3040:

Код:
706 895 2362 562
166 355 1822 22
265 454 1921 121
202 391 1858 58


Нашла квадрат Стенли из смитов с индексом 2088:

Код:
85 94 121 517
346 355 382 778
526 535 562 958
654 663 690 1086

Освежила всё в памяти, переписала заново программы для n=4,5.
Подготовила и отправила материалы "Антимагические квадраты Стенли" на сайт primepuzzles.net
Напомню известные квадраты Стенли из простых чисел (n - порядок квадрата, S - индекс).

Код:
n=2, S=16
3 5
11 13

n=3, S=53
3 11 17
5 13 19
23 31 37

n=4, S=150
5 43 19 13
23 61 37 31
3 41 17 11
59 97 73 67

n=5, S=395 (этот квадрат составил Pavlovsky)
5 7 17 31 131
11 13 23 37 137
41 43 53 67 167
71 73 83 97 197
101 103 113 127 227

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

Квадрат Стенли 6-го порядка из простых чисел я тоже построила, но не уверена в минимальности индекса:

Код:
13 19 43 109 139 223
31 37 61 127 157 241
41 47 71 137 167 251
53 59 83 149 179 263
67 73 97 163 193 277
101 107 131 197 227 311

Индекс этого квадрата равен 774. Есть ли с меньшим индексом :?:

Есть и квадраты следующих порядков, но тоже не с минимальными индексами.
Впрочем, для квадрата 7-го порядка никто пока не доказал, что индекс 1597 не является минимальным.

Вот квадрат Стенли 7-го порядка с индексом 1597:

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

Собственно говоря, это примитивный квадрат, из которого я построила методом Россера пандиагональный квадрат 7-го порядка.

 Профиль  
                  
 
 Re: Антимагические квадраты
Сообщение29.12.2012, 17:26 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Очень долго пришлось объяснять автору сайта http://www.primepuzzles.net, что такое квадраты Стенли.
Послала ему то определение, которое здесь приведено (из переведённой на русский язык книги Р. Стенли "Перечислительная комбинаторика"), он пишет, что не понимает по-русски.
Перевела определение на английский язык в Гугле-переводчике, он опять не понял.
Пришлось искать эту книгу на английском языке.
Ну, вот, когда послала ему ссылку на эту книгу (с указанием страницы, где приведено это определение), тогда он понял.

Вот ссылка на эту книгу, может быть, кому пригодится, чтобы не искать,
Richard P. Stanley. Enumerative Combinatorics
http://www-math.mit.edu/~rstan/ec/ec1.pdf

Carlos Rivera в свою очередь прислал мне ссылку на другие антимагические квадраты:
http://mathworld.wolfram.com/AntimagicSquare.html

Увы, антимагических квадратов (разных по определению) очень много, но мне нравятся именно квадраты Стенли. Всё остальное совсем из другой оперы :-)

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


22/03/08

7154
Саратов
Пытаюсь найти квадрат Стенли 6-го порядка из простых чисел с индексом меньше 774.
Пока не получается.
Мне вдруг показалось, что индекс квадрата Стенли 6-го порядка должен быть кратен 6 (по пандиагональным квадратам 6-го порядка). Однако это совсем не так, что ещё раз подтверждает: нет никакой связи между квадратами Стенли и пандиагональными квадратами порядка 6.
Просмотрела черновые записи о квадратах Стенли; найдены квадраты 6-го порядка с индексами:
1204, 984, 966, 922, 900, 774.
Очевидно, что не все индексы кратны 6.

Теперь меня очень заинтересовал вопрос: могут ли быть пропуски в ряду индексов для квадратов Стенли 6-го порядка? Скорее всего, могут. Так, мне не удалось найти квадрат с индексом 780 (прокрутила программу полного перебора для массива из 100 простых чисел). Сейчас запустила программу на поиск квадрата с индексом 786; похоже на то, что и такого квадрата нет.
Далее надо идти в сторону уменьшения индекса. Уже прогнала программу для индексов 772 и 768. Решение не найдено.

-- Вт янв 01, 2013 18:18:54 --

Someone в сообщении #577151 писал(а):
Результат:
Код:
x1 = - x12 - x18 - x24 - x30 - x32 - x33 - x34 - x35 + 3 x36 + x37
x2 = - x12 - x18 - x24 - x30 - x31 - x33 - x34 - x35 + 3 x36 + x37
x3 = - x12 - x18 - x24 - x30 - x31 - x32 - x34 - x35 + 3 x36 + x37
x4 = - x12 - x18 - x24 - x30 - x31 - x32 - x33 - x35 + 3 x36 + x37
x5 = - x12 - x18 - x24 - x30 - x31 - x32 - x33 - x34 + 3 x36 + x37
x6 = - x12 - x18 - x24 - x30 - x31 - x32 - x33 - x34 - x35 + 4 x36 + x37
x7 = x12 + x31 - x36
x8 = x12 + x32 - x36
x9 = x12 + x33 - x36
x10 = x12 + x34 - x36
x11 = x12 + x35 - x36
x13 = x18 + x31 - x36
x14 = x18 + x32 - x36
x15 = x18 + x33 - x36
x16 = x18 + x34 - x36
x17 = x18 + x35 - x36
x19 = x24 + x31 - x36
x20 = x24 + x32 - x36
x21 = x24 + x33 - x36
x22 = x24 + x34 - x36
x23 = x24 + x35 - x36
x25 = x30 + x31 - x36
x26 = x30 + x32 - x36
x27 = x30 + x33 - x36
x28 = x30 + x34 - x36
x29 = x30 + x35 - x36
Это решение я проверил подстановкой чисел из квадрата в сообщении http://dxdy.ru/post577021.html#p577021.

Это общая формула квадратов Стенли 6-го порядка, найденная решением системы из 720 уравнений с 37 неизвестными.

Поскольку установлено, что квадраты Стенли это то же самое, что примитивные квадраты по Россеру, предложу другую общую формулу квадратов Стенли 6-го порядка, полученную по алгоритму составления примитивного квадрата:

Код:
x8 = x2 + x7 - x1
x9 = x3 + x8 - x2
x10 = x4 + x9 - x3
x11 = x5 + x10 - x4
x12 = x6 + x11 - x5
x14 = x8 + x13 - x7
x15 = x9 + x14 - x8
x16 = x10 + x15 - x9
x17 = x11 + x16 - x10
x18 = x12 + x17 - x11
x20 = x14 + x19 - x13
x21 = x15 + x20 - x14
x22 = x16 + x21 - x15
x23 = x17 + x22 - x16
x24 = x18 + x23 - x17
x26 = x20 + x25 - x19
x27 = x21 + x26 - x20
x28 = x22 + x27 - x21
x29 = x23 + x28 - x22
x30 = x24 + x29 - x23
x31 = x37 - x6 - x11 - x16 - x21 - x26
x32 = x26 + x31 - x25
x33 = x27 + x32 - x26
x34 = x28 + x33 - x27
x35 = x29 + x34 - x28
x36 = x30 + x35 - x29

Эквивалентность этих двух формул должна быть железно.

Вопрос такой: какая из формул предпочтительнее для программирования :?:
В обеих формулах переменные обозначают одно и то же: $x_i$ - элементы квадрата (i = 1,2,3,...,36), $x_{37}$ - индекс квадрата.

У меня сейчас запрограммирована вторая формула. По этой программе я нашла квадрат Стенли с индексом 774 (показан чуть выше). Уменьшить индекс пока не удаётся.
Программа выполняет полный перебор для массива из 100 простых чисел (квадраты составляются из простых чисел). Алгоритм - перебор с возвратом.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 237 ]  На страницу Пред.  1, 2, 3, 4, 5, 6, 7, 8 ... 16  След.

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

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