2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 34, 35, 36, 37, 38, 39, 40 ... 67  След.
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение21.08.2013, 14:35 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Ещё 4,5 часа...
Это, наверное, последний результат, введённый на конкурс:

Цитата:
3 7.71 Dmitry Ezhov Sterlitamak, Russia 20 Aug 2013 17:22

В дискуссионной группе появилось пожелание узнать генеральные стратегии :D
Надеюсь, что Jarek расскажет, как конкурс закончится.
Участники этой темы генеральную стратегию уже знают. Ну, может быть, есть у Jarek маленькие хитрости. И dimkadimon тоже писал о некоторых хитростях, к которым он пришёл.
Ждём подробного описания этих эвристик :wink:

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение21.08.2013, 15:01 


16/08/05
776
dimkadimon в сообщении #756330 писал(а):
Может кто поможет с общей формулой для обычного магического квадрата 7х7? У меня нет математических пакетов которые могут это сделать. Вот система из 16 уравнений. Она состоит из 30ти известных (а) и 19ти неизвестных (х) и магической суммы S:

S=a00+a01+a02+a03+a04+a05+x06
S=a10+a11+a12+a13+a14+a15+x16
S=a20+a21+a22+a23+a24+a25+x26
S=a30+a31+a32+a33+a34+a35+x36
S=a40+a41+a42+a43+a44+a45+x46
S=x50+x51+x52+x53+x54+x55+x56
S=x60+x61+x62+x63+x64+x65+x66
S=a00+a10+a20+a30+a40+x50+x60
S=a01+a11+a21+a31+a41+x51+x61
S=a02+a12+a22+a32+a42+x52+x62
S=a03+a13+a23+a33+a43+x53+x63
S=a04+a14+a24+a34+a44+x54+x64
S=a05+a15+a25+a35+a45+x55+x65
S=x06+x16+x26+x36+x46+x56+x66
S=a00+a11+a22+a33+a44+x55+x66
S=x06+a15+a24+a33+a42+x51+x60


CAS находит только схему 34+15:
Код:
S = x60 + x61 + x62 + x63 + x64 + x65 + x66
x50 = -x51 - x52 - x53 - x54 - x55 - x56 + x60 + x61 + x62 + x63 + x64 + x65 + x66
x06 = -x16 - x26 - x36 - x46 - x56 + x60 + x61 + x62 + x63 + x64 + x65
a05 = -a00 - a01 - a02 - a03 - a04 + x16 + x26 + x36 + x46 + x56 + x66
a15 = -a10 - a11 - a12 - a13 - a14 - x16 + x60 + x61 + x62 + x63 + x64 + x65 + x66
a25 = -a20 - a21 - a22 - a23 - a24 - x26 + x60 + x61 + x62 + x63 + x64 + x65 + x66
a33 = a02 + a10 + a11 + 2 a12 + a13 + a14 + a22 - a24 + a32 + 2 x16 + x26 + x36 + x46 - x51 + x52 + x56 - 3 x60 - 2 x61 - x62 - 2 x63 - 2 x64 - 2 x65 - x66
a34 = a00 + a02 - a04 + a10 + 2 a11 + 2 a12 + a13 + 2 a22 - 2 a24 + a32 + 2 x16 + x26 + x36 + x46 - x51 + x52 - x54 + x55 + x56 - 3 x60 - 2 x61 - x62 - 2 x63 - 3 x64 - 2 x65
a35 = -a00 - 2 a02 + a04 - 2 a10 - 3 a11 - 4 a12 - 2 a13 - a14 - 3 a22 + 3 a24 - a30 - a31 - 3 a32 - 4 x16 - 2 x26 - 3 x36 - 2 x46 + 2 x51 - 2 x52 + x54 - x55 - 2 x56 + 7 x60 + 5 x61 + 3 x62 + 5 x63 + 6 x64 + 5 x65 + 2 x66
a40 = -a00 - a10 - a20 - a30 + x51 + x52 + x53 + x54 + x55 + x56 - x60
a41 = -a01 - a11 - a21 - a31 - x51 + x60 + x62 + x63 + x64 + x65 + x66
a42 = -a02 - a12 - a22 - a32 - x52 + x60 + x61 + x63 + x64 + x65 + x66
a43 = -a02 - a03 - a10 - a11 - 2 a12 - 2 a13 - a14 - a22 - a23 + a24 - a32 - 2 x16 - x26 - x36 - x46 + x51 - x52 - x53 - x56 + 4 x60 + 3 x61 + 2 x62 + 2 x63 + 3 x64 + 3 x65 + 2 x66
a44 = -a00 - a02 - a10 - 2 a11 - 2 a12 - a13 - a14 - 2 a22 + a24 - a32 - 2 x16 - x26 - x36 - x46 + x51 - x52 - x55 - x56 + 4 x60 + 3 x61 + 2 x62 + 3 x63 + 3 x64 + 3 x65 + x66
a45 = 2 a00 + a01 + 3 a02 + a03 + 3 a10 + 4 a11 + 5 a12 + 3 a13 + 2 a14 + a20 + a21 + 4 a22 + a23 - 2 a24 + a30 + a31 + 3 a32 + 4 x16 + 2 x26 + 2 x36 + x46 - 2 x51 + 2 x52 - x54 + x56 - 8 x60 - 6 x61 - 4 x62 - 6 x63 - 7 x64 - 7 x65 - 4 x66


