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

[Nataly-Mak]

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

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

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

Хм, квадрат из смитов 5-го порядка у меня искался несколько недель.

Ну, тогда квадрат 6-го порядка из смитов у вас будет строиться несколько месяцев
Берите пример с программ ice00! Его программы строят квадрат в худшем случае за несколько минут, в лучшем - в долю секунды. Если программа так не работает - это плохая программа. Таково моё мнение - профессионального программиста.
Когда я спросила ice00, сколько нужно ждать, чтобы программа построила квадрат, он ответил, что составлял программу так, чтобы она находила квадрат очень быстро. Либо она находит квадрат практически мгновенно, либо не находит вообще. Вот, к примеру, наименьший квадрат 10-го порядка из смитов мне не удалось найти по его первоначальному варианту программы. Тогда мы сделали хитрый ход: я по своей программе сгенерировала 202 полумагических квадрата, а ice00 сделал программку превращения уже готовых полумагических квадратов в магические. Это сработало, квадрат был найден очень быстро (за минуты). Но этот приём уже не работает для квадратов порядков 6 - 9. И надо искать другие методы.

[Бодигрим]

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

Когда я спросила ice00, сколько нужно ждать, чтобы программа построила квадрат, он ответил, что составлял программу так, чтобы она находила квадрат очень быстро. Либо она находит квадрат практически мгновенно, либо не находит вообще.

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

[ice00]

Цитата:

Насколько я понял, работа его программы имеет вероятностный характер

Yes, the program starts with random square and apply some transformation that could bring it to the magic state.
With some statistic analysis made recently, the program can build a square if the number of sequences that make the magic constant is at least at 1% of the total combination for the order being used.

[Mathusic]

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

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

Уважаемые участники. Кто-нибудь мог бы поделиться программой, генерирующей "неограниченно большие" числа смита, а то своих 70Mb маловато..?

На PARI/GP:

