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

[dimkadimon]

Congratulations Jarek! You have blown us away with your amazing results. Thank you everyone for the interesting discussion and for making this contest fun. Thank you to Natalia for coming up with this great, albeit difficult problem. Thanks to Al for hosting the competition.

Here is a brief description of my approach. As always, I use simulated annealing as my optimization method. I use various moves that don't change the pandiagonality of the square, but can change the number of unique primes:

1. Change 8 +/-1 locations. This is the same move as Jarek described. I got the idea from Pavlovsky, thank you. This move does not change S. I pre-generate all these moves for N<=13 by observing that they all contain 2 rectangles of the form (1 -1; -1 1). For N>13 I pre-generate 1000 random such moves. Earlier I wrote the number of such moves for N<=13.

2. For prime N, change the value of N cells. This move changes S. The matrix of changed cells must contain a single 1 in each row/column/diagonalA/diagonalB. Here is an example for N=5:

1,0,0,0,0
0,0,1,0,0
0,0,0,0,1
0,1,0,0,0
0,0,0,1,0

As remarked by Jarek, there are N*(N-3) such moves. These moves can be generated like so: place a 1 somewhere in the first row, now make a jump where change in row=1 and change in column=2 to N-2 (with wraparound), repeat until you've place N ones.

3. Change a single value or swap two values in the square. I found that a series of such moves could turn any square into a pandiagonal square (eventually). Once we have a pandigonal square we can try to remove non-primes using move 1. I used these moves for both prime and non-prime N. For prime N, I found them to work even better than move 2.


For N=7 I used a general formula that contained 24 independent cells and 25 dependent cells. I could initialize all the independent cells with primes and then hope that the dependent cells turned out to be prime too. I used moves 3 to make changes to the independent cells. This formulation allowed me to look for arbitrary S. If I wanted to find a particular (fixed) S then I added an extra independent cell and used the same method. I allowed negative numbers and counted them as a single mistake (like a non-prime).


For N=14, 16, 18 and 20 I used the method that Jarek and Natalia suggested. Construct an ideal N x N rectangle where opposite pairs of numbers sum up to the same constant K (the best K can be pre-computed). This can be accomplished by constructing a particular N/2 x N rectangle. In particular, we want every row to be magic and the sum in column c to be the same as the sum in column (c+N/2). This method only gave marginal improvement over the known results. Here is an example for N=14:

(Оффтоп)

N=14, K=2310, S=16170
(1787,1663,761,1637,283,2293,131,743,563,313,2267,1483,2017,229),
(421,641,337,1913,1481,1867,1451,1741,281,499,643,1601,1823,1471),
(2239,2003,1831,983,881,2083,701,757,937,823,2129,41,613,149),
(2113,2153,103,1693,431,167,739,379,1847,521,1627,821,1523,2053),
(23,317,877,2243,2281,199,1999,2251,1559,2039,409,97,1427,449),
(37,2099,727,587,1619,557,173,1871,1499,1733,359,2087,1399,1423),
(1453,13,1381,509,601,1877,2237,331,2203,89,2131,1447,241,1657),
(1567,1747,1997,43,827,293,2081,523,647,1549,673,2027,17,2179),
(569,2029,1811,1667,709,487,839,1889,1669,1973,397,829,443,859),
(1553,1373,1487,181,2269,1697,2161,71,307,479,1327,1429,227,1609),
(1931,463,1789,683,1489,787,257,197,157,2207,617,1879,2143,1571),
(59,751,271,1901,2213,883,1861,2287,1993,1433,67,29,2111,311),
(439,811,577,1951,223,911,887,2273,211,1583,1723,691,1753,2137),
(1979,107,2221,179,863,2069,653,857,2297,929,1801,1709,433,73)

Here are my best results:

6 x 6 450
7 x 7 959
8 x 8 1496
9 x 9 2601
10 x 10 3594
11 x 11 5797
12 x 12 7332
13 x 13 9997
14 x 14 16170
15 x 15 18231
16 x 16 25200
17 x 17 38033
18 x 18 35910
19 x 19 49087
20 x 20 54600

I was able to improve all N, except N=15.

I look forward to meeting you all in the next contest!

-- 22.08.2013, 12:00 --

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

The most important special tricks I used:

