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

[Pavlovsky]

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

Я неверно поняла указанную теорему?

Бегло посмотрел теорему 5.5. В теореме 5.5 описывается способ построения класссического квадрата из последовательных натуральных чисел. Как этот способ можно применить к построению квадрата из простых чисел?
И как эта теорема относится к вашему алгоритму пострения квадрата порядка 4m из m^2 квадратов порядка 4??

В общем случае (нетрадиционных квадратов) у нас возможны квадраты с решетками L(2) (теорема 2.4) и с решетками L(3) (теорема 2.5). О существовании квадратов с решетками L(m), где m>3 ничего неизвестно.

[Nataly-Mak]

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

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

Я неверно поняла указанную теорему?

Бегло посмотрел теорему 5.5. В теореме 5.5 описывается способ построения класссического квадрата из последовательных натуральных чисел. Как этот способ можно применить к построению квадрата из простых чисел?

Ещё раз: выше я дала ссылки на две статьи - о построении нетрадиционных квадратов порядков 8 и 12. Вы их посмотрели? Там же всё написано!

Строите примитивный квадрат из произвольных натуральных чисел (или же из простых чисел, или же из чисел Смита), который удовлетворяет указанным условиям.
Построили? Далее применяете к этому квадрату преобразование Россера, да, да именно то, которое он использует при построении классических пандиагональных квадратов данных порядков. Оно работает и для нетрадиционных пандиагональных квадратов.
В статье о квадратах 8-го порядка приведён пример из произвольных натуральных чисел. Для простых чисел я этот метод не реализовала.

Всё точно так же для порядков 12,16 и т.д., вообще для любого порядка n=4k, k=1,2,3,...

Цитата:

И как эта теорема относится к вашему алгоритму построения квадрата порядка 4m из m^2 квадратов порядка 4??

Так это же построение по решёткам Россера.
Например, квадрат порядка 12 (4*3) строится по решёткам из 9 пандиагональных квадратов порядка 4.

Цитата:

В общем случае (нетрадиционных квадратов) у нас возможны квадраты с решетками L(2) (теорема 2.4) и с решетками L(3) (теорема 2.5). О существовании квадратов с решетками L(m), где m>3 ничего неизвестно.

То есть вы хотите сказать, что невозможно иметь 9 решёток, или m^2 решёток?
Не знаю, я такие пандиагональные квадраты построила для порядков 12, 15, 18.
Все они правильные, если судить по тому, что многие ввели эти мои решения на конкурс и конкурсная программа их приняла.

[Pavlovsky]

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

То есть вы хотите сказать, что невозможно иметь 9 решёток, или m^2 решёток?

Я утверждаю что невозможно иметь 16,25 и так далее m^2 решеток.

[Nataly-Mak]

А я про 16,25 и т.д. ничего и не говорила вроде. У меня 9 решёток в моих алгоритмах используется.
(может, где и обобщила невзначай на m^2 решёток, тогда виновата; сейчас гляну, где я писала о построении по решёткам Россера).

Вот, например, пандиагональный квадрат 12-го порядка из чисел Смита, построенный из 9 пандиагональных квадратов 4-го порядка:



Вот что яписала о построении по решёткам для N нечётных и кратных 3:

Цитата:

Если N нечётное составное число, например, кратное 3 (N>9), тогда строим квадрат порядка N из девяти пандиагональных квадратов порядка N/3. Решёток в этом случае будет девять. Пример для N=15 можно найти в моих статьях.

Pavlovsky
где вы нашли обобщение на m^2 решёток?
Хотя я думаю, что и 16 решёток вполне возможны и 25 тоже.
У меня, кажется есть, квадрат 16-го порядка, построенный по решёткам. Сейчас посмотрю.

-- Чт июл 04, 2013 16:56:09 --

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

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

То есть вы хотите сказать, что невозможно иметь 9 решёток, или m^2 решёток?

Я утверждаю что невозможно иметь 16,25 и так далее m^2 решеток.

Возможно
В статье
http://www.natalimak1.narod.ru/kompl556.htm
приведён пандиагональный квадрат 16-го порядка из простых чисел, построенный из 16 пандиагональных квадратов 4-го порядка, заполняющих 16 решёток.

Да, Pavlovsky, а статьи-то мои вы совсем не читали, пренебрегли

[Pavlovsky]

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

Всё точно так же для порядков 12,16 и т.д., вообще для любого порядка n=4k, k=1,2,3,...

Для N=16 надо пострить 16 квадратов 4х4.

[Nataly-Mak]

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

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

Всё точно так же для порядков 12,16 и т.д., вообще для любого порядка n=4k, k=1,2,3,...

Для N=16 надо пострить 16 квадратов 4х4.

Это вы о решётках? Да, да, именно 16 квадратов я и построила
См. предыдущий пост.
Это решение единственное известное на начало конкурса (S=48048).

[Pavlovsky]

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

