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

[Nataly-Mak]

В дискуссионной группе поступило предложение искать решения для N>20.
Хорошее предложение!
Своё решение для N=24 я здесь уже показала. Сейчас представила это решение в дискуссионной группе. Решение построено по решёткам Россера, магическая константа квадрата равна 72072.
Кто может улучшить моё решение?

Jarek
у вас есть решение для N=20, S=29700.
Как вы думаете, можно найти ещё три пандиагональных квадрата 20х20 с такой же магической константой, но составленных из других простых чисел?
Если это возможно, тогда по решёткам Россера легко построить пандиагональный квадрат 40х40 с магической константой 59400.

Я предполагаю такие действия: вы должны выбросить из массива простых чисел те числа, из которых составлено ваше решение. Затем вы снова запускаете программу поиска решения для N=20 с магической константой S=29700.
Реально найти такое решение? Если второй квадрат найдётся, всё повторяете.
Так действовала я, когда строила свои квадраты по данному алгоритму Россера.

-- Сб авг 24, 2013 09:50:00 --

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

240, 395, 450, 761, 1248, 2025, 2850, 4199, 5544, 7631, 9170, 12645, 13440, 19493, 22410, 28439, 29700

Здесь приведены данные для N=4-20. Хорошо ведут себя магические константы
Последовательность строго возрастающая.
Как я уже отмечала, самые плохие показатели у квадратов порядков 17,19 (что хорошо видно и в приведённой последовательности). Нуждаются в улучшении
Так же сильный скачок от магической константы квадрата 14х14 к магической константе квадрата 15х15: 9170 --> 12645. Тут тоже возможно улучшение. Хотя ничего нельзя сказать определённо. Может быть, решения для порядков 15,17,19 не допускают кардинальных улучшений.

[Nataly-Mak]

У меня возник интересный вопрос!

Сначала данные для анализа. Известны следующие магические константы пандиагональных квадратов 7-го порядка из различных простых чисел:

1895, 1649, 1597, 959, 769, 761

Обратите внимание: ни одна из этих констант не кратна 3, то есть не равна 0 по модулю 3.
Случайность или закономерность?

Внимание, вопрос!
Может ли магическая константа пандиагонального квадрата 7-го порядка из различных простых чисел быть кратна 3

Если ответ на этот вопрос отрицательный, это даст нам возможность исключить следующие потенциальные магические константы: 735, 741, 747, 753, 759.

P.S. У кого есть другие магические константы? Важно для анализа.

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

2 2 2 2 2 1 1

которая и даст магическую константу кратную 3.

-- Сб авг 24, 2013 11:40:00 --

Кстати, о шаблонах...

Решению с магической константой 769 соответствует такой шаблон из вычетов по модулю 3:

0 2 1 2 2 1 2
2 2 2 2 2 1 2
1 1 2 1 1 2 2
2 2 1 1 1 1 2
2 2 1 1 1 1 2
1 2 2 1 1 2 1
2 2 1 2 2 2 2

решению с магической константой 761 соответствует такой шаблон тоже из вычетов по модулю 3:

0 1 1 2 2 1 1
2 2 1 2 1 2 1
1 2 1 2 2 2 1
1 2 2 1 1 2 2
1 2 2 1 1 2 2
1 1 2 2 2 1 2
2 1 2 1 2 1 2

Не будем забывать и этот метод - построение квадратов по шаблонам. Это намного сокращает перебор. Правда, шаблонов очень много. Какой выбрать для построения?
Понятно, что шаблон должен соответствовать выбранной магической константе. Например, для магической константы 759 все суммы элементов в строках, столбцах и диагоналях обоих направлений в шаблоне должны быть кратны 3.

[dmd]

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

Внимание, вопрос!
Может ли магическая константа пандиагонального квадрата 7-го порядка из различных простых чисел быть кратна 3

(Да, может)

    n= 7    S= 23331
