# Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки

 На страницу Пред.  1 ... 35, 36, 37, 38, 39, 40, 41 ... 67  След.
 Печатать страницу | Печатать всю тему Пред. тема | След. тема

 Re: Дьявольские магические квадраты из простых чисел22.08.2013, 06:10

01/06/12
949
 Последний раз редактировалось dimkadimon 22.08.2013, 06:15, всего редактировалось 1 раз. 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,00,0,1,0,00,0,0,0,10,1,0,0,00,0,0,1,0As 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 4507 x 7 9598 x 8 14969 x 9 260110 x 10 359411 x 11 579712 x 12 733213 x 13 999714 x 14 1617015 x 15 1823116 x 16 2520017 x 17 3803318 x 18 3591019 x 19 4908720 x 20 54600I 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?

 Re: Дьявольские магические квадраты из простых чисел22.08.2013, 06:26
 Заблокирован

22/03/08

7154
Саратов
 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.Поздравляю вас с титулом - Почётный участник конкурса!

 Re: Дьявольские магические квадраты из простых чисел22.08.2013, 06:27

01/06/12
949
 Последний раз редактировалось dimkadimon 22.08.2013, 06:29, всего редактировалось 1 раз. dmd в сообщении #756384 писал(а):CAS находит только схему 34+15:Спасибо! Значит схема Nataly-Mak оптимальна.-- 22.08.2013, 12:14 --Nataly-Mak в сообщении #756514 писал(а):Для N=10 вроде тоже не улучшили известное решение. Я вижу в вашей таблице для N=10 результат 3594.Поздравляю вас с титулом - Почётный участник конкурса!Спасибо за поздравление. Ах да N=10 тоже не улучшил...

 Re: Дьявольские магические квадраты из простых чисел22.08.2013, 06:58
 Заблокирован

22/03/08

7154
Саратов
 Последний раз редактировалось Nataly-Mak 22.08.2013, 07:05, всего редактировалось 2 раз(а). Следовательно, решения для 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.htm3. есть проект по идеальным магическим квадратам из различных простых чисел (в теме я подробно описала, какие квадраты найдены);4. поиск пандиагональных квадратов 5-го порядка из последовательных простых чисел. Очень сложная задача! Квадрат 4-го порядка из последовательных простых чисел недавно найден Jarek, но минимальность его не доказана.Вы можете писать в этой теме, в темах "Магические квадраты", "Антимагические квадраты", а также личные сообщения.

 Re: Дьявольские магические квадраты из простых чисел22.08.2013, 07:11

21/02/10
1594
Екатеринбург
 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 minimal2) Несомнено премию заслужил Jarek Wroblewski. Теперь очевидно, что нерегулярный квадрат 7х7 с магической суммой меньше 1597 нашел первым он.Делить весьма небольшую сумму на несколько человек, было бы абсурдным решением.

 Re: Дьявольские магические квадраты из простых чисел22.08.2013, 07:14

16/08/05
993
 Последний раз редактировалось dmd 22.08.2013, 07:16, всего редактировалось 2 раз(а). Квадраты 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], "),"))};

 Re: Дьявольские магические квадраты из простых чисел22.08.2013, 07:20
 Заблокирован

22/03/08

7154
Саратов
 dmd в сообщении #756521 писал(а):Квадраты 14х14, 15х15, 20х20, найденные мною по решеткам:14x14 _3731015x15 _1806320x20 _64060Хорошие решения!Удалось улучшить решения для N=15,20, хотя и не намного.

 Re: Дьявольские магические квадраты из простых чисел22.08.2013, 07:29

21/02/10
1594
Екатеринбург
 Nataly-Mak в сообщении #756460 писал(а):И результат dmd тоже совсем неплохой. Да конечно. Поздравляю нового лидера российской сборной с третьим местом.

 Re: Дьявольские магические квадраты из простых чисел22.08.2013, 07:34

