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

[Pavlovsky]

Трудно дается конкурс. Уже реализовал три алгоритма, с довольно большим объемом кодинга. Результаты нулевые. Приступаю к программированию алгоритма №4. Так что отдых в дали от цивилизации отменяется.

[Nataly-Mak]

Вчера до полночи просматривала тему "Магические квадраты". Читала, как захватывающий роман

Вообще у меня была конкретная цель...
Я решила заняться поиском пандиагонального квадрата 5-го порядка из последовательных простых чисел. В памяти осталось, что поиском таких квадратов вроде занимался maxal. Вот и искала информацию об этом, но, увы, не нашла. Есть информация о поиске пандиагональных квадратов 4-го порядка из последовательных простых чисел. Такой квадрат не найден.
Для пандиагональных квадратах 5-го порядка нашла только общую формулу maxal:

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

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

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

Вот эффективная формула для таких квадратов:

$$\begin{bmatrix} x_1 & x_2 & x_{13} & x_{14} & x_7 \\ x_{18} & x_{10} & x_5 & x_3 & x_{19} \\ x_6 & x_{20} & x_{15} & x_{21} & x_{11} \\ x_8 & x_{22} & x_{12} & x_{23} & x_{16} \\ x_{24} & x_{17} & x_9 & x_4 & x_{25} \end{bmatrix} $$

Нумерация переменных здесь, как и раньше, в порядке перебора/вычисления значений. Переменные $x_1$, $x_2$, $x_3$, $x_5$, $x_7$, $x_{10}$, $x_{13}$, $x_{18}$ - независимые, остальные - зависимые:

$$ \begin{cases} x_4 = x_1 + x_2 - x_3 \\ x_6 = -x_1 + x_3 + x_5 \\ x_8 = x_1 + x_2 - x_3 - x_5 + x_7 = x_4 - x_5 + x_7\\ x_9 = x_1 - x_5 + x_7 \\ x_{11} = x_5 - x_7 + x_{10} \\ x_{12} = -x_1 + x_3 + x_5 - x_7 + x_{10} = x_6 - x_7 + x_{10} \\ x_{14} = S - x_1 - x_2 - x_7 - x_{13} \\ x_{15} = S - x_3 - x_5 - x_{10} - x_{13} \\ x_{16} = S - x_2 - x_5 - x_{10} - x_{13} \\ x_{17} = S - x_1 - x_2 - x_{10} - x_{13} \\ x_{19} = S - x_3 - x_5 - x_{10} - x_{18} \\ x_{20} = S - x_2 - x_5 - x_{10} - x_{18} \\ x_{21} = -S + x_1 + x_2 + x_7 + x_{10} + x_{13} + x_{18} = x_7 - x_{17} + x_{18} \\ x_{22} = -S + x_1 + x_2 + x_5 + x_{10} + x_{13} + x_{18} = x_5 - x_7 + x_{21} \\ x_{23} = S - x_1 - x_2 - x_{10} - x_{18} \\ x_{24} = S - x_1 - x_2 - x_7 - x_{18} = - x_7 + x_{10} + x_{23}\\ x_{25} = -S + x_2 + x_3 + x_5 + x_{10} + x_{13} + x_{18} = -x_1 + x_3 + x_{22} \end{cases} $$

Внимательно изучила формулу, сравнила её со своей формулой, которая представлена чуть выше. Моя общая формула получена по алгоритму Россера.
maxal получил свою формулу, решая систему линейных уравнений, описывающих пандиагональный квадрат 5-го порядка.
1. обе формулы имеют тип 8+17, то есть 8 свободных переменных и 17 зависимых.
2. линейные функции, задающие зависимые переменные, в моей формуле намного лаконичнее.
3. не сравнила пока порядок перебора свободных переменных и вычисления зависимых переменных.

Как мне кажется при беглом сравнении, формула, полученная по алгоритму Россера, эффективнее. Но для окончательного вывода нужны эксперименты по обеим формулам. Нужно написать программу по формуле maxal и сравнить работу двух программ.

Свою формулу я уже реализовала программно; программа работает очень быстро, один массив из 25 чисел проверяется долю секунды. Вчера проверила 717 потенциальных массивов, решение не найдено. Здесь может быть такая ситуация, как с квадратами 4-го порядка: проверять придётся очень много потенциальных массивов и неизвестно, осилю ли я эту проверку, ибо неизвестно, из какого потенциального массива квадрат составится. В том, что он существует, я почти не сомневаюсь.

-- Пт авг 02, 2013 07:46:24 --

Очень интересно читать, как осваивали статью Россера.

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

В данный момент бьюсь над Леммой 4.1. И почему из нее следует тривиальный вывод, что пандиагональных МК 3х3 не существует.

