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

[ice00]

Цитата:

It is necessary to make the program displays the results of stages

If my program will be compiled adding the

#define DEBUG

string, it is able to show internal state (it shows the % of rows/columns/diagonals that are magic).

In the Windows released programs these are not inserted, otherwise you have too many printed text, but if you want a specific order to be compiled for debug information, let me know

[Nataly-Mak]

Будем сейчас говорить конкретно о квадрате порядка 6. У вас есть два вида программ для построения квадрата порядка 6. Первая - pms6. Она не даёт результата и, кроме того, вообще неизвестно, что в ней происходит, потому что она работает, не останавливаясь и поэтому её приходится прерывать. К сожалению, я не знаю алгоритм этой программы, её внутреннюю логику. Блок-схему своей программы я знаю и вижу на экране монитора, что происходит в программе в каждый данный момент - какой она выполняет этап и что из этого получается. В вашей программе я ничего не знаю и не вижу. Для меня это - чёрный ящик.
Ваша вторая программа - pms_diag6_ Это программа доработки полумагических квадратов. Тут есть завершённость процесса, программа проверяет все введённые полумагические квадраты и останавливается, если магический квадрат будет найден, она его выдаст. Но пока ни один из полученных мной полумагических квадратов не превратился в магический. Видимо, здесь вероятность такого превращения ничтожно мала по сравнению, скажем, с квадратами порядка 10, которые нам удалось построить таким способом.
У меня есть идея одного алгоритма для квадрата порядка 6. Сейчас я пытаюсь реализовать эту идею. Вы тем временем обдумывайте свои идеи.
Хочу заметить, что для построения этого квадрата надо исходить из массива, содержащего больше 36 чисел. Вот, посмотрите, например на наименьший квадрат 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

Здесь разброс чисел очень большой (от 1-го до 41-го смита). Угадать конкретный массив для наименьшего квадрата 6-го порядка очень трудно. Поэтому я генерирую исходные наборы строк из произвольных массивов (в пределах 80-100 первых смитов). Надо построить хотя бы один магический квадрат с маленькой магической константой, научиться составлять такие квадраты, а потом уже добиться минимальности константы.
Бодигрим
Вы занимаетесь этой задачей? Не поделитесь с нами предварительными результатами?

[Mathusic]

Я тут от темы отстал. Найдены ли наименьшие квадраты порядка 6 из смитов обоих типов (вообще посторены $6\times6$)?
compend:
Прогнал старую программку на поиск последовательностей спецвида (в смитах $< \approx 210\cdot 10^6$) (только нового вида) (для одного $b=36$)
Вот файл:
Это он
А вот наименьший набор.

688074,688434,689154,689946,690810,691782,
508405,508657,509161,509809,510745,511753,
54265,54373,54553,54841,55345,56281,
674194,674554,675058,675706,676534,677434,
2578,2722,2974,3442,3946,4702,
292198,292594,293026,293674,294394,295258.

[ice00]

Цитата:

Nataly
For example, the first 5 candidates nimenshie magic squares of order 6 of Smith (the original array always the same - the first 36 Smith, and then indicates which must make a change):
Код:

S = 2460   заменить 706 на 729 S = 2460 to replace the 706 at 729
S = 2467  заменить 663 на 728 S = 2467 to replace the 663 at 728
S = 2472  заменить числа 690 и 706 на числа 729 и 762 S = 2472 to replace the number 690 and 706 at number 729 and 762
S = 2473  заменить числа 666 и 690 на числа 728 и 729 S = 2473 to replace the number 666 and 690 at number 728 and 729
S = 2475  заменить числа 654 и 690 на числа 728 и 729 S = 2475 to replace the number 654 and 690 at number 728 and 729 

I just start to see for the order 6 how many sequences of 6 Smith numbers taken from 36 gives the magic constant. From the value of $C36,6=1947792$ combinations, there are:

S = 2460 -> 1291 sequences 
S = 2467 -> 1948 sequences 
S = 2472 -> 1982 sequences 
S = 2473 -> 986  sequences 
S = 2475 -> 1290  sequences 

This means that only 0,1% of the possible combination can be choosed for making a row/column/diagonal magic.
My idea is to going in choosing 38 sequences inside this that contains all the numbers for making the square magic, or see if it cannot be built analising that kind of sequences.

-- Fri Oct 23, 2009 23:40:18 --

p.s.
If I test this with sequence of prime number, I find that there are about 12980 sequences for a square that my program (pms6) is able to build a square. This means 1% of space of combination.

