2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 69, 70, 71, 72, 73, 74, 75 ... 192  След.
 
 Re: Магические квадраты
Сообщение03.11.2009, 11:48 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Друг прислал книгу У. Болл, Г. Коксетер. Математические эссе и развлечения. – М.: Мир, 1986. Он выложил книгу на файлообменнике Народа; может быть, кто-то захочет скачать, вот ссылка для скачивания:

http://narod.ru/disk/14684506000/Boll%2 ... %2C%201986)(ru)(600dpi)(471s).djvu.html

Просмотрела немного книгу, конечно, больше всего остановилась на главе «Магические квадраты». В книге приводится общая формула для магического квадрата 4-го порядка. Цитата:

Цитата:
На рис. 7.18 показана общая схема Бергхольта для построения любых магических квадратов четвёртого порядка [14] (совершенных при a=b=d-c=1/2(A-B-C+d), симметрических при a+c=d=b-c и A+C=B+D).

Общая схема, изображённая на рис. 7.18 выглядит так:

Код:
A-a  C+a+c  B+b-c  D-b
D+a-d     B   C   A-a+d
C-b+d    A   D   B+b-d
B+b   D-a-c   A-b+c   C+a

Пример (из книги), известный наименьший магический квадрат 4-го порядка из простых чисел и числа 1

Код:
3 71 5 23
53 11 37 1
17 13 41 31
29 7 19 47

получается при таких значениях: A=13, B=11, C=37, D=41, a=10, b=18, c=24, d=-2.
Но я так и не поняла, как же пользоваться этой формулой. Она похожа на формулу, приведённую в книге Ю. В. Чебракова (я приводила эту формулу). Если только лобовым перебором? Например, мы хотим построить магический квадрат из смитов по данной схеме. Тогда нам придётся по этой формуле перебирать все A, B, C, D – смиты, и все a, b, c, d – произвольные целые числа, затем вычислять каждый элемент по формулам и проверять, принадлежат ли полученные значения множеству смитов, а потом проверять суммы чисел в строках, столбцах и диагоналях квадрата.

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение03.11.2009, 17:37 
Заслуженный участник


04/03/09
906
Есть 2 новости, обе хорошие.
1) Найден квадрат из смитов 5-го порядка с минимальной константой 1636.
Код:
355  576  4  319  382 
454  85  391  648  58 
27  535  346  526  202 
706  166  378  121  265 
94  274  517  22  729 

2) Есть программа, которая находит все магические квадраты 5-го порядка из смитов с заданной магической константой. Чтоб она работала, надо в папку с программой положить файлик smith.txt с массивом смитов. В файле magic.txt будет список магических квадратов.
Программа

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


14/08/09
1140
12d3 в сообщении #257980 писал(а):
Есть 2 новости, обе хорошие.
1) Найден квадрат из смитов 5-го порядка с минимальной константой 1636.
Код:
355  576  4  319  382 
454  85  391  648  58 
27  535  346  526  202 
706  166  378  121  265 
94  274  517  22  729 

2) Есть программа, которая находит все магические квадраты 5-го порядка из смитов с заданной магической константой. Чтоб она работала, надо в папку с программой положить файлик smith.txt с массивом смитов. В файле magic.txt будет список магических квадратов.
Программа

То есть, получается, квадрат Бодигрима не минимален?

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


11/01/06
5660
Mathusic в сообщении #256330 писал(а):
Хотелось бы узнать какие диапозоны уже проверены на минимальные квадраты порядка $3,4,5,6$ из последовательных смитов?

Закончил поиск квадрата $3\times 3$ в интервале до $3\cdot 10^{10}$. Безуспешно.

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


14/08/09
1140
maxal в сообщении #258106 писал(а):
Mathusic в сообщении #256330 писал(а):
Хотелось бы узнать какие диапозоны уже проверены на минимальные квадраты порядка $3,4,5,6$ из последовательных смитов?

Закончил поиск квадрата $3\times 3$ в интервале до $3\cdot 10^{10}$. Безуспешно.

Спасибо за информацию!
Ps. Трудный квадрат, однако... Может быть он найдётся в следующем миллиарде, а может не найдётся и в квадратильоне, или не существует вообще...

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


22/03/08

7154
Саратов
12d3 в сообщении #257980 писал(а):
Есть 2 новости, обе хорошие.
1) Найден квадрат из смитов 5-го порядка с минимальной константой 1636.

