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

[Nataly-Mak]

svb
Скачала ваш архив и распаковала.
Программа test у меня выполнилась.
Программа, которая имеет вид исполняемой, промелькнула в мгновение ока, что она там делала, не знаю.
Пожалуйста, подскажите, что мне нужно сделать, чтобы скомпилировать программу.
Есть ещё файлы: TPC, turbo, ST11, ST13, ST14.

[svb]

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

svb
Программа test у меня выполнилась.
Программа, которая имеет вид исполняемой, промелькнула в мгновение ока, что она там делала, не знаю.
Пожалуйста, подскажите, что мне нужно сделать, чтобы скомпилировать программу.
Есть ещё файлы: TPC, turbo, ST11, ST13, ST14.

Они уже даны откомпилированными, но они ДОСовские, поэтому желательно их запускать по старинке. Я пользуюсь навигатором FAR, он дружит с виндовозом.
Батовский файл test.bat просто запустил по очереди программы mak1.exe, mak3.exe и mak4.exe. Каждая из этих программ создала свой текстовый файл, ST11, ST13, ST14, соответственно. В качестве исходного набора они использовали файл st1.txt с 25 числами 1,..,25 (из виндовоза этот файл вы можете посмотреть тем же блокнотом). Файлов ST11, ST13, ST14 в архиве не было - они уже были созданы на вашей машине. Можете их переименовать с расширением .txt , тогда блокнотом увидите их содержимое - в конце каждого файла указано время исполнения на вашей машине. Файл !README.TXT дан в альтернативной кодировке, поэтому если будете его смотреть блокнотом в виндовозе, то переключитесь на шрифт Terminal. В нем коротко описано, что делать.
Вчера попробовал запустить mak4.exe, скормив ей простые числа из набора prost2.txt - менее 2-х часов понадобилось для создания более 11 тысяч квадратов. И это было только начало, но, похоже, можно сгенерировать весь набор квадратов за "приемлемое" время. У меня возникло ощущение, что простые числа - очень хороший материал для магических квадратов (и для задачи о рюкзаке ).
Компилятор tpc.exe я вам прислал для того, чтобы вы переходили на паскаль. Конечно, это уже старенький компилятор для ДОС, но пока им можно работать. Для ваших задач он очень хорош и язык проще BASIC-а. Вам уже советовали переходить на Free Pascal, но, боюсь, он может вас отпугнуть абсолютно ненужными вам вещами - слишком много там добавлено для работы под виндовоз. Для расчетных задач это не нужно. Но там есть аналогичный tpc компилятор fpc.exe, но уже 32 и 64 битовый, что более подходит для современных машин. А самое главное - там можно использовать очень большую память, вам может она понадобиться. Хотя переборным задачам она не всегда нужна - пример, ваш алгоритм.
tpc вы можете использовать уже сейчас - исправьте в тексте программы тип переменной w с integer на longint, а то сумма w быстро превысит 32000 и возникнут проблемы. После компиляции будет новый работоспособный вариант программы.
Если у вас нет навигатора, то в виндовозе в меню запуск наберите CMD - запустится досовское окно. В нем вы сможете запускать присланные программы.

Чтобы не загромождать форум информацией не по теме, можете писать мне на мой адрес [e-mail]

[Nataly-Mak]

svb
Спасибо, но пока ничего не поняла
Я напишу вам ЛС.

Только вопрос интересный всем: вы какие квадраты порядка 4 строили? Из какого массива? Судя по количеству построенных квадратов, этот массив состоял не из 16 чисел. Так?

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

-- Сб фев 13, 2010 09:29:13 --

maxal
У меня есть вопросы, касающиеся плотности множества простых чисел.
Вы привели параметр, характеризующий эту плотность.

Вопрос 1: каким условиям должен удовлетворять этот параметр, если множество достаточно плотное?

Вопрос 2.
Известно, что для любого натурального $k$ существует отрезок из $k$ последовательных натуральных чисел, в котором нет ни одного простого числа.
Не является ли наличие таких пустых оазисов нарушением достаточной плотности множества простых чисел?
И не будет ли это серьёзным препятствием в построении магических квадратов больших порядков из последовательных простых чисел?