и вот над этим

Цитата:

The general solution of these equations, the elements being linear functions of a certain number of essential, independent parameters, shall be called the general square of order n admitting the given configurations.

Никак не могу понять что такое "general square". Как можно общее решение системы линейных уравнений, которое в данном случае прямоугольник сделать квадратом?!

Оказвается, Россер тоже использовал понятие "общая формула магического квадрата", только формулировал это несколько по-другому.

Вот, например, этот самый "general square":

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

25 линейных функций, задающих 25 элементов квадрата. При этом определяющими элементами являются 9, остальные выражаются через них.
Это и есть общая формула пандиагонального квадрата 5-го порядка, полученная по алгоритму Россера.
Такой же "general square" можно составить и по формуле maxal. Только линейные функции в его формуле более громоздкие.

[Nataly-Mak]

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

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

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

Сделала небольшую оптимизацию в программе.
Массив последовательных простых у меня всегда ранжирован, то есть числа следуют в порядке возрастания. Нормализовала массив, то есть уменьшила каждое число массива на $x_1$ (самое маленькое число; напомню, что элемент $x_1$ я фиксирую).
Тогда все формулы для вычислений зависимых переменных стали ещё лаконичнее: $x_i+x_j$, за исключением переменной $x_9$, которая вычисляется по формуле:

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

(слагаемое $3x_1$ в формуле опущено, так как в нормализованном массиве $x_1=0$)

Наверное, можно придумать и другие оптимизации, но программа и сейчас уже работает вполне удовлетворительно в смысле быстродействия.
У меня имеется массив простых чисел в интервале (1, 50 000 000).
Проверила этот массив полностью. Решение не найдено.
Я вполне могла ошибиться, так как проверка у меня порционная - считывала из массива в программу по 100000 простых чисел и проверяла их. Затем следующую порцию. Просто побоялась, что Бейсик не возьмёт сразу весь массив, в котором 3 001 134 простых числа.
Вот последняя порция простых чисел, которая проверена (я добавила в массив 25 первых натуральных чисел, чтобы убедиться, что программа правильно проверяет массивы по 25 чисел):

49999231  49999253  49999267  49999289  49999291  49999297  49999307  49999349  
49999351  49999361  49999387  49999403  49999409  49999423  
49999427  49999441  49999463  49999471  49999489  49999529  49999553  49999561  
49999589  49999597  49999603  49999613  49999619  49999627  
49999637  49999639  49999643  49999667  49999673  49999693  49999699  49999711  
49999739  49999751  49999753  49999757  49999759  49999777  
49999783  49999801  49999819  49999843  49999847  49999853  49999877  49999883  
49999897  49999903  49999921  49999991  1  2  3  4  5  6  7  8  9  10  11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Здесь всего 79 чисел. Программа выдала пандиагональный квадрат, построенный из последнего массива, состоящего из 25 первых натуральных чисел:

 0  18  24  12  6 
 22  11  5  3  19 
 8  4  17  21  10 
 16  20  13  9  2 
 14  7  1  15  23 
S=60 

Это классический пандиагональный квадрат 5-го порядка, составленный из нормализованного массива (0,1,2,...,24).
Вроде правильно программа работает. Главное - очень быстро. Массив из 100000 простых чисел проверяется около минуты.
Дальше у меня нет простых чисел. Надо их генерировать. Такая вот задача

[Nataly-Mak]

Запостила эту нерешённую проблему в дискуссионной группе:

http://tech.groups.yahoo.com/group/AZPC ... essage/138

Может быть, кто-то заинтересуется и попробует найти решение.

[Nataly-Mak]

(Оффтоп)

Ха!
Вот и первый "заинтересовавшийся" нерешённой проблемой

Цитата:

the discovery of new pandiagonal squares of consecutive primes does not really benefit mankind a lot.

Can't we use that energy to do something more useful ?

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

Я не сомневаюсь, что автор процитированного сообщения использует свою энергию на решение задач, которые принесут человеческому обществу неоспоримую пользу.

Интересно, а открытие новых пандиагональных квадратов из простых чисел (конкурсная задача) принесёт человечеству какую-нибудь пользу?
Что думает по этому поводу Jarek? Не растрачивает ли он свою энергию напрасно?
Может, надо вовремя остановиться и переключиться на более полезные задачи?

[Nataly-Mak]

Проверила простые числа в интервале (1, 500 000 000). Пандиагональный квадрат 5-го порядка из последовательных простых чисел не найден

Например, такой потенциальный массив из 25 последовательных простых чисел:

389999527  389999543  389999579  389999593  389999611  389999641  389999693  
389999759  389999767  389999773  389999783  389999789  
389999821  389999851  389999861  389999879  389999881  389999887  389999899  
389999903  389999927  389999963  389999977  389999989  389999999 

