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

[maxal]

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

Ты вроде занимался проблемой возможности (невозможности) построения пандиагональных МК 4х4 из последовательных простых чисел. Как у тебя дела в этом направлении?

Нет. Я искал квадраты из последовательных смитов - в пределах до $10^{12}$ ничего не нашлось.

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

Задача. Найти 16 последовательных простых чисел, образующих 8 пар комплементарных чисел.

Вот наименьший такой набор последовательных простых:

[1071065111, 1071065123, 1071065129, 1071065137, 1071065141, 1071065153, 1071065167, 1071065179, 1071065201, 1071065213, 1071065227, 1071065239, 1071065243, 1071065251, 1071065257, 1071065269]

Кстати, в OEIS имеется несколько последовательностей, напрямую связанных с этой задачей:
A055380
A055381
A055382

[Nataly-Mak]

Из приведённого набора пандиагональный квадрат 4-го порядка не составился.

maxal
а ещё есть такие наборы? Может быть, по указанным вами ссылкам в OEIS, но мне надо долго разбираться (по незнанию языка).

Если такие наборы есть ещё, не могли бы вы их все нормализовать, чтобы я могла их быстро проверить по своей программе на предмет составления пандиагонального квадрата 4х4?

___

Программа проверки потенциальных массивов из 49 чисел (то есть таких, сумма чисел которых кратна 7) на предмет составления из чисел этих массивов примитивного квадрата работает и довольно быстро даже на Бейсике. Например, массив из простых чисел проверяется около 30 секунд, а массив из смитов 2-3 секунды. Для порядка 7 это неплохо. Если переписать программу на другой язык, скорость будет ещё больше.

Вот здесь архив, в котором есть две программы.

Первая программа - GENER49.EXE - генерирует случайным образом 50 массивов из 49 различных произвольных простых чисел (так чтобы сумма всех чисел массива была кратна 7). Я взяла первые 60 простых чисел.
Для работы этой программы нужен файл MK.txt, в котором находятся первые 60 простых чисел. Этот файл есть в архиве (он у меня вообще-то содержит больше простых чисел, но это не важно, не стала его обрезать до 60 чисел). Сгенерированные массивы программа запишет в файл MK4.txt.
Вторая программа - PRIMIT7.EXE - проверяет полученные массивы на предмет построения примитивного квадрата.
Ещё в архиве есть пакетный файл, в котором записаны эти две программы. Просто запускаем пакетный файл, и обе программы выполняются одна за другой. Если примитивный квадрат будет найден, он запишется в файл MK10.txt.

Так работает мой алгоритм для произвольных простых чисел (можно и из произвольных смитов так же сделать). Конечно, случайная генерация - это не дело. По-хорошему надо сформировать все потенциальные массивы, скажем, из первых 60 простых чисел (или смитов) и все эти потенциальные массивы проверить по предложенной программе. Если примитивный квадрат будет найден, из него мы сразу получим пандиагональный квадрат с помощью преобразования, приведённого в статье Россера.

Для проверки массивов из последовательных простых чисел (или из смитов) надо выбросить программу генерации массивов. Потенциальные массивы из последовательных чисел легко формируются. Надо помещать порцию из 50 потенциальных массивов в файл MK4.txt и сразу выполнять программу проверки - PRIMIT7.EXE.

Просьба ко всем подключиться к поиску примитивного квадрата 7х7 из простых чисел и из смитов (как последовательных, так и произвольных).

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

Нижние границы магических констант квадратов 7-го порядка:
из произвольных простых чисел - 733;
из последовательных простых чисел - 797;
из произвольных смитов - 3720;
из последовательных смитов - 5551.

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

[Pavlovsky]

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

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

Ты вроде занимался проблемой возможности (невозможности) построения пандиагональных МК 4х4 из последовательных простых чисел. Как у тебя дела в этом направлении?

Нет.

Тогда можете подробнее и доступнее рассказать о чем шла речь в этой теме.
topic12959-1185.html

