Магические квадраты

[svb]

Еще попытка:

17 1979 1567 613 383 211 109 
397 223 53 23 1987 1579 617 
1999 1583 631 409 167 59 31 
173 67 43 2003 1597 643 353 
1609 587 359 181 79 47 2017 
83 61 2029 1553 593 367 193 
601 379 197 97 73 1973 1559 
S= 4879

-- Ср май 19, 2010 03:41:34 --

13 887 919 911 491 269 277 
521 317 19 61 929 967 953 
977 1009 983 569 59 67 103 
107 109 151 1019 1039 1031 311 
1087 773 359 149 157 193 1049 
199 223 1097 829 821 401 197 
863 449 239 229 271 839 877 
S= 3767

[Nataly-Mak]

svb
От души поздравляю! Классный результат!

Напомню единственный пандиагональных квадрат 7-го порядка из смитов:

567274     3279802  5859274     20502022   33961666  75835678  191489962
75839458 191484922  562234     3274762     5863054     20505802  33965446
20500762   33960406   75843238   191488702 566014    3278542     5858014
3282322      5861794    20504542    33964186   75838198  191483662 560974
191487442  564754     3277282    5856754   20499502   33967966  75841978
33962926   75836938   191482402 568534     3281062  5860534    20503282
5855494    20507062    33966706  75840718  191486182  563494    3276022

Этот квадрат построен из 7 арифметических прогрессий длины 7 с одинаковой разностью.

[svb]

Еще не вечер

(Оффтоп)

13 1009 887 739 499 233 137 
509 281 19 31 1019 907 751 
1039 919 761 557 163 37 41 
181 47 61 1051 929 809 439 
977 691 457 191 67 73 1061 
79 83 1109 859 709 467 211 
719 487 223 89 131 991 877 
S= 3517

23 881 691 653 439 331 263 
457 337 149 41 911 727 659 
947 733 677 463 223 167 71 
241 197 107 953 751 683 349 
757 569 367 271 233 113 971 
239 131 977 643 587 397 307 
617 433 313 257 137 863 661 
S= 3281

7 1097 593 409 307 233 137 
317 263 31 17 1103 613 439 
1123 643 449 347 157 41 23 
167 47 43 1153 653 479 241 
683 373 251 173 67 73 1163 
97 83 1193 577 383 257 193 
389 277 223 107 113 1087 587 
S= 2783

13 659 521 547 307 251 223 
317 283 37 29 677 601 577 
757 631 587 349 97 53 47 
113 71 127 787 641 619 163 
673 433 179 131 151 157 797 
181 167 829 487 449 197 211 
467 277 241 191 199 643 503 
S= 2521

11 619 491 337 367 359 293 
409 383 41 29 661 557 397 
727 617 439 433 131 59 71 
149 101 137 787 659 463 181 
683 211 199 191 167 197 829 
227 239 853 431 229 241 257 
271 307 317 269 263 601 449 
S= 2477

[Nataly-Mak]

Вы волшебник!
Алгоритмом поделитесь, пожалуйста. Как строите примитивные квадраты?

[svb]

Сначала стал подбирать шаблоны, как уже писал. Вручную, но потом это быстро надоело. Решил брать их из исходного набора данных, т.е. программно последовательно просматриваю исходный массив (простых чисел) и определяю по какому шаблону они лежат (только соседние), затем ищу еще наборы с тем же шаблоном - как набираю 7 штук, так и примитивный квадрат готов. По мере получения p.s. отбираю с меньшей суммой. Этот способ хорошо помог, но ... попробовал на 5 порядке - вижу не дотягиваю до 395, где-то около 500. Тогда решил шаблоны не из последовательных данных, а через 1, через 2, ..., через 5 - оказалось выгодно брать каждый 6. Для 5-го порядка сдвинулся до 403, т.е. совсем рядом с 395. Попробовал смещения в шаблоне брать случайно - от 1 до 5..10 - 5-й порядок стал ловить 395. Для 7-го порядка вы видели. Попробовал эту же программу на таблице смитов - на 5 порядке шустро находит, до лучшего результата не дотягивает, но 10694 ловит. На 7 порядке глухо. Вот, пожалуй, и все.