[Nataly-Mak]

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

А вот наименьший набор.

688074,688434,689154,689946,690810,691782,
508405,508657,509161,509809,510745,511753,
54265,54373,54553,54841,55345,56281,
674194,674554,675058,675706,676534,677434,
2578,2722,2974,3442,3946,4702,
292198,292594,293026,293674,294394,295258.

Не сразу сообразила, как вы составляли последовательности
Вот, например, первая последовательность:

a1, a1+10b, a1+20b, a1+22b, a1+24b, a1+27b

Параметр у вас $b = 36$.
Вы эту последовательность составили?
Начинаю проверять: а1 = 688074, а1 + 10b = 688074 + 360 = 688434. Пока всё правильно. Далее: а1 + 20b = 688074 + 720 = 688794, а у вас этот член последовательности равен 689154. Догадалась, что вы прибавляли 20b не к а1, а к предыдущему члену последовательности: 688434 + 720 = 689154. Поняли ошибку? И дальше вы действовали так же: прибавляли nb к предыдущему члену последовательности.
А старые последовательности у вас были правильные. Нельзя отставать от темы
Наименьшие квадраты 6-го порядка из смитов пока не построены (ни одного вида), бьёмся над этой задачей. Подключайтесь!
ice00
Вы провели хороший анализ статистики. Получается, что наборы из 6 строк, в которых сумма чисел в каждой строке равна магической константе, для смитов генерируются примерно в 10 раз реже, чем для простых чисел. Вот уж упрямые эти смиты!

[Mathusic]

Ага. Nataly, ошибку понял, сейчас переделаю. А возникла она из-за того, что я просто вбил в программу не ту матрицу (нужно было матрицу разностей).
Вот http://www.4shared.com/file/143232426/a ... eq_18.html ($b=18$)
Только числа там не очень хорошие.
Попробую ещё те наборы, которые вы искали (тоже $b=18$)

[Nataly-Mak]

К сожалению, у меня не получается скачать с этого сервера. Пожалуйста, выложите на Народе или приведите здесь набор минимальных последовательностей. Спасибо!
___
Сегодня утром отправила ice00 новый алгоритм для построения квадрата 6-го порядка из смитов. Он любезно согласился реализовать его на С++.
Жду, затаив дыхание

[Mathusic]

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

К сожалению, у меня не получается скачать с этого сервера. Пожалуйста, выложите на Народе или приведите здесь набор минимальных последовательностей. Спасибо!

Вот выложил на Япапка.
Кстати, пробовал искать дополнить вашу последовательность (вы искали $a_3$) - нашлось много, но ни одной для $a_4$! Попробую ещё другие.

-- Сб окт 24, 2009 16:58:08 --

Короче говоря, последовательности регулярно ищутся, но только числа огромны (вплоть до сотен миллионов)

[Nataly-Mak]

Спасибо, Япапка файл "отдала". Но числа в последовательностях действительно большие. Можно, конечно, составить ещё один квадрат. Это один из методов построения нетрадиционных магических квадратов 6-го порядка. К сожалению, он не позволяет построить магический квадрат из смитов с маленькой магической константой.

-- Сб окт 24, 2009 19:11:55 --

Тем временем я продолжила построение магических квадратов из последовательных смитов для порядков 41 – 50 по программам ice00. Все квадраты построены. Вот таблица, содержащая данные для этих квадратов:

*** ORDER: 41 - SEQ(10) FROM: 265 TO: 52785 MAGIC=1064245
            *** ORDER: 42 - SEQ(50) FROM: 1086 TO: 56208 MAGIC=1197607
            *** ORDER: 43 - SEQ(48) FROM: 958 TO: 58932 MAGIC=1281024
            *** ORDER: 44 - SEQ(78) FROM: 1935 TO: 62518 MAGIC=1412359
            *** ORDER: 45 - SEQ(406) FROM: 11388 TO: 75559 MAGIC=1972412
            *** ORDER: 46 - SEQ(5) FROM: 85 TO: 65706 MAGIC=1501638
            *** ORDER: 47 - SEQ(4) FROM: 58 TO: 68395 MAGIC=1600904
            *** ORDER: 48 - SEQ(43) FROM: 861 TO: 73201 MAGIC=1764784
            *** ORDER: 49 - SEQ(199) FROM: 5388 TO: 79953 MAGIC=2113573
            *** ORDER: 50 - SEQ(154) FROM: 4054 TO: 81965 MAGIC=2163213

