2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 81, 82, 83, 84, 85, 86, 87 ... 192  След.
 
 Re: Магические квадраты
Сообщение20.02.2010, 05:56 
Модератор
Аватара пользователя


11/01/06
5660
Nataly-Mak в сообщении #290537 писал(а):
Называя формулу Бергхольта более совершенной, я имела в виду то, что она даёт возможность строить также ассоциативные и пандиагональные квадраты (что я и сделала в своей статье). Ермаков в своей формуле построение таких квадратов не предусматривал.

Это неважно, предусматривал он или нет. Как я уже сказал, любой квадрат, полученный по одной формуле, можно получить и по другой. В частности, и по формуле Ермакова также можно получить ассоциативные и пандиагональные квадраты.

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


22/03/08

7154
Саратов
maxal в сообщении #290538 писал(а):
Это неважно, предусматривал он или нет. Как я уже сказал, любой квадрат, полученный по одной формуле, можно получить и по другой. В частности, и по формуле Ермакова также можно получить ассоциативные и пандиагональные квадраты.

Это как раз очень важно!
Конечно, если по той и по другой формуле построить из данного массива абсолютно все магические квадраты, то они окажутся одинаковыми.
Но если ставить конкретно задачу построения пандиагонального квадрата (как, например, сейчас я решаю такую задачу для пандиагональных квадратов из последовательных простых чисел), то нужна специальная формула именно для построения пандиагональных квадратов. Формула Ермакова таковой не является.

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

Обе программы представлены выше. Программу для пандиагональных квадратов собираюсь модифицировать, уменьшить количество свободных переменных с 6 до 4.

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


22/03/08

7154
Саратов
Программу модифицировать удалось. Теперь в схеме всего 4 свободных параметра, остальные 12 параметров вычисляются по этим 4 и магической константе квадрата. Программа работает очень быстро.
Теперь дело за массивами-кандидатами. Понятно, что такими кандидатами являются прежде всего обычные магические квадраты. Если из заданного массива даже обычный квадрат не строится, то понятно, что и пандиагональный не построится.

Если кого-то интересует схема построения пандиагонального квадрата 4-го порядка из массива, состоящего точно из 16 чисел, пишите, выложу.

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


20/01/10
766
Нижний Новгород
О пандиагональных квадратах 4 порядка
Код:
s+a+b+c+d  s-a-b+c-d  s+a-b-c+d  s-a+b-c-d
s-a-b-c+d  s+a+b-c-d  s-a+b+c+d  s+a-b+c-d
s-a+b+c-d  s+a-b+c+d  s-a-b-c-d  s+a+b-c+d
s+a-b-c-d  s-a+b-c+d  s+a+b+c-d  s-a-b+c+d

если s=17/2, (a,b,c,d)=любая перестановка из (1/2, 2/2, 2/4, 8/2) с любыми знаками то получаем 24*16=384 обычных пандиагональных квадратов, с точность до поворотов и симметрии 48

-- Сб фев 20, 2010 20:12:19 --

Аналогично, ассоциативные квадраты 4 порядка:
Код:
s+a+b+c+d  s-a-b-c+d  s+a-b-c-d  s-a+b+c-d
s-a-b+c-d  s+a+b-c-d  s-a+b-c+d  s+a-b+c+d
s-a+b-c-d  s+a-b+c-d  s-a-b+c+d  s+a+b-c+d
s+a-b-c+d  s-a+b+c+d  s+a+b+c-d  s-a-b-c-d

если s=17/2, (a,b,c,d)=любая перестановка из (1/2, 2/2, 2/4, 8/2) с любыми знаками то получаем 24*16=384 обычных ассоциативных квадрата, с точность до поворотов и симметрии 48

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


22/03/08