? sd(n) = local(v); v=eval(Vec(Str(n))); sum(j=1,#v,v[j])
? issmith(n) = local(f); if(ispseudoprime(n),return(0)); f=factor(n); sum(j=1,matsize(f)[1],f[j,2]*sd(f[j,1]))==sd(n)
? for(n=2,10^10, if(issmith(n),print1(n,", ");); )

Спасибо, большое! Буду осваивать $\operatorname{PARI/GP}$ (уже установил с офсайта ). Пока мало что понятно. Прочитал 2 Ваши лекции. Как я понял, чтобы выполнить программу, нужно просто ввести её в командную строку и нажать $Enter$? И еще. Насколько я понимаю, программа будет печатать смиты в командной строке. А как её нужно модифицировать, чтобы числа печатались по возрастанию в txt-файл?
Спасибо.

[maxal]

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

Как я понял, чтобы выполнить программу, нужно просто ввести её в командную строку и нажать $Enter$?

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

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

А как её нужно модифицировать, чтобы числа печатались по возрастанию в txt-файл?

Перед выполнением третьей строки наберите:

? \l result.txt

тогда все что печатается на экране будет дублироваться и в файл result.txt (в той же директории, откуда запущен gp). Можно указать файл с полным путем, если хотите его видеть в другом месте.
Выключить вывод в файл можно командой:

? \l

[Nataly-Mak]

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

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

Когда я спросила ice00, сколько нужно ждать, чтобы программа построила квадрат, он ответил, что составлял программу так, чтобы она находила квадрат очень быстро. Либо она находит квадрат практически мгновенно, либо не находит вообще.

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

Но ведь с наименьшим квадратом 10-го порядка из смитов у нас всё получилось! И минимальная константа оказалась равна теоретической. И с наименьшими квадратами из смитов для порядков больше 10 ещё проще дело идёт (построены уже до порядка 28 включительно, и строятся по программам ice00 за несколько секунд: а из последовательных смитов до порядка 50 включительно построены).

[dezdlisa]

Цитата:

Шрёппель предпочитает делить это число на 4 и считает, что существует 68826306

Да, я это знаю. На 4 мы будем делить только количество четвертых и пятых квадратов, так как М-преобразований у этих квадратов по четыре штучки. У шестого и седьмого квадратов М-преобразований уже по 6 штук.

Цитата:

Какая программа работает годами?

Если бы программа pms5 расчитывала не случайные квадраты, а все существующие, то ей работать до победного конца около 4-х лет. Я примерно посчитал, взяв все 275 млн. квадратов. Программа в сутки рассчитывает около 200000 штук, получаем, что 1 млн. квадратов расчитаем за 5 суток, следовательно 275*5=1375 дней нам до завершения программы.

Цитата:

Возьмите алгебраическую формулу квадрата 5-го порядка, составьте на основе этой формулы программу, введите в программу массив первых 25 натуральных чисел и - вперёд!

Я бы с удовольствием, но я не программист.

[Nataly-Mak]

Сейчас "вгрызаюсь" в свой новый алгоритм построения квадрата порядка 6 из заданного массива, состоящего ровно из 36 чисел. Реализация этого алгоритма давольно сложная. Поэтапно я сделала всё. И отдельно все программы работают и выдают ожидаемые результаты. Но вот объединить это всё в одну программу и выполнить на Бейсике нереально. Сегодня уже очень притомилась, завтра, возможно, расскажу подробно этот алгоритм.

[Mathusic]

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

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

Как я понял, чтобы выполнить программу, нужно просто ввести её в командную строку и нажать $Enter$?

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

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

А как её нужно модифицировать, чтобы числа печатались по возрастанию в txt-файл?

Перед выполнением третьей строки наберите:

? \l result.txt

тогда все что печатается на экране будет дублироваться и в файл result.txt (в той же директории, откуда запущен gp). Можно указать файл с полным путем, если хотите его видеть в другом месте.
Выключить вывод в файл можно командой:

? \l

Спасибо. Только не получается запись в файл. Все делаю по указаниям. Запускаю $GP$ из отдельной папки (ярлык). Там же сначала не создавал файл result.txt (думал, он может автоматически создаваться как в C), потом создал. Всё равно: запись в файл не идёт. Попробую ещё...

UPD:
Вввёл полный путь файла - печать пошла. Считаем, что с этим проблема решена.
Обычно печатаю числа не через запятую, а с новой строки, поэтому попробовал изменить "Ваш" print1 на свой print1(n,"\n"); Оказалось, что в командной строке это работает, то есть числа идут с новой строки, а в файле - нет. Странно.
И еще. Насколько я понимаю, то запись чисел в командную строку замедляет создание файла (так?) (он-то мне и нужен). Нельзя ли как-нибудь это отключить?
Upd:
Да, печать в командной строке замедляет процесс...

[EtCetera]

Mathusic
Наберите программку (только без строк с выводом в файл, типа "\l result.txt") в текстовый файлик, условно назовем его SmithNumbers.txt. Также создайте bat-файл (пусть он будет называться SmithNumbers.bat) со следующим содержимым:

"c:/Program Files/PARI/gp.exe" < SmithNumbers.txt > result.txt

Вместо "c:/Program Files/..." введите правильный путь к программе. Если файл SmithNumbers.txt лежит в другом каталоге, нежели SmithNumbers.bat, то также введите и полный путь к нему (если есть пробелы, обязательно заключайте все в кавычки). Чтобы процесс пошел, отправьте на выполнение файл SmithNumbers.bat. Результирующий файл result.txt будет создан в том каталоге, в котором находится SmithNumbers.bat.
Для удобства (чтобы не заморачиваться с путями) имеет смысл все это проделать в каталоге программы (в котором лежит exe-файл gp).
P.S. Это универсальный способ для 100% адекватно написанных программ, работающих с командной строкой. В PARI/GP наверняка должна быть специфическая функция подавления печати на экране. Подождем, что скажет maxal...

[Mathusic]

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

1480028201 1480028129 1480028183 
1480028153 1480028171 1480028189 
1480028159 1480028213 1480028141

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

a-c, a-b+c, a+b, a+b+c, a, a-b-c, a-b, a+b-c, a+c

Иначе говоря, из этих 9 чисел можно образовать три арифметические прогрессии с одинаковой разностью; кроме того, наименьшие члены этих прогрессий тоже образуют арифметическую прогрессию (с другой разностью).
Так, для приведённого выше магического квадрата a = 1480028171, b = 12, c = 30.
Может быть, эта алгебраическая формула поможет кому-нибудь в поисках наименьшего магического квадрата 3-го порядка из последовательных смитов. В этом случае число $a$ должно быть смитом, числа $b$ и $c$ - произвольные натуральные числа, а все члены приведённой выше последовательности тоже должны являться смитами, причём последовательными.
ice00, я не видела на вашем сайте ничего о квадрате 3-го порядка из последовательных простых чисел. Вы его составляли?

Действительно, это минимальный квадрат. Проверил детерминированным алгоритмом все простые в пределах двух миллиардов. Получил $2$ (с точностью до массива) квадрата. Вот они:

1480028141, 1480028189, 1480028183
1480028213, 1480028171, 1480028129
1480028159, 1480028153, 1480028201

1850590069, 1850590117, 1850590111
1850590141, 1850590099, 1850590057
1850590087, 1850590081, 1850590129

[maxal]

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

Обычно печатаю числа не через запятую, а с новой строки, поэтому попробовал изменить "Ваш" print1 на свой print1(n,"\n"); Оказалось, что в командной строке это работает, то есть числа идут с новой строки, а в файле - нет. Странно.

Печать с переводом строки делается так: print(n);

EtCetera в сообщении #256043 писал(а):

В PARI/GP наверняка должна быть специфическая функция подавления печати на экране. Подождем, что скажет maxal...

Да, есть: \e, но, честно говоря, я ей никогда не пользовался.
Еще вариант - вместо print использовать команду write: write("result.txt",n);

[Mathusic]

EtCetera в сообщении #256043 писал(а):

Mathusic
Наберите программку (только без строк с выводом в файл, типа "\l result.txt") в текстовый файлик, условно назовем его SmithNumbers.txt. Также создайте bat-файл (пусть он будет называться SmithNumbers.bat) со следующим содержимым:

"c:/Program Files/PARI/gp.exe" < SmithNumbers.txt > result.txt

Вместо "c:/Program Files/..." введите правильный путь к программе. Если файл SmithNumbers.txt лежит в другом каталоге, нежели SmithNumbers.bat, то также введите и полный путь к нему (если есть пробелы, обязательно заключайте все в кавычки). Чтобы процесс пошел, отправьте на выполнение файл SmithNumbers.bat. Результирующий файл result.txt будет создан в том каталоге, в котором находится SmithNumbers.bat.
Для удобства (чтобы не заморачиваться с путями) имеет смысл все это проделать в каталоге программы (в котором лежит exe-файл gp).
P.S. Это универсальный способ для 100% адекватно написанных программ, работающих с командной строкой. В PARI/GP наверняка должна быть специфическая функция подавления печати на экране. Подождем, что скажет maxal...

EtCetera, спасибо большое! Всё получилось. Только скорость по-моему не увеличилась. Засёк. Генерация идёт со скоростью примерно Mb/4 минуты. Это очень медленно. Для проверки всех натуральных в $10 \cdot 10^9$ понадобятся десятки дней. Посмотрел на загрузку системы. ЦП используется практически на максимум. А вот памяти выделяется примерно 2,5 Mb. Можно ли как-то убыстрить выполнение, отдав "почти все ресурсы на эту задачу"?

-- Чт окт 29, 2009 00:57:47 --

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

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

Обычно печатаю числа не через запятую, а с новой строки, поэтому попробовал изменить "Ваш" print1 на свой print1(n,"\n"); Оказалось, что в командной строке это работает, то есть числа идут с новой строки, а в файле - нет. Странно.

Печать с переводом строки делается так: print(n);

EtCetera в сообщении #256043 писал(а):

В PARI/GP наверняка должна быть специфическая функция подавления печати на экране. Подождем, что скажет maxal...

Да, есть: \e, но, честно говоря, я ей никогда не пользовался.
Еще вариант - вместо print использовать команду write: write("result.txt",n);

Команду print() тоже пробовал (пробил в help), но это не помогло. В комстроке все отображается как надо, а вот в файле - нет: числа идут без разделения вообще.
По поводу \e. Когда нужно вводить? Перед выполнением 3-ей строки?

[maxal]

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

В книге также приведена алгебраическая формула любого магического квадрата 3-го порядка. Девять чисел могут составить магический квадрат 3-го порядка тогда и только тогда, когда они являются членами следующей последовательности:

a-c, a-b+c, a+b, a+b+c, a, a-b-c, a-b, a+b-c, a+c

Если под последовательностями подразмевать возрастающие последовательности, то тут их может быть две (в предположении, что $a$ - центральный элемент и $0<b<c$):

a-b-c, a-c, a-c+b, a-b, a, a+b, a+c-b, a+c, a+b+c
a-b-c, a-c, a-b, a-c+b, a, a+c-b, a+b, a+c, a+b+c

Какая из них реально имеет место, зависит от соотношения величин $c-b$ и $b$ (или же $c$ и $2b$).

-- Wed Oct 28, 2009 16:00:33 --

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

Действительно, это минимальный квадрат. Проверил детерминированным алгоритмом все простые в пределах двух миллиардов. Получил $2$ (с точностью до массива) квадрата.

Всё так. Дальнейшие квадраты (а точнее их центральные элементы) приведены в A166113

-- Wed Oct 28, 2009 16:14:34 --

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

Для проверки всех натуральных в $10 \cdot 10^9$ понадобятся десятки дней. Посмотрел на загрузку системы. ЦП используется практически на максимум. А вот памяти выделяется примерно 2,5 Mb. Можно ли как-то убыстрить выполнение, отдав "почти все ресурсы на эту задачу"?

Тут все от быстродействия зависит. Комп по сути занимается факторизацией чисел снова и снова, и память ему для этого особо не нужна. В зависимости от быстродействия до $10^{10}$ можно добраться за несколько дней. Например, в поиске квадратов $3\times 3$ из последовательных смитов я уже к $3\cdot 10^{10}$ подбираюсь.
Если хотите ускорить генерацию смитов, то нужно использовать что-то типа решета Эратосфена, где при прогоне каждого простого $p$ и его степени к соответствующим элементам массива нужно прибавлять сумму цифр $p$. Тогда сумма цифр простых делителей будет накапливаться в элементах массива без всякой факторизации. Но реализация этого алгоритма для достижения предела $10^{10}$ будет уже не три строчки и сильно зависеть от объёма доступной памяти.

-- Wed Oct 28, 2009 16:27:26 --

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

Команду print() тоже пробовал (пробил в help), но это не помогло. В комстроке все отображается как надо, а вот в файле - нет: числа идут без разделения вообще.
По поводу \e. Когда нужно вводить? Перед выполнением 3-ей строки?

Проблема с print вероятно связана с разными способами перевода строки в юниксах и винде. Попробуйте печатать так: print(n,Strchr(13)); или print1(n,Strchr(13),Strchr(10));
Насчет \e - поэксперементируйте.

[Mathusic]

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

print(n,Strchr(13)); или print1(n,Strchr(13),Strchr(10));
Насчет \e - поэксперементируйте.

Первая вещь сработала, спасибо.
Вы говорите, приблизились к 30 млрд. в поиске, всё так безнадёжно для квадрата $3\times3$? Вы отметку в 25 млрд. преодолели?
Nataly, не могли бы Вы привести общие алгебраические формулы для квадратов порядков $4$ и $5$?