2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 18, 19, 20, 21, 22, 23, 24 ... 67  След.
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение28.07.2013, 10:50 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Для N=9 получилась не совсем хорошая формула: всего 40 неизвестных, независимых 19. Это многовато. Программу написала. Работает долго даже для классического квадрата.

Тут надо пробовать приём, о котором написал dmd --- часть переменных задавать, выбирая их случайным образом из заданного набора комплементарных пар, для остальных переменных полный перебор. Например, для 11 переменных случайный выбор, для 8 - полный перебор, или 13+6.

Не могу обещать, что квадрат такой структуры вообще может составиться из простых чисел.
Надо брать подходящие наборы комплементарных пар и пробовать.
Подходящий набор должен содержать не менее 40 комплементарных пар. Кроме того, смотрите далее замечание о $k/2$.

Известный идеальный квадрат 9-го порядка построен для $k=5386$.
Не забываем, что в пандиагональном квадрате 9-го порядка, составленном из комплементарных пар чисел, присутствует элемент $k/2$, значит, это число должно быть простым. В известном квадрате $k/2=2693$.

-- Вс июл 28, 2013 12:17:03 --

Ближайшие потенциальные константы комплементарности (начиная от $k=5386$ в сторону уменьшения); в скобках указано количество пар для данной константы комплементарности:

Код:
k=5378 (56)
k=5374 (63)
k=5366 (60)
k=5354 (58)
k=5342 (64)
k=5326 (63)

Напомню: для квадрата 9-го порядка $S=9k/2$.

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


22/03/08

7154
Саратов
dmd в сообщении #749528 писал(а):
А не могли бы Вы сделать описание псевдокомплиментарного квадрата 8х8?

dmd
я попробовала сделать схему такого квадрата (по рис. 27 из указанной статьи):

Код:
x1 x9 x17 x25 x5 x13 x21 x29
x10 x2 x26 x18 x14 x6 x30 x22
x27 x19 x11 x3 x31 x23 x15 x7
x20 x28 x4 x12 x24 x32 x8 x16
k-x5+p1 k-x13-p1 k-x21+p3 k-x29-p3 k-x1+p1 k-x9-p1 k-x17+p3 k-x25-p3
k-x14-p1 k-x6+p1 k-x30-p3 k-x22+p3 k-x10-p1 k-x2+p1 k-x26-p3 k-x18+p3
k-x31-p3 k-x23+p3 k-x15-p1 k-x7+p1 k-x27-p3 k-x19+p3 k-x11-p1 K-x3+p1
k-x24+p3 k-x32-p3 k-x8+p1 k-x16-p1 k-x20+p3 k-x28-p3 k-x4+p1 k-x12-p1

При рассмотрении этой схемы обнаружила, что напрасно волновалась по поводу параметров $p_i$, так как при описании квадрата они все исчезают.

Описать этот квадрат сами сможете?
Описание получится, как для совершенного квадрата 8-го порядка, только без условия равенства всех сумм в квадратах 2х2. По-моему, вы как раз по этой формуле уже и работали (как сообщили выше).
Таким образом, описание вот в таком виде ничего нового не дало.

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


16/08/05
993
Nataly-Mak в сообщении #749791 писал(а):
Известный идеальный квадрат 9-го порядка построен для $k=5386$.
Не забываем, что в пандиагональном квадрате 9-го порядка, составленном из комплементарных пар чисел, присутствует элемент $k/2$, значит, это число должно быть простым. В известном квадрате $k/2=2693$.

Ближайшие потенциальные константы комплементарности (начиная от $k=5386$ в сторону уменьшения); в скобках указано количество пар для данной константы комплементарности:

Код:
k=5378 (56)
k=5374 (63)
k=5366 (60)
k=5354 (58)
k=5342 (64)
k=5326 (63)

Напомню: для квадрата 9-го порядка $S=9k/2$.


Полный список кандидатов довольно большой

(Оффтоп)

