2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 124, 125, 126, 127, 128, 129, 130 ... 192  След.
 
 Re: Магические квадраты
Сообщение03.09.2010, 14:04 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Я ищу сразу наборы (квадраты 2х2) из разных чисел. Первый набор найду, сразу выбрасываю из исходного массива эти 4 числа и ищу второй набор, затем снова выбрасываю из массива найденные 4 числа и так далее. В результате программа выдаёт мне только по 9 различных квадратов.
Теперь надо для каждого набора из 9 различных квадратов дописать блок проверки условий для отклонений. Вроде всё просматривается чётко.

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


20/01/10
766
Нижний Новгород
Nataly-Mak в сообщении #349367 писал(а):
В результате программа выдаёт мне только по 9 различных квадратов.
Именно таких 9-ок и много, вот, например, 10000-ая 9-ка:
Код:
  5  11  17   7  13  29
19  23  31 101  61  47
41  43  53  71  79  59
37  67 137 283 241 149
103  97  73 109 151 181
89  83 107 131 127 113

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


22/03/08

7154
Саратов
Так и радуйтесь, что их много, есть из чего выбирать :-)

Программу дописала, тест она проходит, но только если задаю конкретные значения для получения первых трёх квадратов 2х2. Остальные 6 квадратов она находит быстро. Но если убираю конкретные значения для третьего квадрата, всё! Программа задумывается надолго.
Для тестирования взяла недавно построенный пандиагональный квадрат с магической константой 510.

Таким образом, первая реализация есть (через квадраты 2х2), но результатов пока нет.