$N = 8, 10, 11, 12, 13, 17, 18, 19$
I was able to construct starting square with numbers nondivisible by 3 and with equal or close numbers of terms 1(mod 3) and 2(mod 3). Then the terms were changed by a multiple of 3 only.

$N = 14, 16, 20$
I split prime numbers into 4 disjoint sets, with 2 residues (mod 30) in one set. Then in step 1 I constructed 4 pandiagonal squares (N/2)x(N/2) with equal magic sums and each having primes coming from one of the 4 sets. I allowed one of the 4 squares to have one fault (a composite number or a repeated prime). Then in step 2 I was putting those 4 squares together and was fixing the fault.

Cool tricks! I didn't think of those. Did you use any tricks for N=7?

[Nataly-Mak]

dimkadimon
спасибо за подробный рассказ о ваших подходах. С интересом ознакомилась.

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

This method only gave marginal improvement over the known results. Here is an example for N=14:

Хорошее решение.

Цитата:

I was able to improve all N, except N=15.

Для N=10 вроде тоже не улучшили известное решение. Я вижу в вашей таблице для N=10 результат 3594.

Поздравляю вас с титулом - Почётный участник конкурса!

[dimkadimon]

dmd в сообщении #756384 писал(а):

CAS находит только схему 34+15:

Спасибо! Значит схема Nataly-Mak оптимальна.

-- 22.08.2013, 12:14 --

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

Для N=10 вроде тоже не улучшили известное решение. Я вижу в вашей таблице для N=10 результат 3594.

Поздравляю вас с титулом - Почётный участник конкурса!

Спасибо за поздравление. Ах да N=10 тоже не улучшил...

[Nataly-Mak]

Следовательно, решения для N=10,15 были не так уж плохи
Улучшить их оказалось непросто.
Решение N=10, S=3594 принадлежит Pavlovsky, решение N=15, S=18231 моё.

Теперь немного об итогах конкурса.

В целом я очень довольна результатами конкурса. Получены замечательные результаты. Открыты новые интересные алгоритмы совсем не такие, как алгоритмы Россера, которыми мы пользовались в своё время. Новое всегда очень интересно узнавать!
Пристально посмотрели на статью svb, оценили
А могли бы это сделать давно, как только статья была написана. К сожалению, внимание к проблеме постепенно сошло на нет у моих замечательных коллег. Я занималась задачей долго, но тоже со временем перешла к другим задачам. Хотя подспудно всегда думаю о пандиагональных квадратах из различных простых чисел. Думаю и об идеальных квадратах, и о совершенных квадратах, которые тоже являются пандиагональными, но обладают некоторыми дополнительными свойствами.

Немного огорчает малая доля участия со стороны коллег. Не участвовал в конкурсе svb, да и alexBlack фактически не участвовал, просто отметился. А ведь они могли найти очень хорошие решения. Мне искренне жаль!

Порадовал интерес dmd к конкурсной задаче. Было очень интересно общаться и сотрудничать в рамках этой темы, он помог мне со многими общими формулами, решив мои системы уравнений. Спасибо!

Теперь у меня есть просьба к Jarek: пожалуйста, внесите изменения в статью A179440.

В заключение, прошу всех, кому понравились пандиагональные квадраты, продолжить решение всех нерешённых задач в этой области. А их много!
Например:
1. надо доказать минимальность пандиагонального квадрата 7-го порядка из различных простых чисел с магической константой S=769, найденного Jarek;
2. есть мой проект по совершенным магическим квадратам из различных простых чисел, смотрите http://www.primepuzzles.net/puzzles/puzz_671.htm
3. есть проект по идеальным магическим квадратам из различных простых чисел (в теме я подробно описала, какие квадраты найдены);
4. поиск пандиагональных квадратов 5-го порядка из последовательных простых чисел. Очень сложная задача! Квадрат 4-го порядка из последовательных простых чисел недавно найден Jarek, но минимальность его не доказана.

Вы можете писать в этой теме, в темах "Магические квадраты", "Антимагические квадраты", а также личные сообщения.

[Pavlovsky]

post348692.html#p348692

Цитата:

А блин, не обеднею. Объявляю приз, решившему задачу, вышлю на веб-кошелек 500 (Пятьсот) рублей.
Точно формулирую задачу:

Найти пандиагональный МК 7х7 из различных простых чисел с магической константой C и доказать, что не существует регулярного (по Россеру) пандиагонального МК 7х7 из различных простых чисел с константой равной или меньшей C. Или доказать, что это невозможно.