Нормализую массив:

0 16 52 66 84 114 166 232 240 246 256 262 294 324 334 352 354 360 372 376 400 436 450 462 472

Чем плох массив? Сумма всех чисел кратна 5, $S=1344$. Но не составляется пандиагональный квадрат и всё тут
И таких потенциальных массивов огромное количество в указанном интервале.

Кстати, интересная статистика по количеству простых чисел. Я генерировала простые числа порциями, захватывая каждый раз новые 10 млн. натуральных чисел. Количество простых чисел с каждым миллионом уменьшается. Вот некоторые данные:

1 млн. - 50 млн. --- 3 001 134 простых чисел
50 млн. - 60 млн. --- 560981 
60 млн. - 70 млн. --- 555949
70 млн. - 80 млн. --- 551318
80 млн. - 90 млн. --- 547572
90 млн. - 100 млн. --- 544501
. . .
150 млн. - 160 млн. --- 530062
. . .
190 млн. - 200 млн. --- 523464
. . .
300 млн. - 310 млн. --- 512196
. . .
400 млн. - 410 млн. --- 504387
. . .
490 млн. - 500 млн. --- 499499

P.S. Программу проверки массива уже и так, и сяк тестировала, вроде правильно работает, не врёт на каждом отдельно взятом массиве. Может быть, в организации конвейрной проверки где-то напортачила. Ну, помощи ждать, как я понимаю, неоткуда. Все заняты полезными для общества задачами (или, по крайней мере, полезными для собственного кошелька).

[Nataly-Mak]

Трудная задача...и решение её где-то далеко-далеко...и существует ли оно вообще
Вчера проверила все простые в интервале (1, $10^9$).
Не нашла решения

По-прежнему проверяла порциями по 10 млн. Интересно, что в некоторых порциях нарушен закон убывания количества простых.
Например,

820-830 млн. - 486902 простых чисел
830-840 млн. - 487006

920-930 млн. - 483850
930-940 млн. - 483991
940-950 млн. - 484047

970-980 млн. - 482782
980-990 млн. - 483129

Но общая тенденция убывания с ростом интервала сохраняется.

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

-- Вс авг 04, 2013 06:55:51 --

Продолжаю просматривать тему "Магические квадраты" в надежде найти информацию о поиске пандиагонального квадрата 5-го порядка из последовательных простых чисел.
Начала от поста maxal с его формулой. Вот нашла сообщение о своей программе построения пандиагонального квадрата 5-го порядка из 25 заданных чисел:

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

Программа на Бейсике готова. Протестировала, получила новый (оригинальный) пандиагональный квадрат из того же массива проcтых чисел, потому что здесь совсем другая структура квадрата:

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

Этот пандиагональный квадрат найден за 8 минут (на компилируемом Бейсике).

Это была реализована формула типа 8+17, но не формула maxal, а моя формула.
Сейчас моя новая программа (тот же Бейсик и тот же компилятор) находит это решение за долю секунды. Вот такой прогресс

Пойду дальше смотреть тему, может, всё же найду чего-нибудь об этой нерешённой проблеме.
Жалко, что maxal в тему не заглядывает. Может, вспомнил бы: занимался он таким поиском или не занимался.

-- Вс авг 04, 2013 07:07:26 --

И ещё сообщение:

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

Программа получилась супер! Работает очень быстро.
Если по предыдущей программе не было найдено за 4 часа ни одного классического пандиагонального квадрата, то по новой программе такой квадрат нашёлся практически мгновенно:

1 17 24 10 13
9 15 3 16 22
18 21 7 14 5
12 4 20 23 6
25 8 11 2 19

Однако с пандиагональными квадратами из простых чисел пока результатов нет. Из последовательных простых проверила уже 100 потенциальных массивов, пандиагонального квадрата не нашла.
Из произвольных простых проверила оба варианта наименьшего квадрата (с константой 233), тоже пандиагонального квадрата нет.

Может быть, совсем не случайно известен пандиагональный квадрат 6-го порядка из последовательных простых и неизвестны такие квадраты порядков 4 - 5. Вполне возможно, что автор квадрата 6-го порядка пытался построить и квадраты порядков 4 - 5. Не получилось?

И сама занималась поиском пандиагональных квадратов 5-го порядка из последовательных простых чисел, проверила 100 потенциальных массивов.
Сейчас эти же массивы заново проверила. Подтверждается, что решения нет. Проверила и намного больше первых 100 потенциальных массивов.

-- Вс авг 04, 2013 07:19:45 --

А это сообщение Pavlovsky о задаче построения пандиагонального квадрата 4-го порядка из последовательных простых чисел:

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

maxal

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

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

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

