Дьявольские магические квадраты из простых чисел

[Nataly-Mak]

Поясню, почему я писала об оптимальном решении 733.
Такое оптимальное решение, может быть, и не существует. Я отвечала YuriiS, который сообщил, что нашёл решение 733 в самом начале конкурса.

Вполне допускаю, что оптимальное решение для N=7 уже найдено Wes Sampson, это решение $S=749$. Конечно, доказать оптимальность этого решения сложно.

[Nataly-Mak]

Хочу попробовать поискать решение $S=1168$ для N=8 с помощью алгоритма, использующего псевдокомплементарные пары чисел.

Объединённый массив для магической константы 1168 (для квадратов 8-го порядка) – все числа от 3 до 443, кроме 439 и 431, всего 83 числа:

3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  
101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199  211  223  227  229  233  239  241  251  257  263  269  271  277  281  283  293  307  311  313  317  331  337  347  349  353  359  367  373  379  383  389  397  401  409  419  421  433  443

Всего 292 потенциальных массива из 64 различных простых чисел; нашла по программе whitefox.

-- Вс сен 08, 2013 11:24:02 --

Приближение к решению S=1168 нашлось мгновенно:

 7  3  193  107  223  257  181  197 
 151  227  179  163  19  13  139  277 
 11  97  241  313  131  211  103  61 
 271  191  73  109  67  37  263  157 
 101  3  193  13  317  257  181  103 
 241  311  71  97  109  97  31  211 
 79  163  157  263  199  277  19  11 
 307  173  61  103  103  19  251  151

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

Разбиение показанного выше массива на 4 группы псевдокомплементарных пар чисел в этом примере такое:

группа 1 - отклонение 32, 20 пар

7  11  13  17  31  41  43  47  53  61  67  73  83  97  101  113  127  131  151  157  167  173  193  197  211  223  227  241  251  257  263  271  277  281  283  293  307  311  313  317

группа 2 - отклонение -32, 10 пар

3  19  31  37  61  67  79  97  103  109  151  157  163  181  193  199  223  229  241  257

группа 3 - отклонение 82, 10 пар

7  37  43  61  67  97  103  151  163  181  193  211  223  271  277  307  313  331  337  367

группа 4 - отклонение -82, 19 пар

11  13  17  19  29  31  37  43  47  53  59  61  71  73  79  83  97  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199

Из этих 4-х групп выбрать 4 набора по 8 непересекающихся пар, наверное, невозможно. Поэтому в решении так много повторений.

Я не знаю, возможно ли при каких-то отклонениях от комплементарности получить "хорошее" разбиение на 4 группы. Вопрос остаётся открытым.

[Nataly-Mak]

Ещё одно приближение к решению $S=1168$ для пандиагонального квадрата 8-го порядка:

7  3  271  139  283  241  151  73 
 193  307  107  103  79  47  109  223 
 13  43  229  317  127  211  97  131 
 313  199  61  31  37  53  311  163
41  19  223*  137  317*  257  103*  71 
 181  277  101  151*  67  17  103*  271* 
 83  163*  163*  193*  197  331  31*  7* 
 337  157  13*  97*  61*  11  263  229*

Все повторенные простые числа отметила звёздочками, 15 дырок. Многовато, конечно, но и для квадрата 7-го порядка я начинала с 35 найденных элементов (14 дырок); потом получила решения с 4-5 дырками, а для магической константы 735 даже с 3 дырками. Тут всё дело во времени выполнения программы, я сейчас долго не жду, максимум 10-15 минут. Если никакого решения не находится, изменяю исходные данные или условия перебора.

Обратите внимание, что все дырки сосредоточены в нижней половине квадрата, как и в приближении, показанном выше. В верхней половине квадрата все 32 элемента различны.

Ещё обратите внимание: в любом пандиагональном квадрате 8-го порядка выполняется правило решёток (по Россеру). В этом квадрате оно тоже выполняется (можете проверить), несмотря на то, что много одинаковых чисел.

P.S. Решение системы уравнений я, видимо, не получу уже никогда
Может быть, общая формула содержит меньше свободных переменных. А может и не быть. Но я этого уже никогда не узнаю...

[dimkadimon]

Последние результаты. После 6ти дней, нашёл 466 решений для 743 с одной ошибкой.

[Nataly-Mak]