(257,4259,2341,991,8117,4463,2903),
(5153,1789,6581,2309,3433,1097,2969),
(8423,1373,919,937,2939,6833,1907),
(449,431,6917,10453,659,1109,3313),
(4423,6151,331,1381,3011,1747,6287),
(277,1259,3163,4813,3271,5749,4799),
(4349,8069,3079,2447,1901,2333,1153)


    n= 7    S= 2331
(103,307,439,839,383,223,37),
(41,239,79,53,101,1091,727),
(257,887,433,461,137,89,67),
(367,541,73,127,359,491,373),
(281,23,503,563,733,197,31),
(863,17,173,61,599,109,509),
(419,317,631,227,19,131,587)

[Nataly-Mak]

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

Кстати, сейчас посмотрела в теме "Магические квадраты" все регулярные квадраты, найденные svb, когда он осваивал алгоритм Россера. Вот магические константы:

29891, 11939, 4879, 3767, 2477, 2437, 2435, 2363, 2279, 2125, 2047

Удивительно, но и среди этих констант не оказалось кратных 3.

Сейчас сделаю по вашему квадрату шаблон для магических констант кратных 3.

[Jarek]

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

Jarek
у вас есть решение для N=20, S=29700.
Как вы думаете, можно найти ещё три пандиагональных квадрата 20х20 с такой же магической константой, но составленных из других простых чисел?
Если это возможно, тогда по решёткам Россера легко построить пандиагональный квадрат 40х40 с магической константой 59400.

Not a chance For $N=40$ there is no solution below 250,000 - to see this it is enough to add 1600 smallest primes.

As for $N=7$ with magic sum divisible by 3, here is the smallest I have (777):
(157,13,193,107,7,127,173),
(101,103,257,113,3,181,19),
(11,43,23,179,191,163,167),
(199,281,73,5,151,31,37),
(239,61,59,67,149,131,71),
(41,139,83,227,223,47,17),
(29,137,89,79,53,97,293)

[Nataly-Mak]

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

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

Jarek
у вас есть решение для N=20, S=29700.
Как вы думаете, можно найти ещё три пандиагональных квадрата 20х20 с такой же магической константой, но составленных из других простых чисел?
Если это возможно, тогда по решёткам Россера легко построить пандиагональный квадрат 40х40 с магической константой 59400.

Not a chance For $N=40$ there is no solution below 250,000 - to see this it is enough to add 1600 smallest primes.

Действительно, я об этом не подумала.

Цитата:

As for $N=7$ with magic sum divisible by 3, here is the smallest I have (777):

Спасибо.

-- Сб авг 24, 2013 12:51:28 --

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

Сейчас сделаю по вашему квадрату шаблон для магических констант кратных 3.

Вот такой шаблон получился:

1 1 1 2 2 1 1
2 2 1 2 2 2 1
2 2 1 2 2 2 1
1 1 1 1 2 2 1
2 2 2 2 1 2 1
2 2 2 1 2 1 2
2 2 1 2 1 2 2

Понятно, что в шаблоне отсутствует вычет 0, так как в пандиагональном квадрате отсутствует простое число 3.

Возникает такой вопрос: два решения - с магическими константами 761 и 769 - содержат простое число 3. Может ли пандиагональный квадрат 7-го порядка с магической константой $S<761$, если такой существует, не содержать число 3

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

-- Сб авг 24, 2013 13:14:08 --

Вот шаблон:

1 1 1 2 1 1 2
2 1 2 2 0 1 1
2 1 2 2 2 1 2
1 2 1 2 1 1 1
2 1 2 1 2 2 2
2 1 2 2 1 2 2
2 2 2 1 2 1 2

Можно пробовать строить по этому шаблону квадраты с магическими константами: 735, 741, 747, 753, 759.
Понятно, что это не единственный шаблон такого вида (для магических констант кратных 3 и с использованием простого числа 3).

[Jarek]

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