(Извините, если вопрос опять тривиальный, но здесь ведь нет перечня тривиальных и нетривиальных вопросов )

[svb]

Nataly-Mak писал(а):

Только вопрос интересный всем: вы какие квадраты порядка 4 строили? Из какого массива? Судя по количеству построенных квадратов, этот массив состоял не из 16 чисел. Так?

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

Я, вроде, писал про порядок 5 ? Исходный массив prost2.txt - 25 простых чисел 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 101 103. Построил 11916 квадратов за 5251.26 сек.
Вот из файла последний квадрат:
11916:
3 41 29 89 71
79 83 23 11 37
17 7 61 101 47
103 59 53 13 5
31 43 67 19 73

Подсунул какой-то набор 25 смитов (чтобы сумма делилась на 5) - программа достаточно быстро сделала полный перебор и не нашла ни одного квадрата. Это, в общем, понято - нет взаимной простоты, по той же четности набор мог не проходить.

[Nataly-Mak]

Я что-то просмотрела из ваших сообщений?

Итак, ваша программа замечательно работает для проверки массивов из 25 чисел. Это же здорово!
Тогда вперёд. Поверим 12d3 , что в первом миллионе нет подходящего массива, складывающегося в магический квадрат. Берите следующий миллион и проверяйте всех кандидатов. Надеюсь, что квадрат 5-го порядка построится хотя бы в пределах 10 миллионов. Хотя как знать! Но квадрат 6-го порядка построился вообще из малюсеньких последовательных смитов - прямо из первого кандидата.

Кстати, протестируйте свою программу для массива смитов, из которого магический квадрат 5-го порядка точно строится, например, вот для такого:

4 166 634 762 265 
382 346 663 355 85 
645 517 454 121 94 
526 483 58 202 562 
274 319 22 391 825

[svb]

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

Итак, ваша программа замечательно работает для проверки массивов из 25 чисел. Это же здорово!

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

Nataly-Mak писал(а):

Кстати, протестируйте свою программу для массива смитов, из которого магический квадрат 5-го порядка точно строится, например, вот для такого:

4 166 634 762 265 
382 346 663 355 85 
645 517 454 121 94 
526 483 58 202 562 
274 319 22 391 825

Что ж , программа честно прошла полный перебор, а я с тоской наблюдал и думал, что нужно ее дорабатывать - она работает в 32 раза дольше, чем нужно!
Зря вы дали уже готовый квадрат - он мог оказаться единственным и что тогда отвечать? Но ... все же программа выдала 64 решения, т.е. еще один квадрат:

319 526 382 483 121
  22 645 562 517  85
 634   4 166 202 825
  94 265 663 355 454
 762 391  58 274 346

[maxal]

Обсуждение OEIS отделено в тему topic30306.html

[Nataly-Mak]

svb
Поздравляю! Это уже хороший результат.

Сколько времени программа выполняла полный перебор для этого массива смитов?

Как я уже отмечала, для смитов перебор должен выполняться гораздо быстрее, чем для простых чисел, потому что смиты плохо складываются в пятёрки, дающие магическую константу квадрата. И магических квадратов из заданного массива смитов строится очень мало. Вот из проверенного вами массива смитов построились всего два квадрата! А из проверенного раньше массива простых чисел построились тысячи квадратов (даже если разделить общее количество на 32, всё равно много получается).

[maxal]

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

Вопрос 1: каким условиям должен удовлетворять этот параметр, если множество достаточно плотное?

Точно сказать затрудняюсь. Может, что-то типа $\geq n^c$, где $c$ - некоторая константа (например, $c=-1/2$).

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

Вопрос 2.
Известно, что для любого натурального $k$ существует отрезок из $k$ последовательных натуральных чисел, в котором нет ни одного простого числа.
Не является ли наличие таких пустых оазисов нарушением достаточной плотности множества простых чисел?
И не будет ли это серьёзным препятствием в построении магических квадратов больших порядков из последовательных простых чисел?