Цитата:

Сомнений нет, даже, наоборот, не сомневаюсь, что и большие квадраты можно будет легко построить, причем они будут соответствовать представленным в качестве гипотез формулам.

А формулы вот эти:

%F A104157 Conjecture: for n>4, a(n)=prime(s) where s>1 is the smallest integer such that (Sum[i=s..s+n^2-1] prime(i))/n is an integer of the same evenness as n.

%F A073520 Conjecture: for n>=5, a(n) equals the smallest integer of the form (A000040(s+1)+...+A000040(s+n^2))/n = (A007504(s+n^2)-A007504(s))/n of the same oddness as n.

A000040 - это последовательность простых чисел (то есть A000040(k)=prime(k) представляют собой k-е простое число).

И далее:

Цитата:

Гипотеза состоит в том, что формула является и достаточным условием для существования квадратов всех порядков, начиная с 5.
Именно это хотелось бы доказать.

Если аккуратно формализировать и доказать это утверждение, то доказательство исходной гипотезы можно было бы провести так: из того, что данное множество достаточно плотное, следует, что количество наборов чисел с магической суммой достаточно велико, откуда следует, что квадрат обязан существовать.

-- Вт май 18, 2010 10:06:56 --

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

Вот наименьший такой набор последовательных простых:

[1071065111, 1071065123, 1071065129, 1071065137, 1071065141, 1071065153, 1071065167, 1071065179, 1071065201, 1071065213, 1071065227, 1071065239, 1071065243, 1071065251, 1071065257, 1071065269]

Кстати, в OEIS имеется несколько последовательностей, напрямую связанных с этой задачей:
A055380
A055381
A055382

Круто! Классный у тебя генератор простых чисел! Еще немного и пандиагональный МК 4х4 из последовательных простых чисел будет найден! По моим оценкам он где то в районе значений простых чисел 500 миллиардов.

За ссылки спасибо.

[maxal]

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

Если такие наборы есть ещё, не могли бы вы их все нормализовать, чтобы я могла их быстро проверить по своей программе на предмет составления пандиагонального квадрата 4х4?

Вот все такие наборы в пределах до $10^{11}$ (указан первый элемент и смещения остальных):

