Магические квадраты

[Nataly-Mak]

Всё очень просто: магическая константа квадрата, заполненного только нечётными числами, должна совпадать по чётности с порядком квадрата. Ещё в вашем ряду не существует квадрат порядка 788.

[ice00]

Цитата:

С порядками меньшими 12-ти квадратов не существует (если верить Манси), а вот почему в вашем ряду пропущены порядки 30, 78 и 98 - их что, тоже не существует?

With prime number you have to look at magic constant with the same parity of order: so:

30 97849 => 0 9 not same parity
35 162759 => 5 9 same parity

The table should be:

2 8
3 33
12 4514 
15 9635 
17 14691
22 34926
35 162759 
124 9912840 
191 39541261
774 3337076100
1405 21739504261 
1522 27937907474 
3988 567797235614 
6220 2267788228264
7448 3972430454150
8038 5035120564686
11404 14927463168710

[maxal]

Да, четность я как-то упустил из виду. В диапазоне простых до $10^{11}$ обнаружился еще один подходящий порядок:

63027 2969686034462495

[Nataly-Mak]

В статье, которую я сейчас пишу, есть такая табличка:

n = 12    1, 3, ..., 827   S = 4514
n = 15   1, 3, ..., 1427      S = 9635
n = 17   1, 3, ..., 1879      S = 14691
n = 22   1, 3, ..., 3461      S = 34926
n = 35   1, 3, ..., 9931      S = 162759
n = 124   1, 3, ..., ?           S = 9912840
n = 191   1, 3, ..., ?           S = 39541261

Последние числа массивов для квадратов порядков 124 и 191 мне неизвестны. Какие это числа?
maxal, думаю, что в приведённой вами таблице полезно указать последнее число массива. Хотя, конечно, его легко определить. Но у меня маленький массив простых чисел, содержит всего 2000 чисел.

[ice00]

Цитата:

n = 124 1, 3, ..., ? S = 9912840

168523 (I just open my pascal source code and copy the value)

*** ORDER: 41   - SEQ(8)         FROM: 19         MAGIC=276243
*** ORDER: 42   - SEQ(8)         FROM: 19         MAGIC=298868
*** ORDER: 43   - SEQ(25)        FROM: 97         MAGIC=328957
*** ORDER: 44   - SEQ(80)        FROM: 409        MAGIC=375504
*** ORDER: 45   - SEQ(3)         FROM: 5          MAGIC=372165
*** ORDER: 46   - SEQ(76)        FROM: 383        MAGIC=429614
*** ORDER: 47   - SEQ(10)        FROM: 29         MAGIC=431917
*** ORDER: 48   - SEQ(33)        FROM: 137        MAGIC=472418
*** ORDER: 49   - SEQ(75)        FROM: 379        MAGIC=523341
*** ORDER: 50   - SEQ(70)        FROM: 349        MAGIC=555320

These orders for consecutive primes are now calculated with the new program. As soon as I compile the Windows executable, I will share them.

-- Tue Oct 13, 2009 19:22:01 --

Цитата:

n = 191 1, 3, ..., ? S = 39541261

433981

I just enter my program to generate that 191*191 sequence of primes

[maxal]

Nataly-Mak
вот они:

sage: for m in [12,15,17,22,35,124,191,774,1405,1522,3988,6220,7448,8038,11404,63027]: print([m,nth_prime(m^2)])
....: 
[12, 827]
[15, 1427]
[17, 1879]
[22, 3461]
[35, 9931]
[124, 168523]
[191, 433981]
[774, 8945501]
[1405, 32003669]
[1522, 37956491]
[3988, 293207051]
[6220, 749699149]
[7448, 1096053473]
[8038, 1287003997]
[11404, 2686570057]
[63027, 96313592413]

[ice00]

Orders 41 to 50 for windows are here:

http://www.4shared.com/file/140624365/405970d3/pms41_50.html

[Nataly-Mak]

