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

[Бодигрим]

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

БодигримВы занимаетесь этой задачей? Не поделитесь с нами предварительными результатами? :)

Какой именно "этой"?

[ice00]

I just code a little program for test the order 3 of consecutive primes (I just count the number of sequences and if less that 8 then a square cannot be built).

I can agree that until prime 179424527 no square of consecutive primes cannot be built, however for reaching the primes 1480028129 it will need lot of times for generating the primes and then check for square. I will run the program the next weekend so it can complete the task.

[Nataly-Mak]

ice00 в сообщении #255013 писал(а):

I just code a little program for test the order 3 of consecutive primes (I just count the number of sequences and if less that 8 then a square cannot be built).
I can agree that until prime 179424527 no square of consecutive primes cannot be built, however for reaching the primes 1480028129 it will need lot of times for generating the primes and then check for square. I will run the program the next weekend so it can complete the task.

Да, в этой задаче самый сложный момент - очень большие числа. У меня есть программа построения квадрата 3-го порядка, которая эффективно работает даже на Бейсике. Эта программа очень быстро даёт ответ: построен квадрат из данного массива или нет. Я проверила по этой программе несколько кандидатов в магические квадраты из последовательных смитов. Решения не найдено. Здесь сообщали tolstopuz и maxal, что они проверили смиты до 10^_{10}. Результат не получен. Поэтому хорошо, если вы будете решать эту задачу не только для простых чисел, но и для смитов.
А потом и задача для квадрата порядка 4 из последовательных смитов. Как я уже сообщала, по своей программе проверила 800 первых кандидатов в магический квадрат 4-го порядка из последовательных смитов. Среди этих кандидатов решения не нашлось. А дальше не могу проверить, так как у меня закончился массив смитов. Для порядка 4 очень хорошо проверять, программа работает быстро и даёт однозначный ответ. Думаю, что если у кого-то есть возможность сгенерировать очень большие смиты, он может решить эту задачу быстро.
Скажите, а как у вас дела с реализацией моего нового алгоритма для построения магического квадрата порядка 6? Я жду с нетерпением и очень волнуюсь: будет алгоритм работать или нет

Бодигрим, я имела в виду задачу построения наименьшего магического квадрата 6-го порядка из произвольных смитов (а заодно и из последовательных смитов). Выше приведена последовательность магических констант наименьших квадратов из произвольных смитов. В этой последовательности отсталось неизвестно всего 4 члена - магические константы наименьших квадратов порядков 6 - 9. Повторяю это специально для вас, так как вы, похоже, тоже отстали от темы Вы построили наименьший квадрат 5-го порядка из смитов, мы с ice00 построили подобный квадрат 10-го порядка. Для порядков n>10 с построением таких квадратов нет проблем, все они прекрасно строятся по программам ice00, и уже построены до порядка 28 включительно.

[ice00]

Цитата:

Скажите, а как у вас дела с реализацией моего нового алгоритма для построения магического квадрата порядка 6? Я жду с нетерпением и очень волнуюсь: будет алгоритм работать или нет

I'm in analysis phase: the data structure to use to achieve the task.
As I'm a programmer, I did not like to code in spaghetti mode, so before coding the program, I structured it the best I can for having the result.
I'm, however, in the phase to evaluate if it is the case to switch from c++ to Java for having more library ready to use and reduce the code to write. Maybe the Java performing could be not so distance from c++.
At the moment I have not switch to Java as the preliminary data structure to use is not so complex (but I look only for first step of algorithm)

[Бодигрим]

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

Повторяю это специально для вас, так как вы, похоже, тоже отстали от темы :)

Да нет, я вполне себе в курсе.

Программа для детерминированного поиска квадратов 6-го порядка у меня готова, но выполняется она необозримо долго. Есть предложения, где бы ее запустить поработать?

[Nataly-Mak]

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

Программа для детерминированного поиска квадратов 6-го порядка у меня готова, но выполняется она необозримо долго. Есть предложения, где бы ее запустить поработать?

К сожалению, в этом я не могу вам ничем помочь. Может, кто-нибудь из других участников...
Я предложила ice00 для реализации алгоритм построения квадрата 6-го порядка из заданного массива смитов (либо любых других чисел), состоящего из 36 чисел. Мне думается, что программа, составленная на основе этого алгоритма, будет выполняться довольно быстро (в разумных пределах времени; на языке с хорошим быстродействием что-то в пределах одного часа). Но это предварительная оценка с позиций работы этой программы на Бейсике. На Бейсике я могу выполнять её только поэтапно, а выполнить во всём объёме не могу. Алгоритм содержит три этапа.
Надо подождать оценки ice00.