Нужно придумывать оптимизации. Пока ничего хорошего не приходит в голову :-(

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

P.S. Мне кажется, через квадраты 2х2 плохая реализация: очень много циклов.
Надо что-то другое попробовать.

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


20/01/10
766
Нижний Новгород
Nataly-Mak в сообщении #349378 писал(а):
Надо что-то другое попробовать.
Есть одна идейка. Квадратов 2х2 не так уж и много. Для $S=498$ всего 931, если выкинуть 3 из состава простых чисел. Для каждого квадрата всего 3 возможных положительных $p$. Можно для каждого $p$ создать списки квадратов, которые допускают этот параметр "псевдокомплементарности". Эта предварительная работа не должна занять много времени.
Далее приступаем к следующему перебору.

1. Выбираем произвольные 4-ки параметров $p$ для $p2, p4, p6, p8$
2. Для каждой 4-ки вычисляем оставшиеся $p1, p3, p5, p7, p9$
3. Находим соответствующие квадраты с этими параметрами в списках квадратов с проверкой на совпадение входящих чисел.
4. В случае удачи восстанавливаем пандиагональный квадрат (к сожалению, не всегда).

Шаг 1 можно будет брать и в урезанном виде - обнадеживает то, даже для очень частных случаев выбора $p2, p4, p6, p8$:
$(0,0,0,0)$
$(p,0,0,-p)$
которые рассматривались ранее, был некоторый успех.

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


22/03/08

7154
Саратов
Сначала брала массив из 50 первых простых чисел. Потом решила сократить массив до минимума, сгенерировала случайным образом массив из 36 чисел, дающий магическую константу 498:

Код:
29 211 67 113 191 73 23 139 181 43 41 151 149 101 53 59 97 3 19 11 5 17 137 71 131 107 37 31 13 61 79 103 199 109 127 7

Проверила, обычный МК из чисел этого массива строится.

Не стала массив ранжировать. Запустила программу поиска квадратов 2х2, программа нашла 7 правильных квадратов с ходу, вот с такими отклонениями p_i: 74, 14, 48, 58, 2, -64, -50. Условия для этих отклонений выполняются (я их сразу проверяю). Но дальше никак не хочет найти ещё два квадратика.
Интересный момент: когда числа идут вразброд, отклонения лучше получаются - и положительные, и отрицательные. И результат, наверное, получить быстрее удастся.

Да, надо заметить, что пока всего два условия из 6 проверены. Добавив ещё два отклонения, надо будет проверить ещё 4 условия, и там много чего не получится. Вот и нету последних двух квадратов :-(

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


22/03/08

7154
Саратов
Разложила два шаблона пандиагональных квадратов на квадратики 2х2, получились такие шаблоны:

Код:
1 5   1 1   5 5   1 1   5 1   5 5   1 5   1 1   5 5
1 1   5 1   5 5   1 5   1 1   5 5   1 1   5 1   5 5

Второй шаблон подобный, только в нём три квадрата состоят из одних единиц, а в остальных по три пятёрки и одной единице.
Простое число 3 в этих квадратах не содержится. Количество единиц и пятёрок одинаково.
Может быть, шаблоны чем-то помогут.

Я уже начала переписывать программу с учётом шаблонов квадратов 2х2. В этом случае весь массив можно разделить на две равные части, например: 25 чисел с вычетом 1 и 25 чисел с вычетом 5 (можно увеличить количество чисел в массиве, но чем больше чисел, тем дольше программа будет выполняться; для магических констант 486 и 498 вполне достаточен массив из 50 чисел).
Тогда переменные циклов пробегают ровно в два раза меньше значений, что, естественно, убыстряет выполнение программы.

Товарищи программисты! Где же вы? Тему просматривают многие. Задача очень интересная! Тот случай, когда от очень изящного алгоритма до его реализации, как от неба до земли. Написать абы какую программу - это запросто (я уже написала такую). Но! Надо сделать такую программу, которая не за сутки выполнится и не за 12 часов. Вот в чём суперзадача.
Например, программа по предыдущему алгоритму svb находит пандиагональные квадраты за 10-20 секунд (сама в этом убедилась). Это высший пилотаж!

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


22/03/08

7154
Саратов
Детализация предложенного svb алгоритма на самых простых примерах.

Пример 1.

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

Код:
157  151  139  163  73  97  31  43  13  103  109  19  79  37  7  181  193  67  11  71  23  89  149  113  59  5  137  41  47  53  17  83  167  101  29  131

Массив разделила на две группы: первые 18 чисел - с вычетом 1, следующие 18 чисел - с вычетом 5.
Теперь программа долго не думала :-) Она отработала полностью за 1 секунду и ничего не нашла. Это может означать только одно: из чисел данного массива нельзя составить 9 квадратов 2х2, составленных по запрограммированному шаблону и удовлетворяющих нужным условиям.
Однако ещё ничего нельзя сказать о возможности или невозможности составления из чисел данного массива пандиагонального квадрата 6-го порядка с магической константой 498. Потому что есть другие шаблоны для квадратов 2х2, сколько их всего я пока не выяснила, но два вида точно имеется.

Но уже хоть что-то, по крайней мере, программа массив обсчитала мгновенно, это уже хорошо.

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


20/01/10
766
Нижний Новгород
Забыл сказать. Та же программа, которая выдавала очень много 9-ок квадратов 2х2 для $S=498$ не выдала ни одной 9-ки для $S=488$, но полную проверку провести не удалось - долго :-(

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


22/03/08

7154
Саратов
svb в сообщении #349557 писал(а):
Забыл сказать. Та же программа, которая выдавала очень много 9-ок квадратов 2х2 для $S=498$ не выдала ни одной 9-ки для $S=488$...

Вы хотели сказать для S = 486?

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


20/01/10
766
Нижний Новгород
Nataly-Mak в сообщении #349564 писал(а):
Вы хотели сказать для S = 486?
Хотел :-) , но сейчас решил заново проверить. Где-то через час 9-ки посыпались и вот 10000-ый набор:
Код:
  5  11  17   7  13  29
23  31  37  79  47  73
41  43  59  71  53  61
19 107 127 293 193 151
83  89 101 139 157 113
103  97  67 109 131 137

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


22/03/08

7154
Саратов
А как насчёт 4 квадратов 3х3 с суммой чисел в них равной 3S/2?
Вот, например, такой квадратик из того же самого пандиагонального квадрата из последовательных простых чисел:

Код:
67 71 109
241 191 163
199 227 127

Я сейчас расписала эту решётку, в ней всё совершенно аналогично. И с отклонениями всё так же: всем отклонениям в одной паре групп соответствуют отклонения с обратным знаком в другой паре групп.

Интересно, что проще искать: наборы по 9 квадратов 2х2 или наборы по 4 квадрата 3х3?
Вообще обо всех этих необходимых условиях построения пандиагонального квадрата 6-го порядка писал в одном из сообщений Pavlovsky. Он, помнится, доказал с помощью вычетов, что из какого-то конкретного массива чисел пандиагональный квадрат построить невозможно именно потому, что не выполняется одно из необходимых условий разбиения массива чисел на группы.

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


22/03/08

7154
Саратов
В статье Россера приведён следующий классический нерегулярный пандиагональный квадрат 9-го порядка:

Код:
1 65 48 41 24 58 81 34 17
57 76 33 13 8 70 53 39 20
68 49 44 27 62 75 28 12 4
80 36 16 3 64 47 40 23 60
52 38 19 56 78 32 15 7 72
30 11 6 67 51 43 26 61 74
42 22 59 79 35 18 2 66 46
14 9 71 54 37 21 55 77 31
25 63 73 29 10 5 69 50 45

Чтобы понять, как построен этот квадрат, изучила его "анатомию". Она очень занятная. Сразу увидела, что нетрадиционный нерегулярный пандиагональный квадрат, подобный данному классическому, можно построить из девяти арифметических прогрессий длины 9 с одинаковой разностью, первые члены которых a_i удовлетворяют следующим условиям:
a_1 + a_6 + a_8 = a_2 + a_4 + a_9 = a_3 + a_5 + a_7
a_1 + a_5 +a_9 = a_2 + a_6 + a_7 = a_3 + a_4 + a_8

Понятно, что этим условиям будут удовлетворять такие прогрессии, первые члены которых тоже образуют арифметическую прогрессию. Вот такие прогрессии я и взяла из произвольных натуральных чисел; разность прогрессий равна 3, первые члены a_i прогрессий образуют арифметическую прогрессию с разностью 10:

a_1 = 3, a_2 =13, a_3 = 23, a_4 = 33, a_5 = 43, a_6 = 53, a_7 =63, a_8 = 73, a_9 = 83
Замечу, что прогрессии, конечно, составляют примитивный квадрат.
Нетрадиционный нерегулярный пандиагональный квадрат 9-го порядка из чисел этих прогрессий получился такой:

Код:
3 76 59 55 38 72 107 51 34
69 92 48 22 24 91 74 49 26
85 62 64 47 84 89 33 19 12
104 57 31 9 73 56 52 35 78
71 46 23 66 98 45 28 21 97
39 16 18 82 68 61 44 81 86
58 32 75 101 54 37 6 79 53
25 27 94 77 43 29 63 95 42
41 87 83 36 13 15 88 65 67

Интересно, можно ли найти 9 прогрессий из простых чисел, удовлетворяющих указанным условиям? Ну, понятно, что условиям будет удовлетворять арифметическая пргогрессия длины 81, но такой пока не найдено :-) Хотя теоретически она существует, значит и нерегулярный пандиагональный квадрат 9-го порядка из простых чисел существует, как, впрочем, и регулярный, потому что из чисел прогрессии длины 81 можно построить и регулярный пандиагональный квадрат.