1071065111: [0, 12, 18, 26, 30, 42, 56, 68, 90, 102, 116, 128, 132, 140, 146, 158]
1613902561: [0, 6, 12, 40, 60, 66, 82, 88, 90, 96, 112, 118, 138, 166, 172, 178]
3144269839: [0, 54, 58, 84, 88, 118, 120, 138, 190, 208, 210, 240, 244, 270, 274, 328]
4342255499: [0, 8, 14, 24, 98, 114, 162, 164, 168, 170, 218, 234, 308, 318, 324, 332]
5421518587: [0, 4, 30, 42, 52, 72, 94, 112, 132, 150, 172, 192, 202, 214, 240, 244]
6171000013: [0, 6, 10, 24, 28, 40, 54, 58, 66, 70, 84, 96, 100, 114, 118, 124]
6227816701: [0, 18, 30, 46, 52, 66, 78, 96, 112, 130, 142, 156, 162, 178, 190, 208]
8332932121: [0, 12, 40, 52, 66, 70, 72, 78, 100, 106, 108, 112, 126, 138, 166, 178]
9457965683: [0, 18, 24, 26, 50, 80, 84, 108, 176, 200, 204, 234, 258, 260, 266, 284]
9585742667: [0, 2, 14, 26, 30, 44, 54, 72, 74, 92, 102, 116, 120, 132, 144, 146]
15507351449: [0, 2, 32, 44, 72, 74, 128, 140, 162, 174, 228, 230, 258, 270, 300, 302]
40145495939: [0, 8, 20, 54, 68, 80, 128, 132, 170, 174, 222, 234, 248, 282, 294, 302]
51780164959: [0, 4, 12, 18, 48, 54, 130, 160, 222, 252, 328, 334, 364, 370, 378, 382]
62479937413: [0, 4, 10, 64, 76, 78, 88, 106, 108, 126, 136, 138, 150, 204, 210, 214]
67637760121: [0, 10, 52, 66, 70, 112, 120, 126, 136, 142, 150, 192, 196, 210, 252, 262]
69303590249: [0, 20, 32, 50, 54, 60, 90, 108, 134, 152, 182, 188, 192, 210, 222, 242]
71292758149: [0, 4, 12, 22, 28, 30, 42, 70, 72, 100, 112, 114, 120, 130, 138, 142]
74422046563: [0, 16, 40, 60, 88, 100, 118, 120, 124, 126, 144, 156, 184, 204, 228, 244]
76014749749: [0, 22, 28, 54, 70, 78, 94, 102, 130, 138, 154, 162, 178, 204, 210, 232]
81661695239: [0, 12, 14, 24, 78, 122, 138, 150, 152, 164, 180, 224, 278, 288, 290, 302]
82420305791: [0, 6, 32, 38, 68, 80, 120, 162, 206, 248, 288, 300, 330, 336, 362, 368]
89028856249: [0, 4, 12, 22, 34, 82, 88, 100, 102, 114, 120, 168, 180, 190, 198, 202]
91530217393: [0, 16, 18, 24, 30, 46, 108, 114, 130, 136, 198, 214, 220, 226, 228, 244]
92946283811: [0, 56, 66, 72, 78, 80, 108, 110, 138, 140, 168, 170, 176, 182, 192, 248]
96296734561: [0, 42, 46, 48, 60, 70, 76, 82, 96, 102, 108, 118, 130, 132, 136, 178]

На пандиагональность я их проверил - квадрата не нашлось, но перепроверить не помешает.

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

Тогда можете подробнее и доступнее рассказать о чем шла речь в этой теме.

Если вы это имели в виду под "занимался", то да - но это была работа больше теоретического плана.

[Nataly-Mak]

maxal
большое спасибо за наборы, обязательно проверю на пандиагональность.

[Pavlovsky]

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

Если вы это имели в виду под "занимался", то да - но это была работа больше теоретического плана.

Так давайте реанимируем теоретическое обсуждение этой темы. В качестве затравки не могли бы вы изложить свои идеи в одном посте.

[Nataly-Mak]

maxal
все ваши наборы проверила, пандиагональный квадрат не составился.

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

Из произвольных простых построены наименьшие квадраты порядков 4 и 5.
Сейчас пытаюсь найти пандиагональный квадрат порядка 7.

Нужна помощь в таком плане: нужно сформировать все потенциальные массивы из 49 произвольных простых чисел, скажем, из первых 60 простых (сумма всех чисел потенциального массива должна быть кратна 7).
Эти массивы надо поместить в отдельные файла порциями по 50 штук. Тогда я смогу их все проверить по своей программе PRIMIT7.EXE. Впрочем, это может сделать любой, программа здесь выложена.

Да, ещё не забыть: магические константы, определяемые потенциальными массивами, должны быть больше 733.

Сейчас я гоняю эту программу со случайно сгенерированными массивами. Ещё руки не дошли написать программу формирования потенциальных массивов (у меня такая программа есть только для квадратов 5-го порядка).

[maxal]

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

В качестве затравки не могли бы вы изложить свои идеи в одном посте.

Не вижу смысла повторяться. По указанной вами ссылке собственно все сказано. Если что-то непонятно - спрашивайте.

[svb]

От Rosser-а в восторге. Вот попробовал применить для простых чисел:

19 855713 595949 113161 88807 76001 1303 
88811 76003 1279 23 855719 595951 113167 
855721 595957 113171 88813 75979 1283 29 
75983 1289 31 855727 595961 113173 88789 
595963 113149 88793 75989 1291 37 855731 
1297 41 855733 595939 113153 88799 75991 
113159 88801 75997 1301 43 855709 595943 