К вопросу построения наименьшего квадрата 3-го порядка из последовательных смитов. Для этого вполне сгодилась бы девятка смитов-близнецов. Но, насколько мне известно, не найдена даже восьмёрка смитов-близнецов.
Наименьшая семёрка смитов-близнецов начинается с 164736913905 (данные с сайта http://www.shyamsundergupta.com/smith.htm ). Ещё одна хорошая задача!

Ещё хорошо посмотрела на структуру любого магического квадрата 3х3. Удивительная гармония в этих квадратах! Если записать образующие его числа в виде арифметических прогрессий, это будет выглядеть так:

a, a+b, a+2b
a+c, a+c+b, a+c+2b
a+2c, a+2c+b, a+2c+2b

То есть эти 9 чисел образуют арифметические прогрессии и "вдоль", и "поперёк" (и в строках, и в столбцах).
Вот, например, наименьший магический квадрат 3х3 из простых чисел:

17 113 47
89 59 29
71 5 101

Числа, составляющие этот квадрат, складываются в такие арифметические прогрессии:

5, 17, 29
47, 59, 71
89, 101, 113

Здесь a = 5, b = 12, c = 42.
Красиво!

[dezdlisa]

На счет программки для шестого квадрата это очень хорошо. Я недавно с помощью pms5 решил построить все традиционные квадраты, но остановился на 50000, так как по расчетам, работать программе оставалось около года, а текстовый документ к концу работы весил бы 22Гб. Поэтому не плохо былоб делать для таких программ сохранение с места прерывания программы. А так же хорошо, если бы программа порционировала текстовик, допустим по 10 Мб, и еще лучше чтоб была команда не только находить определенное количество квадратов, но и нахождение всех возможных. ice00, конечно же это только мечты, но если в будущем программа примет такой вид, то ей цены небудет.
Так что, на Счет шестого квадрата, нужно ждать быстродействующих программ, а не гонять по полгода программу в надежде, что не заглючит комп или напругу вдруг не отключат.

[Nataly-Mak]

dezdlisa в сообщении #255410 писал(а):

Я недавно с помощью pms5 решил построить все традиционные квадраты, но остановился на 50000, так как по расчетам, работать программе оставалось около года, а текстовый документ к концу работы весил бы 22Гб.

Вы решили построить по программе ice00 все традиционные квадраты 5-го порядка, которых больше 25 миллионов?
Зачем они вам? Они ведь уже давно построены американцами. И они уложились всего в 100 часов машинного времени (а в середине 70-х годов прошлого века ЭВМ, наверное, всё-таки были не такие быстродействующие, как современные компьютеры).
По поводу квадрата 6-го порядка - что именно хорошо? Пока нет ничего хорошего Может быть, вы подкинете парочку идей, как сделать быстродействующую программу построения такого квадрата?
Да, кстати, в книге Ю. В. Чебракова есть алгебраическая формула магического квадрата 5-го порядка. Думаю, что если составить программу построения всех классических квадратов данного порядка с использованием этой формулы, можно справиться с их построением менее чем за 100 часов (если ещё язык будет с хорошим быстродействием). Вот только записать более 25 миллионов квадратов, наверное, проблематично. Ну, если вы запасётесь центнером бумаги и сразу будете выводить результаты на принтер, то можно уложиться.
Для сравнения: я строила все 880 традиционных магических квадратов 4-го порядка на старой ЭВМ примерно в 1993 г. Это была "Электроника 100/25". Программа работала очень долго (тем более что и алгоритм у меня был не наилучший - лобовой перебор всех вариантов). К тому же программа работала только в обеденный перерыв или после работы (в ней было и сохранение с прерванного места). Два года назад проверила выполнение той же самой программы на компьютере, это заняло несколько минут.

[ice00]

With $pms5$ you cannot generate all the traditional squares as they are generated at random and so if you generate $N$ squares, maybe you can find two equal square in it.

[Nataly-Mak]

Продолжаю экспериментировать с квадратами 6-го порядка из смитов. Провела такой эксперимент: взяла массив смитов, из которого составлен единственный известный мне магический квадрат 6-го порядка. Вот этот массив:

22, 94, 346, 382, 562, 778, 1822, 1966, 2326, 2362, 2578, 2902, 20362, 20506, 20542, 20974, 21226, 21262, 681817, 682177, 682393, 682609, 682681, 682897, 1446106, 1446142, 1446178, 1446538, 1446574, 1446934, 3003898, 3004186, 3004402, 3004618, 3004654, 3004762

Далее сгенерировала по своей программе 500 полумагических квадратов и применила программу ice00 - pms_diag6_, которая превращает полумагические квадраты в магические. Получила море магических квадратов! Правда, всё равно далеко не все полумагические превратились в магические. Получила три варианта магических квадратов: тот, который ранее сама построила, второй получен из него основным преобразованием (отражение относительно горизонтальной оси симметрии), третий получен из ранее построенного М-преобразованием. Покажу третий вариант квадрата:

3004618 22      1446178 2902    21226   681817  
94      682681  21262   1446142 1822    3004762 
1446106 20362   1966    3004654 682897  778     
682609  3004186 562     20542   1446538 2326    
2362    1446934 3004402 682177  382     20506   
20974   2578    682393  346     3003898 1446574

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

[Mathusic]

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

[maxal]

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,", ");); )