Код:
? forstep(k=5386,1,-2,if(isprime(k/2),K=Set();forprime(p=3,k,q=k-p;if(isprime(q),K=setunion(K,[p]);K=setunion(K,[q])));if(#K>79,print("k= ",k,"   (",(#K-1)/2,")    S= ",9*k/2))));
k= 5386    (67)    S= 24237
k= 5378    (56)    S= 24201
k= 5374    (63)    S= 24183
k= 5366    (60)    S= 24147
k= 5354    (58)    S= 24093
k= 5342    (64)    S= 24039
k= 5326    (63)    S= 23967
k= 5318    (57)    S= 23931
k= 5314    (61)    S= 23913
k= 5294    (62)    S= 23823
k= 5266    (58)    S= 23697
k= 5242    (63)    S= 23589
k= 5234    (62)    S= 23553
k= 5218    (59)    S= 23481
k= 5186    (60)    S= 23337
k= 5182    (68)    S= 23319
k= 5158    (59)    S= 23211
k= 5114    (64)    S= 23013
k= 5102    (55)    S= 22959
k= 5098    (67)    S= 22941
k= 5086    (60)    S= 22887
k= 5078    (50)    S= 22851
k= 5062    (60)    S= 22779
k= 5042    (58)    S= 22689
k= 5006    (62)    S= 22527
k= 4954    (63)    S= 22293
k= 4946    (56)    S= 22257
k= 4934    (61)    S= 22203
k= 4918    (56)    S= 22131
k= 4894    (59)    S= 22023
k= 4882    (62)    S= 21969
k= 4874    (52)    S= 21933
k= 4846    (57)    S= 21807
k= 4834    (62)    S= 21753
k= 4822    (61)    S= 21699
k= 4798    (57)    S= 21591
k= 4786    (58)    S= 21537
k= 4778    (55)    S= 21501
k= 4766    (53)    S= 21447
k= 4762    (58)    S= 21429
k= 4754    (59)    S= 21393
k= 4742    (57)    S= 21339
k= 4714    (54)    S= 21213
k= 4702    (56)    S= 21159
k= 4694    (55)    S= 21123
k= 4682    (53)    S= 21069
k= 4678    (56)    S= 21051
k= 4666    (55)    S= 20997
k= 4622    (53)    S= 20799
k= 4618    (56)    S= 20781
k= 4594    (56)    S= 20673
k= 4586    (53)    S= 20637
k= 4574    (49)    S= 20583
k= 4562    (51)    S= 20529
k= 4546    (54)    S= 20457
k= 4538    (53)    S= 20421
k= 4534    (56)    S= 20403
k= 4502    (51)    S= 20259
k= 4486    (60)    S= 20187
k= 4478    (47)    S= 20151
k= 4474    (56)    S= 20133
k= 4442    (49)    S= 19989
k= 4426    (53)    S= 19917
k= 4414    (48)    S= 19863
k= 4406    (50)    S= 19827
k= 4358    (49)    S= 19611
k= 4322    (48)    S= 19449
k= 4306    (57)    S= 19377
k= 4286    (55)    S= 19287
k= 4282    (58)    S= 19269
k= 4274    (54)    S= 19233
k= 4262    (50)    S= 19179
k= 4258    (52)    S= 19161
k= 4226    (52)    S= 19017
k= 4222    (55)    S= 18999
k= 4198    (52)    S= 18891
k= 4178    (51)    S= 18801
k= 4174    (46)    S= 18783
k= 4166    (54)    S= 18747
k= 4162    (56)    S= 18729
k= 4138    (55)    S= 18621
k= 4126    (49)    S= 18567
k= 4106    (52)    S= 18477
k= 4078    (50)    S= 18351
k= 4058    (43)    S= 18261
k= 4054    (54)    S= 18243
k= 4034    (53)    S= 18153
k= 4022    (42)    S= 18099
k= 4006    (51)    S= 18027
k= 3998    (46)    S= 17991
k= 3994    (51)    S= 17973
k= 3986    (53)    S= 17937
k= 3974    (51)    S= 17883
k= 3958    (52)    S= 17811
k= 3946    (51)    S= 17757
k= 3902    (42)    S= 17559
k= 3898    (49)    S= 17541
k= 3866    (50)    S= 17397
k= 3862    (46)    S= 17379
k= 3826    (51)    S= 17217
k= 3814    (48)    S= 17163
k= 3802    (45)    S= 17109
k= 3778    (47)    S= 17001
k= 3758    (48)    S= 16911
k= 3754    (41)    S= 16893
k= 3746    (45)    S= 16857
k= 3742    (43)    S= 16839
k= 3734    (47)    S= 16803
k= 3722    (49)    S= 16749
k= 3694    (46)    S= 16623
k= 3662    (45)    S= 16479
k= 3646    (51)    S= 16407
k= 3622    (47)    S= 16299
k= 3602    (47)    S= 16209
k= 3578    (46)    S= 16101
k= 3574    (49)    S= 16083
k= 3566    (46)    S= 16047
k= 3554    (42)    S= 15993
k= 3518    (43)    S= 15831
k= 3494    (47)    S= 15723
k= 3482    (44)    S= 15669
k= 3466    (41)    S= 15597
k= 3446    (41)    S= 15507
k= 3442    (47)    S= 15489
k= 3418    (49)    S= 15381
k= 3398    (44)    S= 15291
k= 3394    (47)    S= 15273
k= 3338    (41)    S= 15021
k= 3334    (43)    S= 15003
k= 3326    (47)    S= 14967
k= 3314    (43)    S= 14913
k= 3274    (46)    S= 14733
k= 3254    (43)    S= 14643
k= 3238    (45)    S= 14571
k= 3226    (42)    S= 14517
k= 3214    (41)    S= 14463
k= 3194    (42)    S= 14373
k= 3166    (43)    S= 14247
k= 3158    (41)    S= 14211
k= 3142    (43)    S= 14139
k= 3118    (40)    S= 14031
k= 3106    (45)    S= 13977
k= 3098    (47)    S= 13941
k= 3046    (43)    S= 13707
k= 3022    (41)    S= 13599
k= 2998    (45)    S= 13491
k= 2986    (43)    S= 13437
k= 2974    (48)    S= 13383
k= 2906    (40)    S= 13077
k= 2902    (46)    S= 13059
k= 2894    (44)    S= 13023
k= 2866    (40)    S= 12897
k= 2854    (41)    S= 12843
k= 2846    (40)    S= 12807
k= 2746    (41)    S= 12357
k= 2734    (41)    S= 12303
k= 2722    (41)    S= 12249
k= 2554    (40)    S= 11493
?

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


22/03/08

7154
Саратов
Описание совершенного квадрата 6-го порядка:

Код:
x1+x2+x3+x4+x5+x6=3k
x7+x8+x9+x10+x11+x12=3k
x13+x14+x15+x16+x17+x18=3k
x1+x7+x13-x4-x10-x16=0
x2+x8+x14-x5-x11-x17=0
x3+x9+x15-x6-x12-x18=0
x1+x2+x7+x8=2k
x2+x3+x8+x9=2k
x3+x4+x9+x10=2k
x4+x5+x10+x11=2k
x5+x6+x11+x12=2k
x7+x8+x13+x14=2k
x8+x9+x14+x15=2k
x9+x10+x15+x16=2k
x10+x11+x16+x17=2k
x11+x12+x17+x18=2k
x1+x6-x16-x15=0
x1+x7+x6+x12=2k
x7+x13+x12+x18=2k
x1+x2-x16-x17=0
x2+x3-x17-x18=0
x3+x4-x18-x13=0
x4+x5-x13-x14=0
x5+x6-x14-x15=0

Классического совершенного квадрата 6-го порядка не существует.
Пример совершенного квадрата 6-го порядка из произвольных натуральных чисел:

Код:
3 199 53 159 43 209
167 75 117 115 127 65
133 69 183 29 173 79
63 179 13 219 23 169
107 95 157 55 147 105
193 49 143 89 153 39

$k=222$

$S=3k$

dmd
прошу решить систему ещё разок :-)

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


16/08/05
993

(Оффтоп)

Код:
x2 = -x1 + x16 + x17
x3 = x1 - x16 + x18
x4 = 3 k - x1 - 2 x17 - 2 x18
x5 = -3 k + x1 + x16 + 3 x17 + 2 x18
x6 = 3 k - x1 - x16 - 2 x17 - x18
x7 = -(k/2) - x1 + x16 + x17 + x18
x8 = (5 k)/2 + x1 - 2 x16 - 2 x17 - x18
x9 = -(k/2) - x1 + 2 x16 + x17
x10 = -(k/2) + x1 - x16 + x17 + x18
x11 = (5 k)/2 - x1 - 2 x17 - x18
x12 = -(k/2) + x1 + x17
x13 = 3 k - x16 - 2 x17 - 2 x18
x14 = -3 k + 2 x16 + 3 x17 + 2 x18
x15 = 3 k - 2 x16 - 2 x17 - x18

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


22/03/08

7154
Саратов
dmd
спасибо!
Отличная формула. Я насчитала 14 зависимых переменных, значит свободных всего 4.
Сейчас напишу программу по этой формуле и проверю свой наименьший совершенный квадрат из различных простых чисел - действительно ли он наименьший.

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


22/03/08

7154
Саратов
Эх, как работает программа с 4 свободными переменными!
Известный совершенный квадрат из простых чисел проверила по программе, он построился мгновенно (в массиве 532 числа, 266 пар крмплементарных чисел, $k=9930$).

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

Код:
1  110  180  19  92  198
196  93  17  184  105  5
13  98  192  7  104  186
181  108  2  199  90  20
16  95  195  4  107  183
193  96  14  187  102  8
S=600

Этот квадрат тоже построился мгновенно.
Теперь надо проверить по этой программе все потенциальные константы комплементарности, а их очень много (начиная от 9930 и далее по убыванию с шагом 2). Всё это я уже проделала раньше по другой программе, которая у меня работала намного медленнее, ибо была написана по другому алгоритму.

Кстати, интересно: магическая константа соверешнного квадрата 6-го порядка из простых чисел равна 29790, а квадрата 8-го порядка - 24024. Может быть, всё-таки квадрат 6-го порядка у меня не наименьший? Но по своей прежней программе я не нашла квадрат с меньшей магической константой.

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


22/03/08

7154
Саратов
Проверила все потенциальные константы комплементарности для совершенного квадрата 6-го порядка по новой программе. Очень быстро проверились. Квадрат с меньшей магической константой не найден.
Итак, наименьший совершенный квадрат 6-го порядка из различных простых чисел имеет магическую константу 29790.
Для двух порядков - 4,6 - вопрос с наименьшими совершенными квадратами из простых чисел решён.
Для порядков 8,10 есть общие формулы, но к сожалению, программы работают не так быстро, как для порядка 6. Буду проверять решение для порядка 8 ($S=24024$) на предмет минимальности, а для порядка 10 пока вообще нет никакого решения.

Ради интереса решила поискать второй совершенный квадрат 6-го порядка из простых чисел. Запустила программу теперь от константы комплементарности 9930 в сторону увеличения с шагом 2. Программа дошла уже до константы 10710 (340 пар комплементарных чисел), решение пока не найдено. Трудно составить совершенный квадрат :-)

-- Пн июл 29, 2013 07:33:47 --

Оригинальная идея :roll:

Берём минимальный квадрат Стенли 4-го порядка:

Код:
3 11 17 41
5 13 19 43
23 31 37 61
59 67 73 97

Достраиваем этот квадрат до квадрата Стенли 5-го порядка (процедура, смутившая иностранцев :D ):
Код:
3 11 17 41 x1
5 13 19 43 x1+2
23 31 37 61 x1+20
59 67 73 97 x1+56
x2 x2+8 x2+14 x2+38 x1+x2-3

Применяем к этому квадрату преобразование Россера
$A(i,j) = B(2i - j,-i + 2j)$
и получаем регулярный пандиагональный квадрат 5-го порядка:

Код:
3 x1+20 x2+38 19 67
x2+14 13 59 x1 61
x1+56 41 37 x2+8 5
31 x2 x1+2 97 17
43 73 11 23 x1+x2-3

И вот формула регулярного пандиагонального квадрата 5-го порядка:

$x_1+x_2+147=S$

($S$ - магическая константа квадрата)

Понятно, что формула эта не является общей. Однако какая простая формула!

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

Задаём x1 и x2 соверешенно произвольно:

$x_1=2$, $x_2=10$

получаем регулярный пандиагональный квадрат с магической константой $S=159$:

Код:
3 22 48 19 67
24 13 59 2 61
58 41 37 18 5
31 10 4 97 17
43 73 11 23 9

Можно задать магическую константу и по ней построить регулярный пандиагональный квадрат из произвольных натуральных чисел. С произвольными натуральными числами всё просто.
Если строить квадрат из простых чисел, тогда:

1. задаём простые x1 и x2 из массива простых чисел, в котором выброшены числа, входящие в исходный квадрат Стенли 4-го порядка;
2. проверяем на простоту и уникальность следующие 7 элементов:

$x_1+2$, $x_1+20$, $x_1+56$, $x_2+8$, $x_2+14$, $x_2+38$, $x_1+x_2-3$

Думаю, что минимальное решение для N=5 ($S=395$) эта формула не даст.

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


22/03/08

7154
Саратов
Второй совершенный квадрат 6-го порядка из простых чисел нашёлся :!:

Поскольку для N=6 оптимальное решение известно (есть в OEIS), покажу этот совершенный квадрат:

Код:
1627  9181  5647  6247  4561  10267
10163  4049  6143  6983  7229  2963
4657  6151  8677  3217  7591  7237
6263  7949  2243  10883  3329  6863
5527  5281  9547  2347  8461  6367
9293  4919  5273  7853  6359  3833
S=37530

$k=12510$, 317 комплементарных пар чисел.

Здорово программа работает :-) Такую бы для N=8.
Это первый интересный результат, полученный из всех общих и частных формул, которые мы тут насочинили.

