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

[SomePupil]

(Оффтоп)

Оскар Уайльд писал(а):

Можно простить человеку, который делает нечто полезное, если только он этим не восторгается. Тому же, кто создает бесполезное, единственным оправданием служит лишь страстная любовь к своему творению.

Всякое искусство абсолютно бесполезно.

Модераторы, инженера - в топку!

[Anton_Peplov]

dani1978 в сообщении #1111262 писал(а):

есть ли у магических квадратов какое-либо практическое/теоретическое/методологическое применение?

Устойчивое к ошибкам кодирование. Если какое-то число в магическом квадрате было нечаянно заменено на другое, это легко обнаружить и восстановить исходное число.

[kotenok gav]

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

Другая интересная задача - найти нетрадиционный магический квадрат 3x3, состоящий из различных точных квадратов.

А если нашёл или доказал что нет таких, то куда это отправлять?

[maxal]

kotenok gav
См. http://www.multimagie.com/English/Enigmas.htm

[maxal]

Вести с полей: посчитали количество полумагических квадратов 6x6 и ассоциативных квадратов 7x7.
На вскидку похоже, что использовались методы сродни тем, что продвигали в своё время alexBlack и Zealint (см., например, эту тему или на хабре).

[Dmitriy40]

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

Я не измеряю близость к решению, а просто проверяю является ли набор оным или нет. Вот для примера последний набор, прошедший предпроверку (но проваливший проверку):

531511414105079: 0 18 30 42 48 90 102 132 144 150 182 200 212 272 282 290 302 314 332 338 422 440 464 470 524

Ради интереса попробовал поискать такие квадраты с данной точки, в основном было интересно можно ли ускорить перебор оптимизацией порядка проверок последовательности на квадрат (при относительно медленном генераторе простых). В итоге добился примерно двухкратного ускорения (в одном потоке, многопоточная версия не писалась), за три месяца счёта продвинулся от указанной точки до 4e15, квадрата не нашёл, лучшее приближение выдало лишь 21 правильное число из 25:

2723400964811209: [0, 12, 28, 60, 72, 88, 90, 100, 112, 118, 172, 198, 202, 204, 210, 270, 288, 300, 310, 330, 342, 358, 400, 468, 558], s=1058
    0   12   28  112  270
   60   72   88  172  330
   90   -1  118  202   -1
  198  210   -1  310  468
  288  300   -1  400  558

И до двух десятков приближений с 20-ю заполненными местами.
Если за приближение считать и размещения, в принципе не дающие полный квадрат, то таких вероятно можно получить и c 22-ю заполненными местами, но это не интересно.

Дополнительно до 1e16 проверил квадраты с началом 0, 2, 6, 8 (все эти числа попадают в левый верхний угол 2х2 квадрата), таковых нет даже близко.

[Dmitriy40]

Решил проверить где собственно надо ожидать пандиагональных квадратов 5 порядка с некоторыми паттернами, благо Yadryara разобрался как к этому делу применить первую гипотезу Харди-Литлвуда. И вот что получил для количества ожидаемых квадратов:

Используется синтаксис Text

v=[0, 2, 6, 20, 30, 32, 36, 42, 50, 60, 62, 66, 72, 80, 84, 86, 90, 102, 104, 114, 116, 120, 126, 134, 156]
10^35: 0.007092237879253027271031150819
10^36: 0.03501715032542102722797543779
10^37: 0.1762950319096647244641893687
10^38: 0.9040711466245417097963702113
10^39: 4.717877273605430480110822565
10^40: 25.03129073292239930569964976
v=[0, 22, 30, 36, 40, 42, 52, 54, 66, 70, 72, 76, 84, 90, 94, 96, 106, 114, 120, 124, 126, 136, 150, 154, 156]
10^35: 0.007371380710763159840078912631
10^36: 0.03632498968755170946786675763
10^37: 0.1825555029777636099924092166
10^38: 0.9346531209686807868116097102
10^39: 4.870161204708877062765634591
10^40: 25.80350005532992337698220372
v=[0, 10, 12, 22, 24, 36, 40, 52, 54, 60, 66, 70, 84, 96, 100, 102, 106, 112, 114, 120, 126, 136, 142, 150, 156]
10^33: 0.008321487739334267290597734825
10^34: 0.03926712459058754477596387582
10^35: 0.1894284219280883345700495865
10^36: 0.9330283564613868380504911085
10^37: 4.686747021653138882029885638
10^38: 23.98339114399110592111333046
v=[0, 6, 14, 20, 30, 36, 42, 44, 50, 54, 56, 60, 72, 86, 90, 96, 102, 104, 116, 120, 132, 134, 144, 146, 156]
10^33: 0.007843763815997610635933111196
10^34: 0.03704676356917710383236719709
10^35: 0.1788824677193354309785577814
10^36: 0.8819005019685335777922631903
10^37: 4.434009168485627271776644600
10^38: 22.71079593830150096780279134
v=[0, 14, 18, 20, 30, 32, 38, 44, 48, 60, 62, 74, 78, 80, 90, 92, 98, 104, 108, 114, 122, 128, 134, 144, 158]
10^33: 0.002543913449316953502078679182
10^34: 0.01198458197638103337542045989
10^35: 0.05773138496350626614222892346
10^36: 0.2839909213684983897045188474
10^37: 1.424900393720820774044602324
10^38: 7.284166303918651122439406851
10^39: 37.90154103459330557024382373
v=[0, 14, 24, 30, 36, 44, 50, 54, 60, 66, 68, 78, 80, 84, 96, 98, 110, 114, 120, 126, 128, 138, 140, 144, 158]
10^33: 0.002223737249861272214486219677
10^34: 0.01054311410651694756763164990
10^35: 0.05108433310443247708183355639
10^36: 0.2526403964432575478135327920
10^37: 1.273860997398290576556743597
10^38: 6.541743268907158259518528381
10^39: 34.18227643366454152162772402

