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

[tolstopuz]

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

(Согласно определению чисел-смитов все простые числа тоже являются смитами. Так?)

В известных мне определениях - не так. Только составные.

http://en.wikipedia.org/wiki/Smith_number
http://mathworld.wolfram.com/SmithNumber.html
http://www.shyamsundergupta.com/smith.htm

[Nataly-Mak]

Посмотрела в Википедии. Да, там написано, что это составные числа (догадываюсь, что composite значит "составной"). Тогда это меняет дело. И нет нужды писать, что квадрат должен заполняться составными смитами, если смиты всегда составные числа. По-моему, в статье из журнала "Наука и жизнь", по которой я познакомилась со смитами, не написано, что это обязательно составные числа. Может быть, невнимательно читала.

-- Пн июл 20, 2009 12:32:14 --

Ещё один нетрадиционный совершенный магический квадрат 4-го порядка из простых чисел по последней, приведённой только что tolstopuz'ом, прогрессии длиной 16:

53297929 121195759 169694209 159994519
179393899 150294829 62997619 111496069
82396999 92096689 198793279 130895449
189093589 140595139 72697309 101796379

(если не ошиблась в вычислениях).
Понятно, что аналогичные квадраты 4-го порядка можно строить из простых чисел, образующих прогрессии большей длины (17, 18 и т. д.). В этих случаях можно построить не один квадрат.

-- Пн июл 20, 2009 15:45:03 --

Да, невнимательно читала, хотя надо заметить, что определение смитов в статье можно было бы дать поотчётливее. Вот цитата из статьи (журнал "Наука и жизнь", № 3, 2009 г.):
"Быть может, этот факт так и остался бы в разряде числовых курьёзов, не вмешайся в историю родственник Смита — математик, профессор одного из американских университетов Альберт Виланский. Он опубликовал в 1982 году заметку об обнаруженном свойстве, а обладающие им составные числа назвал именем Смита. Тогда же Виланский предположил, что таких чисел существует бесконечно много. И оказался прав: вскоре эту гипотезу доказал его коллега. Так было положено начало исследованию весьма интересного множества чисел". (выделено мной)

-- Пн июл 20, 2009 16:58:35 --

А из прогрессий меньшей длины (меньше 16) тоже можно строить магические квадраты 4х4, только в этом случае будут повторяющиеся числа. На худой конец сгодятся и такие квадраты. Вот, например, прогрессия из шести простых чисел, котрая находится с ходу: $7,37,67,97,127,157$. Запускаю программу для построения нетрадиционных магических квдаратов 4-го порядка для данного массива чисел, вот первое из полученных решений:

7 67 97 37
157 7 37 7
37 127 37 7
7 7 37 157

Здесь разных чисел очень мало, поэтому повторений много.
tolstopuz, из найденной вами прогресии из 12 смитов уже можно построить магический квадрат 4х4, будет всего 4 числа повторяться. Это решение задачи в первом приближении. Принимается

[Бодигрим]

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

Восхищена вашим решением! Мне пока не удалось решить задачу. Я пыталась, но моя программа выполняется очень долго. Думаю, что это действительно минимальный квадрат 5-го порядка из различных простых чисел (в классическом определении).

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

     7    13   101    43    71
    67    79    53    19    17
    11    23    47    41   113
    89    37    31    73     5
    61    83     3    59    29

Поскольку для пятого порядка магическая константа должна быть нечетной и больше 231.8, то обогнать этот пример может только квадрат с константой 233.

[tolstopuz]

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

Нашелся квадрат с константой 235.

Просто праздник какой-то - там все простые, кроме последнего, последовательные. А я за 5x5 еще не брался.

Вообще надо бы в OEIS потом это кинуть, как maxal предлагал.

-- Пн июл 20, 2009 19:50:12 --

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

tolstopuz, из найденной вами прогресии из 12 смитов уже можно построить магический квадрат 4х4, будет всего 4 числа повторяться.

Раз уж я запустил перебор до миллиарда, пусть считает - вдруг найдет 13 или даже 14. Там где-то на неделю работы на моем трехгигагерцовом процессоре. Второе ядро не занимаю, чтобы не перегревался и не мешал работать на нем в это время.

[Бодигрим]

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

Просто праздник какой-то - там все простые, кроме последнего, последовательные.

Кроме двух: между 89 и 101 еще 97 полагалось бы быть.

[Nataly-Mak]

Браво, Бодигрим!
Искренне рада вашему успеху. Квадрат действительно замечательный.
Таким образом, найдены два наименьших квадрата, которые являются соседями. Так? Между константами 265 и 235 больше нет квадратов?
tolstopuz, вам от души желаю удачи в поисках прогрессии из смитов длиной 16!
А что такое OEIS?

[tolstopuz]

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

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

Просто праздник какой-то - там все простые, кроме последнего, последовательные.