P.S. В конкурсе этот квадрат тянет на 0.01 балла :D

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


22/03/08

7154
Саратов
Nataly-Mak в сообщении #750064 писал(а):
Понятно, что формула эта не является общей.

А почему бы не сделать общую формулу регулярного пандиагонального квадрата 5-го порядка? Вот она:

Код:
x1 x5+x7-x1 x4+x9-x1 x3+x6-x1 x2+x8-x1
x3+x9-x1 x2+x6-x1 x8 x5 x4+x7-x1
x5+x8-x1 x4 x3+x7-x1 x2+x9-x1 x6
x2+x7-x1 x9 x5+x6-x1 x4+x8-x1 x3
x4+x6-x1 x3+x8-x1 x2 x7 x5+x9-x1

Свободными элементами являются $x_i$, i=1,2,3,...,9.
При этом свободные элементы связаны с магической константой квадрата следующей формулой:

$x_2+x_3+x_4+x_5+x_6+x_7+x_8+x_9-3x_1=S$

Из этой формулы хорошо видно, что при заданной магической константе квадрата мы имеем 8 свободных элементов.

Формулу проверила на своём регулярном пандиагональном квадрате из простых чисел, который был построен мной ещё до знакомства со статьёй Россера совсем другим методом (из арифметических прогрессий с одинаковой разностью):