Если говорить о простых числах в начальном отрезке натуральных чисел, то такие "оазисы" без простых чисел проблем доставлять не должны. Дело в том, что в совокупности простые все равно распределены более-менее равномерно (см. Теорему о распределении простых чисел), и если такой оазис не может быть очень большим по сравнению с длиной выбранного отрезка. Например, в пределах первых 100 натуральных чисел максимальное расстояние между простыми равно лишь 8, в пределах первых 1000 натуральных чисел оно равно лишь 20 и т.д. (см. последовательность A038460).

[Nataly-Mak]

Вот пример (если я правильно понимаю определение плотности множества):

n = 1, M = 907, m = 888.

В этом случае:

ρ = 1/(907 - 888 + 1) = 0,05

И это никак не удовлетворяет приведённому вами условию для плотности множества.

[maxal]

Nataly-Mak
Не удовлетворяют, но я и не говорил, что всякое множество простых является плотным. Те множества, что возникают в задачах построения магических квадратов больших порядков ($n\geq 5$) из как можно меньших простых, являются подмножествами относительно коротких начальных отрезков натурального ряда. И вот они-то являются плотными.

[Nataly-Mak]

maxal в сообщении #288963 писал(а):

Nataly-Mak
Не удовлетворяют, но я и не говорил, что всякое множество простых является плотным. Те множества, что возникают в задачах построения магических квадратов больших порядков ($n\geq 5$) из как можно меньших простых, являются подмножествами относительно коротких начальных отрезков натурального ряда. И вот они-то являются плотными.

Но почему же "относительно коротких начальных отрезков натурального ряда"?
Если порядок квадрата будет $n = 100000$, разве этот отрезок будет коротким?

svb

Ура! Ваша программа у меня заработала!
Вы наблюдали за её работой с тоской, а я - с восторгом. Потому что такое быстродействие мне и не снилось.
Программа перебрала все параметры для I = 1 за 15 минут и перешла к I = 2.
Для этих значений параметров найдено 8 квадратов.
Восторг! Вот первые два квадрата, записанные в выходной файл:

1:
   4 166 762 634 265
 382 346  58 483 562
 517 645 454 121  94
 654 355 535 202  85
 274 319  22 391 825
2:
   4 166 762 634 265
 382 346 535 483  85
 517 645 454 121  94
 654 355  58 202 562
 274 319  22 391 825

Хорошо работает программа.
Если вы её ещё оптимизируете, будет вообще отлично.

А вариант другого языка (с более высоким быстродействием) возможен?

Приглашаю всех искать наименьший магический квадрат 5-го порядка из последовательных смитов по предложенной svb программе.

[Nataly-Mak]

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

Я проверила уже 10 таких массивов.
Первый массив взяла тот, который первым переваливает за миллион, вот этот:

999153, ..., 1000462

Беда в том, что массивов-кандидатов очень много, потому что я накладываю на массив только одно условие: сумма всех чисел массива кратна 5.

Значит, надо ещё как-то оптимизировать поиск массивов-кандидатов (как это сделал maxal для кандидатов в квадрат 4х4), чтобы их было поменьше, а то слишком много массивов приходится проверять.

Впрочем, можно и все подряд проверять, но тогда надо в программу вставить блок поиска массивов-кандидатов; сначала ищется массив, потом сразу проверка найденного массива идёт, потом ищется следующий кандидат и проверяется и т. д.
Ввести в эту программу приличный массив смитов и - вперёд. Пусть программа работает несколько часов. За это время она сможет обработать много массивов-кандидатов, если в час она обрабатывает примерно 15 массивов.

svb
Вы поняли моё предложение?

[svb]

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

Если вы её ещё оптимизируете, будет вообще отлично.

А вариант другого языка (с более высоким быстродействием) возможен?