ice00, maxal
Спасибо. Теперь пробел в моей табличке ликвидирован.

[ice00]

Цитата:

[191, 433981]

It differs from mine, so there is an error in my program that generates sequences..

Ops, no it is equals, maybe I take the wrong line where compare the two values

[Nataly-Mak]

ice00
Среди магических квадратов из последовательных простых чисел первый квадрат, который начинается с числа 3, имеет порядок 35.
Массив для этого квадрата такой: 3, 5, ..., 9931, 9941.
Квадраты каких порядков тоже составляются из подобного массива, начинающегося с числа 3? Я посмотрела приведённые вами таблицы с квадратами до порядка 50, в этих таблицах нет подобных квадратов. А для порядков больше 50 есть ещё такие квадраты?
maxal
у вас есть огромный массив простых чисел до 10^{11}. Тогда, наверное, вы можете сенерировать такой же большой массив и из смитов? Меня очень интересуют наименьшие магические квадраты порядков 3 и 4 из последовательных смитов. tolstopuz сообщил, что проверил смиты до миллиарда и не нашёл такого квадрата порядка 3 (не поняла, только порядка 3 или и порядка 4 тоже). Я проверила по своей программе 220 первых кандидатов для порядка 4. Квадрат не найден. Программы для порядков 3 и 4 у меня есть, они работают очень быстро даже на Бейсике. Но у меня нет большого массива смитов. Кроме того, Бейсик не работает с большими числами. Может быть, вы попробуете решить эту задачу? Для данных порядков программы дают однозначный ответ: существует или не существует квадрат из данного массива чисел. Если он существует, то обязательно будет построен. Так как в этих программах выполняется полный перебор всех вариантов.
Напомню, что первый наименьший квадрат из последовательных смитов имеет порядок 10 (но нет уверенности, что это действительно наименьший, потому что первый кандидат по моей программе не дал магического квадрата; это однако не означает, что он не существует). Квадрат 11-го порядка мне не удалось построить. А начиная с порядка 12 всё пошло прекрасно, по программам ice00 такие квадраты строятся очень быстро.

-- Ср окт 14, 2009 08:52:12 --

Вот код программы для построения нетрадиционного магического квадрата порядка 4 (впрочем, по этой программе можно строить и традиционные магические квадраты, если в качестве исходного массива ввести первые 16 чисел натурального ряда):