7154
Саратов
svb
результаты тестирования небогатые, потому что проверка одного массива из последовательных простых выбила меня из рабочего режима на 6 часов (в 4 часа запустила программу, в 10 она выкарабкалась).
Но всё по порядку. Я хотела дать вам для сравнения результаты работы программ mak5 и mag5x5, но сравнение получилось только в одном случае, во всех остальных у меня не хватило вдохновения проверить :(

Начала с массива из последовательных простых:

Код:
127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257

И начала с программы mak5. Программа работала 21349.61 сек. Найдено 4035 оригинальных квадратов.

Далее проверила только что построенный наименьший квадрат из последовательных смитов. Этот квадрат проверила по обеим программам. Найден 1 квадрат и там, и там. Прогрмма mak5 работала 368.79 сек., а программа mag5x5 - 225.6 сек. Налицо уменьшение времени. Однако сравнение с вашим результатом показывает, что мой компьютер по сравнению с вашим тихоход.

И ещё один тест дал интересный результат. Оказывается, квадратов из смитов тоже может быть очень много. Для теста взяла построенный мной квадрат из 5 арифметических прогрессий длины 5 с одинаковой разностью:

Код:
627 4619515 4653553 6633256 11989264
6633265 11989273 636 4619479 4653562
4619488 4653526 6633274 11989282 645
11989291 654 4619497 4653535 6633238
4653544 6633247 11989255 663 4619506

(см. статью "Нетрадиционные магические квадраты из чисел Смита".
Этот квадрат тоже проверила только по программе mak5. Программа работала 5340.49 сек. Найдено 12840 оригинальных квадратов! Невероятно. Видимо сыграло свою роль то, что числа образуют арифметические прогрессии.

Вот пока и всё у меня. А время уже почти обед :)

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


20/01/10
766
Нижний Новгород
Nataly-Mak в сообщении #290906 писал(а):
Однако сравнение с вашим результатом показывает, что мой компьютер по сравнению с вашим тихоход.

Досовские программы плохо проспособлены к XP. Я запускаю их в FAR - при полностью открытом окне они работают значительно медленнее, чем в случае окна виндовоза (alt+enter).

У меня маленький вопрос о пандиагональных квадратах 6 порядка. Их должно быть много, но не факт, что из чисел 1,..,36. Примеры имеются?

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


22/03/08

7154
Саратов
svb в сообщении #290922 писал(а):

У меня маленький вопрос о пандиагональных квадратах 6 порядка. Их должно быть много, но не факт, что из чисел 1,..,36. Примеры имеются?


Из чисел 1, ..., 36 пандиагональных квадратов 6-го порядка не существует. Это факт :)
Что касается нетрадиционных пандиагональных квадратов 6х6, примеров много. Например, тут пандиагональный квадрат из последовательных простых чисел:

Есть даже идеальный нетрадиционный квадрат 6-го порядка (то есть одновременно пандиагональный и ассоциативный).
См. мою статью "Нетрадиционные магические квадраты".

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


22/03/08

7154
Саратов
Вот какие результаты у меня по магическим квадратам 4-го порядка из последовательных простых чисел.

$S = 258$

Код:
37 83 97 41
53 61 71 73
89 67 59 43
79 47 31 101

Количество оригинальных квадратов 4. Это наименьший квадрат 4-го порядка из последовательных простых (см. A073520 и A073521).

$S = 276$

Код:
41 37 97 101
103 83 47 43
71 67 79 59
61 89 53 73

Количество оригинальных квадратов 8.

$S = 5118$

Код:
1229 1249 1321 1319
1301 1303 1231 1283
1297 1277 1307 1237
1291 1289 1259 1279

Количество оригинальных квадратов 12.

$S = 19896$

Код:
4943 4933 5011 5009
4999 4973 4967 4957
5003 4969 4987 4937
4951 5021 4931 4993

Количество оригинальных квадратов 4.

$S = 50478$

Код:
12553 12583 12689 12653
12641 12647 12601 12589
12671 12611 12619 12577
12613 12637 12569 12659

Количество оригинальных квадратов 4.

Эти квадраты я нашла по своей программе ( в том числе и все варианты квадратов).

А вчера svb по моей просьбе прислал мне специальную программу для поиска таких квадратов.
(Кстати, maxal, это очень эффективная программа для поиска наименьшего магического квадрата 4х4 из последовательных смитов. Работает гораздо быстрее моей программы.)

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

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

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


20/01/10
766
Нижний Новгород
До простого 1299791 больше квадратов нет.

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


22/03/08

7154
Саратов
Вот какой интересный результат получается. Есть 5 счастливых массивов из последовательных простых (да и те не все следуют подряд), которые складываются в магические квадраты 4-го порядка. А дальше разрыв непонятно какого размера. Так что и простые числа иногда не очень-то благополучно складываются в квадраты, хотя, конечно, лучше смитов.

То же самое я решила проверить для квадратов 5-го порядка из последовательных простых чисел.
Первые 7 массивов (подряд) оказались счастливыми, квадраты из них складываются. Но уже массив