Код:
7 337 131 197 181
227 241 37 277 71
307 11 167 271 97
211 127 367 41 107
101 137 151 67 397

Этот квадрат не наименьший, его магическая константа $S=853$.
Формула верная.
Можно проверить формулу и на оптимальном решении $S=395$, которое Pavlovsky получил как раз по алгоритму Россера.

-- Пн июл 29, 2013 15:06:22 --

Вот наименьший регулярный пандиагональный квадрат:

Код:
5 167 127 23 73
113 13 71 131 67
197 31 53 103 11
43 101 137 97 17
37 83 7 41 227

Этот квадрат получается по общей формуле при следующих значениях свободных переменных:

$x_1=5$, $x_2=7$, $x_3=17$, $x_4=31$, $x_5=131$, $x_6=11$, $x_7=41$, $x_8=71$, $x_9=101$.

В этой формуле нет ничего нового, просто записан алгоритм Россера.
Точно такую же формулу можно написать и для N=7,11,13... (для всех порядков, являющихся простыми числами). Однако регулярные пандиагональные квадраты уже мало интересны, так как они не дают оптимальных решений. Оптимальное решение по этому алгоритму получается только для N=5, так как все пандиагональные квадраты 5-го порядка являются регулярными, нерегулярных просто нет.

P.S. Наверное, в выражении "регулярный пандиагональный квадрат 5-го порядка" слово "регулярный" является лишним.

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