Отличный результат! А наименьший магический квадрат 5-го порядка из последовательных смитов можно найти по вашей программе?
Можете рассказать, какой алгоритм в вашей программе? Этот алгоритм можно применить для построения наименьшего магического квадрата порядка 6 из смитов?

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


22/03/08

7154
Саратов
12d3
Хотела проверить по вашей программе первые 9 кандидатов в наименьшие магические квадраты 5-го порядка из последовательных смитов, но программа у меня почему-то не скачалась.
Вот эти кандидаты:

Код:
454, …, 861  S = 3269
535, …, 922  S = 3602
861, …, 1776  S = 6522
915, …, 1842  S = 7080
1086, …, 1894  S = 7825
1219, …, 1921  S = 8299
1376, …, 1966  S = 8854
1507, …, 2067  S = 9110
1872, … , 2409  S = 10544

Самый первый кандидат с магической константой 1516 отпадает автоматически, если минимальная константа квадрата 5-го порядка из смитов равна 1636.
Как я уже сообщала, моя программа не построила магический квадрат ни из одного приведённого массива. Однако моя программа не даёт точного ответа, возможна ошибка хотя и с малой вероятностью. А что “говорит” об этих квадратах ваша программа?

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение04.11.2009, 16:03 
Заслуженный участник


04/03/09
906
Nataly-Mak в сообщении #258127 писал(а):
А наименьший магический квадрат 5-го порядка из последовательных смитов можно найти по вашей программе?

Можно, только пока не находится. Проверял числа до миллиона. Если не скачалась, то вот на народе.
Nataly-Mak в сообщении #258127 писал(а):
Можете рассказать, какой алгоритм в вашей программе?

Идея такая: сначала генерируем все строки, дающие в сумме магическую константу.(я их про себя называю цепочки) Потом для каждой пары цепочек вычисляю количество общих чисел. В полумагическом квадрате каждая пара строка-столбец имеет ровно одно общее число, а каждая пара строка-строка или столбец-столбец - 0. Исходя из этого, составляю все возможные полумагические квадраты.(причем квадраты, получающиеся друг из друга перестановкой строк или/и столбцов, считаются за один) Потом в получившемся квадрате ищу кандидаты на диагональные цепочки. Такие кандидаты должны иметь ровно 1 общее число с каждой строкой и столбцом. Дальше еще парочка условий, чтобы эти две цепочки перестановками в полумагическом квадрате могли одновременно встать на диагонали, и все, магический квадрат получен.
Nataly-M[quote="Nataly-Mak в сообщении #258127 писал(а):
Этот алгоритм можно применить для построения наименьшего магического квадрата порядка 6 из смитов?

Можно, только шибко долго работает. Пока что вообще ни одного квадрата не выдало. Авось, вам повезет больше. Вот программа. Кстати, вы можете давать во входном массиве не обязательно 36 чисел, а сколько угодно.

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


22/03/08

7154
Саратов
12d3 в сообщении #258247 писал(а):
Nataly-M[quote="Nataly-Mak в сообщении #258127 писал(а):
Этот алгоритм можно применить для построения наименьшего магического квадрата порядка 6 из смитов?

Можно, только шибко долго работает. Пока что вообще ни одного квадрата не выдало. Авось, вам повезет больше.

Насколько я поняла из описания вашего алгоритма, в нём отсутствует элемент "везения" :)
Вот в моём первоначальном алгоритме (с генерацией набора из $n$ строк случайным образом) такой элемент действительно присутствует. Может повезти, а может - и нет. И мне много раз повезло - магический квадрат был найден. Самое большое везение было, когда мне удалось построить магический квадрат 10-го порядка из последовательных смитов. Правда, потом выяснилось, что он не наименьший. Совместными с ice00 усилиями удалось получить подобный магический квадрат и из первого кандидата.
Спасибо, что выложили программы. Но теперь, после вашего сообщения, мне уже они вряд ли понадобятся. У меня маленький массив смитов, а вы уже проверили квадрат 5-го порядка из последовательных смитов до миллиона. Да, похоже, что с квадратами из последовательных смитов порядков 3 - 9 придётся помучиться :)
Другие участники могут попробовать по вашим программам искать квадраты порядков 5 и 6 из смитов.

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение05.11.2009, 10:45 