Напомню, что пандиагональный квадрат 9-го порядка из простых чисел у нас вообще пока отсутствует, никакого нет :-(

(Оффтоп)

Опять все пропали :-(
Один svb воюет с квадратами 2х2 :-)
Pavlovsky, ау! Как у вас дела с нерегулярными пандиагональными квадратами? Мой квадрат вам не поможет?
Похоже, ваш приз останется невостребованным :-) У меня тоже иногда возникало желание учредить приз за решение очень трудной задачи. Одна была у меня такая - построение обычного магического квадрата 7-го порядка из смитов, полгода её решала, но всё-таки решила. Но..., наверное, чтобы хоть кого-нибудь заинтересовать, приз надо учредить как минимум в миллион долларов или евро. Да где же мне взять такой приз :-(

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


22/03/08

7154
Саратов
Ещё одна деталь к алгоритму svb.

Пример 2.

Судя по сообщению svb для константы 486 наборов по 9 квадратов 2х2 получается значительно больше, чем для константы 498.
Я попробовала для этой константы конкретный массив, состоящий ровно из 36 чисел (случайная генерация):

Код:
139  37  7  41  23  131  157  181  47  73  173  31  67  109  151  97  11  13  17  71  59  113  137  53  89  43  61  199  19  5  79  107  163  83  29  101

По-прежнму разбила массив на две группы - с вычетом 1 и с вычетом 5.
Запустила программу построения квадратов 2х2 по шаблону, программа задумалась надолго. Вот! А для константы 498 программа через секунду вышла в конец и ничего не нашла.
Так что константа 486 подаёт большие надежды на составление пандиагонального квадрата 6-го порядка с такой константой.

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

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


20/01/10
766
Нижний Новгород
Nataly-Mak в сообщении #349697 писал(а):
Я сейчас расписала эту решётку, в ней всё совершенно аналогично.
Любопытно, действительно:
$\left( {\begin{array}{*{20}c}
   {\left( {q1} \right)} & { - q3} & {\left( {q2} \right)} & { - q1} & {\left( {q3} \right)} & { - q2}  \\
   { - q7'} & {q9'} & { - q8'} & {q7'} & { - q9'} & {q8'}  \\
   {\left( {q4} \right)} & { - q6} & {\left( {q5} \right)} & { - q4} & {\left( {q6} \right)} & { - q5}  \\
   { - q1'} & {q3'} & { - q2'} & {q1'} & { - q3'} & {q2'}  \\
   {\left( {q7} \right)} & { - q9} & {\left( {q8} \right)} & { - q7} & {\left( {q9} \right)} & { - q8}  \\
   { - q4'} & {q6'} & { - q5'} & {q4'} & { - q6'} & {q5'}  \\
\end{array}} \right)$
При этом соотношения между $q$ напоминают (но не совпадают!) соотношения между $p$
$q1+q5+q9=0$
$q3+q5+q7=0$
$q1+q6+q8=0$
$q9+q2+q4=0$
$q3+q4+q8=0$
$q7+q2+q6=0$
Жаль, что не совпадают :-) , иначе можно было бы получить симпатичное преобразование квадратов. Но ... в любом случае необходимо будет в этом направлении "покопать".

