2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 56, 57, 58, 59, 60, 61, 62 ... 67  След.
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение15.09.2013, 16:03 


02/11/12
141
64-bit Windows: https://www.dropbox.com/s/rjbx2ot427mkbr9/Pan737.exe

64-bit Linux: https://www.dropbox.com/s/tfdquiu14lcbzaz/panlinux737

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


01/06/12
862
Adelaide, Australia
После 12.5 дней так и не нашёл решение для 743. Нашёл 1026 решений с одной ошибкой. Останавливаю все программы, пусть компьютер отдыхает.

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


19/12/10
1539
dimkadimon в сообщении #763778 писал(а):
Интересно, а сколько требуется времени чтобы проверить один из шаблонов и возможно ли это вообще?

Массив №2 имеет следующее распределение вычетов по модулю 12:
Код:
1 -- 10
3 -- 1
5 -- 12
7 -- 13
11 -- 13

Вот один из шаблонов:
Код:
B B 5 B B 5 7
B 7 5 7 1 7 B
7 7 1 B 5 B 7
7 7 B 7 B 7 B
5 B 5 B 7 5 5
7 5 5 1 1 1 5
1 1 5 1 1 1 3
здесь B означает 11.

Свободные переменные:

$x_{23},x_{24},x_{25},x_{26},x_{27},x_{28},x_{30},x_{31},x_{32},x_{33},x_{34},x_{35},$

$x_{37},x_{38},x_{39},x_{40},x_{41},x_{42},x_{44},x_{45},x_{46},x_{47},x_{48},x_{49}$

Положение тройки фиксировано ($x_{49}$). Среди остальных свободных переменных вычеты по модулю 12 распределены так:
Код:
1 -- 7
5 -- 7
7 -- 4
11 --5


Всего имеется $\mathrm P_{10}^7=604800$ вариантов выбора 1,
$\mathrm P_{12}^7=3991680$ вариантов выбора 5,
$\mathrm P_{13}^4=17160$ вариантов выбора 7,
$\mathrm P_{13}^5=154440$ вариантов выбора 11.

То есть полная проверка этого шаблона потребует рассмотреть примерно $6{,}398\cdot10^{21}$ вариантов.

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


01/06/12
862
Adelaide, Australia
whitefox в сообщении #764467 писал(а):
То есть полная проверка этого шаблона потребует рассмотреть примерно $6{,}398\cdot10^{21}$ вариантов.


Значит мы даже один шаблон не сможем проверить :(

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


19/12/10
1539
С шаблонами по модулю 60 ситуация иная.

Массив №2 имеет следующее распределение вычетов по модулю 60:
Код:
1 -- 2
3 -- 1
5 -- 1
7 -- 3
11 -- 4
13 -- 3
17 -- 3
19 -- 4
23 -- 2
29 -- 3
31 -- 3
37 -- 3
41 -- 2
43 -- 3
47 -- 4
49 -- 2
53 -- 3
59 -- 3
Имеется некоторая свобода в выборе свободных переменных.

Пусть мы выбрали свободные переменные так, чтобы вычеты по модулю 60 распределились среди них следующим образом:
Код:
1 -- 2
3 -- 1
5 -- 1
7 -- 2
11 -- 0
13 -- 2
17 -- 1
19 -- 0
23 -- 2
29 -- 2
31 -- 1
37 -- 1
41 -- 2
43 -- 1
47 -- 0
49 -- 2
53 -- 2
59 -- 2

Тогда полная проверка такого шаблона потребует рассмотреть 10077696 вариантов.

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


06/09/13
2
I switched back to the older pan.exe program (the first version with random seed) and S=737 popped up after running 13 days. 249 1-holes.

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


01/06/12
862
Adelaide, Australia
Congratulations Wes!!! Now we just need to find 733 and we are done :)

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


01/06/12
862
Adelaide, Australia
Для тех кто не знает, Al Zimmermann начал новый конкурс, который обсуждается тут: topic76097.html

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


21/02/10
1594
Екатеринбург
Цитата:
7 x 7 733 Jarek Wroblewski Wroclaw, Poland 10 Oct 2013 08:22
(3,7,173,223,17,197,113), (181,211,11,79,131,23,97), (43,41,149,89,137,191,83), (233,103,107,73,127,31,59), (29,167,101,19,199,67,151), (5,47,139,179,109,61,193), (239,157,53,71,13,163,37)


Jarek Wroblewski нашел таки оптимальное решение для N=7!

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


16/08/05
827
Грандиозно!!!

Изображение

Мечтаю, надеюсь изучить статью с описанием алгоритма, давшего это решение.

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


27/09/13

230
Для чего нужны Дьявольские магические квадраты ?

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


21/02/10
1594
Екатеринбург
Изгонять Дьявола.

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


27/09/13

230
А такой нетрадиционный дьявольский и причем совершенный магический квадрат сможете строить?
(1,78,8,80,6,73),(54,31,47,29,49,36),(64,15,71,17,69,10),(72,13,65,11,67,18),(46,33,53,35,51,28),(9,76,2,74,4,81)

 Профиль  
                  
 
 Posted automatically
Сообщение04.11.2013, 01:39 
Основатель
Аватара пользователя


11/05/05
4193
London
 i  Тема перемещена из форума «Программирование» в форум «Олимпиадные задачи (CS)»
Причина переноса: не указана.

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


22/03/08

7154
Саратов
Замечательные решения Jarek Wroblewski, найденные уже после конкурса - это пандиагональные квадраты из простых чисел и числа 1, можно посмотреть здесь:

http://www.primepuzzles.net/puzzles/puzz_699.htm

Найдены решения до порядка n=13 включительно, однако наименьший опять же только для порядка n=7:

Код:
1 131 229 43 11 181 137
163 41 157 151 109 23 89
67 17 127 31 179 79 233
173 149 107 47 191 5 61
199 53 37 197 101 139 7
59 239 73 97 29 223 13
71 103 3 167 113 83 193
S=733

Конкурс закончился и запал у всех закончился :D
А ведь тут ещё решать и решать!
Даже для порядка n=8 не доказано, что найденное решение минимальное (что с числом 1, что без него).

Когда переписывались немного с Jarek после конкурса, я изложила ему свой алгоритм поиска решений для n=8 и попросила помочь с программной реализацией. Давно это было, летом ещё. Он написал тогда, что в данный момент очень занят, но, возможно, вернётся к этой задаче (не обязательно с моим алгоритмом, можно и с другими подходами).
Ну, скоро и новое лето наступит, а времени на эту задачу так и не нашлось.
Увы и ах!

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1005 ]  На страницу Пред.  1 ... 56, 57, 58, 59, 60, 61, 62 ... 67  След.

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



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

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


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

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