fixfix
2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 96, 97, 98, 99, 100, 101, 102 ... 192  След.
 
 Re: Магические квадраты
Сообщение19.05.2010, 03:28 
Аватара пользователя


20/01/10
766
Нижний Новгород
Еще попытка:
Код:
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

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


22/03/08

7154
Саратов
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 с одинаковой разностью.

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


20/01/10
766
Нижний Новгород
Еще не вечер :shock:

(Оффтоп)


Код:
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

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


22/03/08

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

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


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

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


22/03/08

7154
Саратов
Если честно, пока ничего не поняла :-)
Но это не столь важно.

Взяла ваш массив из квадрата с константой 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

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

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


21/02/10
1594
Екатеринбург
Для последовательных простых чисел пока тоже ничего. Проверил первые 23 миллиона простых чисел.

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


22/03/08

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

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


22/03/08

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

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

Код:
94  454  202  706
562  346  454  94
526  22  634  274
274  634  166  382

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

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение19.05.2010, 21:47 
Аватара пользователя


20/01/10
766
Нижний Новгород
Наконец-то выспался :-) - более суток не спал с этими квадратами.
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" в итоговом квадрате об этом подскажут.

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


11/01/06
5710
Nataly-Mak в сообщении #321449 писал(а):
maxal
а вы из смитов искали наборы, состоящие из 8 пар комплементарных чисел?

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

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

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение20.05.2010, 01:33 
Аватара пользователя


20/01/10
766
Нижний Новгород
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 года на этом форуме она обсуждается, а воз и ныне там. Надеюсь "доканать" этот перевод и выложить его на своем сайте. Честно говоря, сталкиваясь с подобными вещами, становится обидно за нашу страну. Много слов о пользе английского языка, об "информировании" сообщества "ученых" только на "международном" языке общения ведет к тому, что у нас останутся одни прохановы. Чебышёв вел переписку с Эрмитом и для него не было проблем с иностранными языками, но "запад" почти ничего не знал о его работах - это я к позиции многих форумчан, которые искренне считают, что без разницы кому "служить". Это не так, как и многое другое, математика далеко не самодостаточна.

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

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


22/03/08

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

Да, хорошая идея, сама об этом думала.
Но пандиагонального квадрата 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'е за то, что она нашла и выложила эту статью.

(Оффтоп)


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


21/02/10
1594
Екатеринбург
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 писал(а):
Надеюсь "доканать" этот перевод и выложить его на своем сайте.


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

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


22/03/08

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2876 ]  На страницу Пред.  1 ... 96, 97, 98, 99, 100, 101, 102 ... 192  След.

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



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

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


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

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