-- Ср авг 21, 2013 17:14:14 --

Мне тоже было бы интересно узнать, откуда в контексте этого конкурса примориалы возникают.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение21.08.2013, 15:39 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
dmd в сообщении #756384 писал(а):
CAS находит только схему 34+15:

О! Так значит, я не ошиблась.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение21.08.2013, 18:31 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Через несколько минут Jarek станет героем дня :wink:
Все ждут его рассказа о поразительном алгоритме и о том, как он добился таких замечательных результатов.
Меня очень интересуют сами решения. Больше всего интересно, найдено ли минимальное решение хотя бы для N=7. Ведь пока в последовательности A179440 доказана минимальность только для порядков N=4,5,6.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение21.08.2013, 19:01 
Аватара пользователя


18/11/10
72
The main idea of the algorithm I have used is the following:
Take any pandiagonal square (a square with all terms equal is fine, but sometimes it is good to use some other square as the starting point) and while keeping pandiagonality intact change 8 terms at a time to arrive at all terms being distinct primes.

How did I find the algorithm?
I was well aware of the basic configuration of 8 fields of a chessboard with the property of having 0 or 2 fiels on each horizontal, vertical or diagonal line, since in early June 2013 I have given a related problem to the participants of a scientific camp for winners of Polish math olympiad for lower secondary school students. The relevant file is under link:
http://www.omg.edu.pl/uploads/attachmen ... oszura.pdf
and the picture you may want to look at is on page 22 (problem 28). It is easy to place numbers $\pm1$ in the 8 squares in such a way that sum of numbers on each line is zero.
Therefore in a pandiagonal square we may increase 4 properly placed terms and decrease other 4 properly placed terms by the same constant without destroying pandiagonality.
My intuition indicated that it would be insane to expect making 8 terms to be similtaneously prime that way, I was aware however that this is possible when we use very large numbers. I aplied this method to construct solutions for $N=17$ and $N=19$ with 10-digit magic sums. Then step by step I walked down to smaller numbers and other N, being trully surprised that this method worked exteremely well (frankly, I was surprised it was working at all). Most likely the strength of the algorithm comes from the large number of octuplets of the fields we can try.

I was starting from a pandiagonal square and was making changes at random using all proper configurations of eight $\pm1$ I could think of, to arrive at a square with distinct primes. The rest was a matter of tuning up the search program and working out some tricks improving its performance.

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.

In the archive placed in:
http://www.math.uni.wroc.pl/~jwr/PMS
you can find C-source of the version of the program I used for finding my best solutions. The code is not optimized and not very reader-friendly, it is just my working version of the program I used for the search and published as is.

Jarek

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение21.08.2013, 19:03 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Всё, ура!

Jarek, поздравляю вас с победой в этом трудном для многих конкурсе :!: Это очень большая победа. Я восхищена! Браво!

Всем большое спасибо за участие в конкурсе, а также за участие в обсуждении конкурсной задачи и сопутствующих задач.
Об итогах конкурса я напишу позже.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение21.08.2013, 19:25 
Аватара пользователя


21/02/10
1594
Екатеринбург
От всей души поздравляю Jarek Wroblewski с великолепной победой!

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение21.08.2013, 19:27 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
И вот рекордные результаты:

Цитата:
Problem Score Solver Date Achieved
7 x 7 769 Jarek Wroblewski Wroclaw, Poland 4 Aug 2013 03:26
8 x 8 1248 Jarek Wroblewski Wroclaw, Poland 16 Aug 2013 03:09
9 x 9 2025 Jarek Wroblewski Wroclaw, Poland 16 Jul 2013 18:12
10 x 10 2850 Jarek Wroblewski Wroclaw, Poland 12 Aug 2013 02:14
11 x 11 4199 Jarek Wroblewski Wroclaw, Poland 11 Jul 2013 02:11
12 x 12 5544 Jarek Wroblewski Wroclaw, Poland 17 Aug 2013 03:07
13 x 13 7631 Jarek Wroblewski Wroclaw, Poland 18 Aug 2013 18:30
14 x 14 9170 Jarek Wroblewski Wroclaw, Poland 10 Jul 2013 04:04
15 x 15 12645 Jarek Wroblewski Wroclaw, Poland 20 Jul 2013 04:17
16 x 16 13440 Jarek Wroblewski Wroclaw, Poland 18 Aug 2013 03:10
17 x 17 19493 Jarek Wroblewski Wroclaw, Poland 12 Jul 2013 09:48
18 x 18 22410 Jarek Wroblewski Wroclaw, Poland 13 Aug 2013 01:57
19 x 19 28439 Jarek Wroblewski Wroclaw, Poland 13 Jul 2013 15:32
20 x 20 29700 Jarek Wroblewski Wroclaw, Poland 14 Aug 2013 17:26