22/03/08

7154
Саратов
Nataly-Mak в сообщении #750157 писал(а):
А почему бы не сделать общую формулу регулярного пандиагонального квадрата 5-го порядка? Вот она:

Код:
x1 x5+x7-x1 x4+x9-x1 x3+x6-x1 x2+x8-x1
x3+x9-x1 x2+x6-x1 x8 x5 x4+x7-x1
x5+x8-x1 x4 x3+x7-x1 x2+x9-x1 x6
x2+x7-x1 x9 x5+x6-x1 x4+x8-x1 x3
x4+x6-x1 x3+x8-x1 x2 x7 x5+x9-x1

Свободными элементами являются $x_i$, i=1,2,3,...,9.
При этом свободные элементы связаны с магической константой квадрата следующей формулой:

(1) $x_2+x_3+x_4+x_5+x_6+x_7+x_8+x_9-3x_1=S$

Из этой формулы хорошо видно, что при заданной магической константе квадрата мы имеем 8 свободных элементов.

Хочу попробовать поискать по этой формуле пандиагональный квадрат 5-го порядка из последовательных простых чисел
(как я уже писала, из последовательных простых чисел не удалось построить пандиагональные квадраты порядков 4 и 5, а такой квадрат 6-го порядка существует, он есть в OEIS)
Мы имеем массив последовательных простых чисел, состоящий ровно из 25 чисел. Массив должен удовлетворять только одному условию: сумма всех чисел массива $M$ должна быть кратна 5. Магическая константа составляемого квадрата определена: $S=M/5$.
Далее, поскольку в массиве ровно 25 чисел, мы можем зафиксировать любой угловой элемент квадрата, например, зафиксируем элемент $x_1$.
Из формулы (1) видим, что свободных элементов остаётся всего 7 штук. Это неплохо: перебор 7 свободных элементов из 24 чисел.
Сейчас напишу программу и посмотрю, как быстро она будет работать.