Возникает такой вопрос: два решения - с магическими константами 761 и 769 - содержат простое число 3. Может ли пандиагональный квадрат 7-го порядка с магической константой $S<761$, если такой существует, не содержать число 3

If we skip 3, the smallest 49 primes left are 5-233, adding up to 5345 and 1/7th of that is 763.571. Hence the smallest magic sum we could hope for, when avoiding 3, is 765.

[Nataly-Mak]

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

If we skip 3, the smallest 49 primes left are 5-233, adding up to 5345 and 1/7th of that is 763.571. Hence the smallest magic sum we could hope for, when avoiding 3, is 765.

Да, вы правы.
Следовательно, простое число 3 обязательно должно присутствовать в квадратах с магической константой $S<761$, если такие существуют.
Это хороший вывод. Мы имеем одно фиксированное число!

[Jarek]

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

Своё решение для N=24 я здесь уже показала. Сейчас представила это решение в дискуссионной группе. Решение построено по решёткам Россера, магическая константа квадрата равна 72072.
Кто может улучшить моё решение?

My program in 4 minutes produced 13 files, which can be seen in
http://www.math.uni.wroc.pl/~p-k1g4/PMS/

However there is no scorer to submit them and my program does no final verification - if I have a bug somewhere, files may contain garbage.

[Nataly-Mak]

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

My program in 4 minutes produced 13 files, which can be seen in
http://www.math.uni.wroc.pl/~p-k1g4/PMS/

Здорово!
Я проверила квадрат с магической константой $S=63000$ в программе mertz



Отличное решение!
А вы можете найти решения для N=21,22,23?

-- Сб авг 24, 2013 15:18:56 --

Скопировала решение $S=63000$ для N=24:

(Оффтоп)

(2293,6791,2851,2267,3469,4079,5857,1109,5227,557,1447,887,1327,1973,1801,2099,223,4391,7573,2063,3739,167,619,191),
(3931,6317,337,2333,6373,1823,3643,1571,2683,4673,349,1553,1789,4451,2689,5471,643,3911,673,4283,751,1523,67,1163),
(1093,2273,7213,233,541,587,4051,5399,499,3467,2017,2357,1777,1259,1489,431,4903,827,6379,5387,1951,443,5413,3011),
(37,809,8563,3833,2437,2729,733,3779,8431,4523,2251,11,103,1019,3499,4931,151,197,1663,1367,2311,6449,373,2801),
(2113,3167,331,1733,709,1277,9349,911,2593,419,2791,5849,61,2381,157,683,1741,2753,5233,929,1279,8969,739,6833),
(2179,2111,2203,1949,3727,3533,109,2141,2617,149,1993,3041,2377,4211,1453,3659,6211,3989,2671,1847,769,4649,4231,1181),
(1021,617,2269,1499,3853,3203,5077,3881,757,3527,4021,5153,199,1301,5839,2309,2551,1373,2647,4133,2347,2897,1117,1409),
(1621,1097,2857,881,2707,3023,2029,503,3907,3851,1867,1229,5827,2417,4447,947,3463,1901,1129,2963,2719,3863,3109,4643),
(1423,1913,163,4547,73,17,2473,2789,3943,293,4129,1217,8059,4289,991,2549,2221,1871,4969,4517,5197,719,3319,1319),
(5743,2861,313,521,3079,2003,3169,5381,3559,29,1609,5507,3919,2081,13,1307,2467,383,1039,2939,523,5171,6133,3251),
(3769,83,2383,2819,1069,5801,1669,2447,3343,6983,409,4373,2803,4457,3529,599,3541,1361,2011,1877,4099,2393,691,491),
(5023,1223,5557,6173,97,71,1693,59,919,3221,241,653,6553,2633,1153,281,3607,3209,31,53,7297,3323,5881,4049),
(6269,2083,3581,1009,2459,1879,971,6481,3923,1033,7541,1249,3947,937,347,5209,1439,367,4877,877,2591,1231,2423,277),
(5639,2503,4481,1699,5081,1543,107,4201,467,3433,4583,1201,839,997,4871,661,4889,607,5501,1873,773,853,5231,967),
(2237,3391,2027,2161,251,4651,449,1303,5417,5347,857,2557,509,3967,1697,3187,359,3181,479,4159,5099,2281,2837,4597),
(569,439,3491,463,4139,571,6143,613,941,1291,2621,6607,2927,1747,659,3253,5333,3307,239,1627,1451,3163,6287,5119),
(1493,4153,2129,5623,401,2917,1613,3331,2339,5503,5009,1579,173,6343,5867,307,1667,3637,269,1051,2699,229,2579,2089),
(4271,6367,3767,1753,2153,3517,1031,2713,3539,79,3137,631,797,5011,4733,7933,257,139,2843,2053,2687,457,113,3019),
(2711,3271,47,4243,8111,3067,1013,1213,863,3571,4091,6781,179,2539,263,5449,137,1861,1487,1399,4337,4957,977,433),
(41,1381,353,2287,2411,3313,2087,1063,311,4621,101,3457,317,2659,4493,2131,6053,5431,5,5779,743,1483,2609,9871),
(983,2833,1187,6961,4973,4999,1193,1237,1709,397,227,211,5591,883,3557,283,3761,3511,1619,5407,5351,1597,821,3709),
(1511,127,3407,1321,1997,4831,3461,6079,1289,1123,5237,1567,1583,379,3299,4801,2693,6337,1979,2137,2477,1531,2663,1171),
(3617,2239,2399,421,2297,19,1151,1999,2441,2389,4259,5323,7523,4519,2531,1459,1433,1723,4943,3373,761,3793,1811,577),
(3413,4951,1091,6271,593,3547,3929,2797,1283,2521,2213,7,3821,547,3623,3061,3257,6733,2741,907,1049,859,2957,829)

