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

[Nataly-Mak]

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

I am thinking of a new approach, namely constructing pandiagonal squares modulo 30 from a given set of primes. Let start from the other end, namely 733. My question is: Can we use the two sets of primes to construct pandiagonal squares modulo 30?

Я не совсем понимаю ваш вопрос. Что должно быть "по модулю 30"?

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

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

Только эти простые числа могут участвовать в построении пандиагонального квадрата 7-го порядка с магической константой 733 из различных простых чисел. Никакие другие простые числа не должны участвовать!
Здесь объединены два потенциальных массива из 49 различных простых чисел; эти два массива показаны выше отдельно, они отличаются друг от друга только парами чисел: (223, 233) и (227, 229).

[Jarek]

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

Я не совсем понимаю ваш вопрос. Что должно быть "по модулю 30"?

I mean: use one of the two sets of primes. All the 28 magic sums should be congruent to 733 modulo 30, i.e. to 13 modulo 30.

[Nataly-Mak]

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

All the 28 magic sums should be congruent to 733 modulo 30, i.e. to 13 modulo 30.

Разумеется, все 28 сумм в пандиагональном квадрате 7-го порядка с магической константой 733 всегда должны быть равны 733, что равно 13(mod 30). Так будет даже в том случае, если в решении будут не простые числа или одинаковые числа, то есть решение будет с ошибками.
Но куда это надо приложить, всё равно не поняла Это, видимо, как-то связано с вашим алгоритмом, в котором я не разбиралась.

Показываю два потенциальных массива из 49 различных простых чисел для магической константы 733 отдельно:

Массив №1

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 233 239

Массив №2

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 227 229 239

-- Ср сен 11, 2013 22:37:23 --

И найдено решение $S=1224$ c 6 дырками!

101  5  383  127  173  193  199  43 
 211  233  83  181  59  47  139  271 
 37  61  151  167  0  353  41  13 
 313  0  19  31  29  0  257  179 
 157  89  263  107  229  277  79  23 
 223  283  11  191  71  97  67  281 
 0  109  241  317  113  401  131  163 
 433  0  73  103  149  0  311  251

[Nataly-Mak]

Jarek
у меня вот такое есть приближение к решению $S=733$:

11  115*  197  191  163  53*  3 
67  97  17  29  181  131  211 
157  187*  71  13  59  107  139 
151  31  211*  199  79*  43  19 
61  23  127  109  193  167  53 
173  101  37  103  7  83  229 
113  179  73  89  51*  149  79

Здесь 6 ошибок (дырок). Есть не простые числа, есть одинаковые числа. Но все 28 сумм (элементов строк, столбцов и всех диагоналей) имеют значение 733. То есть этот квадрат пандиагональный.
В решении нет чисел бОльших 239 (это максимальное простое число объединённого массива).

[Jarek]

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

Но куда это надо приложить, всё равно не поняла Это, видимо, как-то связано с вашим алгоритмом, в котором я не разбиралась.

No, it has nothing to do with my algorithm - it is just another idea, completely independent. At the moment I do not know how to proceed further, but I would like to investigate this idea.

You were investigating шаблоны modulo 3 - my idea is to investigate шаблоны modulo 15 (or equivalently 30).

-- Чт сен 12, 2013 08:10:38 --

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

Jarek
у меня вот такое есть приближение к решению $S=733$:

11  115*  197  191  163  53*  3 
67  97  17  29  181  131  211 
157  187*  71  13  59  107  139 
151  31  211*  199  79*  43  19 
61  23  127  109  193  167  53 
173  101  37  103  7  83  229 
113  179  73  89  51*  149  79

Здесь 6 ошибок (дырок). Есть не простые числа, есть одинаковые числа. Но все 28 сумм (элементов строк, столбцов и всех диагоналей) имеют значение 733. То есть этот квадрат пандиагональный.
В решении нет чисел бОльших 239 (это максимальное простое число объединённого массива).

It is very good that there are no numbers above 239.
But one fault is bad:
51 - which is divisible by 3 - apart from 3 we cannot have another number divisible by 3.