Код:
167, 173, 179, ..., 293, 307

похоже, даёт осечку. Хотя пока ничего конкретного сказать не могу.
Три часа работала программа mag5x5, на экране 0 квадратов, при этом

Код:
I J K L   2, 9, 12, 23

Я не выдержала и прервала программу. Это ведь ещё неизвестно сколько времени ей осталось работать.

svb
если можно, помогите проверить этот массив :cry:
Скорее всего, квадрат из него не составится. Но почему так медленно работает программа? Ну, я понимаю, если бы квадраты составлялись, но ведь их нет! У меня такой тяжёлый случай впервые попался. Раньше было так: если квадраты не складываются, то программа очень быстро выполняется.

Следующие массивы пока не проверяла.

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


20/01/10
766
Нижний Новгород
Nataly-Mak в сообщении #291240 писал(а):
если можно, помогите проверить этот массив :cry:
Скорее всего, квадрат из него не составится. Но почему так медленно работает программа? Ну, я понимаю, если бы квадраты составлялись, но ведь их нет! У меня такой тяжёлый случай впервые попался. Раньше было так: если квадраты не складываются, то программа очень быстро выполняется.

Запустил.

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


22/03/08

7154
Саратов
Спасибо!
Ждём...

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


20/01/10
766
Нижний Новгород
Time : 2796.15 s
квадратов нет

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


11/01/06
5660
Nataly-Mak в сообщении #285845 писал(а):
В моей программе реализована общая формула для квадрата 4-го порядка (приведённая в моей статье "Общие формулы магических квадратов", см. конец статьи).

Эта формула составлена в предположении, что квадрат строится из массива, состоящего точно из 16 чисел. Формула в таком случае зависит всего от 7 параметров и проверка выполняется очень быстро.

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

Занумеруем элементы квадрата $4\times 4$ так:
$$
\begin{bmatrix} 
x_1 & x_5 & x_{10} & x_2\\ 
x_{13} & x_8 & x_6 & x_{14} \\
x_{15} & x_{11} & x_7 & x_{16} \\
x_9 & x_3 & x_4 & x_{12}
\end{bmatrix}
$$
Элементы $x_1$, $x_2$, $x_3$, $x_5$, $x_6$, $x_8$, $x_{10}$, $x_{13}$ назовем независимыми, а остальные элементы - зависимыми, и укажем явные зависимости:
$$\begin{cases}
x_4 = x_1 + x_2 - x_3\\
x_7 = x_3 + x_5 - x_6\\
x_9 = -x_2 + x_3 + x_5 - x_6 + x_8\\
x_{11} = x_1 + x_2 - x_3 - x_8 + x_{10}\\
x_{12} = x_2 - x_3 + x_6 - x_8 + x_{10}\\
x_{14} = x_1 + x_2 + x_5 - x_6 - x_8 + x_{10} - x_{13}\\
x_{15} = 2x_2 - x_3 + x_6 - x_8 + x_{10} - x_{13}\\
x_{16} = -2x_2 + x_3 + 2x_8 - x_{10} + x_{13}
\end{cases}
$$
Важным свойством этих зависимостей является то, что каждый элемент зависит лишь от элементов с меньшими номерами и сам при этом имеет минимально возможный номер.

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

На любом шаге алгоритма свободными числами назовем ранее неиспользованные числа. Изначально все данные числа свободны.

Начинаем определение элементов $x_i$ в их естественном порядке (т.е. для $i=1,2,\dots,16$):
* если $x_i$ независимый элемент, перебираем все свободные числа в качестве его значения (текущее выбранное значение перестает быть свободным), и переходим к следующему элементу;
* если $x_i$ зависимый элемент, вычисляем его значение по вышеуказанным формулам и проверяем является ли это значение свободным. Если да, то число становится несвободным, а мы переходим к следующему элементу; если нет - то возвращаемся к предыдущему элементу.

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

Важно отметить, что для отбрасывания заведомо прохих вариантов, здесь не всегда нужно знать значения всех независимых элементов. Например, элемент $x_4$ зависит лишь от $x_1$, $x_2$ и $x_3$ и проверить его значение можно, зная лишь значения этих трех элементов (совершенно неважно, чему равны остальные). Именно поэтому этот элемент имеет номер $4$ и проверяется сразу после того, как становятся известны значения $x_1$, $x_2$ и $x_3$. Именно эта идея делает алгоритм эффективным. Причем в своём классе этот алгоритм является самым эффективным (то есть, большего ускорения выжать из этой идеи не получится).