приведён пандиагональный квадрат 16-го порядка из простых чисел, построенный из 16 пандиагональных квадратов 4-го порядка, заполняющих 16 решёток.

Повезло. Россер этого не обещал.

[Nataly-Mak]

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

Повезло. Россер этого не обещал.

Везёт тому, кто сам везёт
Не обязательно ждать от кого-то обещаний, можно и своей головой подумать.

[Pavlovsky]

Наверно вы попали в теорему 2.3. Надо будет в ней разобраться.

[Nataly-Mak]

Pavlovsky
если попала, то совершенно случайно
Я просто усвоила метод построения по решёткам (о котором писали в теме "Магические квадраты" вы и svb) и далее применяла его всюду, где было возможно, не задумываясь, что там Россер обещал.

Вообще, алгоритмы Россера хороши, но... алгоритм Jarek, наверное, намного лучше, потому что он нашёл решения несравнимо лучшие, чем были найдены нами по алгоритмам Россера.

-- Чт июл 04, 2013 17:34:13 --

Цитата:

Europe
1 Poland 1
5 Netherlands 1
6 Germany 2
12 Belgium 1
14 United Kingdom 2
16 Latvia 1
19 Switzerland 1
25 Finland 1
North America
2 United States 8
15 Mexico 1
Australia – Oceania
3 Australia 2
Asia
4 Russia 3
10 India 1
11 Israel 1

Число слева - лучшее место, занимаемое участником из данной страны; число справа - количество участников из страны.
Как всегда, по количеству участников лидируют США, Россия на втором месте - 3 участника.
Но очень мало, очень
Среди участников из Азии Россия на первом месте

[Nataly-Mak]

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

Для квадратов 12-го порядка условия для примитивного квадрата мной тоже были сформулированы:

Цитата:

Интересно отметить, что примитивный квадрат 12-го порядка удовлетворяет условиям, аналогичным условиям для примитивных квадратов 4-го и 8-го порядков. Обозначим элементы первой строки и первого столбца примитивного квадрата символами

c a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11
b1           
b2           
b3           
b4           
b5           
b6           
b7           
b8           
b9           
b10           
b11

Тогда условия для элементов примитивного квадрата можно записать так:

c + a6 = a1 + a7 = a2 + a8 = a3 + a9 = a4 + a10 = a5 + a11
c + b6 = b1 + b7 = b2 + b8 = b3 + b9 = b4 + b10 = b5 + b11

(см. статью)

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

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

dmd
обратите внимание - примитивный квадрат я строила вручную, без Excel, с калькулятором
Сначала записала числа в первой строке и в первом столбце квадрата так, чтобы выполнялись приведённые в цитате условия, а потом элементарно достроила квадрат.
Вот он:

3 5 11 17 23 37 211 209 203 197 191 177
43 45 51 57 63 77 251 249 243 237 231 217
51 53 59 65 71 85 259 257 251 245 239 225
59 61 67 73 79 93 267 265 259 253 247 233
67 69 75 81 87 101 275 273 267 261 255 241
71 73 79 85 91 105 279 277 271 265 259 245
321 323 329 335 341 355 529 527 521 515 509 495
281 283 289 295 301 315 489 487 481 475 469 455
273 275 281 287 293 307 481 479 473 467 461 447
265 267 273 279 285 299 473 471 465 459 453 439
257 259 265 271 277 291 465 463 457 451 445 431
253 255 261 267 273 287 461 459 453 447 441 427

Теперь применяю к этому примитивному квадрату преобразование Россера:

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

и получаю следующий пандиагональный квадрат:

71 267 267 259 321 289 293 473 457 441 3 51
273 265 495 283 287 299 463 447 177 45 65 93
509 281 281 285 465 453 191 43 59 79 275 271
275 279 291 459 197 217 53 73 101 277 515 455
277 461 203 231 51 67 87 279 521 469 273 273
209 237 225 61 81 105 527 475 447 267 271 287
239 59 75 91 529 481 461 265 265 273 211 243
69 85 355 487 467 439 259 267 37 249 245 233
341 489 473 453 257 261 23 251 251 247 67 79
479 459 431 255 17 77 257 253 241 73 335 315
445 253 11 63 259 259 255 71 329 301 481 465
5 57 85 265 261 245 323 295 307 471 451 427

Всё чётко работает. Осталось найти решение, полученное этим методом, для квадратов порядка 8 и 12 из (различных) простых чисел. Ну, это уже задача для участников конкурса, я в конкурсе не участвую
Вообще-то решения для N=8,12 мной были найдены, но по другим алгоритмам.
Для N=8 сначала строила по решёткам Россера, а потом по другому алгоритму получила лучшее решение (S=1584). Для N=12 решение получено по решёткам (S=8820).
Я не знаю, лучшие или худшие решения даст этот алгоритм.

-- Чт июл 04, 2013 19:40:46 --