-- Вс сен 05, 2010 12:26:26 --

Nataly-Mak в сообщении #349787 писал(а):
Судя по сообщению svb для константы 486 наборов по 9 квадратов 2х2 получается значительно больше, чем для константы 498.
Я сейчас уже не уверен в этом, т.к. "сыпались" они так же быстро, как и для 498, просто позднее.

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


22/03/08

7154
Саратов
svb
по вашей программе perebor2.exe составила вот такую любопытную статистику по отклонениям для магической константы 486. S_c = 162.
Далее в первой колонке таблицы S_b, во второй колонке отклонение, в третьей колонке - количество пар с суммой S_b, в четвёртой колонке - S_a, в пятой колонке количесвто пар с суммой S_a:

Код:
162   0   9   162   9
164   2   5   160   8
166   4   5   158   4
168   6   13 156   11
170   8   9   154   8
172  10   5   152   3
174   12  11 150   12
176  14   7   148   5
178  16   6   146   5
180  18  14   144   10
182  20   6   142   7
184  22   8   140   7
186  24  12   138   7
188  26   5   136   5
190  28   8   134   5
192  30  11   132   9
194  32   6   130   7
. . . . . . . . . . .
316  154   10   8   1
318  156   15   6   0
320  158   10   4   0
322  160   11   2   0
324  162   20   0   0

Как вы думаете, эта статистика не может нам как-то помочь?

Для статистики я взяла массив первых 86 простых чисел (конечно, без числа 2, но включая число 3). Если взять меньше чисел, количество многих пар уменьшится. Вообще зря взяла такой большой массив, надо было взять из 50 чисел. Но это недолго пересчитать.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2871 ]  На страницу Пред.  1 ... 124, 125, 126, 127, 128, 129, 130 ... 192  След.

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



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

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


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

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