Все квадраты можно посмотреть здесь.
Итак, предлагается новая последовательность для OEIS – последовательность магических констант наименьших квадратов из последовательных смитов. Но пока в этой последовательности есть пробел, неизвестны константы наименьших квадратов порядков 3 – 9. Последовательность на сегодня имеет такой вид:

4, 0, x, x, x, x, x, x, x, 15681, 20978, 26062, 28301, 35936, 50560,55330, 66877, 88738, 94465, 111840, 128860, 177659, 179929, 230580, 261107, 275220, 300070, 361843, 395338, 457169, 446645, 505470, 560168, 595423, 788455, 726591, 825412, 854154, 908925, 1044248, 1064245, 1197607, 1281024, 1412359, 1972412, 1501638, 1600904, 1764784, 2113573, 2163213

[Nataly-Mak]

И ещё одна последовательность предлагается в OEIS - магические константы наименьших квадратов из произволных смитов. В этой последовательности на сегодня неизвестны 4 члена - для квадратов порядков 6 - 9. Построены наименьшие магические квадраты данной группы до порядка 28 включительно. Последовательность выглядит так:

4, 0, 822, 1195, 1831, x, x, x, x, 12202, 16335, 21333, 27612, 35185, 43968, 54013, 65464, 78281, 92422, 107932, 126404, 147816, 171556, 197041, 224506, 253587, 285314, 320620

Квадраты этой группы составляли: неизвестный автор (порядок 3; впрочем, возможно, в книге М. Гарднера указан автор этого квадрата), tolstopuz (порядок 4), Бодигрим (порядок 5), Nataly-Mak и ice00 (порядок 10), maxal (уточнение константы для квадрата порядка 20).
Квадраты для порядков n>10 построены по программам ice00.
Приглашаю всех принять участие в нахождении четырёх неизвестных членов этой последовательности - магических констант наименьших магических квадратов порядков 6 - 9 из произвольных (различных) смитов. Задача не относится к разряду элементарных. Нужно очень хорошо подумать, чтобы её решить. Есть желающие подумать?

Магические квадраты данной группы для порядков n>9 можно посмотреть здесь.

[maxal]

Если кому-то интересно, то второй по величине магической константы квадрат 3x3 из смитов такой:
634 202 526
346 454 562
382 706 274
у него константа = 1362

[Nataly-Mak]

Этот квадрат уже давно был показан.
См. post226563.html#p226563
Интересно что-нибудь новенькое
Кстати, в качестве лирического отступления... maxal, вы автор 1000-го сообщения в теме.

[ice00]

Squares for consecutive primes are created for order 58..63

*** ORDER: 58   - SEQ(24)        FROM: 89         MAGIC=862750
*** ORDER: 59   - SEQ(61)        FROM: 283        MAGIC=932257
*** ORDER: 60   - SEQ(61)        FROM: 283        MAGIC=983426
*** ORDER: 61   - SEQ(14)        FROM: 43         MAGIC=1009425
*** ORDER: 62   - SEQ(92)        FROM: 479        MAGIC=1109864
*** ORDER: 63   - SEQ(43)        FROM: 191        MAGIC=1137781

Windows program is released here:

http://www.4shared.com/file/143472664/a03ee994/pms58-63.html

[Nataly-Mak]

Цитата из книги М. Гарднера "От мозаик Пенроуза к надёжным шифрам":

Цитата:

В 1987 г. в своей заметке о магических квадратах из простых чисел, опубликованной в «Календаре математических наук, 1988 г.» (Rome Press, 1987), я предложил премию в 100 долларов тому, кто первым построит магический квадрат три на три из последовательных простых чисел.
Свое предложение я повторил в книге «Загадки сфинкса» (Математическая ассоциация Америки, 1987). В начале 1988 г. Гарри Нелсон из Калифорнийского университета, используя составленную им хитроумную программу и компьютер Cray, выиграл премию, получив 22 решения
задачи, одно из которых с наименьшей постоянной представлено на рис. 147. Программа Нелсона не позволяет доказать, что это решение имеет наименьшую из возможных магических постоянных, хотя с высокой вероятностью можно утверждать, что это именно так.

На рис. 147 представлен следующий магический квадрат:

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-го порядка из последовательных простых чисел. Вы его составляли?

[ice00]

Цитата:

ice00, я не видела на вашем сайте ничего о квадрате 3-го порядка из последовательных простых чисел. Вы его составляли?

I did not search for this very low order. But order 3 with only 9 numbers is very easy to search for those squares (just brute force).
Maybe I can write a program that can see if effectively the solution we have for order 3 of consecutive primes is true