Очевидно искать эти квадраты до 1e35-1e37 бессмысленно.

Дополнительно проверил все паттерны диаметром до 210, на интервале 97#=2.3e36 ни у одного не стоит ожидать более 12 штук. Т.е. до скажем 1e35 пандиагональных квадратов 5 порядка диаметром до 210 вероятно просто нет.
Весь 97# мне проверять каждый паттерн в одном потоке несколько миллиардов лет, что разумеется абсолютно нереально. Т.е. искать эти квадраты поиском по паттерну бессмысленно. Насчёт больших диаметров у меня данных нет (просчитать первую гипотезу Харди-Литлвуда не получается), но как-то слабо верится что встретится паттерн с на десяток порядков лучшей вероятностью (для проверенных разница вероятностей менее трёх порядков).

[Dmitriy40]

Yadryara
Наткнулся на странную закономерность: среднее время нахождения первого грязного кортежа почти не зависит от паттерна, только от длины. Под временем понимаю отношение количества вариантов в некоем интервале к количеству грязных кортежей в нём же по гипотезе HL1. Вот например данные по аж 42654 паттернам пандиагонального квадрата 5 порядка из последовательных простых чисел диаметром до 250 (количество грязных кортежей, количество вариантов, отношение второго к первому):

v=[  0,  2,  6, 20, 30, 32, 36, 42, 50, 60, 62, 66, 72, 80, 84, 86, 90,102,104,114,116,120,126,134,156]; \\97#:   0.090254, d=  1.386e24, k=15.353e24
v=[  0, 10, 12, 22, 24, 36, 40, 52, 54, 60, 66, 70, 84, 96,100,102,106,112,114,120,126,136,142,150,156]; \\97#:   2.232089, d= 34.268e24, k=15.353e24
v=[  0, 42, 60, 66, 70, 90,100,102,108,112,120,126,130,132,142,150,160,168,172,186,190,192,202,210,220]; \\97#:   0.080993, d=  1.227e24, k=15.153e24
v=[  0,  4, 18, 22, 24, 30, 34, 42, 48, 52, 60, 64, 84, 90, 94,168,172,192,198,202,210,214,234,240,244]; \\97#:   3.456506, d= 48.087e24, k=13.912e24
v=[  0, 18, 46, 48, 60, 64, 90, 94,106,130,136,148,150,156,168,174,178,190,198,204,210,216,220,240,246]; \\97#:  48.754172, d=738.781e24, k=15.153e24

Количество грязных кортежей отличается почти на три порядка, а средний объём перебора (т.е. фактически среднее время) до нахождения первого из них на жалкие 10%.

С увеличением диаметра время улучшается, но всего лишь до полутора раз:

v=[  0, 14, 24, 36, 38, 60,114,128,150,540,554,576,686,710,800,954,968,990,1016,1040,1130,1226,1556,1640,1970]; \\97#:  73.430544, d=742.102e24, k=10.106e24
v=[  0,  6, 30, 36,114,126,144,156,166,172,280,292,546,552,660,672,790,796,904,916,1386,1416,1552,1932,2176]; \\97#: 172.424510, d=1931.009e24, k=11.199e24

Может у Вас есть по этому поводу мысли?

Понятно что чистых кортежей меньше чем грязных и значит вполне возможно что для нахождения первого указанного квадрата (с любым диаметром) надо перебрать не меньше порядка 1e25 вариантов ... Т.е. с имеющейся техникой (включая и вариант боинка) совершенно бесперспективно.

[Yadryara]

Dmitriy40 в сообщении #1658037 писал(а):

Может у Вас есть по этому поводу мысли?

Ну есть конечно. Грязные кортежи ведь жутко разные. То ли дело почти чистые (1 лишнее простое), то ли 30. Да даже если 10, а не 30.

Мы же уже убедились что нужно прям конкретные лен и валидс смотреть.

Я немного уже отошёл от этой проблематики, но кое-что помню.

[Dmitriy40]

Так это и удивило, что жуть какие разные, но вот отношение двух чисел почти постоянное. Сначала думал вообще одинаковое, лишь потом заметил разницу. Просто странно что несмотря на сильно разное количество в 97# (почти три порядка разницы) среднее время нахождения почти не меняется. Подумал может помните как это может быть связано с расчётом в HL1 по Вашей методике, я ж в неё не особо вникал. Очень уж грустные ограничения получаются на ожидаемое время поиска квадрата.

[Yadryara]

Dmitriy40 в сообщении #1658048 писал(а):

Подумал может помните как это может быть связано с расчётом в HL1 по Вашей методике,

Вот что я писал по другому методу, но и с HL1 было так же:

Yadryara в сообщении #1636638 писал(а):

спросите меня: Антоха, а как ты сумел получить эти два массива чисел для каждой длины? А я уже не всё помню! И не всё понимаю!

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

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

Возможно, с новым компом буду вникать по новой.