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

[Бодигрим]

У меня получился квадрат смитов с суммой 1362:

$$ \begin{matrix} 274 & 706 & 382 \\ 562 & 454 & 346 \\ 526 & 202 & 634 \end{matrix} $$

Искал лобовым перебором при помощи Mathematica и PARI/GP.

[Nataly-Mak]

Точно такой, как у меня!
Я решала задачу так. Сначала нашла в интервале (1, 1000) все простые числа, которые после удвоения превращаются в смитов. Для этого написала программку. Программка в секунду выдала такие простые числа. Вот они:
$11, 29,47,83,101,137,173,191,227,263,281,317,353,389,461,479,641,821,839,911,929,947,983$
Затем воспользовалась своей программой для построения нетрадиционных магических квадратов 3-го порядка из простых чисел (она у меня раньше была составлена). Эта программа выдала мне два квадрата:

47 191 173
263 137 11
101 83 227

137 353 191
281 227 173
263 101 317

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

-- Вс июл 05, 2009 11:49:44 --

Если же строить нетрадиционный магический квадрат 3-го порядка из составных смитов, которые могут повторяться, то квадрат с наименьшей магической константой будет такой:

58 22 94
94 58 22
22 94 58

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

 22 94 58 166
166 58 94 22
94 22 166 58
58 166 22 94

Предлагаю новую задачу: построить нетрадиционный магический квадрат 4-го порядка из различных составных смитов с минимальной магической константой.
Здесь, наверное, лобовой перебор не будет эффективным решением, надо придумать более оптимальный путь.
Я пока не решала эту задачу.

[Nataly-Mak]

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

22 382 706 778
526 922 346 94
634 58 562 634
706 526 274 382

Ну, с повторяющимися числами вообще построить квадрат очень легко, о чём я уже говорила. А вот из разных составных чисел-смитов пока не получается.
Может быть, кто-нибудь предложит изящный алгоритм построения такого магического квадрата? При этом не забывайте, что он должен иметь минимальную магическую константу из всех возможных для квадратов такого рода.

[tolstopuz]

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

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

22 346 562 265
778 274 85 58
4 454 382 355
391 121 166 517

[Nataly-Mak]

Отлично, только вы сделали опечатку: вместо 236 должно быть число 346. Число 236 не является смитом, кроме того, с этим числом квадрат не магический.
Я пока решала задачу аналогично квадрату Гарднера, то есть пыталась составить его из удвоенных простых чисел. Это у меня не получилось ещё. В плане у меня был такой алгоритм, при котором смиты получаются не только удвоением простых чисел, но не реализовала его пока.
А вы каким путём решили задачу? Этот квадрат имеет минимальную магическую константу?

[tolstopuz]

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

Отлично, только вы сделали опечатку: вместо 236 должно быть число 346.

Да, спасибо, исправил.

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

А вы каким путём решили задачу?

Перебором. Модифицировав свою программу для квадратов 4x4, которую вы ранее сочли неинтересной.

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

Этот квадрат имеет минимальную магическую константу?

Кажется, да, но надо еще раз проверить.

[Nataly-Mak]

Цитата:

Перебором. Модифицировав свою программу для квадратов 4x4, которую вы ранее сочли неинтересной.

Не поняла! О какой программе речь?
Тогда постройте, пожалуйста, по своей программе магический квадрат 4-го порядка, составленный из разных смитов, являющихся удвоенными простыми числами. Я сегодня весь день над этим билась, но так и не получила решение.
У меня тоже где-то была программа построения всех 880 магических квадратов 4-го порядка (традиционных). Надо раскопать её, может, пойдёт. А я сегодня пыталась решать не лобовым перебором, а чуть-чуть оптимизированным путём. И ни черта не решила!

[tolstopuz]

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

Цитата:

Перебором. Модифицировав свою программу для квадратов 4x4, которую вы ранее сочли неинтересной.

Не поняла! О какой программе речь?

post202750.html#p202750

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

Тогда постройте, пожалуйста, по своей программе магический квадрат 4-го порядка, составленный из разных смитов, являющихся удвоенными простыми числами.

58 778 634 526
1282 274 94 346
202 922 706 166
454 22 562 958

Предыдущий квадрат я проверил, константа действительно минимальна. У этого тоже.

[Nataly-Mak]

Цитата:

О задаче про магические квадраты 4х4 не совсем поняла. Это что же получаются нетрадиционные магические квадраты, если элементы от 0 до 9 в них повторяются. И чем же интересны такие квадраты?

Это я писала в ответ на ваше сообщение о той задаче (теперь вспомнила!). Однако вы несколько исказили мой ответ. Разве я написала, что эта задача мне не интересна? Я вас спросила, чем интересны такие квадраты, потому что действительно не поняла, в чём изюминка этих квадратов. И до сих пор не понимаю. Приведите один из таких магических квадратов. Что значит, элементы от 0 до 9 в них повторяются? То есть они составлены из чисел от 0 до 9, которые могут повторяться?
Квадрат, который получила я (с повторяющимися числами) имеет магическую константу 1888 (см. предыдущий пост). Квадрат из разных чисел, котрый построили вы, имеет магическую константу 1996. Значит, я была близка к цели. Я строила магические квадраты из простых чисел (которые превращаются в смиты после удвоения) по наперёд заданной магической константе. У меня была эта константа 944 (1888/2). Следующая была 980, для неё я вообще ничего не получила. Следующая была бы 998 (при этой константе я получила бы ваш квадрат). Завтра попробую свою программу для этой константы. Все возможные магические константы я сгенерировала заранее (для первых 23 простых чисел, превращающихся в смиты после удвоения).
Спасибо за решение задачи!