[Nataly-Mak]

Если честно, пока ничего не поняла
Но это не столь важно.

Взяла ваш массив из квадрата с константой 2477 и протестировала на нём ещё раз свою программу построения примитивного квадрата. Программа выдала примитивный квадрат мгновенно:

853 683  463  433  383  293  263  
829 659  439  409  359  269  239 
787 617  397  367  317  227  197 
727 557  337  307  257  167  137 
661 491  271  241  191  101  71 
619 449  229  199  149  59  29 
601 431  211  181  131  41  11

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

Для последовательных смитов всё плохо. Хорошо только одно: программа проверки массива работает за 10-20 секунд для 100 массивов! Проверила уже 500 массивов, ни одного примитивного не составилось.

Кстати, вы каким преобразованием пользуетесь для превращения примитивного квадрата в пандиагональный?
Я пользуюсь таким:
A(i,j) = B(3i+2j,2i+j).
Из показанного примитивного квадрата с помощью данного преобразования получаю такой пандиагональный квадрат:

293 397 71 181 829 257 449
601 359 557 59 463 197 241
229 263 367 661 131 659 167
191 431 269 337 29 433 787
137 199 853 317 491 41 439
617 101 211 239 307 619 383
409 727 149 683 227 271 11

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

[Pavlovsky]

Для последовательных простых чисел пока тоже ничего. Проверил первые 23 миллиона простых чисел.

[Nataly-Mak]

Мне кажется, что для последовательных простых чисел крайне сложно найти набор из 49 чисел, для которых будут такие стройные смещения, какие нужны для составления примитивного квадрата. То же самое из последовательных смитов.
Кстати, из последовательных простых (и из смитов) не найден и пандиагональный квадрат 5-го порядка, да и 4-го не найден.

[Nataly-Mak]