dimkadimon
какой массив простых чисел вы используете при поиске решения $S=743$?
Выше я привела объединённый массив, который надо использовать.

[dimkadimon]

Я использую програму Jarek без изменений. Даже не знаю какой массив он использует.

[Nataly-Mak]

Jarek сообщил, что он использует массив из первых 138 нечётных простых чисел (все числа меньше 800). Это очень большой массив! Последнее простое число в этом массиве 797.

Jarek в сообщении #759399 писал(а):

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

Jarek
вопрос к вам: какой массив простых чисел вы задействовали в вашей программе
При поиске решения с магической константой 737 сейчас у меня появилось решение с двумя ошибками, в котором присутствует число 373. Это число ни в каком случае не может входить в решение с магической константой 737, так как оно слишком большое для данной магической константы.
Я определяю максимально возможный размер массива так: вычисляю сумму всех чисел для квадрата с данной магической константой; при $S=737$ сумма всех чисел в квадрате равна 5159. Далее вычисляю сумму первых 48 нечётных простых чисел - от 3 до 227 (она равна 4886) и потом смотрю на разность этих двух сумм. В данном примере $5159-4886=273$.
Очевидно, что число 373 не может входить в квадрат с магической константой 737.

I didn't do a good job here, all primes below 800 are allowed by the program. You are right, the program should not recognize as primes numbers, which are too large to be used in final solution.

В пандиагональном квадрате 7-го порядка с магической константой 743 максимальное простое число может быть 313.
mertz изменил количество чисел в массиве для магической константы 737 сначала до 75, потом до 60.
Попробуйте и вы изменить количество чисел в массиве. Перебирать так много лишних простых чисел очень нерационально. Ведь все большие числа участвуют в построении квадрата, а они не должны участвовать.
Если для магической константы 743 задать все нечётные простые числа подряд, не выбрасывая два числа (которые не входят в объединённый массив чисел), это будет массив из 64 первых нечётных простых чисел (все числа от 3 до 313). Всего 64 числа, а не 138, как в программе Jarek.

-- Пн сен 09, 2013 07:21:25 --

И вот здесь я писала о массиве для магической константы 743:

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

Таким образом, объединённый массив для магической константы 743 состоит из 62 простых чисел:

3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  
101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199  211  223  227  229  233  239  241  251  257  263  269  271  277  281  283  293  313 

Если не выбрасывать числа 307 и 311, то есть задать все простые числа от 3 до 313, тогда надо задать 64 числа в массиве.

-- Пн сен 09, 2013 07:28:38 --

А я ломаю голову, как выбрать из 4-х групп чисел набор по 8 непересекающихся пар чисел. Что-то ничего путного в голову не лезет Какой-нибудь там алгоритм "танцующих связей", например...

Запостила задачу здесь:
post761869.html#p761869

Коллеги, подбросьте идею, пожалуйста.
Очень сильно подозреваю, что из тех 4-х групп, которые я привела для примера, невозможно выбрать 4 набора по 8 непересекающихся пар чисел.
Но у меня таких комплектов по 4 группы много, надо проверить каждый комплект, а для этого надо написать программу проверки.

[Nataly-Mak]

Выполнила десятки экспериментов.
Пока действую наполовину вручную, точнее - визуально (при выборе 4-х групп чисел с различными отклонениями p1, p3).
Уже попробовала искать решения с магическими константами 1240 и 1232 (лучшее решение Jarek имеет магическую константу 1248).
Приближения с повторениями чисел находятся мгновенно!
Например, решение $S=1240$ (13 повторений)

11  3  167  151  367  127  131  283 
 157  389  109  163  19  41  223  139 
 229  17  103  293  193  307  37  61 
 271  277  67  73  89  211  55  197 
 53  73  199  7  409  197  163  139 
 181  379  67  191  43  31  181  167 
 97  23  163  359  61  313  97  127 
 241  79  365  3  59  13  353  127

[Nataly-Mak]

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

In[4]:= Solve[x1+x9+x17+x25+x5+x13+x21+x29==S&&
x10+x2+x26+x18+x14+x6+x30+x22==S&&
x27+x19+x11+x3+x31+x23+x15+x7==S&&
x20+x28+x4+x12+x24+x32+x8+x16==S&&
x1+x10+x27+x20-x5-x14-x31-x24==0&&
x9+x2+x19+x28-x13-x6-x23-x32==0&&
x17+x26+x11+x4-x21-x30-x15-x8==0&&
x25+x18+x3+x12-x29-x22-x7-x16==0,{x25,x26,x27,x28,x29,x30,x31,x32}]//FullSimplify