855709 595943 113159 88801 75997 1301 43 
76001 1303 19 855713 595949 113161 88807 
595951 113167 88811 76003 1279 23 855719 
1283 29 855721 595957 113171 88813 75979 
113173 88789 75983 1289 31 855727 595961 
37 855731 595963 113149 88793 75989 1291 
88799 75991 1297 41 855733 595939 113153 

855709 1257233 595949 113161 88807 76001 1303 
88811 76003 1279 855713 1257239 595951 113167 
1257241 595957 113171 88813 75979 1283 855719 
75983 1289 855721 1257247 595961 113173 88789 
595963 113149 88793 75989 1291 855727 1257251 
1297 855731 1257253 595939 113153 88799 75991 
113159 88801 75997 1301 855733 1257229 595943 

[Pavlovsky]

Поздравляю!!!!!!

Я решил сначала из последовательных простых поискать. Проверил первые два миллиона простых чисел, ничего не нашел. Чтоб пробежать первые 50 миллионов простых чисел потребуется около 50 часов.

-- Вт май 18, 2010 19:16:27 --

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

Вот все такие наборы в пределах до $10^{11}$ (указан первый элемент и смещения остальных):

1071065111: [0, 12, 18, 26, 30, 42, 56, 68, 90, 102, 116, 128, 132, 140, 146, 158]
1613902561: [0, 6, 12, 40, 60, 66, 82, 88, 90, 96, 112, 118, 138, 166, 172, 178]
3144269839: [0, 54, 58, 84, 88, 118, 120, 138, 190, 208, 210, 240, 244, 270, 274, 328]
4342255499: [0, 8, 14, 24, 98, 114, 162, 164, 168, 170, 218, 234, 308, 318, 324, 332]
5421518587: [0, 4, 30, 42, 52, 72, 94, 112, 132, 150, 172, 192, 202, 214, 240, 244]
6171000013: [0, 6, 10, 24, 28, 40, 54, 58, 66, 70, 84, 96, 100, 114, 118, 124]
6227816701: [0, 18, 30, 46, 52, 66, 78, 96, 112, 130, 142, 156, 162, 178, 190, 208]
8332932121: [0, 12, 40, 52, 66, 70, 72, 78, 100, 106, 108, 112, 126, 138, 166, 178]
9457965683: [0, 18, 24, 26, 50, 80, 84, 108, 176, 200, 204, 234, 258, 260, 266, 284]
9585742667: [0, 2, 14, 26, 30, 44, 54, 72, 74, 92, 102, 116, 120, 132, 144, 146]
15507351449: [0, 2, 32, 44, 72, 74, 128, 140, 162, 174, 228, 230, 258, 270, 300, 302]
40145495939: [0, 8, 20, 54, 68, 80, 128, 132, 170, 174, 222, 234, 248, 282, 294, 302]
51780164959: [0, 4, 12, 18, 48, 54, 130, 160, 222, 252, 328, 334, 364, 370, 378, 382]
62479937413: [0, 4, 10, 64, 76, 78, 88, 106, 108, 126, 136, 138, 150, 204, 210, 214]
67637760121: [0, 10, 52, 66, 70, 112, 120, 126, 136, 142, 150, 192, 196, 210, 252, 262]
69303590249: [0, 20, 32, 50, 54, 60, 90, 108, 134, 152, 182, 188, 192, 210, 222, 242]
71292758149: [0, 4, 12, 22, 28, 30, 42, 70, 72, 100, 112, 114, 120, 130, 138, 142]
74422046563: [0, 16, 40, 60, 88, 100, 118, 120, 124, 126, 144, 156, 184, 204, 228, 244]
76014749749: [0, 22, 28, 54, 70, 78, 94, 102, 130, 138, 154, 162, 178, 204, 210, 232]
81661695239: [0, 12, 14, 24, 78, 122, 138, 150, 152, 164, 180, 224, 278, 288, 290, 302]
82420305791: [0, 6, 32, 38, 68, 80, 120, 162, 206, 248, 288, 300, 330, 336, 362, 368]
89028856249: [0, 4, 12, 22, 34, 82, 88, 100, 102, 114, 120, 168, 180, 190, 198, 202]
91530217393: [0, 16, 18, 24, 30, 46, 108, 114, 130, 136, 198, 214, 220, 226, 228, 244]
92946283811: [0, 56, 66, 72, 78, 80, 108, 110, 138, 140, 168, 170, 176, 182, 192, 248]
96296734561: [0, 42, 46, 48, 60, 70, 76, 82, 96, 102, 108, 118, 130, 132, 136, 178]