maxal в своё время искал пандиагональные квадраты порядков 4 и 5 из последовательных простых чисел, но не нашёл. Не помню, сколько потенциальных массивов он проверил для n=5. Для n=4 он проверил простые числа в диапазоне до 7,5 триллионов натуральных чисел. Удивительно! Пандиагональный квадрат 6-го порядка из последовательных простых чисел составился, а для порядков 4 и 5 такие квадраты найти не удаётся.

-- Вт июл 30, 2013 06:22:47 --

(Оффтоп)

На конкурсе тишина. Кто-то сетовал, что мало времени - 2 месяца :D
Остаётся только ждать 21 августа, когда Jarek сможет рассказать о своём алгоритме. Мне очень хочется узнать его алгоритм.
Зато конкурс очень хорошо меня "завёл": позанималась от души этой задачей. Не нашла слишком много новых результатов, но кое-что интересное получила. Например, общие формулы совершенных магических квадратов порядков 4 - 10. Формулы для порядков 6 - 10 программно реализовала. Для порядка 6 программа работает очень быстро. Удалось найти второй совершенный квадрат из простых чисел. Для порядков 8 - 10 буду продолжать поиск решений.

Вчера запостила задачу о совершенных магических квадратах в дискуссионную группу. Al удалил пост. Прислал объяснение, почему удалил: не туда запостила :-) Вообще-то совершенные магические квадраты являются пандиагональными, поэтому они имеют самое непосредственное отношение к конкурсу "Pandiagonal magic squares".
Ну, спорить не стала, перенесла пост в его "дочернюю" группу - AZs Programming Contests --- Off Topic. Пусть будет оффтопик :-) Хотя как в основной группе, так и в "дочерней" сейчас вообще ничего не пишут.

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