Среди 50 миллионов первых простых чисел такой последовательности не нашел.

Ниже представлены все последовательности 14-ти последовательных простых чисел образующих 7 пар комплементарных чисел, среди первых 50 миллионов простых чисел.
Первое число медиана (половина суммы пары комплементарных чисел). Следующие 7 чисел смещение, для образования пары комплементарных чисел надо медиану сложить и вычесть со смещением.

Задача тоже не решена. Для всех энтузиастов, кто ищет нерешённые проблемы

[Pavlovsky]

Наталия, возник вот такой вопрос.
Существуют латинские квадраты. Строки и столбцы которых заполнены числами от 1 до N.
А существуют ли пандиагональные латинские квадраты? В которых еще и разорванные диагонали заполнены числами от 1 до N.

PS Наконец то алгоритм №4 дал первые результаты. Результаты весьма скромные, и увы перспективы для нахождения прорывных решений весьма призрачны.

[Nataly-Mak]

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

Наталия, возник вот такой вопрос.
Существуют латинские квадраты. Строки и столбцы которых заполнены числами от 1 до N.
А существуют ли пандиагональные латинские квадраты? В которых еще и разорванные диагонали заполнены числами от 1 до N.

Существуют диагональные латинские квадраты; это такие, в которых главные диагонали заполнены числами от 1 до N. А таких, чтобы в разломанных диагоналях тоже были числа от 1 до N, я что-то не припомню.
Есть пандиагональные латинские квадраты в том смысле, что суммы чисел по всем диагоналям тоже равны магической константе, например:

0 3 6 1 4 7 2 5 8
2 5 8 0 3 6 1 4 7
1 4 7 2 5 8 0 3 6
3 6 0 4 7 1 5 8 2
5 8 2 3 6 0 4 7 1
4 7 1 5 8 2 3 6 0
6 0 3 7 1 4 8 2 5
8 2 5 6 0 3 7 1 4
7 1 4 8 2 5 6 0 3

Цитата:

PS Наконец то алгоритм №4 дал первые результаты. Результаты весьма скромные, и увы перспективы для нахождения прорывных решений весьма призрачны.

Поздравляю!

Старею и память подводит
Есть, конечно, и такие латинские квадраты, что во всех разломанных диагоналях тоже числа от 1 до N:

1 2 3 4 5
3 4 5 1 2
5 1 2 3 4
2 3 4 5 1
4 5 1 2 3

Здесь группы ортогональных латинских квадратов.

-- Пн авг 05, 2013 08:14:32 --

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

Задача тоже не решена. Для всех энтузиастов, кто ищет нерешённые проблемы

Первое решение найдено! Автор Jarek.

320572022166380833 320572022166380921 320572022166380849 320572022166380917
320572022166380909 320572022166380857 320572022166380893 320572022166380861
320572022166380911 320572022166380843 320572022166380927 320572022166380839
320572022166380867 320572022166380899 320572022166380851 320572022166380903

Пандиагональный квадрат 4-го порядка из последовательных простых чисел.

[Pavlovsky]

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

1 2 3 4 5
3 4 5 1 2
5 1 2 3 4
2 3 4 5 1
4 5 1 2 3

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

Тогда. Пусть у нас есть пандиагональный квадрат 5х5. Тогда добавление/вычитание константы к числам в ячейках из выбранной группы, дает нам опять пандиагональный квадрат. На этом простеньком свойстве основан мой алгоритм №4.

[Nataly-Mak]

Ну, вот и прорывная идея

[Pavlovsky]

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

Для квадратов простых порядков это не трудно. А вот для квадратов, где N составное число, у меня возникли затруднения. Например, пандиагональный латинский квадрат 9х9 у меня вообще не строится (хотя бы один).

[alexBlack]

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

Получается следующая задача...

A085801
Первое непростое, для которого это возможно $25$

[Pavlovsky]

Спасибо за информацию.

Цитата:

Polya showed that a(n)=n if n is not divisible by 2 and not divisible by 3.

Значит пока сосредоточимся на простых порядках N=7,11,13,17.

[Jarek]

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

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

Тогда. Пусть у нас есть пандиагональный квадрат 5х5. Тогда добавление/вычитание константы к числам в ячейках из выбранной группы, дает нам опять пандиагональный квадрат. На этом простеньком свойстве основан мой алгоритм №4.

If I understand correctly, you start with any pandiagonal square (easy to constuct, e.g. with all numbers equal) and while keeping pandiagonality intact, change terms (N at a time) to arrive at distinct prime terms.

I would really love to discuss this idea and explain why this is very similar to what I am doing and why a slight difference in you approach and mine gives rather little hope for you to get great results (unless you find the missing little piece of the algorithm), but I feel that till the end of the contest I should keep my mouth shut