10 DIM P(16), Z(16), A(4, 4)
15 OPEN "MK1.txt" FOR INPUT AS #1
17 FOR I = 1 TO 16
18 INPUT #1, P(I)
19 NEXT I
20 CLOSE #1
21 S1 = 0
22 FOR I = 1 TO 16: S1 = S1 + P(I): NEXT I
23 S1 = S1 / 4
32 OPEN "MK2.txt" FOR OUTPUT AS #1
33 FOR I = 1 TO 16
34 FOR J = 1 TO 16
35 PRINT "J"; J
36 IF J = I THEN 530
38 FOR K = 1 TO 16
40 IF K <> I THEN IF K <> J THEN 56
42 GOTO 525
56 FOR L = 1 TO 16
58 IF L <> I THEN IF L <> J THEN IF L <> K THEN 62
60 GOTO 520
62 S = P(I) + P(J) + P(K) + P(L): Z(1) = P(I): Z(2) = P(J): Z(3) = P(K): Z(4) = P(L)
63 IF S <> S1 THEN 520
64 FOR M = 1 TO 16
66 IF M <> I THEN IF M <> J THEN IF M <> K THEN IF M <> L THEN 70
68 GOTO 515
70 B = S - P(J) - P(M) - P(K): Z(5) = P(M)
72 IF B < 1 THEN 515
73 FOR T = 1 TO 5
74 IF B = Z(T) THEN 515
75 NEXT T
78 FOR T = 1 TO 16
80 IF B = P(T) THEN 85
82 NEXT T
84 GOTO 515
85 Z(6) = B
86 FOR N = 1 TO 16
88 IF N <> I THEN IF N <> J THEN IF N <> K THEN IF N <> L THEN IF N <> M THEN IF P(N) <> B THEN 92
90 GOTO 510
92 C = S - B - P(N) - P(M): Z(7) = P(N)
94 IF C < 1 THEN 510
95 FOR T = 1 TO 7
96 IF C = Z(T) THEN 510
98 NEXT T
100 FOR T = 1 TO 16
102 IF C = P(T) THEN 109
104 NEXT T
106 GOTO 510
109 Z(8) = C
110 FOR Q = 1 TO 16
112 IF Q <> I THEN IF Q <> J THEN IF Q <> K THEN IF Q <> L THEN IF Q <> M THEN IF Q <> N THEN IF P(Q) <> B THEN IF P(Q) <> C THEN 116
114 GOTO 505
116 D = S - P(I) - P(Q) - C: Z(9) = P(Q)
118 IF D < 1 THEN 505
119 FOR T = 1 TO 9
120 IF D = Z(T) THEN 505
121 NEXT T
123 FOR T = 1 TO 16
124 IF D = P(T) THEN 127
125 NEXT T
126 GOTO 505
127 Z(10) = D
128 E = S - D - B - P(K)
129 IF E < 1 THEN 505
130 FOR T = 1 TO 10
131 IF E = Z(T) THEN 505
132 NEXT T
134 FOR T = 1 TO 16
135 IF E = P(T) THEN 139
136 NEXT T
138 GOTO 505
139 Z(11) = E
140 F = S - P(Q) - P(J) - P(M)
142 IF F < 1 THEN 505
144 FOR T = 1 TO 11
146 IF F = Z(T) THEN 505
148 NEXT T
152 FOR T = 1 TO 16
154 IF F = P(T) THEN 159
156 NEXT T
158 GOTO 505
159 Z(12) = F
160 FOR R = 1 TO 16
162 IF R <> I THEN IF R <> J THEN IF R <> K THEN IF R <> L THEN IF R <> M THEN IF R <> N THEN IF R <> Q THEN IF P(R) <> B THEN IF P(R) <> C THEN IF P(R) <> D THEN IF P(R) <> E THEN IF P(R) <> F THEN 165
164 GOTO 500
165 G = S - P(I) - P(N) - P(R): Z(13) = P(R)
166 IF G < 1 THEN 500
169 FOR T = 1 TO 13
170 IF G = Z(T) THEN 500
171 NEXT T
172 FOR T = 1 TO 16
173 IF G = P(T) THEN 177
174 NEXT T
176 GOTO 500
177 Z(14) = G
178 H = S - P(R) - P(J) - B
179 IF H < 1 THEN 500
180 FOR T = 1 TO 14
181 IF H = Z(T) THEN 500
182 NEXT T
185 FOR T = 1 TO 16
186 IF H = P(T) THEN 189
187 NEXT T
188 GOTO 500
189 Z(15) = H
190 O = S - C - H - P(L)
192 IF O < 1 THEN 500
194 IF G + P(M) + P(K) + O <> S THEN 500
196 FOR T = 1 TO 15
197 IF O = Z(T) THEN 500
200 NEXT T
208 FOR T = 1 TO 16
210 IF O = P(T) THEN 288
220 NEXT T
222 GOTO 500
288 A(1, 1) = P(I): A(1, 2) = P(R): A(1, 3) = G: A(1, 4) = P(N)
290 A(2, 1) = P(Q): A(2, 2) = P(J): A(2, 3) = P(M): A(2, 4) = F
292 A(3, 1) = D: A(3, 2) = B: A(3, 3) = P(K): A(3, 4) = E
294 A(4, 1) = C: A(4, 2) = H: A(4, 3) = O: A(4, 4) = P(L)
296 W = W + 1: PRINT W: PRINT #1, W
300 FOR X = 1 TO 4
302 FOR Y = 1 TO 4
304 PRINT A(X, Y);
306 NEXT Y
308 PRINT
310 NEXT X
316 PRINT
318 FOR X = 1 TO 4
320 FOR Y = 1 TO 4
322 PRINT #1, A(X, Y);
324 NEXT Y
326 PRINT #1,
328 NEXT X
330 PRINT #1,
500 NEXT R
505 NEXT Q
510 NEXT N
515 NEXT M
520 NEXT L
525 NEXT K
530 NEXT J
535 NEXT I
700 PRINT S1: PRINT
705 CLOSE #1
710 END