Этот приз ждал своего хозяина почти три года. После долгих сомнений, все таки принял свое субъективное решение, вручить этот приз Dmitry Kamenetsky.

1) Он первый сообщил о существовании нерегулярного квадрата 7х7 с магической суммой меньше 1597. post742025.html#p742025 Что на тот момент было ценной подсказкой для участников конкурса.
2) В ответном посте (post742029.html#p742029) я фактически объявил присуждение премии Dmitry Kamenetsky. Менять свое решение как то не правильно.

Много людей было достойно получить эту премию:

1) Andersen, сообщивший первым, что регулярный квадрат порядка 7 с магической суммой 1597 минимально возможный.
http://www.primepuzzles.net/puzzles/puzz_681.htm

Цитата:

(7,1597) is also minimal

2) Несомнено премию заслужил Jarek Wroblewski. Теперь очевидно, что нерегулярный квадрат 7х7 с магической суммой меньше 1597 нашел первым он.

Делить весьма небольшую сумму на несколько человек, было бы абсурдным решением.

[dmd]

Квадраты 14х14, 15х15, 20х20, найденные мною по решеткам:

(Оффтоп)

14x14 _37310
(1439,2213,3881,499,3833,3517,1523,3079,811,3767,1229,4283,5939,1297),
(4657,2111,4241,3943,1427,1433,4483,1789,67,1801,3011,2557,769,5021),
(2203,3967,179,4751,4457,1949,3581,2251,3389,929,3023,3559,1823,1249),
(4513,7,191,4261,3433,1787,523,5231,4721,2917,4451,1913,823,2539),
(5531,967,2531,3989,1013,1291,2503,2137,1571,4951,3407,2417,2099,2903),
(587,6037,4931,887,3847,3019,853,757,4637,2467,613,3491,3187,1997),
(1871,3121,4799,2617,1049,3371,4049,1619,4673,4027,521,1721,1693,2179),
(977,3217,5059,1697,367,3701,3251,2803,797,4007,4327,1993,3877,1237),
(3191,4679,2663,1759,1201,2609,1061,3163,5099,787,2441,3571,2999,2087),
(3461,773,193,5113,4357,211,4001,3697,1399,2447,4813,1907,431,4507),
(4289,829,2741,1741,4391,2287,2141,5147,1181,2411,3343,2647,569,3593),
(4423,2927,1153,2657,4877,2713,641,2477,2857,1879,223,3331,4481,2671),
(131,2879,1861,3299,2711,3631,3797,1259,1931,1783,4691,457,3533,5347),
(37,3583,2887,97,347,5791,4903,1901,4177,3137,1217,3463,5087,683)

15x15 _18063
(149,1381,1049,2141,1627,1151,1171,1123,383,1721,859,2221,839,1031,1217),
(2027,1483,1609,337,1019,2153,1289,1489,1789,857,499,367,1511,1531,103),
(547,1187,1063,2341,947,2161,601,557,2467,1823,1423,67,709,1907,263),
(809,1873,541,1259,787,1871,521,281,2039,1181,3001,1319,2251,79,251),
(167,967,1723,2129,1543,397,659,211,1399,1637,2389,1583,1429,911,919),
(1777,1949,2383,983,1831,277,43,1163,47,2647,257,1993,571,821,1321),
(1553,1901,2309,1291,1453,419,1889,829,409,347,1801,191,941,37,2693),
(269,1117,1373,2729,2281,349,307,389,853,1439,2011,1753,1277,223,1693),
(2143,233,977,877,131,1153,1747,2213,1237,937,2357,2593,317,1087,61),
(1427,757,59,29,1051,1013,1973,1657,2963,1663,353,1409,929,2203,577),
(1579,1433,883,587,691,3049,887,1129,1667,1361,1009,139,1607,1759,283),
(907,2621,1447,271,1613,2377,2417,157,991,373,107,137,2053,1523,1069),
(2083,109,2063,1301,1103,1567,467,2131,227,1109,7,881,1061,2671,1283),
(1979,1021,433,239,487,73,2879,2803,313,727,113,2179,197,1597,3023),
(647,31,151,1549,1499,53,1213,1931,1279,241,1877,1231,2371,683,3307)