На пандиагональность я их проверил - квадрата не нашлось, но перепроверить не помешает.

Классный результат. Решение где то рядом. Простая арифметика - пандиагональный МК 4х4 описывается 12-ю независимыми линейными уравнениями. Комплементарность задается 8-ю уравнениями. Осталость найти набор, чтоб сошлись оставшиеся 4 уравнения.

[svb]

Дело в том, что примитивные квадраты имеют прозрачную структуру. Пусть имеем первую строку такого квадрата, тогда все остальные строки - это просто смещения этой строки на некоторые величины. Я по быстрому сгенерировал 100000 простых чисел и пробежался по всем семеркам последовательных чисел, записывая только те семерки, которые имеют небольшую разницу между крайними числами (не более 24) :

      1277: 2 6 12 14 20 24

Потом посмотрел на эти наборы, надеясь найти строчки с одинаковыми смещениями, нашел:

        19 4 10 12 18 22 24
      1279 4 10 12 18 22 24
     75979 4 10 12 18 22 24
     88789 4 10 12 18 22 24
    113149 4 10 12 18 22 24
    595939 4 10 12 18 22 24
    855709 4 10 12 18 22 24
   1257229 4 10 12 18 22 24

А дальше просто по Rosser-у

[Nataly-Mak]

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

[svb]

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

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

Попробовал найти с меньшей суммой:

23 595949 284731 163987 113171 88813 1307 
113173 88817 1283 29 595951 284737 163991 
595957 284741 163993 113177 88793 1289 31 
88799 1291 37 595961 284743 163997 113153 
284747 163973 113159 88801 1297 41 595963 
1301 43 595967 284723 163979 113161 88807 
163981 113167 88811 1303 47 595943 284729 
S= 1247981

Вопрос открыт

[svb]

Наверняка имеются пандиагональные квадраты из простых чисел 7 порядка со значительно меньшей суммой - слишком большое ограничение было наложено на исходный примитивный квадрат. Каждая строка в нем - это последовательные простые числа. Например, квадрат 5-го порядка, который приведен в вашей статье имеет следующий исходный примитивный:

 5  13  19  29  53
 23  31  37  47  71
 59  67  73  83 107
 89  97 103 113 137
149 157 163 173 197

Здесь последовательными числами и не пахнет, но любопытны разницы: 8, 6, 10, 24. Возможно разумно задавать шаблоны подобных разностей?

[svb]

Еще немного уменьшил сумму:

31 14723 12487 1553 449 397 251 
479 421 101 37 14753 12517 1583 
14783 12547 1613 503 271 107 67 
277 137 97 14813 12577 1637 353 
12601 1487 359 307 167 127 14843 
197 157 14867 12451 1493 389 337 
1523 419 367 227 181 14717 12457 
S= 29891

-- Вт май 18, 2010 22:27:50 --

И еще меньше:

11 9437 907 613 617 197 157 
647 227 37 17 9461 919 631 
9473 937 661 677 107 43 41 
113 67 53 9491 967 691 557 
997 571 563 137 79 71 9521 
97 101 9551 877 577 587 149 
601 599 167 127 131 9431 883 
S= 11939