В файл MK1.txt помещается исходный массив чисел, в файл MK2.txt выводятся построенные магические квадраты.
Возможно, что программу можно ещё оптимизировать, но, как я уже сказала, она и так работает быстро.
Конечно, для проверки кандидатов из смитов надо бы присоединить к этой программе программу определения кандидатов, то есть подходящих массивов смитов, чтобы подходящий массив определялся и сразу же проверялся.

Задача хороша для всех! Построить наименьшие магические квадраты 3-го и 4-го порядков из последовательных смитов.
Если надо, я приведу и программу для проверки квадратов 3-го порядка.

[ice00]

Цитата:

Квадраты каких порядков тоже составляются из подобного массива, начинающегося с числа 3? Я посмотрела приведённые вами таблицы с квадратами до порядка 50, в этих таблицах нет подобных квадратов. А для порядков больше 50 есть ещё такие квадраты?

Up to order 500, this is the result:

*** ORDER: 35   - SEQ(2)         FROM: 3          MAGIC=163043
*** ORDER: 215   - SEQ(2)        FROM: 3          MAGIC=57689237
*** ORDER: 225   - SEQ(2)        FROM: 3          MAGIC=66684561
*** ORDER: 398   - SEQ(2)        FROM: 3          MAGIC=408313130

[Nataly-Mak]

Спасибо, ice00!
Это тоже интересная серия наименьших магических квдаратов, квадраты этой серии составляются из первых n^2 простых чисел. Ради интереса я построила подобный квадрат 35-го порядка по программе ice00 и поместила его в свою статью, которую сейчас пишу. У ice00 тоже такой квадрат построен. Понятно, что данная группа квадратов входит в группу наименьших магических квадратов из последовательных простых чисел (последовательность А073520).

-- Ср окт 14, 2009 12:45:29 --

Завершила статью "Наименьшие магические квадраты из простых чисел". Статья состоит из 3 частей. Это последняя часть:
http://www.natalimak1.narod.ru/sqmin3.htm
Теперь можно ещё продолжить построение магических квадратов для последовательностей А164843 и А073502. Я построила квадраты только до порядка 31 включительно. А ice00 уже прислал мне программы до порядка 50.
Но я хочу сначала немного доработать статью "Нетрадиционные магические квадраты из чисел Смита".

[maxal]

ice00 в сообщении #251561 писал(а):

Up to order 500, this is the result:

*** ORDER: 35   - SEQ(2)         FROM: 3          MAGIC=163043
*** ORDER: 215   - SEQ(2)        FROM: 3          MAGIC=57689237
*** ORDER: 225   - SEQ(2)        FROM: 3          MAGIC=66684561
*** ORDER: 398   - SEQ(2)        FROM: 3          MAGIC=408313130

Вот все такие порядки для простых вплоть до $10^{11}$:

? s=0; n=0; forprime(p=3,10^11,s+=p;n++;if(issquare(n)&&s%sqrtint(n)==0,m=s\sqrtint(n);if(Mod(m,2)==n,print([sqrtint(n),p,m]))) )
[1, 3, 3]
[35, 9941, 163043]
[215, 562129, 57689237]
[225, 620227, 66684561]
[398, 2137687, 408313130]
[2097, 75056941, 76233525727]
[5205, 514776401, 1302265491787]
[7452, 1097291053, 3979069350494]
[22359, 11035537423, 120433087004965]

[ice00]