Кроме двух: между 89 и 101 еще 97 полагалось бы быть.

А, да. Но все равно хорошо.

-- Вт июл 21, 2009 09:44:43 --

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

tolstopuz, вам от души желаю удачи в поисках прогрессии из смитов длиной 16!

Тут уже 13:

58664805 105686871 152708937 199731003 246753069 293775135 340797201 387819267 434841333 481863399 528885465 575907531 622929597

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

А что такое OEIS?

post228601.html#p228601
Там maxal дает на нее ссылки.

[Бодигрим]

И наконец - квадраты с константой 233. Меньше - некуда :) Ура :)

    41    11    79    19    83
    31    67    29    89    17
    61    59     5    71    37
    97    53    13    47    23
     3    43   107     7    73

В этом квадрате первые 24 последовательных нечетных простых числа и 107.

    53    17    13    79    71
    73    37    41    59    23
    61    83    11    47    31
    43    89    67    29     5
     3     7   101    19   103

А тут - 23 последовательных, дырка, 101-103.

Других наборов чисел, дающих квадраты с суммой 233, не существует. Действительно, в наборе 25 простых нечетных чисел с общей суммой 5*233 наибольшее не может превышать 107 - 27-го простого числа. И далее, из 27 первых простых чисел можно лишь двумя способами (приведенными выше) можно выбрать 25 с суммой 5*233.

Все, можно попробовать поработать с квадратами из простых 6 на 6. Авось повезет.

[Nataly-Mak]

Поздравляю с победой, Бодигрим!
Если у вас программа для построения нетрадиционных квадратов 5х5 так хорошо отлажена, вам ничего не стоит решить следующую задачу: построить магический квадрат 5х5 из различных смитов с минимальной магической константой. Думаю, что решение этой задачи появится в ближайшее время.
tolstopuz, уже 13! Близки к цели Ещё немного, ещё чуть-чуть...

-- Вт июл 21, 2009 13:17:45 --

Вот вам основа для построения магического квадрата 4х4 из смитов, образующих прогрессию длины 13 (конечно, вы сами можете такой квадрат построить, но я хочу вам немного помочь в порядке дружеского участия ):

1 11 8 5
13 2 4 6
4 9 10 2
7 3 3 12

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

[tolstopuz]

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

tolstopuz, уже 13! Близки к цели

Проект уже давно перерос первоначальную цель. Какой смысл вписывать полученные программой числа в квадратики? Это может сделать даже ребенок. Получить прогрессию - вот это задача.

[Nataly-Mak]

Спасибо! Желаю удачи в вашем грандиозном проекте! Как я понимаю, мне здесь больше делать нечего...
И для чего же нужна эта прогрессия человечеству? Мне она, например, нужна только для того, чтобы вписать её в квадрат. И, между прочим, строить магические квадраты - это тоже задача! Не всегда решаемая тупым перебором, как поиск прогрессии.

[tolstopuz]

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

И для чего же нужна эта прогрессия человечеству?

Эти смиты человечеству вообще не нужны, я их рассматриваю как интересную задачу по программированию. Мне еще не приходилось просеивать миллиард чисел и из просеянных 25 миллионов составлять прогрессии.

А вот прогрессии из простых чисел получают очень активно:

http://www.primegrid.com/forum_thread.php?id=1246
http://www.primegrid.com/forum_thread.php?id=1182

[maxal]

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

Все, можно попробовать поработать с квадратами из простых 6 на 6. Авось повезет.

Если найдете минимальную константу для 6x6 можно смело посылать последовательность 177, 120, 233, XXX в OEIS - там как раз минимум 4 члена требуется для новых последовательностей.

[Mathusic]

В Вики, написано, что общих методов построения маг. квадратов нет. У меня вопрос: а нельзя ли просто записать СЛУ и найти общее решение в параметрическом виде? После этого, скажем можно найти базис пространства магических матриц (над полем $\mathbb Q$; для этого придётся рассматривать квадраты с рациональными элементами, но ведь из них можно получить с целыми), а дальше конструировать квадраты в виде ЛК векторов базиса.
Подпространства в пространстве $Mat_{n}(\mathbb{Q})$ образуют также ассоциативные, пандиагональные и идеальные магические матрицы.
Или этот способ черезчур громоздок?

[maxal]

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

У меня вопрос: а нельзя ли просто записать СЛУ и найти общее решение в параметрическом виде? После этого, скажем можно найти базис пространства магических матриц (над полем $\mathbb Q$; для этого придётся рассматривать квадраты с рациональными элементами, но ведь из них можно получить с целыми), а дальше конструировать квадраты в виде ЛК векторов базиса.

Вы забываете про существенное условие, что все элементы квадрата являются попарно различными. Описанный метод никак не гарантирует выполнения этого условия.