17/10/09
26
Nataly, выложите пожалуйста, все 833 строки, полученные вами для шестого квадрата и все наборы по четыре строки. Интересно взглянуть. Может быть нужно искать не все строки, а достаточно только строк с неповторяющимися элементами?

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


22/03/08

7154
Саратов
Напоминаю, что для тестирования своего алгоритма я взяла массив смитов, из которого магический квадрат 6-го порядка уже построен:

Код:
22 94 346 382 562 778 1822 1966 2326 2362 2578 2902 20362 20506 20542 20974 21226 21262 681817 682177 682393 682609 682681 682897 1446106 1446142 1446178 1446538 1446574 1446934 3003898 3004186 3004402 3004618 3004654 3004762

Ваше предложение брать не все оригинальные строки, а только строки с неповторяющимися числами, неверно. Надо брать именно все оригинальные строки, иначе мы не получим всех возможных наборов по 4 строки.
В этом файле лежат 833 оригинальных строк, полученных по моей программе. Сумма чисел в строках равна магической константе квадрата – $5156763$. Числа в строках следуют в порядке возрастания. Вот начало этого файла:

Код:
22  1822  20542  682681  1446934  3004762
22  1822  20974  682393  1446934  3004618
22  1822  20974  682609  1446574  3004762
22  1822  20974  682609  1446934  3004402
22  1822  21226  682393  1446538  3004762
22  1822  21226  682897  1446142  3004654
22  1822  21226  682897  1446178  3004618
22  1822  21262  682681  1446574  3004402
22  1822  21262  682897  1446106  3004654
22  1822  21262  682897  1446142  3004618
22  1822  21262  682897  1446574  3004186
22  1966  20506  682681  1446934  3004654
22  1966  20542  682681  1446934  3004618

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

Код:
22  1822  20542  682681  1446934  3004762
94  1966  20974  682897  1446178  3004654
346  2326  20506  682393  1446574  3004618
382  2362  21262  681817  1446538  3004402

22  1822  20974  682393  1446934  3004618
94  1966  20506  682897  1446538  3004762
346  2362  20542  682681  1446178  3004654
382  2326  21262  681817  1446574  3004402

22  1822  20974  682609  1446574  3004762
94  1966  21226  682681  1446142  3004654
346  2326  20362  682177  1446934  3004618
382  2362  20542  682897  1446178  3004402

Будет очень интересно, если кто-нибудь получит из этих 833 строк все возможные оригинальные наборы из 4 строк и сообщит, сколько же их на самом деле. Далее по формуле $n*24*720^4$ можно посчитать, сколько будет всех вариантов наборов по 4 строки (здесь $n$ – количество оригинальных наборов).
Среди всех вариантов наборов обязательно должен быть такой набор:

Код:
1822 21226 682897 1446538 3003898 382
3004762 681817 778 2326 1446574 20506
1446142 2902 3004654 20542 346 682177
21262 1446178 1966 562 682393 3004402

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

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение05.11.2009, 14:39 
Заслуженный участник


04/03/09
906
Есть магический квадрат 6-го порядка с константой 2787.
Код:
22  4  895  526  1255  85 
355  728  27  1165  391  121 
382  778  454  517  94  562 
576  634  654  319  166  438 
690  378  274  58  535  852 
762  265  483  202  346  729 

Получен с помощью исправленной версии программы из массива
Код:
562, 690, 483, 27, 391, 634, 852, 378, 438, 382, 202, 535, 121, 517, 274, 166, 1255, 454, 22, 94, 85, 1165, 526, 895, 576, 346, 778, 728, 355, 4, 654, 762, 729, 319, 58, 265

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


22/03/08

7154
Саратов
Есть совершенный магический квадрат 4-го порядка из простых чисел! Известен ли такой квадрат? Если кто встречал, дайте, пожалуйста, ссылку.
***
Разобралась в общей алгебраической формуле Бергхольта магического квадрата 4-го порядка (приведена выше). Интересно использование этой формулы для построения пандиагонального (для квадрата 4-го порядка это значит также – совершенного) квадрата. Для пандиагонального квадрата общая формула имеет такой вид (получается из формулы, приведённой в книге с использованием указанных условий):

Код:
A-a C+a+c B+a-c D-a
D-c   B   C   A+c
C+c  A   D   B-c
B+a   D-a-c  A-a+c  C+a

