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

[Nataly-Mak]

Цитата:

Внимание! Будьте осторожны - в вашем варианте программы тип переменных на дает возможности использовать числа более 32000. Я вам уже писал - замените integer на longint в тексте mak4.pas и откомпилируйте. Строка для запуска компилятора:
tpc.exe mak4.pas

Ага! Поняла, почему программа не работает с большими числами. Но я нашла выход из положения: уменьшаю все члены массива на минимальный элемент и получаю вполне "съедобный" массив

Вы хорошо над программой поработали. Осталось совсем малость: найти квадрат

[svb]

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

Ага! Поняла, почему программа не работает с большими числами. Но я нашла выход из положения: уменьшаю все члены массива на минимальный элемент и получаю вполне "съедобный" массив

В аварийном порядке:
mak5 - сумма чисел до 2147000000
набор квадратов

[Nataly-Mak]

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

1:
 729  22 517 274  94
 265 121 378 166 706
 202 526 346 535  27
  58 648 391  85 454
 382 319   4 576 355

Время выполнения программы:
Time : 531.70 s

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

Проверила и для массива из больших чисел (чуть больше миллиона). Программа работала меньше 2 минут (102 секунды).

Можно приступать к поиску квадрата.

-- Пн фев 15, 2010 08:15:44 --

Цитата:

Не коротким, но относительно коротким (по сравнению с количеством простых чисел, равным n^2 ).

Не поняла.
Если вы строите квадрат порядка n из различных чисел, вам в любом случае нужен набор из n^2 различных чисел. Даже если вы его перенесёте в начало ряда натуральных чисел (уменьшив все члены на минимальное число), всё равно это будет набор из n^2 чисел.
О каком относительно коротком наборе чисел вы говорите?

Далее, я рассуждаю так: если множество простых чисел не является достаточно плотным, то найдётся в нём такое подмножество, которое тоже не является достаточно плотным. Поэтому нельзя утверждать, что любой набор из n^2 последовательных простых чисел будет достаточно плотным. Скорее всего, это не так.

[Nataly-Mak]

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

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

Проверила сегодня ещё несколько массивов, квадрата пока нет.

Сильно задумываюсь над оптимизацией поиска массивов-кандидатов, потому что проверять все массивы подряд - скучное занятие, никаких шансов получить квадрат из плохого массива.
А плохим является такой массив, в котором недостаточное количество разбиений на группы по 5 чисел, дающих в сумме магическую константу квадрата.
Кстати, во втором алгоритме этот момент учитывается сразу.

[maxal]

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

Если вы строите квадрат порядка n из различных чисел, вам в любом случае нужен набор из n^2 различных чисел. Даже если вы его перенесёте в начало ряда натуральных чисел (уменьшив все члены на минимальное число), всё равно это будет набор из n^2 чисел.
О каком относительно коротком наборе чисел вы говорите?

В моих обозначениях $n$ - длина стороны квадрата, $n^2$ - соответственно количество элементов в нем. Элементы лежат в относительно коротком отрезке, если расстояние между максимальным и минимальным элементом лишь немного превышает их количество.

[Nataly-Mak]

Не вижу никакой разницы в ваших и моих обозначениях!

Вы присали:

Цитата:

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

Тут пока не фигурируют никакие относительно короткие отрезки.

Так что же это всё-таки такое - относительно короткий отрезок?

Насколько я могу понять, вы говорите о множестве, полученном из первоначального множества n^2 последовательных простых чисел, уменьшением всех элементов этого множества на минимальный элемент, в результате чего множество переносится в начало натурального ряда.
Так что ли?
Но тогда это будет уже не множество последовательных простых чисел и плотность этого искусственно созданного множества не имеет ничего общего с плотностью первоначального множества из n^2 последовательных простых чисел, которое может быть и не достаточно плотным (в смысле данного вами выше определения).

[Nataly-Mak]

Чтобы было понятно, что такое плохой массив-кандидат.
Вот последний из проверенных мной массивов из 25 последовательных смитов на предмет составления магического квадрата 5х5:

1009921  1009966  1010155  1010299  1010605  1010636  1010928  1010945  1011487  1011678  1011747  1012099  1012659 1012666  1012846  1012873  1012927  1013433  1013595  1013665  1013683  1013755  1013991  1014057  1014344

Минимизирую массив, чтобы было удобнее с ним работать:

0  45  234  378  684  715  1007  1024  1566  1757  1826  2178  2738  2745  2925  2952  3006  3512  3674  3744  3762  3834 4070  4136  4423

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

0  1024  2178  3762  4423 
0  1566  2745  3006  4070 
0  2178  2745  2952  3512 
45  234  3512  3762  3834 
45  1757  2745  3006  3834 
378  1566  2925  3006  3512 
684  715  2178  3674  4136 
684  1757  2178  3006  3762

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