Кое-что я вчера сделал, но сначала несколько слов о вашем алгоритме для тех, кто не стал смотреть текст на васике. В нем идет перебор с помощью вложенных циклов - в таблице ниже показаны переменные перебора i,j,..,v. Прежде чем входить в очередной вложенный цикл идут проверки о необходимости подобного вхождения. Например, после задания переменных i,j,k,l вычисляется элемент с индексом x1 и процесс не идет дальше, если проверки не пройдены. Понятно, что это можно организовать разными способами. У Наталии последовательно вычисляются элементы квадрата с индексами x1,x2,x3,x4,x5,x6, а далее элементы 21,22,23,24,25 (это не числа, а обозначения элементов квадрата). Насколько оптимально это сделано у Наталии? Вопрос, вообще говоря, открыт. Но, по крайней мере, весьма неплохо сделано.
Прежде всего (это сделано уже в программах mak3 и mak4), когда я переписывал алгоритм, то обратил внимание, что индексы x1,..,x6 находились, но из дальнейшего перебора не исключались - я немного поправил текст и быстродействие увеличилось в 4 раза. Выкинул ненужные проверки на финише - сумму элементов последней строки проверять не надо, т.к. уже исходный набор чисел выбран с суммой равной 5 магическим числам. Кстати, особого выигрыша по времени это не дало - до последних операций нужно еще добраться .

i  j  k x1  l       
t x3 x5  m x4     
x6 21  n  v  s
u x2 22  q  r    
o 23 24 25  p

После тестирования на смитах стало очевидно, что молотить уже найденные варианты дополнительно 31 раз совсем ни к чему. Для квадратов 5 порядка, хорошо известно, существует понятие изоморфизма, т.е. повороты и симметрия из любого квадрата дают традиционно эквивалентные квадраты, плюс два специальных преобразования увеличивают набор эквивалентных квадратов до 32.
1. Посмотрим на элементы i,l,p,o,x3,m,q,x2 - максимальный элемент можно с помощью преобразования вывести на внешнюю границу, а затем с помощью поворота перевести его на место i. Итак:
i>l,p,o,x3,m,q,x2
2. Смотрим на элементы j,x1,u,t. Не затрагивая элемента i, можно с помощью второго спец. преобразования (одновременное переворачивание внутренних горизонтальных и вертикальных полос) и симметрии относительно диагонали i-p добиться, чтобы максимальный элемент рассматриваемой группы оказался на месте j. Итак:
j>t,x1,u

Осталось чуть изменить пределы перебора циклов и... модифицированная программа mak5 заработала.
Сначала я протестировал ее на тех же смитах, что предложила Наталия.
Было: 12148.90 сек
Стало: 594.83 сек
Программа, как ей и положено, выдала 2 не изоморфных квадрата.

Далее я подсунул программе исходный набор из простых чисел 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 101 103 и лег спать. Результат:
Время работы: 26968.40 сек
Количество не изоморфных квадратов - 58257, что соответствует 233028 традиционно различным квадратам и 1864224 всех квадратов.

Что дальше? Пока выбор элементов из уменьшающегося набора в алгоритме идет с помощью линейного поиска, что "не есть хорошо" - любая "деревянная" конструкция, обычно, лучше, особенно, если попытаться расширить исходный набор. Выбор другого языка и технических средств - это за пределами алгоритма. Конечно, 16-битовый BP7 нужно заменить на FP - эффект должен быть. Далее, в mak4 я заложил тип integer, что уже на смитах мало - пришлось кое-где поставить longint. В особые свойства иных языков я не очень верю - необходимые ассемблерные вставки можно делать уже древнем паскале. Все-таки, основной эффект дает алгоритм, а не язык (интерпретаторы исключаем ), и удачное структурирование данных. Вот здесь всегда есть, над чем поработать.

-- Вс фев 14, 2010 16:51:14 --

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

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

Я проверила уже 10 таких массивов.
Первый массив взяла тот, который первым переваливает за миллион, вот этот:

999153, ..., 1000462

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

[maxal]

svb в сообщении #289039 писал(а):

Но почему же "относительно коротких начальных отрезков натурального ряда"?
Если порядок квадрата будет $n = 100000$, разве этот отрезок будет коротким?

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