Теперь можно приступать к дальнейшему поиску квадрата $4\times 4$ из смитов.

P. S. Дальнейшая оптимизация возможна с учётом того, что если массив содержит элемент 0, то можно считать, что либо $x_1$, либо $x_3$ равен нулю.

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


04/03/09
906
Вот несколько квадратиков. В теге offtop, чтобы много места не занимали.

(Оффтоп)

Код:
101  31  47  79 
43  59  67  89 
73  71  61  53 
41  97  83  37 

1229  1321  1249  1319 
1303  1301  1283  1231 
1307  1237  1297  1277 
1279  1259  1289  1291 

4993  4931  5021  4951 
4937  4987  4969  5003 
4957  4967  4973  4999 
5009  5011  4933  4943 

12553  12689  12583  12653 
12671  12619  12611  12577 
12641  12601  12647  12589 
12613  12569  12637  12659 

3259909  3260021  3259999  3260051 
3260003  3260029  3259931  3260017 
3260027  3259957  3260063  3259933 
3260041  3259973  3259987  3259979 

3324457  3324521  3324329  3324371 
3324353  3324389  3324437  3324499 
3324359  3324361  3324491  3324467 
3324509  3324407  3324421  3324341 

9291749  9291649  9291521  9291613 
9291691  9291523  9291647  9291671 
9291539  9291719  9291643  9291631 
9291553  9291641  9291721  9291617 

24066733  24066683  24066643  24066719 
24066701  24066649  24066689  24066739 
24066677  24066703  24066737  24066661 
24066667  24066743  24066709  24066659 

26025257  26025253  26025107  26025217 
26025127  26025199  26025227  26025281 
26025239  26025179  26025229  26025187 
26025211  26025203  26025271  26025149 

46330187  46330133  46330021  46330177 
46330201  46330057  46330169  46330091 
46330069  46330111  46330181  46330157 
46330061  46330217  46330147  46330093 

95979629  95979511  95979613  95979551 
95979523  95979557  95979581  95979643 
95979599  95979619  95979547  95979539 
95979553  95979617  95979563  95979571 

99268847  99268783  99268649  99268879 
99268861  99268781  99268837  99268679 
99268699  99268691  99268849  99268919 
99268751  99268903  99268823  99268681

116923199  116923193  116923057  116923129 
116923123  116923087  116923181  116923187 
116923097  116923109  116923201  116923171 
116923159  116923189  116923139  116923091 

170995151  170995267  170995361  170995399 
170995387  170995381  170995199  170995211 
170995289  170995229  170995369  170995291 
170995351  170995301  170995249  170995277 

204041471  204041623  204041417  204041689 
204041641  204041587  204041549  204041423 
204041609  204041483  204041581  204041527 
204041479  204041507  204041653  204041561 

213085007  213085003  213084871  213084899 
213084983  213084877  213085039  213084881 
213084889  213084941  213084923  213085027 
213084901  213084959  213084947  213084973 

218568971  218569157  218569079  218569147 
218569111  218569163  218569031  218569049 
218569133  218569037  218569123  218569061 
218569139  218568997  218569121  218569097 

229981441  229981613  229981399  229981601 
229981517  229981573  229981547  229981417 
229981637  229981447  229981487  229981483 
229981459  229981421  229981621  229981553 

232850557  232850621  232850741  232850743 
232850729  232850701  232850623  232850609 
232850707  232850627  232850711  232850617 
232850669  232850713  232850587  232850693 

254042641  254042681  254042837  254042881 
254042821  254042801  254042771  254042647 
254042879  254042689  254042779  254042693 
254042699  254042869  254042653  254042819 

255432869  255432953  255433033  255433051 
255433021  255433069  255432887  255432929 
255433049  255433001  255432949  255432907 
255432967  255432883  255433037  255433019 

256714391  256714349  256714219  256714327 
256714223  256714303  256714373  256714387 
256714363  256714277  256714333  256714313 
256714309  256714357  256714361  256714259 


 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2871 ]  На страницу Пред.  1 ... 81, 82, 83, 84, 85, 86, 87 ... 192  След.

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



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

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


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

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