Это фантастика! Все рекорды принадлежат одному конкурсанту.

Уже выведены и все решения. Здорово! AZ молодец.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение21.08.2013, 19:28 
Аватара пользователя


18/11/10
72
Спасибо за Ваши поздравления.

One way of evaluating quality of solutions for various N is comparing them to known optima of magic sums of magic (not pandiagonal) squares of primes.
Below you can see in each row:

N
p $=$ smallest known magic sum of pandiagonal square of distinct primes
m $=$ smallest existing magic sum of magic square of distinct primes
ratio p/m

6 450 432 1.04167
7 769 733 1.04911
8 1248 1154 1.08146
9 2025 1731 1.16984
10 2850 2470 1.15385
11 4199 3417 1.22886
12 5544 4584 1.20942
13 7631 6013 1.26908
14 9170 7712 1.18906
15 12645 9731 1.29946
16 13440 12088 1.11185
17 19493 14807 1.31647
18 22410 17940 1.24916
19 28439 21501 1.32268
20 29700 25530 1.16334

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение21.08.2013, 19:30 
Аватара пользователя


21/02/10
1594
Екатеринбург
Так же поздравляю, занявшего второе место Dmitry Kamenetsky. А так же всех, кто принимал участие в обсуждениях на этом форуме. С вами, очень интересно. Ну и конечно вдохновителя этих тем Наталию Макарову!!

-- Ср авг 21, 2013 21:33:51 --

Jarek в сообщении #756455 писал(а):
6 450 432 1.04167
7 769 733 1.04911
8 1248 1154 1.08146
9 2025 1731 1.16984
10 2850 2470 1.15385
11 4199 3417 1.22886
12 5544 4584 1.20942
13 7631 6013 1.26908
14 9170 7712 1.18906
15 12645 9731 1.29946
16 13440 12088 1.11185
17 19493 14807 1.31647
18 22410 17940 1.24916
19 28439 21501 1.32268
20 29700 25530 1.16334


Как то выдвигал гипотезу. С ростом N магические константы классических магических квадратов и пандиагональных квадратов должны иметь тенденцию к сближению. Ваша таблица не подтверждает эту гипотезу, впрочем и не опровергает.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение21.08.2013, 19:38 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Pavlovsky в сообщении #756456 писал(а):
Так же поздравляю, занявшего второе место Dmitry Kamenetsky.

Присоединяюсь :-)
dimkadimon
пожалуйста, расскажите о ваших эвристиках и сообщите ваши лучшие результаты.
Ваш результат 10+ выглядит очень солидно.

Цитата:
Ну и конечно вдохновителя этих тем Наталию Макарову!!

Спасибо.

И результат dmd тоже совсем неплохой. И в тройке сильнейших оказаться хорошо в таком очень трудном конкурсе. Поздравляю!

Чуть-чуть не повезло в этом конкурсе Pavlovsky. Однако он первым заговорил о генеральной идее. Именно благодаря ему секретный алгоритм Jarek был разгадан.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение21.08.2013, 19:39 
Аватара пользователя


21/02/10
1594
Екатеринбург
a scientific camp for winners of Polish math olympiad for lower secondary school students. Задача №28
Гуглоперевод не причесывал, впрочем все понятно:

Цитата:
На каждом поле шахматной доске размером 2013 x 2013 находится
лампа накаливания. Для каждого ряда горизонтального, вертикального и усадка мы располагаем
переключателем, который изменяет состояние (не горит/включен) всех ламп накаливания
в этом ряду. Правительство покатый создают поля, в которых средства лежат на прямой опыт-
cinającej стороны доски под углом 45 покрытие. В частности, ряд является одн-
dyncza лампы накаливания в поле преломления.
Сначала горит лампа в центральном поле шахматной доске,
а остальные лампы гаснут. Или с помощью доступных переключателей
можно привести в состояние, в котором все лампы гаснут?

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение21.08.2013, 19:54 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Интересно:

Цитата:
17 19493 14807 1.31647
19 28439 21501 1.32268

для N=17,19 самые большие отношения р/m. Тяжёлые случаи.

Да, в самом деле, оптимальное решение для N=6 первым ввёл не Jarek, поэтому в альтернативной таблице у него результат 14.99.

-- Ср авг 21, 2013 21:32:12 --