Кстати, нижняя граница для N=24 равна 46840.

[Jarek]

Could you verify 22?

[mertz]

It is a month to Al's next contest. I am willing to contribute CPU time for the search for N=7. I spent many CPU hours on the AP26 search. I would also be willing to build an application for the search.

[Nataly-Mak]

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

Could you verify 22?

Проверила решение $N=22$, $S=47190$. Всё верно.

(Оффтоп)

(1423,59,3373,89,2917,11,1039,3209,2089,1487,877,3593,1123,4253,2347,2099,1153,2087,6481,2939,2011,2531),
(5297,907,2447,421,3359,2467,1223,3361,1283,4441,197,1783,2423,4423,173,883,1493,823,4967,3697,29,1093),
(181,5333,3037,827,439,839,967,701,103,7583,1759,4409,1867,281,2539,2063,3457,4673,577,1733,2791,1031),
(4327,593,1987,3083,2953,1811,919,599,3301,719,3889,653,1297,2351,607,191,3571,5081,3019,2543,1117,2579),
(1663,6761,4549,2297,1033,1559,937,1613,5197,2039,3919,2069,2311,1061,229,239,2617,2903,1063,101,2221,809),
(859,5657,733,6917,163,2957,1741,3617,373,4937,2593,4007,457,971,1051,521,751,1049,1171,647,4231,1787),
(2383,389,709,3851,3967,3461,523,2339,4261,1193,1279,2381,1693,41,3307,587,1723,4157,4093,137,2767,1949),
(1567,1667,3067,251,331,3323,1447,2741,8581,1091,3331,677,3391,641,1777,4871,1483,887,643,1289,2683,1451),
(337,659,349,1709,151,941,2713,5,997,2633,1543,1877,4297,2003,6367,3911,3733,2417,2083,2591,2293,3581),
(1879,1847,3229,3527,829,1181,397,4733,2251,263,1549,2393,1993,3533,4339,509,1129,857,4099,3491,1789,1373),
(4621,1997,3727,4241,499,4019,3499,1409,463,23,409,3119,379,4463,2551,1013,601,821,1069,1619,1609,5039),
(863,661,317,1933,2909,2269,2843,1021,359,541,3797,1861,71,199,5477,2557,2621,271,3947,1087,5717,5869),
(1951,2777,193,167,1459,3089,4957,1433,991,617,3931,1721,6841,3203,691,1019,3583,3221,1399,449,1627,1871),
(683,31,2549,4363,4721,3463,2729,1489,47,223,6737,547,503,2371,419,5683,2399,13,1823,3607,401,2389),
(1499,1621,1217,5743,953,1291,479,853,1637,2029,6389,67,2441,2647,1697,2731,3677,4933,563,1321,2969,433),
(3011,739,5399,2803,2243,1999,4583,3793,929,277,461,1327,1439,127,4457,307,2309,4021,2837,313,383,3433),
(1151,1597,1523,1231,5279,4723,233,3271,2459,4759,797,3319,977,3547,743,2473,311,2719,2753,1303,443,1579),
(3023,3079,1901,1381,3041,673,761,5323,1571,2179,911,3691,1931,2017,2477,7,131,2749,269,3847,3257,2971),
(3779,3187,1103,157,4133,571,1889,1753,4931,1213,557,1831,4493,1657,2129,3109,3407,619,1097,5443,113,19),
(3167,3049,5231,1471,3191,43,3449,1453,2027,769,17,2797,1583,4987,1553,211,3821,79,1163,5449,149,1531),
(2267,2437,257,487,1301,2053,5981,1747,1187,757,1367,2281,2333,283,2207,9349,2237,1801,1607,367,4073,811),
(1259,2143,293,241,1319,4447,3881,727,2153,7417,881,787,3347,2131,53,2857,983,1009,467,3217,4517,3061)