Perhaps we should not look only at the number of faults, but also try to avoid bad faults:
number above 239,
2 numbers divisible by 3,
2 numbers divisible by 5.

[whitefox]

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

You were investigating шаблоны modulo 3 - my idea is to investigate шаблоны modulo 15 (or equivalently 30).

Очень легко находятся шаблоны по модулю 3 (и эквивалентные им шаблоны по модулю 6), также легко находятся шаблоны по модулю 4.
То есть, фактически, очень легко найти шаблоны по модулю 12.
Найти полным перебором шаблоны по модулю 5 за приемлемое время нереально. Но можно попробовать, например, отжиг.
Имея шаблоны по модулям 3 (6), 4, 5 мы, фактически, будем иметь шаблоны по модулю 60.

А если добавить к ним шаблоны по модулю 7, то, фактически, получим шаблоны по модулю 420, что полностью покрывает всё множество задействованных простых чисел.

Но уже шаблонов по модулю 12 может оказаться вполне достаточно для полного перебора.

[Jarek]

As both sets of primes have:
number 3
23 primes 1 mod 3
25 primes 2 mod 3
perhaps we should be interested only in pandiagonal squares with
number 3
23 numbers 1 mod 3
25 numbers 2 mod 3
all number below 240

[whitefox]

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

perhaps

Почему "возможно"?
Так оно и есть

[Jarek]

whitefox в сообщении #763101 писал(а):

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

Найти полным перебором шаблоны по модулю 5 за приемлемое время нереально.

We are interested olnly in the following two counts of residues modulo 5:
0 1
1 11
2 13
3 12
4 12
and
0 1
1 11
2 12
3 14
4 11
corresponding to the 2 sets.

-- Чт сен 12, 2013 08:25:39 --

whitefox в сообщении #763106 писал(а):

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

perhaps

Почему "возможно"?
Так оно и есть

Natalia's solution has one bad fault, namely numbers 3 and 51 (2 multiples of 3). I was suggesting to avoid such bad faults.

[whitefox]

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

We are interested olnly in the following two counts of residues modulo 5:
0 1
1 11
2 13
3 12
4 12
and
0 1
1 11
2 12
3 14
4 11
corresponding to the 2 sets.

Именно это я и имел ввиду.

Чтобы найти все шаблоны по модуля 5 полным перебором придётся рассмотреть $4^{23}$ различных возможностей.

В то время как при поиске шаблонов по модулю 3(6) и модулю 4 приходится рассматривать всего лишь $2^{23}$ различных возможностей.

[Jarek]

I do not know how to find all such mod 5 patterns (I hope Google will translate patterns as шаблоны) efficiently. Can we do this?

[whitefox]

Полным перебором нет.
Но я хочу попробовать применить алгоритм имитации отжига.

Впрочем, перебор $4^{23}$ различных вариантов не так уж и велик.
Достаточно мощный компьютер справится с ним за несколько дней (или часов).

[dimkadimon]

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

We are interested olnly in the following two counts of residues modulo 5:
0 1
1 11
2 13
3 12
4 12
and
0 1
1 11
2 12
3 14
4 11
corresponding to the 2 sets.

0*1+1*11+2*13+3*12+4*12=0*1+1*11+2*12+3*14+4*11=121. But 121 is not divisible by 7, so we can't even make a normal magic square with these numbers. Or am I missing something?

[Jarek]

dimkadimon в сообщении #763142 писал(а):

But 121 is not divisible by 7, so we can't even make a normal magic square with these numbers. Or am I missing something?

121 is divisible by 7 modulo 5

All magic sums must be 3 modulo 5, but they don't have to be equal - we do all the computations modulo 5.
Of course later we may need to make it pandiagonal by adding multiples of 5 here and there, but the first step is to find all the patterns pandiagonal modulo 5.

[whitefox]

dimkadimon в сообщении #763142 писал(а):

0*1+1*11+2*13+3*12+4*12=0*1+1*11+2*12+3*14+4*11=121. But 121 is not divisible by 7, so we can't even make a normal magic square with these numbers. Or am I missing something?

Всё получается отлично, так как:

$$121\cdot7^{-1}\equiv733\pmod5$$