20x20 _64060
(1277,4973,6131,1423,3187,179,4337,3931,1627,3823,331,2711,3067,1693,2713,2617,6857,5347,2503,5333),
(3229,1163,229,3329,1249,2399,4259,3259,2707,5623,1033,6091,2657,4153,4283,2689,6173,2677,6211,647),
(3011,1301,3331,89,491,1753,1637,2039,2633,3001,1667,4289,4691,4177,6991,4679,5189,5783,2389,4919),
(3851,6607,3079,4027,4621,431,101,4447,2671,1453,199,2417,1361,6353,6067,3061,3511,1171,6569,2063),
(3697,5179,487,2861,3727,1483,4093,2089,4787,4231,1447,3593,191,5039,8117,3733,3613,83,1871,3739),
(4967,5437,3767,907,4409,1009,5113,2099,4513,2521,2767,2789,1087,1019,2609,1327,1039,6029,1759,8893),
(3863,4057,1709,5879,6521,3917,5881,2729,1889,2267,2347,4547,2999,1051,4861,1409,743,4723,1217,1451),
(2311,6709,5689,4957,1601,947,5857,797,1913,6547,3821,4783,5281,751,631,5167,4909,1061,17,311),
(3701,4297,3433,5903,617,4943,5651,3541,5683,1439,2027,3889,4357,4969,1867,2333,1657,367,3037,349),
(2371,2377,5147,787,877,4649,109,6961,3299,5843,4493,3709,6719,2293,4597,317,2749,853,1669,4241),
(1877,2017,3877,5867,3251,4021,4441,821,1973,5779,1259,3041,5693,3797,599,3929,3221,401,5839,2357),
(3343,691,1373,5923,5569,1381,547,1031,4549,6317,5507,2851,2551,1303,5479,2693,3,6323,3109,3517),
(6343,1229,3407,3361,2287,3853,811,593,571,433,5023,2659,4127,4201,967,5711,2687,6299,5807,3691),
(5051,2699,5323,3119,5059,2137,1153,2459,607,709,4049,2239,2161,6007,2647,6421,3137,4463,2843,1777),
(3803,5519,149,1091,2393,281,557,3557,3209,151,7369,3677,2129,4987,3457,5279,4481,5077,4483,2411),
(4789,911,5297,587,953,6679,2731,5413,1433,467,661,4657,3631,1321,1289,1787,5209,6637,6037,3571),
(997,337,2557,2467,6197,5557,1123,5861,3347,6089,7187,3163,4273,113,2351,1621,1201,3919,2797,2903),
(397,4339,1549,7873,4421,5821,5381,1237,4889,1319,3673,1187,3391,2543,1879,5261,2917,1993,3533,457),
(3461,3121,6949,3089,3359,6043,3499,6869,6311,4817,3373,461,503,2003,107,719,2381,31,2087,4877),
(1721,1097,577,521,3271,6577,6779,4327,5449,1231,5827,1307,3191,6287,2549,3307,2383,823,283,6553)

Искавший код для 20х20:

(Оффтоп)