Для сравнения: из массива смитов, который складывается в магический квадрат (квадрат Бодигрима), сгенерировано 236 строк по 5 чисел, дающих в сумме магическую константу.

[12d3]

Вот еще одна программа для поиска магических квадратов из последовательных чисел смита. Скорость приемлемая. До двух миллиардов будет проверять примерно сутки. Хотя все равно долго.

[Nataly-Mak]

О! Кто к нам пришёл!

Вы до какого значения проверили уже смиты для квадрата 5-го порядка? До миллиона или уже больше? А то я сейчас на втором миллионе проверяю. Может, зря
Убыстрила значительно свою работу. Подключила программу генерации строк. Сначала нахожу порцию из 50 массивов, удовлетворяющих только одному условию: сумма всех членов массива кратна 5. Такая порция, понятно, находится моментально. Далее загоняю эти 50 массивов в программу генерации строк. Эта программа выполняется примерно за 4-5 минут.
Интересная статистика: строк генерируется от 3 до 82. Больше 82 у меня ещё ни разу не получилось.
Отметаю все массивы, из которых генерируется менее 70 строк (число взяла с потолка). Из 50 массивов только 1-2 удовлетворяют этому условию (иногда нет ни одного). Эти массивы уже проверяю по программе svb.

Всё равно, конечно, процесс очень трудоёмкий.
Удручает то, что из всех массивов очень мало генерируется строк, дающих магическую константу квадрата.

[12d3]

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

Вы до какого значения проверили уже смиты для квадрата 5-го порядка? До миллиона или уже больше?

До ста миллионов проверял. Дальше сами. =) Хотя что-то мне подсказывает, что не найдется такой квадрат.

[Nataly-Mak]

12d3 в сообщении #289790 писал(а):

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

Вы до какого значения проверили уже смиты для квадрата 5-го порядка? До миллиона или уже больше?

До ста миллионов проверял. Дальше сами. =) Хотя что-то мне подсказывает, что не найдется такой квадрат.

Ну, вот! А я пыхчу, пыхчу на втором миллионе
Спасибо, что сказали. Значит, надо теперь на 101-ом миллионе проверять.

Я всё-таки рекомендую начать с поиска хороших массивов-кандидатов. Вот, например, maxal для квадратов 4-го порядка нашёл всего 28 потенциальных массивов (а проверил до 10^{12}).
Ну, а проверить 28 массивов - это дело пустяковое. Я их за 2 минуты проверила.

Насчёт того, что квадрат не найдётся - это вы зря. Почему бы ему не найтись?
Вот квадрат 3-го порядка нашёлся же. И квадрат 6-го порядка нашёлся.
Найдутся и квадраты порядков 4 - 5. Я почти уверена.

А по поводу "дальше сами", тут не получится. У меня смиты только до 2 миллионов, больше нету.

[12d3]

Несколько глупых вопросов.

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

Вот, например, maxal для квадратов 4-го порядка нашёл всего 28 потенциальных массивов (а проверил до 10^{12}).

Каким образом выбраны эти 28 массивов? Почему остальные не входят в эти потенциальные массивы?

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

Вот квадрат 3-го порядка нашёлся же.

Я походу что-то пропустил. Какая у этого квадрата константа?

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

А по поводу "дальше сами", тут не получится. У меня смиты только до 2 миллионов, больше нету.

А и не надо. В программе смиты на ходу генерируются.

[Nataly-Mak]

Ну, как же вы такое знаменательное событие пропустили!

Вот наименьший магический квадрат 3-го порядка из последовательных смитов (автор maxal):

84138954584 84138954498 84138954532
84138954486 84138954538 84138954590
84138954544 84138954578 84138954492

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

Всё начинается как раз с разбиений на четвёрки чисел, дающих в сумме магическую константу. Далее из этих четвёрок выбираются такие, которые не имеют общих элементов, ну и так далее. Всё в общем-то понятно. Но надо написать грамотно программу подбора таких массивов. Тогда задача сведётся к поиску хорошо подготовленных массивов-кандидатов. А уж проверка найденных массивов - дело второе и очень, кстати, быстрое.

А насчёт того, что вы в своей программе вставили генерацию смитов на ходу - это просто замечательно!

[maxal]

12d3 в сообщении #289798 писал(а):

Каким образом выбраны эти 28 массивов? Почему остальные не входят в эти потенциальные массивы?

См. post285497.html#p285497

[12d3]

В качестве проверки: верно, что у магического квадрата 5-го порядка из последовательных простых чисел минимальная константа 1843?