[dezdlisa]

Да, ice00, я заметил что квадраты строятся из случайных чисел, поэтому вполне возможно, что могут строится одинаковые. К тому же если я вводил большее число, чем реальное число квадратов, то программка надолго заумывалась над построением первого квадрата и я ее прерывал. Так что есть надежда, что из всех этих квадратов одинаковых не будет, но я проверю обязательно.
Nataly, на сколько мне известно, квадратов не 25, а 275 млн.
Зачем мне квадраты? Просто интересно, и хочется чтоб в конце концов программы работали в пределах хотябы нескольких дней, но не годами. И если вскоре будет вполне возможно построить пятый квадрат за короткий срок, то можно будет приступать к нахождению всех шестых квадратов и узнать сколько их всего, а там глядишь может и формула найдется по нахождению количества магических квадратов.

[Nataly-Mak]

dezdlisa в сообщении #255827 писал(а):

Nataly, на сколько мне известно, квадратов не 25, а 275 млн.
Зачем мне квадраты? Просто интересно, и хочется чтоб в конце концов программы работали в пределах хотябы нескольких дней, но не годами.

Ну, во-первых я написала "больше 25 миллионов", а не точно 25 миллионов. Ведь 275 миллионов больше 25 миллионов?
Во-вторых, написала по памяти, помню, что это количество несколько миллионов. Цитата из книги Гарднера была уже приведена в этой ветке, точное количество, указанное в этой книге: 275305224.
Кстати, далее в книге Гарднера написано: "Шрёппель предпочитает делить это число на 4 и считает, что существует 68826306 магических квадратов порядка 5". Здесь речь идёт о М-преобразованиях. Каждый квадрат 5-го порядка порождает группу из 4 квадратов (считая его самого), получаемых друг из друга М-преобразованиями. Если считать количество всех классических магических квадратов 5-го порядка с точностью до основных преобразований и М-преобразований, то их будет 68826306, как считал Шрёппель.

Далее, повторяю, что даже в 1975 году американцы потратили на построение всех классических квадратов 5-го порядка всего 100 часов машинного времени. Вы же всё про года работы программы говорите. Какая программа работает годами? Такую программу здравомыслящий человек просто не будет запускать. Я, например, на своём черепашьем Бейсике не выполняю программы, которые работают более часа. Считаю, что это плохая программа, ищу оптимизацию или принципиально новый алгоритм.
Если вам хочется получить все классические квадраты 5-го порядка, я вам уже говорила, как это сделать. Возьмите алгебраическую формулу квадрата 5-го порядка, составьте на основе этой формулы программу, введите в программу массив первых 25 натуральных чисел и - вперёд! Дня за три-четыре вы получите распечатку всех квадратов. Только сначала бумагой запаситесь
Общую формулу количества классических магических квадратов порядка $n$ вряд ли удастся получить. Оценка этих количеств для нескольких первых порядков приведена на одном сайте (ссылка приводилась в этой ветке).

[Бодигрим]

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

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

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