Я могу выложить программу mertz на файлообменник.

[Jarek]

mertz в сообщении #757324 писал(а):

It is a month to Al's next contest. I am willing to contribute CPU time for the search for N=7. I spent many CPU hours on the AP26 search. I would also be willing to build an application for the search.

Currently I am searching for 755 - the C-source of the program I am running is in
http://www.math.uni.wroc.pl/~p-k1g4/PMS/755/

Unfortunately I am going to be travelling in a couple of hours, so at the moment I do no have time to do much more than just publishing the source as is.

At the moment I have over 700 one-fault solution, so there is a good chance I can find 755 on my own. Perhaps you could start a search for 749. This requires changing Main7-755.c:
line 7: 755 -> 749
line 35: 6 -> 12

[Nataly-Mak]

Почему-то у меня сейчас не работает файлообменник на Яндексе. Загрузила программу mertz на другой файлообменник. Вот ссылка для скачивания:

http://rusfolder.com/37739384

Jarek
попробуйте скачать программу.
Это исполняемая программа PrimeSums.exe
Ввод решения - кнопка Import.
Формат для ввода: числа, разделённые запятыми.
Например:

3,31,97,179,167,211,73,47,89,19,173,79,227,127,109,281,241,23,11,29,67,163,17,113,7,193,
71,197,43,41,101,151,223,149,53,157,103,59,191,83,61,107,239,199,131,37,5,13,137

-- Сб авг 24, 2013 18:36:42 --

Только сейчас увидела по ссылке, что Jarek нашёл решения до N=50.
Грандиозно!

-- Сб авг 24, 2013 18:48:38 --

mertz в сообщении #757324 писал(а):

It is a month to Al's next contest. I am willing to contribute CPU time for the search for N=7. I spent many CPU hours on the AP26 search. I would also be willing to build an application for the search.

mertz
это очень хорошо, что вы можете принять участие в поиске оптимального решения для N=7.
Кажется, Jarek предложил свою программу поиска, чтобы искать решение с магической константой $S=749$ (так я поняла перевод его сообщения).