Приведённый выше примитивный квадрат 12-го порядка в программе mertz (сделанной для конкурса Prime Sums)



К сожалению, mertz не отозвался на мою просьбу модифицировать программу, чтобы показывались все числа квадрата.
Кстати, можно, наверное, модифицировать программу таким образом, чтобы можно было играться с примитивными квадратами, изменяя содержимое ячеек, как это предложил dmd в Excel. Конечно, такая ручная игра мало что может дать, ну если только поиграть

-- Чт июл 04, 2013 19:51:15 --

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



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

[Nataly-Mak]

Pavlovsky
и 25 решёток тоже возможны

Цитата из моей статьи:

Цитата:

Уже дописав статью, решила попробовать построение пандиагонального квадрата 20-го порядка из различных простых чисел по решёткам Россера. Поскольку пандиагональные квадраты 4-го порядка строятся быстрее, чем 5-го порядка, начала с поиска 25 пандиагональных квадратов 4-го порядка.
...
Размещаем найденные 25 квадратов в решётки Россера, и пандиагональный квадрат 20-го порядка готов. Смотрите этот квадрат на рис. 11. Ничего не могу сказать о минимальности построенного квадрата, это первый такой квадрат. Для порядка 20 магическая константа не очень большая. Однако обычный наименьший магический квадрат 20-го порядка из простых чисел имеет магическую константу 25530. Вполне может быть, что существуют пандиагональные квадраты с меньшей магической константой, чем найденный мной квадрат.

Здесь ещё больше повезло, ибо построены 25 пандиагональных квадратов 4-го порядка с одинаковой магической константой и из различных простых чисел.
Везение просто грандиозное

Пример взят из последней статьи цикла "Нетрадиционные пандиагональные квадраты".
Там же показан и самый большой пандиагональный квадрат из различных простых чисел, какой мне удалось построить, это квадрат 24-го порядка. Этот квадрат тоже построен по решёткам. Магическая константа квадрата равна 72072.

[dmd]

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

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

Нет, это важно, и суть проблемы от этого сильно меняется. Т.к. для конкурса квадраты нужно строить из простых чисел. Избегать одинаковые и непростые числа придётся ценою увеличения магической константы. Неприемлемо сильного увеличения. По крайней мере мои программы постоянно мне это демонстрируют. Использую последовательный перебор простых для $2N-1$ независимых переменных примитивного квадрата, проверяю остальные ячейки на уникальность и простоту, пытаюсь сочетать перебор со случайным выбором простого числа из некоторого диапазона - безрезультатно, константы получаются огромадные. Нужны какие-то более сильные эвристики, чтоб при построении квадрата попадать в область текущих минимальных констант.

[Nataly-Mak]

dmd в сообщении #743348 писал(а):

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

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

Нет, это важно, и суть проблемы от этого сильно меняется.

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

Принцип того метода, который я демонстрирую в примере для N=12 (точно так же и для N=8) ничуть не зависит оттого, есть в примитивном квадрате повторяющиеся числа или их нет. Дело в принципе метода!

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

-- Пт июл 05, 2013 00:10:14 --

Вот примеры из статьи
http://www.natalimak1.narod.ru/pannetr2.htm

Это примитивный квадрат 8-го порядка из произвольных натуральных чисел, удовлетворяющий нужным условиям, построенный вручную:

3 7 13 19 47 43 37 31
53 57 63 69 97 93 87 81
59 63 69 75 103 99 93 87
71 75 81 87 115 111 105 99
157 161 167 173 201 197 191 185
107 111 117 123 151 147 141 135
101 105 111 117 145 141 135 129
89 93 99 105 133 129 123 117

В этом квадрате есть одинаковые числа.

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

11 23 53 101 233 221 191 143
19 31 61 109 241 229 199 151
37 49 79 127 259 247 217 169
73 85 115 163 295 283 253 205
145 157 187 235 367 355 325 277
137 149 179 227 359 347 317 269
119 131 161 209 341 329 299 251
83 95 125 173 305 293 263 215

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

Ещё раз: принцип демонстрируемого мной метода не зависит от наличия в примитивном квадрате одинаковых чисел. Преобразование Россера применимо к обоим этим примитивным квадратам! Вы с этим не согласны?

Сейчас у меня на столе среди кучи других задач лежит и эта задача. Просто стало интересно: какое решение даст этот алгоритм для N=8. Как я уже писала, решение для N=8 найдено мной по другим алгоритмам (задолго до конкурса), именно алгоритмам, ибо их было два: первый - решётки, второй основан на идее svb с псевдокомплементарными числами. По второму алгоритму мне удалось получить своё лучшее решение (S=1584).

-- Пт июл 05, 2013 00:31:59 --

И снова Jarek!

Цитата:

1 15.00 Jarek Wroblewski Wroclaw, Poland 4 Jul 2013 19:36

[dimkadimon]

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

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