22/03/08

7154
Саратов
Программу построения пандиагонального квадрата 5-го порядка из массива, состоящего из 25 чисел, написала. Выполняется очень быстро. Протестировала на классическом квадрате и на квадрате из последовательных натуральных чисел.
Это квадрат из последовательных натуральных чисел:

Код:
23  41  47  35  29
45  34  28  26  42
31  27  40  44  33
39  43  36  32  25
37  30  24  38  46
S=175

Теперь надо найти много-много потенциальных массивов из последовательных простых чисел и проверять их по этой программе.

Вспоминаю, как создавалась первая программа построения пандиагональных квадратов 5-го порядка. История хорошая штука :-)
Массив я тоже брала из 25 чисел. Однако программа у меня так быстро не выполнялась. Может быть, полученная сейчас формула самая эффективная? :wink:
Я даже просила своего итальянского коллегу Stefano Tognon переписать эту программу на C++, что он и сделал. Эта версия работала намного быстрее, чем программа на Бейсике. А сейчас-то у меня программа тоже на Бейсике написана, а работает быстро.
Сейчас ещё протестирую её на квадратах из простых чисел (выше показаны эти два квадрата с магическими константами 853 и 395). Вводим в программу массив из 25 чисел, которые составляют известный квадрат, и получаем готовое решение.

-- Вт июл 30, 2013 08:37:41 --

Готово, протестировала.
Ввожу массив из известного квадрата:

Код:
5 167 127 23 73
113 13 71 131 67
197 31 53 103 11
43 101 137 97 17
37 83 7 41 227

Получаю решение в долю секунды:

Код:
5  113  43  37  197
13  97  131  101  53
227  41  23  73  31
83  7  127  167  11
67  137  71  17  103
S=395

Ввожу второй массив из известного квадрата:

Код:
7 337 131 197 181
227 241 37 277 71
307 11 167 271 97
211 127 367 41 107
101 137 151 67 397

Получаю решение, ну очень быстро:

Код:
7  227  211  101  307
241  41  277  127  167
397  67  197  181  11
137  151  131  337  97
71  367  37  107  271
S=853

Формула работает отлично. Однако не надо забывать, что требуется проверить очень большое количество потенциальных массивов.

-- Вт июл 30, 2013 08:45:36 --

О-о-о!
Jarek тоже работает отлично

Цитата:
1 15.00 Jarek Wroblewski Wroclaw, Poland 30 Jul 2013 04:30
2 7.38 Dmitry Kamenetsky Adelaide, Australia 12 Jul 2013 00:11
3 7.26 Wes Sampson La Jolla, California, United States 13 Jul 2013 01:27
4 6.26 Dmitry Ezhov Sterlitamak, Russia 14 Jul 2013 21:09
5 6.00 Valery Pavlovsky Ekaterinburg, Russia 22 Jun 2013 20:28

Первоначальные 12 баллов превратились в 6 баллов.
dmd улучшил известные результаты на 0.26 балла, dimkadimon - на 1.38 балла. Хотя первоначально улучшения были, конечно, больше; это уже с поправкой на новые результаты Jarek.

-- Вт июл 30, 2013 08:57:23 --

Задала вопрос о пандиагональных квадратах порядков 4 и 5 из последовательных простых чисел в дискуссионной группе:

Цитата:
The sequence A073523 (OEIS) - smallest pandiagonal square of order 6 of
consecutive primes.
I not know of a similar squares of order 4, 5, 7, ...
Does anyone know of such squares?