Out[4]= 
{{x25->1/2 (S-x1-x12-x13+x16-x17-x18-x21+x22-x3-x5+x7-x9),
x26->1/2 (S-x10-x11-x14+x15-x17-x18-x2+x21-x22-x4-x6+x8),
x27->1/2 (S-x1-x10-x11+x14-x15-x19-x20-x23+x24-x3+x5-x7),
x28->1/2 (S-x12+x13-x16-x19-x2-x20+x23-x24-x4+x6-x8-x9),
x29->1/2 (S-x1+x12-x13-x16-x17+x18-x21-x22+x3-x5-x7-x9),
x30->1/2 (S-x10+x11-x14-x15+x17-x18-x2-x21-x22+x4-x6-x8),
x31->1/2 (S+x1+x10-x11-x14-x15-x19+x20-x23-x24-x3-x5-x7),
x32->1/2 (S-x12-x13-x16+x19+x2-x20-x23-x24-x4-x6-x8+x9)}}

И мы имеем общую формулу пандиагонального квадрата 8-го порядка, построенного из псевдокомплементарных пар чисел.

Herbert Kociemba, спасибо большое!

Так значит, свободных переменных все-таки 24, при заданной магической константе (раньше я была умнее ибо как раз и свела перебор к 24 свободным переменным; старею и глупею).

Теперь надо переписать программу, потому что сейчас у меня в программе 25 свободных переменных; уменьшение даже на одну свободную переменную даст несомненнный выигрыш во времени.

[Nataly-Mak]

И программа нашла решение $S=1240$ c 10 дырками:

11  3  173  211  337  103  131  271 
 127  379  277  67  37  71  193  89 
 229  13  139  307  283  179  43  47 
 313  181  31  19  23  223  253  197 
 83  97  199  19  409  197  157  79 
 163  349  97  241  73  41  13  263 
 7  151  157  373  61  317  61  113 
 307  67  167  3  17  109  389  181

Повторены (по одному разу) числа: 3,13,19,61,67,97,157,181,197,307.

[Nataly-Mak]

Будет ли последовательность отношений p/m строго убывающей последовательностью при возрастании порядка квадрата N
Пока это не так. Можно предположить, что решения для N=8,9 подлежат улучшению.

[Pavlovsky]

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

Будет ли последовательность отношений p/m строго убывающей последовательностью при возрастании порядка квадрата N

Новая проблема века? Добавлю к этой гипотезе еще одну гипотезу.

Существует $N_0$. такое что для всех $N>N_0$ $p/m=1$.

[dimkadimon]

Pavlovsky в сообщении #762225 писал(а):

Новая проблема века? Добавлю к этой гипотезе еще одну гипотезу.

Существует $N_0$. такое что для всех $N>N_0$ $p/m=1$.

Я на 99% уверен что эта гипотеза верна. Для больших N растёт количество возможностей и должно быть возможно приблизить p и m. В самом начале темы Jarek обсуждает эту гипотезу.

[whitefox]

Пофиксил ещё один баг.
Он не влиял на работу программы, но не позволял задать разность между max и min в одну единицу.
Ссылка прежняя: http://yadi.sk/d/Qr1NDjYR8q67V

[Nataly-Mak]

Начала писать программу построения пандиагонального квадрата 8-го порядка из псевдокомплементарных пар чисел по общей формуле, показанной выше.
Написала первый этап, выполнила его, красиво всё получилось

19  7  269  277  223  157  149  139 
 0  0  0  59  0  0  0  199 
 0  0  0  103  0  0  0  11 
 0  0  0  37  0  0  0  127 
 197  43  181  151  401  193  61  13 
 0  0  0  131  0  0  0  271 
 0  0  0  409  0  0  0  317 
 0  0  0  73  0  0  0  163 

Магическая константа 1240. Пока различных чисел хватило, ну, это только 28 элементов. Здесь уже задействован перебор 12 свободных переменных и две переменных зависимые (вычисляются). Это 14 элементов, и ещё 14 элементов вычисляются по псевдокомплементарности.
Первый этап выполнился в малую долю секунды.

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