I just create the programs for order from 51 to 63. From tommorrow I test them and after release. However this high order is the max I can reach with my programs actually.

If you are wondering how I build order 124 (near the double of actual max order of c++ programs), it was because I use Pascal program that was not full automatic as the c++ programs.

But I'm already starting to think the best way to increase order to c++ programs.

Maybe the solution will need to modify actual main code of the program to allow 128 bits like solution (but I will for sure think how to make it extendible to more that 128 order...)

[Nataly-Mak]

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

  *** ORDER: 3 - FROM: 7695 TO: 7824 MAGIC=23286 NO
            *** ORDER: 4 - SEQ(4) FROM: 58 TO: 454 MAGIC=1082 NO
            *** ORDER: 5 - SEQ(1) FROM: 4 TO: 576 MAGIC=1516 NO
            *** ORDER: 6 - SEQ(13) FROM: 346 TO: 958 MAGIC=3873 ?
            *** ORDER: 7 - SEQ(4) FROM: 58 TO: 1165 MAGIC=4167 ?
            *** ORDER: 8 - SEQ(4) FROM: 58 TO : 1776 MAGIC=6496 ?
            *** ORDER: 9 - SEQ(3) FROM: 27 TO: 2067 MAGIC=9179 ?
            *** ORDER: 10 - SEQ(15) FROM: 378 TO: 2839 MAGIC=15681 ?
            *** ORDER: 10 - SEQ(16) FROM: 382 TO: 2888 MAGIC=15932 YES
            *** ORDER: 11 - SEQ(18) FROM: 438 TO: 3505 MAGIC=20978 YES
            *** ORDER: 12 - SEQ(16) FROM: 382 TO: 4189 MAGIC=26062 YES
            *** ORDER: 13 - SEQ(3) FROM: 27 TO: 4592 MAGIC=28301 YES
            *** ORDER: 14 - SEQ(3) FROM: 27 TO: 5386 MAGIC=35936 YES
            *** ORDER: 15 - SEQ(17) FROM: 391 TO: 6585 MAGIC=50560 YES
            *** ORDER: 16 - SEQ(4) FROM: 58 TO: 7089 MAGIC=55330 YES
            *** ORDER: 17 - SEQ(4) FROM: 58 TO: 8073 MAGIC=66877 YES
            *** ORDER: 18 - SEQ(22) FROM: 526 TO: 9387 MAGIC=88738 YES
            *** ORDER: 19 - SEQ(5) FROM: 85 TO: 9778 MAGIC=94465 YES
            *** ORDER: 20 - SEQ(8) FROM: 166 TO: 11583 MAGIC=111840 YES
            *** ORDER: 21 - SEQ(5) FROM: 85 TO: 12955 MAGIC=128860 YES
            *** ORDER: 22 - SEQ(45) FROM: 913 TO: 15984 MAGIC=177659 YES
            *** ORDER: 23 - SEQ(13) FROM: 346 TO: 16335 MAGIC=179929 YES
            *** ORDER: 24 - SEQ(47) FROM: 922 TO: 18474 MAGIC=230580 YES
            *** ORDER: 25 - SEQ(50) FROM: 1086 TO: 19808 MAGIC=261107 YES
            *** ORDER: 26 - SEQ(29) FROM: 636 TO: 20911 MAGIC=275220 YES
            *** ORDER: 27 - SEQ(19) FROM: 454 TO: 22725 MAGIC=300070 YES
            *** ORDER: 28 - SEQ(48) FROM: 958 TO: 25809 MAGIC=361843 YES
            *** ORDER: 29 - SEQ(41) FROM: 825 TO: 27189 MAGIC=395338 YES
            *** ORDER: 30 - SEQ(63) FROM: 1642 TO: 29172 MAGIC=457169 YES
            *** ORDER: 31 - SEQ(5) FROM: 85 TO: 29227 MAGIC=446645 YES
            *** ORDER: 32 - SEQ(19) FROM: 454 TO: 31846 MAGIC=505470 YES
            *** ORDER: 33 - SEQ(24) FROM: 562 TO: 34182 MAGIC=560168 YES
            *** ORDER: 34 - SEQ(7) FROM: 121 TO: 35793 MAGIC=595423 YES
            *** ORDER: 35 - SEQ(133) FROM: 3294 TO: 42034 MAGIC=788455 YES
            *** ORDER: 36 - SEQ(22) FROM: 526 TO: 40234 MAGIC=726591 YES
            *** ORDER: 37 - SEQ(53) FROM: 1219 TO: 44167 MAGIC=825412 YES
            *** ORDER: 38 - SEQ(20) FROM: 483 TO: 45732 MAGIC=854154 YES
            *** ORDER: 39 - SEQ(7) FROM: 121 TO: 47646 MAGIC=908925 YES
            *** ORDER: 40 - SEQ(56) FROM: 1284 TO: 51846 MAGIC=1044248 YES