[tolstopuz]

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

Я вас спросила, чем интересны такие квадраты, потому что действительно не поняла, в чём изюминка этих квадратов.

Изюминка не в квадратах, а в алгоритме их перебора. Его можно использовать и в других задачах, как, скажем, в сегодняшней.

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

Приведите один из таких магических квадратов.

Все нули

[Nataly-Mak]

А нетривиальный можно?
Однако в сегодняшней задаче числа не повторяются. Какая же связь между этими программами?
Если квадрат 4-го порядка составляется из чисел от 0 до 9, то, наверное, лишне писать, что они могут повторяться. Они просто не могут не повторяться! Или я вообще ничего не поняла в этих квадратах.

[tolstopuz]

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

Какая же связь между этими программами?

Берется одна программа, множество чисел от 0 до 9 заменяется на множество смитов, добавляется проверка на повторяемость, и получается другая программа

[Nataly-Mak]

Множество чисел от 0 до 9 состоит из 10 чисел, множество смитов, из которых строится квадрат, состоит из 16 чисел. Не вижу связи!
Вот моя программа (построение по наперёд заданной константе) действительно использует множество простых чисел, состоящее из 23 чисел.

[tolstopuz]

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

Множество чисел от 0 до 9 состоит из 10 чисел, множество смитов, из которых строится квадрат, состоит из 16 чисел. Не вижу связи!
Вот моя программа (построение по наперёд заданной константе) действительно использует множество простых чисел, состоящее из 23 чисел.

Для первого квадрата я проверял 52 смита от 4 до 1165, для второго - 24 смита от 4 до 1966. Какая программе разница, сколько чисел проверять - 10, 24 или 52?

[Nataly-Mak]

Это смотря какая программа!
Назовём квадраты 4-го порядка, заполненные числами от 0 до 9, о которых вы пишете, нетрадиционными магическими квадратами типа "0-9" ( для краткости). Итак, у вас была программа для построения квадратов типа "0-9". Эта программа построила около семи миллионов квадратов. И абсолютно во всех этих квадратах числа повторяются. Я правильно понимаю? Например, такой латинский квадрат:

0 2 1 3
3 1 2 0
2 0 3 1
1 3 0 2

относится к магическим квадратам типа "0-9"?
Ваша программа строит квадраты из множества чисел, которое состоит всего из 10 чисел. Значит, она проверяет только 10 чисел. Или нет?
Если теперь заменить числа от 0 до 9 десятью любыми смитами, то по вашей программе получится несколько нетрадиционных магических квадратов из смитов, но не будет ни одного квадрата, составленного из разных смитов (потому что нельзя составить магический квадрат 4-го порядка из 10 разных чисел, так чтобы эти числа не повторялись; для этого нужно как минимум 16 разных чисел!).
Метод построения нетрадиционных магических квадратов из простых чисел с применением латинских квадратов описан мной в статье Нетрадиционные магические квадраты из простых чисел. Он работает для любого порядка, а не только для порядка 4. Если заменить в приведённом мной квадрате числа 0, 1, 2, 3 любыми смитами, то получится магический квадрат из смитов, но повторяющихся.
Теперь переходим к построению нетрадиционных магических квадратов 4-го порядка из разных составных смитов. Как же строить такие квадраты по той же программе, если та программа строит квадраты только из 10 чисел, и поэтому во всём квадрате числа разными быть никак не могут? Не могу понять этот момент!
А если вы проверяете в своей программе 24 (или 52) смита, то это будет уже совсем другая программа, не имеющая ничего общего с программой построения квадратов типа "0-9".
Извините, что так пространно написала, но пытаюсь понять, чего же я не так понимаю

-- Вт июл 07, 2009 08:51:09 --

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

29 317 389 263
191 353 281 173
461 137 227 173
317 191 101 389

С разными числами, например, такой квадрат:

29 317 389 263
101 353 461 83
641 47 137 173
227 281 11 479

Это ваш квадрат с точностью до М-преобразования (чтобы получить из моих квадратов квадраты из составных смитов, надо все элементы удвоить).
Моя программа выдаёт все квадраты, получающиеся друг из друга основными преобразованиями и М-преобразованиями. Но чтобы выполнить её полностью, надо довольно много времени. Для магической константы 980 я не выполнила программу до конца; до того момента, как я её прервала, она не выдала ни одного квадрата. Не буду выполнять её дальше. Поверю вам, что магическая константа 1996 минимальная для квадратов такого рода (из удвоенных простых чисел, являющихся смитами).