pdms20x20()=
{
n= 5; SX= 16015; R= 7000; so= Set(); w= vector(16);

for(l=1, 16,

 while(1,
  m= matrix(n,n); s= so;
  p= nextprime(3+random(R));
  if(!setsearch(s, p),
   m[1,1]= p;

   s= setunion(s, [m[1,1]]);
   for(k=2, n,

    a=b=vector(k-1); z= 1; q= 0;
    for(i=1, k-1, a[i]= m[k-1,i]);
    while(z&&(q<1000),
     p= nextprime(3+random(R)); q++;
     if(!setsearch(s, p),
      z= 0; t= s; b[1]= p;
      for(i=2, k-1,
       b[i]= b[i-1]+a[i]-a[i-1];
       if((b[i]<3)||(!isprime(b[i]))||(setsearch(t, b[i])), z= 1; break(), t= setunion(t, [b[i]]))
      )
     )
    );
    if(!z, for(i=1, k-1, m[k,i]= b[i]; s= setunion(s, [b[i]])), break());

    a=b=vector(k); z= 1; q= 0;
    for(i=1, k, a[i]= m[i,k-1]);
    while(z&&(q<1000),
     p= nextprime(3+random(R)); q++;
     if(!setsearch(s, p),
      z= 0; t= s; b[1]= p;
      for(i=2, k,
       b[i]= b[i-1]+a[i]-a[i-1];
       if((b[i]<3)||(!isprime(b[i]))||(setsearch(t, b[i])), z= 1; break(), t= setunion(t, [b[i]]))
      )
     )
    );
    if(!z, for(i=1, k, m[i,k]= b[i]; s= setunion(s, [b[i]])), break())

   );

   if(!z,
    S= sum(i=1, n, m[i,i]);
    if(S==SX,
     print(l); print("    ",S); print(m);
     v= matrix(n,n);
     for(i=1,n,
      for(j=1,n,
       x= 3*i+2*j; x= x%n; if(x<1, x= x+n);
       y= i+j; y= y%n; if(y<1, y= y+n);
       v[x,y]= m[i,j];
       so= setunion(so, [m[i,j]])
      )
     );
     w[l]= v;
     write("pdms.txt",v);
     break()
    )
   )

  )
 )
);

v= matrix(4*n,4*n);
for(i=1, n,
 for(j=1, n,
  a= w[1]; v[4*i-3, 4*j-3]= a[i,j];
  a= w[2]; v[4*i-3, 4*j-2]= a[i,j];
  a= w[3]; v[4*i-3, 4*j-1]= a[i,j];
  a= w[4]; v[4*i-3, 4*j-0]= a[i,j];
  a= w[5]; v[4*i-2, 4*j-3]= a[i,j];
  a= w[6]; v[4*i-2, 4*j-2]= a[i,j];
  a= w[7]; v[4*i-2, 4*j-1]= a[i,j];
  a= w[8]; v[4*i-2, 4*j-0]= a[i,j];
  a= w[9]; v[4*i-1, 4*j-3]= a[i,j];
  a= w[10]; v[4*i-1, 4*j-2]= a[i,j];
  a= w[11]; v[4*i-1, 4*j-1]= a[i,j];
  a= w[12]; v[4*i-1, 4*j-0]= a[i,j];
  a= w[13]; v[4*i-0, 4*j-3]= a[i,j];
  a= w[14]; v[4*i-0, 4*j-2]= a[i,j];
  a= w[15]; v[4*i-0, 4*j-1]= a[i,j];
  a= w[16]; v[4*i-0, 4*j-0]= a[i,j];
 )
);

for(i=1, 4*n,
 write1("pdms.txt", "(");
 for(j=1, 4*n-1,
  write1("pdms.txt", v[i,j], ",")
 );
 write("pdms.txt", v[i,4*n], "),")
)

};

[Nataly-Mak]

dmd в сообщении #756521 писал(а):

Квадраты 14х14, 15х15, 20х20, найденные мною по решеткам:
14x14 _37310
15x15 _18063
20x20 _64060

Хорошие решения!
Удалось улучшить решения для N=15,20, хотя и не намного.

[Pavlovsky]

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

И результат dmd тоже совсем неплохой.

Да конечно. Поздравляю нового лидера российской сборной с третьим местом.

[dmd]

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

Последний вариант моей программы:

(Оффтоп)

