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

[Бодигрим]

Понятно, что перестановка строк и чисел в строках. Я имел в виду, это осуществляется полным перебором всех возможных комбинаций или _наработаны_ какие-то эффективные (эвристические) алгоритмы, ведущие к результату?

[Nataly-Mak]

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

[tolstopuz]

А тем временем нашли новую прогрессию из 25 простых чисел: $20919497549238289+3155495\cdot23\#n (n=0\ldots24)$.

[Nataly-Mak]

tolstopuz в сообщении #239974 писал(а):

А тем временем нашли новую прогрессию из 25 простых чисел: $20919497549238289+3155495\cdot23\#n (n=0\ldots24)$.

И, значит, есть ещё много нетрадиционных магических квадратов 5-го порядка из простых чисел. Но они мне уже совсем неинтересны. Наименьший квадрат 5-го порядка из простых чисел построен. Разве только эта прогрессия может дать наибольший квадрат (из известных на сегодняшний день)
Мне бы 8 прогрессий из смитов в количестве 8 штук (с одинаковой разностью) или соответственно 9 и 10 прогрессий для построения магических квадратов из смитов порядков 8 - 10 (не составных).
А я вчера попробовала построить наименьший магический квадрат 7-го порядка из простых чисел по той же схеме. Выбрала массив из 49 простых чисел, сгенерировала строки из 7 чисел, так что сумма чисел в каждой строке равна 733 (предполагаемая магическая константа). Таких строк моя программа выдала 4261. А на втором этапе я забуксовала, Бейсик не берёт двумерный массив А(4261, 7), выдаётся ошибка: превышена размерность массива. Так что, не могу найти наборы по 7 строк, чтобы все числа в наборах были различны. Выполнила программу второго этапа в усечённом варианте (для массива из 2000 строк), программа нашла набор из 6 строк. Одной строки не хватило! Вот этот набор:

3  5  7  23  223  233  239 
11  13  17  103  193  197  199 
19  29  31  151  163  167  173 
37  41  43  61  179  181  191 
47  53  101  107  137  139  149 
67  89  97  109  113  127  131

Вчера предложила эту задачу на одном форуме. Там её решили, но, как мне кажется, неправильно. Не найдено ни одного набора из 7 строк. Трудно поверить, что из 4261 строк не сформируется ни одного набора из 7 строк, состоящего из различных чисел. На форуме товарищ сгенерировал строки, начинающиеся с разных чисел. Их оказалось всего 23, и из них нужный набор действительно не составляется. Отсюда он делает вывод, что задача не имеет решения. Может быть, она в самом деле не имеет решения, но из предложенного товарищем решения это никак не следует.
На данном форуме, как вижу, никто не желает оказывать мне помощь в построении нетрадиционных магических квадратов

-- Чт сен 03, 2009 07:21:59 --

Кстати, среди арифметических прогрессий из смитов длиной 7, найденных пользователем Mathusic, имеются две прогрессии длиной 8 с разностью $99000$:
$46241302 + 99000n$, $71188258 + 99000n$, $n = 0, 1, ..., 7$.
Для квадрата порядка 8 осталось найти 6 прогрессий длиной 8. Разность уже известна. Думаю, что такие прогрессии найдутся. Кто не боится сверхбольших чисел - вперёд!
Вообще-то все нетрадиционные магические квадраты из смитов до порядка 9 включительно построены. Для некоторой завершённости картины осталось построить квадрат порядка 10.

[Mathusic]

Nataly-Mak, $2$ это не рекорд. Сейчас порылся и нашёл прогрессии длины $8$ c одинаковой разностью

$81900:$
$9410026,9491926,9573826,9655726,9737626,9819526,9901426,9983326, $
$...............9491926,9573826,9655726,9737626,9819526,9901426,9983326,10065226,$
---
$35626315,35708215,35790115,35872015,35953915,36035815,36117715,36199615,$
---
$36216454,36298354,36380254,36462154,36544054,36625954,36707854,36789754,$
$.................36298354,36380254,36462154,36544054,36625954,36707854,36789754,36871654,$
---
$161308795,161390695,161472595,161554495,161636395,161718295,161800195,161882095,$
$192210826,192292726,192374626,192456526,192538426,192620326,192702226,192784126 $

Те, которые отделены имеют повторы, очевидно из них можно составить две девятки. А разных восьмёрок получается есть $5$.

[Бодигрим]

Что касается прогрессий из смитов - наибольшее их число наблюдается при разностях, делящихся на 9, на $10^k$ или $2\cdot10^k$ и на произведение малых простых чисел (вот пример очень типичных делителей: $7\cdot11\cdot13=1001$). Вот "топ" разностей прогрессий длины 4 из смитов до $10^7$:

    900900       692
    180180       671
     18900       579
    207900       561
    189000       555
     69300       526
     81900       505
      9900       501
    100800       497
     99000       496

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

[Mathusic]

Значит Вы ищете прогрессии любых длин?

-- Чт сен 03, 2009 13:18:01 --

Бодигрим в сообщении #240052 писал(а):

Что касается прогрессий из смитов - наибольшее их число наблюдается при разностях, делящихся ... на произведение простых чисел (например, на $7\cdot11\cdot13=1001$).

А я почему-то раньше считал, что любое число делится на произведение простых.

[Бодигрим]

Mathusic в сообщении #240063 писал(а):

А я почему-то раньше считал, что любое число делится на произведение простых.

А кто-то спорит? Я лишь обозначал наиболее типичные делители: 7, 11 и 13 в первой степени.

Mathusic в сообщении #240063 писал(а):