Ответа нет. Значит, никто не видел таких квадратов :?:

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


22/03/08

7154
Саратов
Вспомнила о магических квадратах 5-го порядка (не пандиагональных) из последовательных простых чисел. В статье нашла такую таблицу:

(Оффтоп)

Код:
Массив чисел  S  Комментарии
13, …, 113 313  существует
59, …, 179 577  существует
79, …, 199 703  существует
97, …, 227 785  существует
107, …, 239 865  существует
127, …, 257 949  существует
157, …, 283 1111  существует
167, …, 307 1167  не существует
227, …, 367 1461  не существует
269, …, 419 1703 существует
337, …, 479 2041  существует
347, …, 487 2071  существует
383, …, 541 2283  не существует
439, …, 599 2579  существует
457, …, 613 2677  существует
461, …, 617 2709  не существует
479, …, 641 2809  существует
563, …, 709 3157  существует
601, …, 757 3379  существует
607, …, 761 3411  не существует
631, …, 797 3545  существует
691, …, 859 3897  не существует
719, …, 881 4001  существует
743, …, 911 4135  существует
827, …, 997 4557  не существует
881, …, 1049 4839  не существует
883, …, 1051 4873  существует
947, …, 1103 5143  существует
977, …, 1129 5271  не существует
1009, …, 1171 5409  не существует
1021, …, 1193 5513  существует
1031, …, 1201 5549  существует
1049, …, 1223 5659  существует
1051, …, 1229 5695  существует
1061, …, 1231 5731  существует
1093, …, 1279 5917  существует
1097, …, 1283 5955  не существует
1109, …, 1291 6031  существует
1151, …, 1307 6177  не существует
1171, …, 1327 6277  существует
1181, …, 1361 6315  не существует
1201, …, 1381 6427  существует
1223, …, 1423 6547  существует
1327, …, 1523 7203  не существует
1481, …, 1627 7779  не существует
1487, …, 1657 7845  не существует
1499, …, 1669 7951  существует
1523, …, 1697 8027  существует
1579, …, 1753 8313  не существует
1583, …, 1759 8349  не существует

Понятно, что если из массива не составился обычный магический квадрат, то и пандиагональный тоже не составится.
Вот уже есть несколько потенциальных массивов для проверки, но это очень мало.
Эти массивы сейчас проверю.

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


22/03/08

7154
Саратов
Первые потенциальные массивы проверила. Решения, конечно, не нашла.
Ну, maxal, наверное, эти массивы проверял.
До какого простого числа он тогда проверил? Надо поискать в теме "Магические квадраты", может, он писал что-то об этом.

Дальше надо сделать хорошую программу, то есть сделать непрерывную проверку - массив за массивом, а не по одному массиву проверять, как я делаю сейчас.

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


22/03/08

7154
Саратов
К конкурсу подключилась Италия :-)

Цитата:
22 1.00 Maurizio Morandi Sassuolo, Italy 1 Aug 2013 05:09

Пока довольно робко. 1 балл - известное решение для N=6? Но вполне может быть, что это какие-то другие решения, давшие в сумме 1 балл.

Jarek начал дальше уменьшать 6 баллов :wink:

Куда-то пропал Pavlovsky. Может, отдыхать уехал? Подальше от цивилизации и от всяких конкурсов.

Пока так и не дождалась Vovka17, а на приглашение он ответил и в конкурсе участвовать собирался.

Совершенно убивает alexBlack :-(
Он ведь раньше довольно много занимался магическими квадратами, в том числе и пандиагональными квадратами из простых чисел. У него есть оригинальные решения - идеальные квадраты из простых чисел для N=7,9. У него есть замечательная программа поиска пандиагональных квадратов 6-го порядка, с помощью которой он без труда мог бы найти решение для N=6, если не оптимальное, то довольно близкое.
Не могу понять, что такое его результат - 0.01 балла.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1005 ]  На страницу Пред.  1 ... 18, 19, 20, 21, 22, 23, 24 ... 67  След.

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



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

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


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

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