pdms()=
{
local(L):list;
local(s,m,M,b,s1,s2,s3,s4,s5,s6,bo,b1,b2,b3):vec;
local(n,q,qo,x,i1,j1,i2,j2,i3,j3,i4,j4,io,jo,ii,jj,S,T,k,a,z,y,e,ll):int;

n= 7; L= List();

bo= matrix(n,n); s= Set(); for(i=1, n, s= setunion(s, [i]));
for(r=1, n, i1= r:int;
 for(t=1, n, j1= t:int;
  b1= bo; b1[i1,j1]= 1;
  s1= setminus(s, [i1]); s2= setminus(s, [j1]);
  for(u=1, n-1, i2= s1[u]:int;
   for(v=1, n-1, j2= s2[v]:int;
    e= 1;
    b= b1; b[i2,j2]= 1; b[i1,j2]= b[i2,j1]= -1;
    for(i=1, n, S= 0; for(j=1, n, k= ((i+j-1)%n):int; if(!k, k=n); S= (S+b[j,k]):int); if(abs(S)==2, e= 0));
    for(i=1, n, S= 0; for(j=1, n, k= ((i+j-1)%n):int; if(!k, k=n); S= (S+b[k,(-j)%n+1]):int); if(abs(S)==2, e= 0));
    if(e,
    s3= setminus(s1, [i2]); s4= setminus(s2, [j2]); b2= b;

    for(p=1, n-2, i3= s3[p]:int;
     for(q=1, n-2, j3= s4[q]:int;
      e= 1;
      b= b2; b[i3,j3]= -1;
      T= 0; for(i=1, n, S= 0; for(j=1, n, k= ((i+j-1)%n):int; if(!k, k=n); S= (S+b[j,k]):int); if(abs(S)==2, e= 0); T= T+abs(S)); if(T>3, e= 0);
      T= 0; for(i=1, n, S= 0; for(j=1, n, k= ((i+j-1)%n):int; if(!k, k=n); S= (S+b[k,(-j)%n+1]):int); if(abs(S)==2, e= 0); T= T+abs(S)); if(T>3, e= 0);
      s5= setminus(s3, [i3]); s6= setminus(s4, [j3]); b3= b;
      if(e,

      for(g=1, n-3, i4= s5[g]:int;
       for(h=1, n-3, j4= s6[h]:int;
        e= 1;
        b= b3; b[i4,j4]= -1; b[i3,j4]= b[i4,j3]= 1;
        for(i=1, n, S= 0; for(j=1, n, k= ((i+j-1)%n):int; if(!k, k=n); S= (S+b[j,k]):int); if(abs(S)>0, e= 0));
        for(i=1, n, S= 0; for(j=1, n, k= ((i+j-1)%n):int; if(!k, k=n); S= (S+b[k,(-j)%n+1]):int); if(abs(S)>0, e= 0));
        if(e,
         listput(L, b); \\if(#L>9999, break(8))
        )))
       )
      )
     )
    )
   )
  )
 )
);

x= 183; ll= #L;

while(1, x= 183;
 x-=2; m= matrix(n,n); for(i=1, n, for(j=1, n, m[i,j]= x)); qo= (10^10000):int; z= 0; print();

while(1,

z++; if(z>8, print(); break()); if(random(2), qo= (10^10000):int); print();

for(l=1, ll,
 b= L[l]:vec;

 forstep(c=-1, 1, 2,
  forstep(d=2, 10000, 2,

   M= (m+c*d*b):vec; q= 0; s= Set();
   for(i=1, n,
    for(j=1, n,
     a= M[i,j]:int; if(a<3, break(3));
\\     if((!isprime(a))||(setsearch(s, a)), q++);
     if(!isprime(a), q++); if(setsearch(s, a), q++);
     s= setunion(s, [a]);
    )
   );

   if(q<=qo,
    if(q<qo, qo= q; m= M; print(x,"    ",q,"    ",#s,"    ",ll,"    ",l,"    ",z));
    if(q==qo, if(random(2), m= M;))
   );
   if(q==0,
    S= sum(i=1, n, M[1,i]):int;
    write("pdms.txt"); write("pdms.txt","    n= ",n,"    S= ",S);
    for(i=1,n,
     write1("pdms.txt","(");
     for(j= 1, n-1, write1("pdms.txt",M[i,j],",")); write("pdms.txt",M[i,n],"),")
    );
    write("pdms.txt"); print(M); break(4)
   )

  )
 )

)))
};

[Jarek]

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

Did you use any tricks for N=7?

No, I haven't even tried since I thought I couldn't afford doing that. The 2 tricks I mentioned before, have the property of making search faster and selective. For larger N there is no way of covering noticable fraction of the possible search space, so we do not really care how selective the search is. With $N=7$ I was afraid that there may be so few solutions with the given magic sum, that any selectiveness may cause missing them.

[dimkadimon]

Jarek, for N=7 have you tried any S<769? The best I found was for S=735, which had two bad numbers. Do you think it would be possible to find the optimal for N=7?

[Nataly-Mak]

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

Jarek, for N=7 have you tried any S<769? The best I found was for S=735, which had two bad numbers. Do you think it would be possible to find the optimal for N=7?

Очень хороший вопрос!
Меня тоже весьма интересует проблема с доказательством оптимальности или неоптимальности замечательного решения, найденного Jarek, - $S=769$.
И решение с двумя дырками и магической константой 735 может кому-то пригодиться для анализа проблемы.
И не забываем, что существует нижняя граница - 733.
Если учесть, что магические константы всех искомых квадратов нечётные, осталось не так много вариантов.
Обычный магический квадрат с константой $S=733$ существует.
Для начала можно проверить существование обычных магических квадратов со всеми потенциальными константами в интервале (733,769). Скорее всего, они тоже существуют.

А вот о существовании пандиагональных квадратов с такими магическими константами надо очень сильно подумать.

-- Чт авг 22, 2013 11:36:14 --

Jarek
Это не ваше оптимальное решение для N=6?

3 37 151 113 67 79
53 89 61 43 73 131
109 181 11 71 19 59
5 29 23 179 167 47
173 97 101 31 41 7
107 17 103 13 83 127

Задала вопрос и в дискуссионной группе: кому принадлежит это оригинальное решение? Никто не признаётся

-- Чт авг 22, 2013 12:03:20 --

dimkadimon
вы сообщили, что у вас есть программа поиска решений для N=7 по общей формуле.
Это очень хорошо. Вы можете воспользоваться этой программой.

[у меня тоже должна быть такая программа, надо поискать]

Этой программой можно пользоваться так, что не делать полный перебор, а делать его частично. Вы знаете, как это делается? Ну, во-первых, в программе у меня (да и вас, наверное) работает "перебор с возвратом".
Теперь смотрите: идёт последовательный перебор свободных переменных и вычисление зависимых переменных. Я ставлю ограничение на поиск зависимых переменных, то есть ищу их не все, а, скажем, формирую 5 полных строк квадрата. Понятно, что такой поиск выполнится быстрее, чем полный поиск всего квадрата. Далее рассуждаю так: если программе не удаётся сформировать даже 5 строк квадрата, то тем более ей не удастся составить квадрат полностью. Правильно?
Если же программа формирует 5 строк, можно добавить ещё одну строку. И так далее - до победного конца.
Вот так можно попробовать проверить все оставшиеся потенциальные константы.

[Jarek]

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

Jarek, for N=7 have you tried any S<769? The best I found was for S=735, which had two bad numbers. Do you think it would be possible to find the optimal for N=7?

Yes, I have tried, but I have given up. I was recording solutions with one fault, they could be verified for repetitions to determine whether the program is finding the same solutions again or is still producing new solutions. However, I have never checked the files. Now you can see those one-fault solutions in files x7(there should be a star here to denote arbitrary continuation of the file name, but I do not want to get a warning form a moderator for putting a star outside the TeX mode and TeX used in this forum doesn't like a star either) in the directory http://www.math.uni.wroc.pl/~jwr/PMS/

I have no clue whether we can find the optimal solution for $N=7$.

Natalia, I haven't done any search for $N=6$, just copied the known solution - that was the way to join The Club of 12.00 Gentlemen at the begining of the contest

[Nataly-Mak]

Скромник нашёлся

Цитата:

Solution #2 (that is, the solution beginning with the row “3 37 151 113 67 79”) was submitted by Valery Pavlovsky.

Pavlovsky
ну вы заскромничали совсем
Спрашиваю, спрашиваю: чьё решение? А вы молчите.
Пришлось самому администратору искать автора этого решения

Итак, есть три оригинальных оптимальных решения для N=6:

1. автор Radko Nachev
2. автор Pavlovsky
3. автор svb

Может быть, ещё есть?

[Nataly-Mak]

Нашла в теме "Магические квадраты":

svb в сообщении #733421 писал(а):

Я вам присылал 2 решения для 450:

 179  23  29   5  47 167
  71  11 181 109  59  19
  43  61  89  53 131  73
 113 151  37   3  79  67
  13 103  17 107 127  83
  31 101  97 173   7  41

 179  11  41  29  53 137
   5 157 149  31  61  47
  19  13  71 107 101 139
  89 127  79   3 109  43
 151  59  37 113  23  67
   7  83  73 167 103  17

Попробовал еще раз запустить свою программу, получил еще один квадрат с суммой 450:

 181  31  47  19 167   5
  97 127 103  79   7  37
  13  29  67  83 157 101
  89  59 139  11  43 109
  17 163  23 107   3 137
  53  41  71 151  73  61

Pavlovsky
копирайт?
А я думала, вы скромничаете
Забыла, что svb выкладывал свои решения в теме "Магические квадраты", когда я получила квадрат от Radko Nachev и мы стали проверять минимальность этого квадрата.
Третье решение в этом посте тоже оригинальное.
Таким образом, есть только два автора у всех 4-х оригинальных решений: Radko Nachev и svb.