В этой таблице представлены первые кандидаты, за исключением квадрата порядка 10, для этого квадрата в таблицу внесён также второй кандидат, для которого мне удалось построить магический квадрат. Для первого кандидата у меня не получился магический квадрат, но его существование остаётся под вопросом.
Все построенные квадраты этой серии смотрите здесь.
Программы ice00 работают безукоризненно, квадраты строятся очень быстро. Например, квадрат 40-го порядка построился за 38 секунд.
Предлагаю участникам форума продолжить данную серию квадратов, ice00 уже разработал программы для построения квадратов порядков 41 - 50.
А главная и очень непростая задача - ликвидировать пробелы в начале этой таблицы, то есть найти подобные квадраты порядков 3 - 9.
Ещё интересный вопрос: каков порядок квадрата в данной серии квадратов, который начинается с первого смита - числа 4. Единственный кандидат пока - квадрат 5-го порядка, но такого квадрата не существует, если верить Бодигриму (он построил наименьший магический квадрат из смитов с магической константой 1831). У меня тоже квадрат 5-го порядка из первых 25 смитов не построился.

-- Чт окт 15, 2009 13:50:38 --

Проверила 800 кандидатов 4-го порядка из последовательных смитов. И ни одного магического квдарата!
Послединие 10 кандидатов (791-й - 800-й):

96656  96675  96681  96696  96702  96720  96727  96781  96819  96880  96918  96921  96922  97006  97015  97017 
 96675  96681  96696  96702  96720  96727  96781  96819  96880  96918  96921  96922  97006  97015  97017  97040 
 96702  96720  96727  96781  96819  96880  96918  96921  96922  97006  97015  97017  97040  97053  97078  97105 
 96918  96921  96922  97006  97015  97017  97040  97053  97078  97105  97141  97152  97161  97167  97186  97222 
 96922  97006  97015  97017  97040  97053  97078  97105  97141  97152  97161  97167  97186  97222  97285  97294 
 97040  97053  97078  97105  97141  97152  97161  97167  97186  97222  97285  97294  97299  97339  97352  97370 
 97053  97078  97105  97141  97152  97161  97167  97186  97222  97285  97294  97299  97339  97352  97370  97404 
 97370  97404  97408  97537  97542  97560  97580  97618  97629  97906  97915  97916  97960  97978  98022  98023 
 97560  97580  97618  97629  97906  97915  97916  97960  97978  98022  98023  98025  98043  98052  98080  98109 
 97906  97915  97916  97960  97978  98022  98023  98025  98043  98052  98080  98109  98113  98120  98126  98144

На этом у меня закончился массив смитов. По своей программе 800 кандидатов я проверила за несколько минут (код программы приведён выше).
Горит исследовательский интерес: где будет магический квадрат 4-го порядка из последовательных смитов и существует ли он вообще? Тот же вопрос о подобном квадрате 3-го порядка. Тут я уже не стала выполнять проверку, так как tolstopuz проверил этот порядок до смитов с миллиардным значением и ничего не нашёл.