при этом должно выполняться ещё условие: 2a = A – B – C + D. Здесь $A$, $B$, $C$, $D$ – натуральные числа, $a$ и $c$ – целые числа не равные нулю.
Составила программу для этой схемы. Для простых чисел получила совершенный квадрат мгновенно:

Код:
11 157 41 199
167 73 137 31
163 5 193 47
67 173 37 131

Если учесть внутреннюю логику этой схемы и составленной по этой схеме программы, вроде бы это наименьший пандиагональный квадрат 4-го порядка из простых чисел (магическая константа квадрата, построенного по данной схеме равна: $A+B+C+D$). Магическая константа этого квадрата равна 408.
А вот совершенный квадрат из смитов не получился! Надо расширять массив смитов, я использовала в своей программе массив из 50 чисел.

В этой ветке показан пандиагональный квадрат 6-го порядка из простых чисел. Известны ли пандиагональные квадраты других порядков из простых чисел? Предлагаю создать новую серию магических квадратов – пандиагональные квадраты из простых чисел (а также из смитов). Из простых чисел у нас уже есть пандиагональные квадраты порядков 4 и 6. Из смитов пока вроде бы неизвестно ни одного пандиагонального квадрата.

-- Чт ноя 05, 2009 15:48:24 --

12d3 в сообщении #258561 писал(а):
Есть магический квадрат 6-го порядка с константой 2787.
Код:
22  4  895  526  1255  85 
355  728  27  1165  391  121 
382  778  454  517  94  562 
576  634  654  319  166  438 
690  378  274  58  535  852 
762  265  483  202  346  729 

Получен с помощью исправленной версии программы из массива
Код:
562, 690, 483, 27, 391, 634, 852, 378, 438, 382, 202, 535, 121, 517, 274, 166, 1255, 454, 22, 94, 85, 1165, 526, 895, 576, 346, 778, 728, 355, 4, 654, 762, 729, 319, 58, 265

Ура!!!
Значит, я не зря ожидала, что магический квадрат с такой константой будет. И массив вроде тот же самый, который я приводила.
Но это ведь ещё не наименьший квадрат?

-- Чт ноя 05, 2009 16:16:21 --

12d3
Вот нашла в черновиках ещё один полумагический квадрат с константой $2787$. Он построен из другого массива. Проверьте, пожалуйста, если это нетрудно, получится ли из этого массива магический квадрат.
Вообще я получила море полумагических квадратов с константой $2787$ из разных массивов, но все эти квадраты уже, конечно, давно удалила. Хорошо, что вот в записях остались два квадратика.
Вот полумагический квадрат:

Код:
588 378 985 27 454 355
265 895 121 706 274 526
22 636 166 825 576 562
535 346 922 517 85 382
648 438 202 58 483 958
729 94 391 654 915 4

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


14/08/09
1140
Как сообщил нам товарищ maxal, он проверил $30 \cdot 10^9$ натуральных чисел на квадрат $3 \times 3$ из смитов. Я проверил затем следующие $\ge 682 \cdot 1000000$. Результата нет.
$\operatorname{maxal}$, а Вы начали проверку дальше?

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


22/03/08

7154
Саратов
12d3
Программа супер! Проверила сейчас, работает, выдаёт много магических квадратов (пишет: найден магический квадрат), прервала программу, так как не знаю, сколько времени она будет выполняться. В выходном файле имею море магических квдаратов. Вот самый первый:

Код:
4  958  706  22  895  202 
576  58  588  355  562  648 
483  166  729  636  382  391 
274  526  378  825  346  438 
535  94  265  922  517  454 
915  985  121  27  85  654

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

-- Чт ноя 05, 2009 17:21:14 --

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

Код:
861  958  346  915  355  438 
654  378  690  636  663  852 
778  634  645  728  706  382 
535  729  913  576  666  454 
562  648  762  391  588  922 
483  526  517  627  895  825

Магическая константа равна $3873$.

-- Чт ноя 05, 2009 17:37:30 --

И ещё один из произвольных смитов, с магической константой $2472$:

Код:
729  4  636  762  22  319 
27  663  654  526  85  517 
391  645  58  378  438  562 
382  346  454  121  634  535 
355  648  94  483  627  265 
588  166  576  202  666  274

Сейчас ещё попытаюсь уменьшить.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2871 ]  На страницу Пред.  1 ... 69, 70, 71, 72, 73, 74, 75 ... 192  След.

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



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

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


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

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