На конкурс введены два различных оптимальных решения для N=6. Одно из них в точности такое, как в статье A179440, а второе - оригинальное.

№1
Код:
3 5 89 137 67 149
127 163 7 29 11 113
31 23 167 59 157 13
107 97 43 53 131 19
73 79 41 71 47 139
109 83 103 101 37 17

Ранжированный массив чисел, составляющих этот квадрат:

Код:
3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  149  157  163  167

№2
Код:
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

Ранжированный массив чисел, составляющих этот квадрат:
Код:
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  151  167  173  179  181

Массивы чисел не совпадают.
Интересно, кому принадлежит оригинальное решение?
И ещё вопрос возникает: нет ли других оригинальных решений (из других наборов чисел) :?:

-- Ср авг 21, 2013 21:50:10 --

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

Код:
3 47 139 227 173 127 53
191 113 179 71 11 7 197 
211 79 59 151 157 89 23 
5 107 31 163 97 199 167 
83 263 19 73 181 13 137 
37 131 281 67 109 101 43 
239 29 61 17 41 233 149

Ранжированный массив чисел, составляющих этот квадрат:
Код:
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  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  197  199  211  227  233  239  263  281

Обалденный массив! Почти из последовательных чисел.
Магическая константа квадрата $S=769$. Нижняя граница 733.

Задача века
доказать, что этот пандиагональный квадрат является минимальным (или опровергнуть это новым рекордным решением).

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение22.08.2013, 04:54 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Моё решение для N=14, квадрат построен по решёткам Рщссера из 4-х пандиагональных квадратов 7-го порядка с одинаковой магической константой $S=181355$:

Код:
6247 6091 14621 359 29669 59399 72623 61001 5101 269 18427 967 34667 53269
6857 18461 503 659 44257 50387 69431 56671 307 397 887 2927 59113 51853
68443 60887 9901 409 13913 829 40351 59119 2657 251 20627 14627 25463 45233
69197 56437 607 1697 593 1663 65707 69941 317 419 12347 24317 32587 26881
36761 53279 8663 14519 16421 461 21283 45119 73243 61027 5387 271 19597 6679
59167 51899 12161 24077 677 811 32353 26647 69497 57737 313 433 7187 19751
26083 45259 68729 60889 11071 6121 16007 839 42767 67547 4457 353 12241 347
32653 27947 69203 56473 6907 18521 647 1709 71011 75557 491 571 443 577
22013 15107 38561 53381 277 239 17041 487 21569 45121 74413 66739 7481 281
12491 25367 59341 52051 257 337 743 1877 32359 26683 75797 74561 367 479
12527 349 27253 50971 70823 60899 13487 14549 17807 941 34381 53267 5077 379
449 613 38953 44771 69257 56519 12211 24137 821 1861 59107 51817 557 1637
9281 383 13627 827 39181 53407 563 241 18211 6199 23663 45131 76829 75167
541 631 587 1627 59407 53117 263 373 7043 18701 32413 26729 81101 80177

Магическая константа квадрата $S=362710$.
Рекорд Jarek для N=14 - 9170.
Хотелось бы увидеть другие пандиагональные квадраты 14-го порядка, построенные по решёткам Россера. Как я поняла, такие квадраты нашли dimkadimon и dmd.

-- Чт авг 22, 2013 06:14:05 --

Nataly-Mak в сообщении #756464 писал(а):
На конкурс введены два различных оптимальных решения для N=6. Одно из них в точности такое, как в статье A179440, а второе - оригинальное.

И ещё вопрос возникает: нет ли других оригинальных решений (из других наборов чисел) :?:

Нашла в письме два решения, найденные svb:

Код:
1:
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

2:
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

Первое решение не является оригинальным, а вот второе является!
Ранжированный массив чисел, составляющих этот квадрат:

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

Итак, имеем уже три различных оптимальных решения для N=6.
Есть ли ещё оригинальные решения :?:

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


22/03/08

7154
Саратов

(Оффтоп)

Некоторые неточности...

Цитата:
Position Winner Prize
1st Jarek Wroblewski Wroclaw, Poland Fifty United States Dollars
2nd Dmitry Kamenetsky Adelaide, Australia Bragging Rights

Видимо, на конкурсе итоги подводит программа, и Al не стал её изменять.
Фактически победитель Jarek Wroblewski выиграл оба учреждённых мной приза:

1. $50 - за первое место
2. $25 - за максимальное количество рекордов

Я написала вчера AZ об этом, он ответил: "Yes, Jarek wins $75".
То есть он в курсе, что в таблице итогов приз написан неправильно, но исправить это не хочет. Видимо, это связано с программой, которая подводит итоги.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1005 ]  На страницу Пред.  1 ... 34, 35, 36, 37, 38, 39, 40 ... 67  След.

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



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

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


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group