16/08/05
993
 Если не трудно, перескажите пожалуйста основные триксы по-русски - гугл-перевод не позволяет уловить смысл, к сожалению. У меня основной трикс был - дать побольше по-скользить текущему неоптимальному квадрату в допустимой области путем введения элемента случайности. Тогда шанс уменьшить количество дырок увеличивался.Последний вариант моей программы:(Оффтоп) Код: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

 Re: Дьявольские магические квадраты из простых чисел22.08.2013, 09:48

18/11/10
72
 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.

 Re: Дьявольские магические квадраты из простых чисел22.08.2013, 10:08

01/06/12
949
 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?

 Re: Дьявольские магические квадраты из простых чисел22.08.2013, 10:26
 Заблокирован

22/03/08

7154
Саратов
 Последний раз редактировалось Nataly-Mak 22.08.2013, 11:03, всего редактировалось 3 раз(а). 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 7953 89 61 43 73 131109 181 11 71 19 595 29 23 179 167 47173 97 101 31 41 7107 17 103 13 83 127Задала вопрос и в дискуссионной группе: кому принадлежит это оригинальное решение? Никто не признаётся -- Чт авг 22, 2013 12:03:20 --dimkadimonвы сообщили, что у вас есть программа поиска решений для N=7 по общей формуле.Это очень хорошо. Вы можете воспользоваться этой программой.[у меня тоже должна быть такая программа, надо поискать]Этой программой можно пользоваться так, что не делать полный перебор, а делать его частично. Вы знаете, как это делается? Ну, во-первых, в программе у меня (да и вас, наверное) работает "перебор с возвратом". Теперь смотрите: идёт последовательный перебор свободных переменных и вычисление зависимых переменных. Я ставлю ограничение на поиск зависимых переменных, то есть ищу их не все, а, скажем, формирую 5 полных строк квадрата. Понятно, что такой поиск выполнится быстрее, чем полный поиск всего квадрата. Далее рассуждаю так: если программе не удаётся сформировать даже 5 строк квадрата, то тем более ей не удастся составить квадрат полностью. Правильно?Если же программа формирует 5 строк, можно добавить ещё одну строку. И так далее - до победного конца.Вот так можно попробовать проверить все оставшиеся потенциальные константы.

 Re: Дьявольские магические квадраты из простых чисел22.08.2013, 11:31

18/11/10
72
 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

 Re: Дьявольские магические квадраты из простых чисел22.08.2013, 15:29
 Заблокирован

22/03/08

7154
Саратов
 Последний раз редактировалось Nataly-Mak 22.08.2013, 15:33, всего редактировалось 1 раз. Скромник нашёлся Цитата: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 Nachev2. автор Pavlovsky3. автор svbМожет быть, ещё есть?

 Re: Дьявольские магические квадраты из простых чисел22.08.2013, 16:48
 Заблокирован

22/03/08

7154
Саратов
 Последний раз редактировалось Nataly-Mak 22.08.2013, 16:49, всего редактировалось 1 раз. Нашла в теме "Магические квадраты":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  61Pavlovskyкопирайт? А я думала, вы скромничаете Забыла, что svb выкладывал свои решения в теме "Магические квадраты", когда я получила квадрат от Radko Nachev и мы стали проверять минимальность этого квадрата.Третье решение в этом посте тоже оригинальное.Таким образом, есть только два автора у всех 4-х оригинальных решений: Radko Nachev и svb.

 Показать сообщения за: Все сообщения1 день7 дней2 недели1 месяц3 месяца6 месяцев1 год Поле сортировки АвторВремя размещенияЗаголовок по возрастаниюпо убыванию
 Страница 38 из 67 [ Сообщений: 1005 ] На страницу Пред.  1 ... 35, 36, 37, 38, 39, 40, 41 ... 67  След.

Модераторы: Toucan, maxal, PAV, Karan, Супермодераторы

#### Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей

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

 Найти: