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

[maxal]

Pavlovsky в сообщении #342664 писал(а):

Возьмем одно число вида 6k-1 и четыре числа вида 6k+1. В сумме они дадут 6k+3.

Да, аргументация тут должна быть изощреннее. Но можно и в лоб - полным перебором легко показать, что такого пандиагонального квадрата 5x5 не существует уже по модулю 3 (т.е. когда один элемент равен 0, остальные $\pm 1$, и магическая сумма нулевая по модулю 3).

[Nataly-Mak]

Вот составила таблицы всех МК из простых и из смитов. Если где-то ошиблась, поправьте, пожалуйста.

[Pavlovsky]

maxal в сообщении #342667 писал(а):

Но можно и в лоб - полным перебором легко показать, что такого пандиагонального квадрата 5x5 не существует уже по модулю 3 (т.е. когда один элемент равен 0, остальные $\pm 1$, и магическая сумма нулевая по модулю 3).

Рассматривать четные магические суммы нет смысла для нечетных простых чисел и нечетных порядков МК. Так что при переборе магическую сумму лучше рассматривать равной 3 по модулю 6.

Перебором для МК 5х5 доказать можно. Но вы же понимаете, что как только будет решен вопрос для МК 5х5, то я тут же задам тот же впорос для МК nхn, где n нечетное.

-- Чт авг 05, 2010 10:13:58 --

Хорошие таблички.

Nataly-Mak в сообщении #342668 писал(а):

Уверен, что пандиагональный МК 10х10 с магической суммой 4242 не является наименьшим.

[Nataly-Mak]

Это пандиагональный квадрат 6-го порядка из смитов, полученный из найденного maxal'ем ассоциативного квадрата преобразованием 3-х квадратов:

2722 2326 1255 4054 958 2965
2182 391 2902 634 4306 3865
4198 2605 2839 4414 58 166
706 3802 1795 2038 2434 3505
4126 454 895 2578 4369 1858
346 4702 4594 562 2155 1921

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

[Nataly-Mak]

Смиты как всегда ужасно капризничают. Идеальный квадрат 5-го порядка из простых чисел нашла за 5 минут, из смитов ни в какую
Программа та же самая, но не складывается идеальный квадрат и всё тут. Уже проверила до значения магической константы 87410. Может, где-то у меня прокол...

maxal
что говорит ваша программа по поводу идеального квадрата 5-го порядка из смитов?

-- Чт авг 05, 2010 15:02:48 --

И ещё одну порцию наборов комплементарных пар смитов проверила. Теперь уже до значения магической константы 94970. Нет идеального квадрата

[maxal]

Nataly-Mak в сообщении #342699 писал(а):

что говорит ваша программа по поводу идеального квадрата 5-го порядка из смитов?

Минимальный имеет константу 1700030:

357286, 337486, 402718, 512266, 90274, 
325246, 434794, 170266, 352246, 417478, 
165226, 432238, 340006, 247774, 514786, 
262534, 327766, 509746, 245218, 354766, 
589738, 167746, 277294, 342526, 322726

-- Thu Aug 05, 2010 08:18:47 --

Pavlovsky в сообщении #342669 писал(а):

Рассматривать четные магические суммы нет смысла для нечетных простых чисел и нечетных порядков МК. Так что при переборе магическую сумму лучше рассматривать равной 3 по модулю 6.

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

Pavlovsky в сообщении #342669 писал(а):

Перебором для МК 5х5 доказать можно. Но вы же понимаете, что как только будет решен вопрос для МК 5х5, то я тут же задам тот же впорос для МК nхn, где n нечетное.

Вполне допускаю, что для больших $n$ такие квадраты существуют. Дело в том, что элементы пандиагонального квадрата должны удовлетворять $4n$ уравнениям по модулю 3, каждое в среднем с вероятностью $\frac{1}{3}$, в то время как самих квадратов из $\pm 1$ существует не менее $2^{n^2-n}$ (считая, что один ряд с 0 фиксирован и задает требуемую нулевую сумму по модулю 3). Ожидаемое количество таких квадратов равно примерно $2^{n^2-n}3^{-4n}$, что с ростом $n$ стремится к бесконечности.
Ну а как только квадрат по модулю 3 построен, то существование соответствующих простых можно вывести из правдоподобной гипотезы http://mathworld.wolfram.com/k-TupleConjecture.html

[Nataly-Mak]

О! Вот спасибо, что вы его нашли. Долго же мне ещё пришлось бы проверять
Ну и смиты! Такие фокусы выкидывают.

-- Чт авг 05, 2010 18:09:17 --

Взяла 12 комплементарных пар смитов из вашего квадрата и дала их своей программе. Программа квадрат мгновенно построила:

165226  512266  357286  417478  247774 
 342526  402718  90274  509746  354766 
 434794  352246  340006  327766  245218 
 325246  170266  589738  277294  337486 
 432238  262534  322726  167746  514786

Он не эквивалентен вашему квадрату.

Значит, с программой у меня всё в порядке.

Интересно, сколько же комплементарных пар смитов с суммой в паре 680012? Наверное, очень много?

[maxal]

Nataly-Mak в сообщении #342730 писал(а):

Интересно, сколько же комплементарных пар смитов с суммой в паре 680012? Наверное, очень много?

556 пар:

94, 391, 517, 706, 778, 958, 1219, 1903, 1908, 2578, 2911, 3694, 4198, 4306, 4954, 5098, 5458, 5818, 6188, 6816, 8014, 8518, 9094, 9229, 9598, 9778, 10489, 10664, 10705, 10736, 11358, 13765, 16078, 16474, 16568, 16735, 17221, 18355, 18805, 18994, 19280, 19678, 20074, 20578, 20974, 21478, 22738, 24394, 24538, 24754, 25078, 25429, 25807, 26014, 26167, 26914, 27085, 27209, 27814, 27828, 28392, 28595, 29038, 29254, 29398, 29461, 31639, 32854, 33907, 34555, 34834, 35878, 36535, 37705, 38758, 39478, 39523, 41494, 41557, 42178, 42538, 42754, 43006, 43807, 44554, 45454, 45634, 46134, 46174, 46318, 46615, 46664, 46714, 47074, 48503, 50458, 50818, 51678, 52753, 52834, 52978, 54697, 54958, 56047, 56218, 57307, 57390, 58018, 59638, 59674, 59845, 60538, 60934, 61490, 62158, 62977, 63265, 65218, 65245, 65376, 65434, 65974, 67068, 67117, 67198, 67234, 67594, 68314, 70159, 70267, 72778, 73476, 73498, 74794, 75631, 77485, 78097, 78138, 78680, 78718, 79978, 80851, 81058, 81877, 82309, 82867, 82993, 83398, 84690, 85378, 86148, 86376, 86647, 86683, 86917, 87034, 87164, 87875, 88046, 88735, 89374, 89744, 90238, 90274, 90607, 90644, 90994, 93298, 93658, 93802, 93838, 93968, 94558, 94594, 95278, 95611, 95796, 96727, 97006, 97152, 97294, 98120, 98252, 98338, 99416, 99715, 100066, 101389, 102406, 103796, 106006, 107939, 108085, 109966, 110785, 112855, 112873, 116455, 117067, 117589, 117805, 117886, 117954, 118246, 118777, 118786, 119798, 120082, 122926, 123286, 123763, 124069, 125266, 125977, 129226, 130088, 130846, 131285, 131647, 134167, 135594, 137227, 137497, 138446, 139117, 139594, 141646, 141997, 142726, 143986, 144346, 144517, 145165, 145291, 145615, 145640, 146069, 146916, 148027, 149593, 149917, 150567, 151591, 151735, 152986, 153886, 154255, 154595, 156174, 156397, 157369, 157990, 158444, 158566, 160546, 160726, 162949, 163669, 165226, 165415, 165766, 166279, 167746, 167935, 168745, 169051, 170077, 170266, 170446, 170480, 171028, 171607, 171984, 173290, 173785, 174586, 174946, 175526, 175666, 176926, 177439, 178006, 178726, 180157, 180454, 180805, 181498, 181642, 181705, 181894, 182038, 182254, 182506, 182666, 182794, 183082, 184018, 184306, 184608, 184747, 184918, 185858, 187465, 187645, 187753, 188455, 189058, 189454, 190568, 190678, 191268, 192298, 192838, 193117, 194251, 195007, 195066, 196258, 196654, 196843, 197676, 197750, 197815, 197878, 198274, 198355, 198994, 199652, 201298, 201874, 202558, 202954, 203193, 203377, 204764, 205078, 205906, 206914, 207058, 207238, 207684, 208174, 209407, 209434, 210505, 210757, 212089, 212638, 214717, 216193, 217134, 218074, 218398, 219828, 220918, 220954, 221858, 222097, 222106, 222538, 222727, 222934, 225139, 225598, 225656, 225958, 226476, 226714, 227389, 228217, 228334, 228561, 229657, 229855, 230674, 232447, 237575, 237636, 238198, 238594, 239598, 240695, 241006, 241078, 241197, 241519, 242154, 242788, 243094, 243454, 243628, 243778, 244138, 244417, 244534, 245218, 245424, 245506, 245686, 245726, 246055, 246118, 247063, 247459, 247774, 248134, 249241, 249493, 250438, 250798, 251259, 251367, 251743, 252036, 252085, 252373, 252728, 253615, 254074, 256378, 256544, 257098, 257638, 258169, 258394, 258574, 259078, 259393, 259906, 260158, 260734, 260914, 261094, 261634, 262165, 262534, 262570, 263254, 263856, 263938, 264118, 264440, 265054, 265364, 265693, 267538, 267745, 267934, 268915, 269635, 270238, 270418, 270994, 271291, 271476, 271716, 272434, 272722, 272758, 273649, 274234, 274738, 274954, 275395, 276063, 276106, 276358, 276394, 277294, 277798, 278158, 278734, 279247, 279418, 279444, 281254, 281434, 281479, 281794, 282631, 283918, 285106, 285866, 286735, 287311, 287338, 288391, 290461, 290578, 293278, 293472, 293557, 294178, 294547, 294754, 295258, 295625, 296365, 297085, 297634, 298074, 299353, 300505, 301477, 301981, 302899, 302973, 303466, 304265, 304267, 304366, 306098, 306814, 308227, 309046, 309438, 309766, 309919, 310873, 311377, 314846, 315944, 316273, 317168, 318276, 318757, 318946, 319238, 319369, 320746, 322726, 324409, 324526, 325057, 325246, 326047, 327766, 328117, 328544, 329026, 329197, 330398, 330466, 331861, 332574, 334066, 334417, 335384, 336284, 336586, 337337, 337486, 337783, 337819, 338746, 339457, 340555, 341266, 342193, 342229, 342526, 342675, 343426, 343728, 344628, 345595, 345946, 347438, 348151, 349546, 349614, 350815, 350986, 351468, 351895, 352246, 353965, 354766, 354955, 355486, 355603, 357286, 359266, 360643, 360774, 361066, 361255, 361736, 362844, 363739, 364068, 365166, 368635, 369139, 370093, 370246, 370574, 370966, 371785, 373198, 373914, 375646, 375745, 375747, 376546, 377039, 377113, 378031, 378535, 379507, 380659, 381938, 382378, 382927, 383647, 384387, 384754, 385258, 385465, 385834, 386455, 386540, 386734, 389434, 389551, 391621, 392674, 392701, 393277, 394146, 394906, 396094, 397381, 398218, 398533, 398578, 398758, 400568, 400594, 400765, 401278, 401854, 402214, 402718, 403618, 403654, 403906, 403949, 404617, 405058, 405274, 405778, 406363, 407254, 407290, 407578, 408296, 408536, 408721, 409018, 409594, 409774, 410377, 411097, 412078, 412267, 412474, 414319, 414648, 414958, 415572, 415894, 416074, 416156, 416758, 417442, 417478, 417847, 418378, 418918, 419098, 419278, 419854, 420106, 420619, 420934, 421438, 421618, 421843, 422374, 422914, 423468, 423634, 425938, 426397, 427284, 427639, 427927, 427976, 428269, 428645, 428753, 429214, 429574, 430519, 430771, 431878, 432238, 432553, 432949, 433894, 433957, 434286, 434326, 434506, 434588, 434794, 435478, 435595, 435874, 436234, 436384, 436558, 436918, 437224, 437858, 438493, 438815, 438934, 439006, 439317, 440414, 441418, 441814, 442376, 442437, 447565, 449338, 450157, 450355, 451451, 451678, 451795, 452623, 453298, 453536, 454054, 454356, 454414, 454873, 457078, 457285, 457474, 457906, 457915, 458154, 459058, 459094, 460184, 461614, 461938, 462878, 463819, 465295, 467374, 467923, 469255, 469507, 470578, 470605, 471838, 472328, 472774, 472954, 473098, 474106, 474934, 475248, 476635, 476819, 477058, 477454, 478138, 478714, 480360, 481018, 481657, 481738, 482134, 482197, 482262, 482336, 483169, 483358, 483754, 484946, 485005, 485761, 486895, 487174, 487714, 488744, 489334, 489444, 490558, 490954, 491557, 492259, 492367, 492547, 494154, 495094, 495265, 495404, 495706, 495994, 496930, 497218, 497346, 497506, 497758, 497974, 498118, 498307, 498370, 498514, 499207, 499558, 499855, 501286, 502006, 502573, 503086, 504346, 504486, 505066, 505426, 506227, 506722, 508028, 508405, 508984, 509532, 509566, 509746, 509935, 510961, 511267, 512077, 512266, 513733, 514246, 514597, 514786, 516343, 517063, 519286, 519466, 521446, 521568, 522022, 522643, 523615, 523838, 525417, 525757, 526126, 527026, 528277, 528421, 529445, 530095, 530419, 531985, 533096, 533943, 534372, 534397, 534721, 534847, 535495, 535666, 536026, 537286, 538015, 538366, 540418, 540895, 541566, 542515, 542785, 544418, 545845, 548365, 548727, 549166, 549924, 550786, 554035, 554746, 555943, 556249, 556726, 557086, 559930, 560214, 561226, 561235, 561766, 562058, 562126, 562207, 562423, 562945, 563557, 567139, 567157, 569227, 570046, 571927, 572073, 574006, 576216, 577606, 578623, 579946, 580297, 580596, 581674, 581760, 581892, 582718, 582860, 583006, 583285, 584216, 584401, 584734, 585418, 585454, 586044, 586174, 586210, 586354, 586714, 589018, 589368, 589405, 589738, 589774, 590268, 590638, 591277, 591966, 592137, 592848, 592978, 593095, 593329, 593365, 593636, 593864, 594634, 595322, 596614, 597019, 597145, 597703, 598135, 598954, 599161, 600034, 601294, 601332, 601874, 601915, 602527, 604381, 605218, 606514, 606536, 607234, 609745, 609853, 611698, 612418, 612778, 612814, 612895, 612944, 614038, 614578, 614636, 614767, 614794, 616747, 617035, 617854, 618522, 619078, 619474, 620167, 620338, 620374, 621994, 622622, 622705, 623794, 623965, 625054, 625315, 627034, 627178, 627259, 628334, 629194, 629554, 631509, 632938, 633298, 633348, 633397, 633694, 633838, 633878, 634378, 634558, 635458, 636205, 637006, 637258, 637474, 637834, 638455, 638518, 640489, 640534, 641254, 642307, 643477, 644134, 645178, 645457, 646105, 647158, 648373, 650551, 650614, 650758, 650974, 651417, 651620, 652184, 652198, 652803, 652927, 653098, 653845, 653998, 654205, 654583, 654934, 655258, 655474, 655618, 657274, 658534, 659038, 659434, 659938, 660334, 660732, 661018, 661207, 661657, 662791, 663277, 663444, 663538, 663934, 666247, 668654, 669276, 669307, 669348, 669523, 670234, 670414, 670783, 670918, 671494, 671998, 673196, 673824, 674194, 674554, 674914, 675058, 675706, 675814, 676318, 677101, 677434, 678104, 678109, 678793, 679054, 679234, 679306, 679495, 679621, 679918

[Nataly-Mak]

Что-то у вас не так с парами. А где, например, комплементарная пара (165226, 514786)?
Я взяла все ваши 94 пары и предложила их своей программе. К моему удивлению, она не построила ни одного идеального квадрата. Тогда я начала проверять ваши пары...
Пар должно быть больше.

-- Чт авг 05, 2010 20:19:16 --

Может быть, у вас выброшены все пары, которые вошли в построенный идеальный квадрат?

[maxal]

Nataly-Mak
Не оттуда скопировал. Теперь исправил (всего 556 пар).

[Nataly-Mak]

Ого! Вот это уже солидный массив.

[Nataly-Mak]

maxal
а у вас есть программа построения пандиагонального квадрата 6-го порядка?

Я уже давно написала систему уравнений, но пока не решила. Надо бы её решить; интересно посмотреть, какая получится формула, слишком ли сложная для реализации.
Как уже говорила, для пандиагональных квадратов 7-го порядка систему составила и мне её решили на форуме Портала ЕН. Но тут формула получается сложная для реализации, 24 свободных элемента из 49; даже учитывая, что один элемент можно не варьировать (из-за пандиагональности), всё равно много свободных элементов.
Тут кстати подоспел алгоритм Россера для пандиагональных квадратов 7-го порядка, основанный на примитивных квадратах, и я бросила работать с этой формулой.
Собираюсь преобразовать её для идеальных квадратов (как уже сделала для квадратов 5-го порядка). Может быть, тогда она будет более приемлема для реализации.

Задача для пандиагональных квадратов 6-го порядка из простых чисел у нас такая: выяснить, является ли найденный мной пандиагональный квадрат с магической константой 630 наименьшим. Теперь магическая константа наименьшего квадрата находится в интервале [432, 630). Если учесть, что она может быть только чётной, не так много кандидатов осталось проверить.

[Nataly-Mak]

Продолжим теорию Россера

Хотела сначала преобразовывать общую формулу для пандиагонального квадрата 7-го порядка с учётом ассоциативности, но потом пришла другая идея: построить примитивный квадрат с учётом ассоциативности будущего пандиагонального квадрата.
Написала программу. Пока протестировала её на классическом квадрате.
Ввожу в программу 24 комплементарных пары (48 чисел натурального ряда). Программа мгновенно выдаёт примитивный квадрат:

1  2  4  6  7  3  5 
 8  9  11  13  14  10  12 
 15  16  18  20  21  17  19 
 22  23  25  27  28  24  26 
 29  30  32  34  35  31  33 
 36  37  39  41  42  38  40 
 43  44  46  48  49  45  47

Не ожидала даже, что всё пройдёт без сучка, без задоринки.
Применяю к этому примитивному квадрату преобразование Россера и получаю следующий классический идеальный квадрат:

3 18 33 48 8 28 37
43 14 23 38 4 19 34
39 5 20 29 49 9 24
35 44 10 25 40 6 15
26 41 1 21 30 45 11
16 31 46 12 27 36 7
13 22 42 2 17 32 47

Для классического квадрата всё чудесно получилось.
Замечу, что в программе построения примитивного квадрата только 7 свободных переменных!
Не знаю, можно ли сократить количество свободных элементов.
Программа может проверять сразу любое количество комплементарных пар (конечно, с увеличением размера массива будет резко увеличиваться время выполнения программы; оптимальный вариант - точно 24 комплементарных пары).

maxal
у вас есть программа построения идеального квадрата 7-го порядка? Если есть, сколько в вашей формуле свободных переменных?

По-моему, применение примитивного квадрата даёт очень неплохой результат.
Осталось проверить работу программы для нетрадиционных идеальных квадратов. Надеюсь, что всё получится.

[Nataly-Mak]

Пока нет идеального квадрата 7-го порядка из простых чисел
Проверила наборы комплементарных пар со следующими суммами в паре:

1234, 1282, 1294, 1318, 1346, 1366, 1402, 1454, 1466, 1478, 1486, 1502, 1522, 1538, 1546, 1594, 1618, 1642, 1646, 1654, 1658, 1678

Может быть, сама идея неверная? Хотя почему бы примитивному квадрату не построиться?

svb
вы у нас главный специалист по примитивным квадратам 7-го порядка. Что можете сказать по этому поводу? Можно в принципе построить примитивный квадрат из произвольных простых чисел (образующих комплементарные пары), который даст идеальный квадрат с помощью преобразования Россера?

Надо опробовать метод на квадратах 5-го порядка.

[maxal]

Nataly-Mak в сообщении #342852 писал(а):

maxal
а у вас есть программа построения пандиагонального квадрата 6-го порядка?

Есть, но ее быстродействие оставляет желать лучшего.

-- Fri Aug 06, 2010 11:56:58 --

Nataly-Mak в сообщении #342909 писал(а):

maxal
у вас есть программа построения идеального квадрата 7-го порядка? Если есть, сколько в вашей формуле свободных переменных?

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