Значит Вы ищете прогрессии любых длин?

Нет, в предыдущем посте речь идет о прогрессиях длины 4. Сейчас немного поправлю его, чтобы избегнуть дальнейших недоразумений.

[Mathusic]

А зачем Вам прогрессии этой длины?

-- Чт сен 03, 2009 14:17:32 --

Удача. Найдены нужные прогрессии длины 8.
$d=900900$

395842,1296742,2197642,3098542,3999442,4900342,5801242,6702142,
3603919,4504819,5405719,6306619,7207519,8108419,9009319,9910219,
67260334,68161234,69062134,69963034,70863934,71764834,72665734,73566634,
{
76018702,76919602,77820502,78721402,79622302,80523202,81424102,82325002,
76919602,77820502,78721402,79622302,80523202,81424102,82325002,83225902,
}
88451815,89352715,90253615,91154515,92055415,92956315,93857215,94758115,
124522906,125423806,126324706,127225606,128126506,129027406,129928306,130829206,
154215535,155116435,156017335,156918235,157819135,158720035,159620935,160521835,
165437365,166338265,167239165,168140065,169040965,169941865,170842765,171743665,
167317285,168218185,169119085,170019985,170920885,171821785,172722685,173623585,
175638982,176539882,177440782,178341682,179242582,180143482,181044382,181945282,
180071662,180972562,181873462,182774362,183675262,184576162,185477062,186377962,
199495822,200396722,201297622,202198522,203099422,204000322,204901222,205802122,

Причём пересекающиеся из них только две! (проверял на глаз, но вроде точно)
Да, всё верно, девятка одна. Проверил не вручную

$$900900: 76018702,76919602,77820502,78721402,79622302,80523202,81424102,82325002,83225902, $$

[Nataly-Mak]

Mathusic, теперь вам и флаг в руки! В моей статье "Нетрадиционные магические квадраты из чисел Смита" берите вспомогательные квадраты порядка 8 и стройте магический квадрат 8-го порядка из смитов (в статье приведён пример построения квадрата из обычных арифметических прогрессий).
Это будет принципиально новый квадрат, не составной, как построил tolstopuz. Покажите нам построенный квадрат, пожалуйста.

-- Чт сен 03, 2009 15:06:23 --

Бодигрим в сообщении #240052 писал(а):

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

Позвольте полюбопытствовать, для чего вам 9 непересекающихся прогрессий длиной 4 с одинаковой разностью?
Я сформировала массив из прогрессий длиной 4 с одной и той же разностью $36$. В этом массиве 157 прогрессий. По-моему, я вам посылала этот массив. Разве из этого массива нельзя выбрать 9 непересекающихся прогрессий? Или я что-то не так поняла?

[Mathusic]

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

Mathusic, теперь вам и флаг в руки! В моей статье "Нетрадиционные магические квадраты из чисел Смита" берите вспомогательные квадраты порядка 8 и стройте магический квадрат 8-го порядка из смитов (в статье приведён пример построения квадрата из обычных арифметических прогрессий).
Это будет принципиально новый квадрат, не составной, как построил tolstopuz. Покажите нам построенный квадрат, пожалуйста.

На это у меня уже времени нет, если желаете - дерзайте. Из показанного набора можно выбрать
$2C_{12}^{8}$ восьмёрок прогрессий. Найти 9 по 9 будет уже сложней.

[Nataly-Mak]

Ну, вписать числа готовых прогрессий в квадрат - дело 5 минут (правда, если знать, как их вписывать; впрочем, пользователь tolstopuz высказал здесь мнение, что это может сделать и ребёнок). Будем считать, что такой квадрат построен.

[Бодигрим]

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

Разве из этого массива нельзя выбрать 9 непересекающихся прогрессий?

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

[Nataly-Mak]

Бодигрим в сообщении #240265 писал(а):

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

Разве из этого массива нельзя выбрать 9 непересекающихся прогрессий?

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

А можно подробнее? Что именно вам не удалось? Мне нужно было для всех высланных вам арифметических прогрессий длиной 4 вычислить сумму членов каждой прогрессии. Должен получиться массив из 157 чисел (сумм). Из этих 157 чисел надо попытаться построить магический квадрат 3-го порядка, хотя бы один. Неужели такой квадрат не получается? Хотя это вполне возможно.

[Nataly-Mak]

Я построила магический квадрат 7-го порядка из простых чисел в классическом определении. Магическая константа квадрата равна 733. Минимально возможная константа такого квадрата равна 731. Но мне не удалось сформировать массив из простых чисел так, чтобы сумма чисел массива была равна $731 * 7 = 5117$. Так что, по-моему, построенный мной квадрат является наименьшим.

3 5 7 23 223 233 239
211 191 181 19 31 29 71
79 83 89 107 109 127 139
199 197 103 193 17 11 13
53 149 59 157 101 47 167
151 67 131 137 73 113 61
37 41 163 97 179 173 43

Бодигрим, проверьте меня, пожалуйста, в отношении минимальности магической константы. Если построенный квадрат действительно наименьший, то о нём надо сообщить "в компетентные органы". Правильно? Я, к сожалению, не умею писать по-английски. А туда ведь надо на английском языке сообщать?
Теперь у нас такая последовательность имеется: 177, 120, 233, 432, 733.

-- Пт сен 04, 2009 17:09:00 --

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

5 3 7 23 227 239 229
193 103 197 199 11 17 13
79 211 157 73 71 83 59
149 139 53 137 107 47 101
29 19 31 151 163 173 167
97 67 109 89 113 131 127
181 191 179 61 41 43 37