maxal
а вы из смитов искали наборы, состоящие из 8 пар комплементарных чисел?
По-моему (если не запамятовала), у нас нет ещё пандиагонального квадрата 4-го порядка из произвольных смитов (ну, из последовательных смитов вообще никакого пока нет). Наименьший МК из произвольных смитов имеет константу 1195 (построен давно tolstopuz'ом).

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

94  454  202  706 
562  346  454  94 
526  22  634  274 
274  634  166  382

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

[svb]

Наконец-то выспался - более суток не спал с этими квадратами.

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

Кстати, вы каким преобразованием пользуетесь для превращения примитивного квадрата в пандиагональный?
Я пользуюсь таким:
A(i,j) = B(3i+2j,2i+j).

Да это не имеет принципиального значения. У меня для программки преобразования используется ini-файл, в котором записываются соответствующие матрицы - сейчас там записано

1 1
2 3

. Когда необходимо получить из d.s. примитивный, то просто вписываю в ini-файл обратную матрицу:

3 -1
-2 1

Необходимо лишь выполнять требования взаимной простоты по Rosser-у:

ТЕОРЕМА 3.1. Результат преобразование p.s. порядка n с помощью
$\[ T = \left\| {\begin{array}{*{20}c} a & c \\ b & d \\ \end{array}} \right\| \] $
будет дьявольским квадратом, если $\[ abcd\left( {a^2 - b^2 } \right)\left( {c^2 - d^2 } \right) \] $ взаимно просто с n.

Для обратимости матрицы преобразований необходимо, чтобы определитель матрицы был взаимно прост с порядком n. Использование иной обратной матрицы (от другого преобразования) ведет просто к перемешиванию строк/столбцов примитивного квадрата, но при этом он, естественно, остается примитивным. Rosser - сила!

-- Ср май 19, 2010 22:06:43 --

Вот процедура преобразования на паскале, я думаю, что она понятна для любителей иных языков:

procedure pr(var T:trans;var A,B:mag);
var i,j,ii,jj:integer;
begin
  for i:=0 to N-1 do for j:=0 to N-1 do begin
    B[i,j]:=0;
  end;
  for i:=0 to N-1 do for j:=0 to N-1 do begin
    ii:=(T[0,0]*i+T[0,1]*j);while ii<0 do ii:=ii+N;
    jj:=(T[1,0]*i+T[1,1]*j);while jj<0 do jj:=jj+N;
    ii:=ii mod N;
    jj:=jj mod N;
    B[ii,jj]:=A[i,j];
  end;
end;

Танцы с бубном с индексами необходимы для корректной работы операции "по модулю" - дело в том, что

x:=x mod N;

у меня неправильно работает при отрицательных "x". Замечу, что обнуление матрицы B[i,j] необходимо для того, чтобы можно было работать и с "неправильными" преобразованиями - в этом случае "0" в итоговом квадрате об этом подскажут.

[maxal]

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

maxal
а вы из смитов искали наборы, состоящие из 8 пар комплементарных чисел?

Нет.

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

По-моему (если не запамятовала), у нас нет ещё пандиагонального квадрата 4-го порядка из произвольных смитов (ну, из последовательных смитов вообще никакого пока нет). Наименьший МК из произвольных смитов имеет константу 1195 (построен давно tolstopuz'ом).

Составили бы сводную табличку по текущему состоянию дел в различных типах квадратов - например, подобную приведенной здесь: http://www.multimagie.com/English/Squar ... enProblems

[svb]

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

Использование иной обратной матрицы (от другого преобразования) ведет просто к перемешиванию строк/столбцов примитивного квадрата, но при этом он, естественно, остается примитивным.

Здесь я немного погорячился. Не всегда получается простое перемешивание строк/столбцов. На конкретных примерах это хорошо видно
$$T = \left| {\begin{array}{*{20}c} 1 & 1 \\ 2 & 3 \\ \end{array}} \right|{\rm }T^{ - 1} = \left| {\begin{array}{*{20}c} 3 & { - 1} \\ { - 2} & 1 \\ \end{array}} \right|$ $
$$T' = \left| {\begin{array}{*{20}c} 1 & 1 \\ 2 & {11} \\ \end{array}} \right|{\rm }T'^{ - 1} = \left| {\begin{array}{*{20}c} 2 & { - 4} \\ { - 1} & 4 \\ \end{array}} \right|{\rm mod 7 (!)}$ $
Тогда
$$T^{ - 1} T' = \left| {\begin{array}{*{20}c} 1 & { - 1} \\ 0 & 2 \\ \end{array}} \right|$ $ - при таком преобразовании p.s. не переходит в p.s.
С другой стороны, после перемешивания строк/столбцов примитивного квадрата, при которых он, действительно, остается примитивным, и преобразования его в пандиагональный квадрат с помощью разнообразных преобразований, удовлетворяющих требованиям теоремы 3.1, получается очень много квадратов, далеко не эквивалентных между собой в общепринятом понимании. Все это и позволило Россеру подсчитать, например, число всех пандиагональных квадратов 5-го порядка и сделать еще многое другое. Очень жаль, что до сих пор нет перевода его статьи на русский язык - уже почти 2 года на этом форуме она обсуждается, а воз и ныне там. Надеюсь "доканать" этот перевод и выложить его на своем сайте. Честно говоря, сталкиваясь с подобными вещами, становится обидно за нашу страну. Много слов о пользе английского языка, об "информировании" сообщества "ученых" только на "международном" языке общения ведет к тому, что у нас останутся одни прохановы. Чебышёв вел переписку с Эрмитом и для него не было проблем с иностранными языками, но "запад" почти ничего не знал о его работах - это я к позиции многих форумчан, которые искренне считают, что без разницы кому "служить". Это не так, как и многое другое, математика далеко не самодостаточна.

Предупреждение за оффтопик! С "обидами за страну" - в Свободный полёт.

[Nataly-Mak]

Цитата:

Составили бы сводную табличку по текущему состоянию дел в различных типах квадратов

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

Вчера нашла в своей статье ещё один алгоритм построения пандиагонального квадрата 4-го порядка; это алгоритм, найденный в книге Ю. В. Чебракова. Он основан на применении двух квадратов: латинского и классического.
Для применения этого алгоритма достаточно найти 4 арифметических прогрессии длины 4 (сейчас прогрессии надо искать из смитов, потому что квадрат собираемся из смитов строить) с одинаковой разностью и такие, что их первые члены a_1,a_2,a_3,a_4 связаны условием: a_1+a_4=a_2+a_3.
Арифметических прогрессий длины 4 из смитов очень много (например, с разностью 36). Но я вчера проверила все имеющиеся у меня прогрессии с разностью 36, нужных прогрессий не нашлось. Разность прогрессий может быть любой, но для всех 4 прогрессий одинаковой. Ещё, конечно, все 16 чисел набора должны быть различны. У меня нашлось несколько прогрессий, удовлетворяющих указанному условию, но в них есть повторяющиеся числа (то есть прогрессия длины 4 входит в прогрессию большей длины).

Вот пример реализации предложенного алгоритма для произвольных натуральных чисел. Берём такие 4 прогрессии с разностью $d = 10$:

3, 13, 23, 33
8, 18, 28, 38
1, 11, 21, 31
6, 16, 26, 36

(тоже примитивный квадрат!)

Здесь a_1+a_4=a_2+a_3=9.
Из данного набора чисел получаем такой пандиагональный квадрат:

3 31 28 16
26 18 1 33
11 23 36 8
38 6 13 21

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

Кстати, я спросила Павловского, есть ли в статье Россера алгоритм построения пандиагонального квадрата 4-го порядка. Он ответил, что пока не выяснил.

Приглашаю всех к решению поставленной задачи: построить наименьший пандиагональный квадрат 4-го порядка из произвольных смитов.

svb
да, о статье Россера здесь впервые сказали очень давно (в дискуссии по поводу несуществования классических пандиагональных квадратов порядка $n=4k+2$). Надо сказать огромное спасибо shwedk'е за то, что она нашла и выложила эту статью.

(Оффтоп)

Потом желающих подробно проработать статью не нашлось. Я статью, конечно, скачала, но разобраться в ней не смогла по незнанию языка. А недавно мне удалось привлечь к квадратам Павловского. Он и заинтересовался этой статьёй. Я по его просьбе статью выложила на Портале ЕН, так как здешняя давнишняя ссылка уже не работала. Павловский много уже сделал по этой статье. Тоже обещал перевод выложить. Вот уже два обещанных перевода у меня
Эх, сколько у меня ещё есть хороших статей (на английском) о магических и латинских квадратах! Всё благодаря shwedk'e. Но лежат они у меня мёртвым грузом. Ну, нет, конечно, из некоторых мне что-то удалось выудить (и даже немалое "что-то"). Но большинство статей не проработаны так, как их следовало бы проработать. А прорабатывать некому: нет интересующихся темой квадратов

[Pavlovsky]

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

ТЕОРЕМА 3.1. Результат преобразование p.s. порядка n с помощью
$\[ T = \left\| {\begin{array}{*{20}c} a & c \\ b & d \\ \end{array}} \right\| \] $
будет дьявольским квадратом, если $\[ abcd\left( {a^2 - b^2 } \right)\left( {c^2 - d^2 } \right) \] $ взаимно просто с n.

Эта теорема напрямую применима только для порядков не кратных 2,3. Одно из трех чисел $\[a,b,\left( {a^2 - b^2 } \right)\]$ четно. Одно из трех чисел $\[a,b,\left( {a^2 - b^2 } \right)\]$ делится на 3.
Как Россер преобразует примитивные квадраты в пандиагональные для порядков кратных 2,3 никак не могу понять. Что то про это есть в теоремах 5.4, 5.5. Вроде как перед выполнением преобразования надо переставить строки и колонки примитивного квадрата.

-- Чт май 20, 2010 08:32:08 --

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

Надеюсь "доканать" этот перевод и выложить его на своем сайте.

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

[Nataly-Mak]

Pavlovsky
а мой пример построения пандиагонального квадрата 4-го порядка из примитивного, только что приведённый, ничего не может прояснить? (это построено по другому алгоритму).

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