2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 63, 64, 65, 66, 67
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение12.04.2015, 14:26 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Всё! Проверка полностью завершена. Решений не найдено.

Приступаю к минимизации решения для $n=8$.
Для этого порядка пока найдено решение с магической константой 2520.
Осталось проверить всего две потенциальные магические константы - 2400 и 2040. Для обеих констант массив состоит точно из 32 комплементарных пар простых чисел.

Начну проверку с минимальной магической константы - 2040.
Интересно, что мной давно найдены ассоциативный и пандиагональный квадраты из различных простых чисел с такой магической константой. Кажется, я их уже показывала. Но покажу ещё раз, весьма интересные решения:

ассоциативный квадрат

Код:
7 * Potential scam. Censored * 31
53 421 233 409 317 157 379 71
61 347 239 401 313 227 373 79
173 311 241 179 383 281 359 113
397 151 229 127 331 269 199 337
431 137 283 197 109 271 163 449
439 131 353 193 101 277 89 457
479 43 443 47 23 491 11 503

$K=510, S=2040$

пандиагональный квадрат (получен из ассоциативного с помощью преобразования 3-х квадрантов)

Код:
* Potential scam. Censored * 463
* Potential scam. Censored * 157 317
* Potential scam. Censored * 227 313
173 311 241 179 113 359 281 383
479 43 443 47 503 11 491 23
439 131 353 193 457 89 277 101
431 137 283 197 449 163 271 109
397 151 229 127 337 199 269 331

$S=2040$

Итак, теперь нам надо построить из чисел этого массива

Код:
7  * Potential scam. Censored *  67  71  * Potential scam. Censored *  131  137  151  157  163  173  179  193 
197  199  227  229  233  239  241  269  271  277  281  283  311  313  317  331  337  347  353  359  373  379 
383  397  401  409  421  431  439  443  449  457  463  467  479  487  491  499  503

идеальный магический квадрат 8-го порядка.

Существует ли решение :?: Я пока не знаю ответ на этот вопрос.
Раньше уже пыталась найти решение. Приближение с 6 дырками находится с ходу. Лучшего пока не было.

Программа у меня реализует не общую формулу идеального квадрата! В моей частной формуле всего 14 свободных переменных из 32. Но эта формула даёт группу идеальных квадратов, удовлетворяющих некоторым дополнительным свойствам (по решёткам Россера). Решение с магической константой 2520 удалось найти по этой формуле.
Сейчас подумываю о том, что надо реализовать общую формулу. Шансов найти решение будет больше.

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


22/03/08

7154
Саратов
Есть прогресс :-)
Сегодня немного покрутила старую программу. Нашла решение, в котором формально всего две дырки (помечены звёздочкой), фактически 4 дырки - две неправильные комплементарные пары:

Код:
467 313 47 379 311 163 239 121*
67 401 359 7 31 227 491 457
49* 317 331 137 499 449 157 101
* Potential scam. Censored * 233 241
269 277 229 431 113 127 421 173
* Potential scam. Censored * 193 461
* Potential scam. Censored * 109 443
389 271 347 199 131 463 197 43

$K=510, S=2040$

Это уже хорошее приближение к решению. Однако ничего пока нельзя сказать о существовании полного решения. Бабушка надвое сказала :D

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


22/03/08

7154
Саратов
Рассмотрела внимательнее, что у меня есть в арсенале для идеальных квадратов 8-го порядка.
Есть даже две общие формулы. Первая формула получена по программе svb, она была показана в теме "Магические квадраты". Там обсуждали с svb непонятный параметр $p_1$.
В этой общей формуле имеется 18 свободных переменных из 32 при заданной константе ассоциативности. Ну, так должно быть в любой альтернативной общей формуле.

Вторая формула получена мной решением системы линейных уравнений; она у меня пока не преобразована к привычному виду, в том виде, как выдана онлайн-решателем:

Код:
k = ( r8+ r7+ r6+ r5+ r4+ r3+ r2+ r1)/4,
x1 = r9- r8- r6+ r4+2 r2- r19- r18-2 r17+ r15- r13+ r12+ r11+ r1,
x10 = r9- r8-2 r7- r6- r5- r4+ r19+ r18- r15+ r14+ r13+ r12+ r11 +2 r10- r1,
x11 = r9- r8- r7-2 r6- r5+ r4+ r3+2 r2-2 r19- r18- r17+ r16+ r15 - r14- r13+ r12+2 r11+ r10+ r1,
x12 = r19,
x13 = r9- r6+ r15,
x14 = - r9+ r8+2 r7+2 r6+ r5+ r4+ r2- r19- r18- r17- r13- r12- r11 - r10+ r1,
x15 = r18,
x16 = -2 r9+2 r8+2 r7+3 r6+2 r5- r2+ r19+ r17- r16- r15- r12 -2 r11-2 r10,
x17 = r16,
x18 = - r9+ r8+ r7+ r6+ r5+ r4+ r3+ r2- r16- r14- r13- r12- r11- r10 + r1,
x19 = r14,
x2 = r15,
x20 = r13,
x21 = r12,
x22 = r11,
x23 = r10,
x24 = r9,
x25 = r8,
x26 = r7,
x27 = r6,
x28 = r5,
x29 = r4,
x3 = -2 r9+2 r8+3 r7+3 r6+2 r5- r2+ r19+ r17- r16- r15-2 r12 -2 r11-2 r10,
x30 = r3,
x31 = r2,
x32 = r1,
x4 = r8+ r6- r2+ r18+ r17- r15- r11,
x5 = - r9+ r8+2 r6+ r5- r4- r2+ r19+ r18+ r17-2 r15+ r13- r12- r11,
x6 = r17,
x7 = r3+ r19- r16,
x8 = 2 r9-2 r8-2 r7-4 r6-2 r5+ r4+2 r2-2 r19- r18-2 r17+2 r16 +2 r15+2 r12+3 r11+2 r10,
x9 = - r2+ r17+ r13

Здесь $k$ - константа ассоциативности квадрата; $S=4k$, где $S$ - магическая константа квадрата.
Очевидно, что в этой формуле так же 18 свободных переменных из 32 при заданной константе ассоциативности. Однако формула резко отличается от формулы, полученной по программе svb.

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

Я предпочитаю полученную мной формулу. Сейчас займусь программной реализацией этой формулы.

Далее, уже сейчас сделала шаблон из вычетов по модулю 3 по приведённому в предыдущем посте приближению к решению:

Код:
2  1  2  1  2  1  2  1
1  2  2  1  1  2  2  1
1  2  1  2  1  2  1  2
1  2  2  1  1  2  2  1
2  1  1  2  2  1  1  2
1  2  1  2  1  2  1  2
2  1  1  2  2  1  1  2
2  1  2  1  2  1  2  1

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

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


22/03/08

7154
Саратов
Преобразовала общую формулу идеального квадрата 8-го порядка (перешла от параметров ri к соответствующим переменным Xi).
Сначала покажу схему идеального квадрата 8-го порядка:

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

k - константа ассоциативности квадрата.

И вот такая компактная общая формула у меня получилась:

Код:
X(32)=4*K-X(31)-X(30)-X(29)-X(28)-X(27)-X(26)-X(25)
X(1) = X(24)- X(25)- X(27)+ X(29)+2*X(31)- X(12)- X(15)-2*X(6)+ X(2)- X(20)+ X(21)+ X(22)+ X(32)
X(10) = X(24)- X(25)-2*X(26)- X(27)- X(28)- X(29)+ X(12)+ X(15)- X(2)+ X(19)+ X(20)+ X(21)+ X(22) +2*X(23)- X(32)
X(11) = X(24)- X(25)- X(26)-2*X(27)- X(28)+ X(29)+ X(30)+2*X(31)-2*X(12)- X(15)- X(6)+ X(17)+ X(2) - X(19)- X(20)+ X(21)+2*X(22)+ X(23)+ X(32)
X(13) = X(24)- X(27)+ X(2)
X(14) = - X(24)+ X(25)+2*X(26)+2*X(27)+ X(28)+ X(29)+ X(31)- X(12)- X(15)- X(6)- X(20)- X(21)- X(22) - X(23)+ X(32)
X(16) = -2*X(24)+2*X(25)+2*X(26)+3*X(27)+2*X(28)- X(31)+ X(12)+ X(6)- X(17)- X(2)- X(21) -2*X(22)-2*X(23)
X(18) = - X(24)+ X(25)+ X(26)+ X(27)+ X(28)+ X(29)+ X(30)+ X(31)- X(17)- X(19)- X(20)- X(21)- X(22)- X(23) + X(32)
X(3) = -2*X(24)+2*X(25)+3*X(26)+3*X(27)+2*X(28)- X(31)+ X(12)+ X(6)- X(17)- X(2)-2*X(21) -2*X(22)-2*X(23)
X(4) = X(25)+ X(27)- X(31)+ X(15)+ X(6)- X(2)- X(22)
X(5) = - X(24)+ X(25)+2*X(27)+ X(28)- X(29)- X(31)+ X(12)+ X(15)+ X(6)-2*X(2)+ X(20)- X(21)- X(22)
X(7) = X(30)+ X(12)- X(17)
X(8) = 2*X(24)-2*X(25)-2*X(26)-4*X(27)-2*X(28)+ X(29)+2*X(31)-2*X(12)- X(15)-2*X(6)+2*X(17) +2*X(2)+2*X(21)+3*X(22)+2*X(23)
X(9) = - X(31)+ X(6)+ X(20)

Как уже говорила, в формуле имеем 18 свободных переменных из 32 при заданной константе ассоциативности K.

Сейчас проверю формулу на классическом идеальном квадрате.

-- Пн апр 13, 2015 15:49:31 --

Для проверки взяла следующий классический идеальный квадрат 8-го порядка:

Код:
1 56 49 47 42 31 26 8
* Potential scam. Censored *
4 30 27 46 43 53 52 5
* Potential scam. Censored *
7 50 55 41 48 25 32 2
* Potential scam. Censored *
6 28 29 44 45 51 54 3
57 39 34 23 18 16 9 64

Задаём константу ассоциативности и 18 свободных элементов из данного квадрата:

Код:
K=65
X(2)=56:X(6)=31:X(12)=20:X(15)=37:X(17)=4:X(19)=27:X(20)=46:X(21)=43
X(22)=53:X(23)=52:X(24)=5:X(25)=63:X(26)=33:X(27)=40:X(28)=17:X(29)=24:X(30)=10:X(31)=15

Вычисляем по общей формуле зависимые элементы. Получаем в точности тестируемый квадрат.
Итак, осталось написать программу по полученной общей формуле и найти решение, если оно существует :-)

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


22/03/08

7154
Саратов
Сегодня пока ещё крутилась старая программа.
И найдено последнее приближение к решению! - всего одна неправильная комплементарная пара: (143, 367):

Код:
31 353 239 373 383 199 401 61
467 193 * Potential scam. Censored *
143* 241 313 347 113 47 499 337
331 * Potential scam. Censored * 503
7 431 67 491 359 277 229 179
173 11 463 397 163 197 269 367
439 421 * Potential scam. Censored *
449 109 311 127 137 271 157 479

$K=510, S=2040$

Формально всего одна дырка - не простое число 143.
Объявим на сегодня число 143 простым :D

Интересно, что вчера за весь день не найдено ни одного решения с 2 дырками, а сегодня их найдено много (зато с 4 дырками решений было море вчера; а сегодня я сделала в программе только вывод решений с 2 дырками или совсем без дырок).
Может быть, завтра найдётся решение без дырок :wink: и не придётся писать новую программу.

Кстати, можно проверить на этом квадрате общую формулу (это решение получено не по общей формуле :!: ).

-- Пн апр 13, 2015 23:13:47 --

Проверка общей формулы

задаём из данного квадрата:

Код:
K=510
X(2)=353:X(6)=199:X(12)=101:X(15)=89:X(17)=143:X(19)=313:X(20)=347:X(21)=113
X(22)=47:X(23)=499:X(24)=337:X(25)=331:X(26)=281:X(27)=233:X(28)=151:X(29)=19:X(30)=443:X(31)=79

Вычисляем зависимые элементы по общей формуле, получаем в точности тестируемый квадрат.

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


22/03/08

7154
Саратов
Поиск идеального квадрата 8-го порядка по заданной строке

Общую формулу реализовала с применением одной эвристики. Эту эвристику и раньше применяла. Но вот для идеального квадрата она очень хорошо подходит.
Посмотрите на схему идеального квадрата 8-го порядка (схема сверху на иллюстрации):

Изображение

В зелёных ячейках на схеме находятся свободные элементы, их всего 18 штук из 32.
Оценить возможного полного перебора по общей формуле за приемлемое время трудно, я не берусь это сделать. Кто может оценить :?: Все свободные элементы должны перебираться в массиве, состоящем из 64 простых чисел; все зависимые элементы вычисляются по формуле и должны принадлежать тому же массиву.

Моя эвристика такая: генерируем случайным образом одну строку квадрата и симметричную ей. На иллюстрации вы видите сгенерированные строки (нижний квадрат). Таким образом, мы фактически выбрали значения 7 свободных элементов нужным образом, то есть так, что правильная строка искомого квадрата получена, а также и симметричная ей.
Теперь у нас осталось всего 11 свободных переменных и 48 чисел в массиве (16 чисел из двух полученных строк выбрасываем из массива). Вот этот полный перебор выполняется быстро, по моей программе около часа. По хорошей программе будет намного быстрее.

Всё! Осталась самая малость: посчитать, сколько будет таких строк для искомого квадрата :idea:
Подозреваю, что будет их очень много.

Сейчас кручу программу со случайной генерацией строки. Решение с одной неправильной комплементарной парой с показанным на иллюстрации вариантом строки нашлось с ходу:

Код:
127 277 * Potential scam. Censored *
157 463 119* 503 331 199 71 197
499 109 431 101 239 43 281 337
269 131 283 163 113 487 137 457
* Potential scam. Censored * 379 241
173 229 * Potential scam. Censored *
* Potential scam. Censored ** 47 353
* Potential scam. Censored * 233 383

$K=510, S=2040$

Неправильные элементы помечены звёздочкой.

Что можно добавить к предложенному алгоритму в целях повышения его эффективности :?:

-- Ср апр 15, 2015 09:08:29 --

Кстати, сгенерировать все варианты строк очень просто: это будет полный перебор 7 свободных элементов из 64 чисел массива :-)

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


20/08/14
10142
Россия, Москва
Nataly-Mak в сообщении #1004068 писал(а):
Осталась самая малость: посчитать, сколько будет таких строк для искомого квадрата :idea:
Nataly-Mak в сообщении #1004068 писал(а):
Кстати, сгенерировать все варианты строк очень просто: это будет полный перебор 7 свободных элементов из 64 чисел массива :-)
На самом деле меньше: не каждый вариант из 7-ми чисел будет давать правильный 8-й элемент (или что эквивалентно не каждый набор из 8-ми чисел даст нужную $S$). Кроме того, одну из переменных можно перебирать лишь 32 варианта, а не 64, ещё в два раза меньше.
Мой прямой подсчёт даёт 3050658 наборов по 8 чисел плюс 40320 размещений в каждом, итого 123млрд вариантов строк (вместо 3трлн вариантов по 7 чисел). Многовато.

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


22/03/08

7154
Саратов
Dmitriy40 в сообщении #1004283 писал(а):
На самом деле меньше: не каждый вариант из 7-ми чисел будет давать правильный 8-й элемент (или что эквивалентно не каждый набор из 8-ми чисел даст нужную $S$).

Вы делаете успехи :lol:

Цитата:
Многовато.

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

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

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


22/03/08

7154
Саратов
Есть!!!
Получен минимальный идеальный квадрат 8-го порядка из различных простых чисел ($S=2040$).
Решение нашла программа, в которой реализована общая формула плюс шаблон из вычетов по модулю 3:

Код:
1  1  1  2  2  1  2  2
1  2  1  2  1  2  2  1
1  2  2  2  2  1  1  1
2  2  1  1  2  1  2  1
2  1  2  1  2  2  1  1
2  2  2  1  1  1  1  2
2  1  1  2  1  2  1  2
1  1  2  1  1  2  2  2

Шаблон получен по одному из приближений к решению с двумя дырками.

Решение представлено на конкурс, поэтому пока не показываю.

Ну вот, завершён очень большой этап: минимизированы решения для порядков 7,8.
Для порядка 9 мне пока удалось найти очень незначительное улучшение результата alexBlack.
Его результат $S=24237$, мой результат $S=23319$.

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


22/03/08

7154
Саратов
Общая формула идеального квадрата 9-го порядка, полученная мной решением системы линейных уравнений, показана здесь .
Имеем 24 свободные переменные из 40 при заданной константе ассоциативности квадрата.

Покажу схему идеального квадрата 9-го порядка, по которой составлялась система уравнений:

Изображение

Здесь $k$ - константа ассоциатинвости, связана с магической константой квадрата следующим соотношением:
$S=9k/2$
В зелёных ячейках находятся свободные элементы.

Расскажу алгоритм, с помощью которого я сейчас пытаюсь найти следующее улучшение полученного мной ранее решения с магической константой $S=23319$ (это решение было найдено применением данного алгоритма).
Сначала строю ассоциативный квадрат с заданной константой ассоциативности, для этого использую метод двух точных ортогональных покрытий массива (метод описан подробно в теме "Магические квадраты").

Сразу покажу конкретный пример, сейчас у меня $K=5114$.
Это ассоциативный квадрат с такой константой ассоциативности:

Код:
2731 7 * Potential scam. Censored * 4567 631 2161
* Potential scam. Censored * 3823 5101 127 1321 1783
* Potential scam. Censored * 283 37 4441 1093 4657
157 1423 937 4327 4261 5011 163 3373 3361
* Potential scam. Censored * * Potential scam. Censored * 1063
1753 1741 4951 103 853 787 4177 3691 4957
457 4021 673 * Potential scam. Censored * 883 211
3331 3793 4987 13 1291 2467 751 3943 2437
2953 4483 547 3391 523 463 3163 5107 2383

$K=5114, S=23013$

Ассоциативный квадрат строится легко указанным методом.
Этому ассоциативному квадрату не хватает пандиагональности, чтобы быть идеальным.
Теперь берём из этого ассоциативного квадрата значения 12 свободных элементов:

Код:
X(2)=7:X(3)=1951:X(4)=4651:X(7)=4567:X(8)=631:X(10)=2677:X(24)=37:X(28)=157:X(30)=937
X(34)=163:X(35)=3373:X(36)=3361

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

Пока мне удалось найти для данной константы ассоциативности приближение с одной неправильной комплементарной парой (1999, 3115):

Код:
1171 7 * Potential scam. Censored * 4567 631 883
* Potential scam. Censored * 4363 3121 523 2521 1093
4801 5011 1999* 1723 691 37 1861 4507 2383
157 4831 937 1381 4987 3823 163 3373 3361
* Potential scam. Censored * * Potential scam. Censored * 3643
* Potential scam. Censored * 127 3733 4177 283 4957
2731 607 * Potential scam. Censored * 3115* 103 313
* Potential scam. Censored * 751 * Potential scam. Censored *
4231 * Potential scam. Censored * 3163 5107 3943

$K=5114, S=23013$

Массив для данной константы ассоциативности состоит из 64 комплементарных пар, вот он:

Код:
7 * Potential scam. Censored * 181 211 283 313 331 457 463 523 547 601 607 631 673 691 751 757 787 853 883
937 * Potential scam. Censored * * Potential scam. Censored * * Potential scam. Censored * * Potential scam. Censored * 1657 1723 1741
* Potential scam. Censored * * Potential scam. Censored * * Potential scam. Censored * * Potential scam. Censored * * Potential scam. Censored *
* Potential scam. Censored * * Potential scam. Censored * * Potential scam. Censored * * Potential scam. Censored * * Potential scam. Censored *
* Potential scam. Censored * * Potential scam. Censored * * Potential scam. Censored * * Potential scam. Censored * * Potential scam. Censored *
* Potential scam. Censored * * Potential scam. Censored * * Potential scam. Censored * * Potential scam. Censored * * Potential scam. Censored * 5101 5107

Задача минимизации решения для $n=9$ сложна тем, что потенциальных магических констант много. Нижняя граница известна: 12249. Можно попробовать начать с поиска минимального квадрата.

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


22/03/08

7154
Саратов
Не хочет решение для порядка 9 минимизироваться :-(
Проверила следующие потенциальные магические константы: 23013, 21969, 21393, 18729.
Алгоритм тот же самый. Ассоциативные квадраты со всеми константами строятся легко.
А вот с идеальными плохи дела.
Решения с одной неправильной комплементарной парой есть, но не слишком много.
Например:

Код:
163 313 * Potential scam. Censored * 3001 151 1987
* Potential scam. Censored * * Potential scam. Censored * 877
3331 643 2995* 1381 2371 751 3187 2137 4597
* Potential scam. Censored * 4357 271 3967 523 661
601 811 2953 241 * Potential scam. Censored * 4153
4093 4231 787 4483 397 3541 457 1123 2281
157 * Potential scam. Censored * 3373 1759* 4111 1423
3877 2593 733 * Potential scam. Censored * 2803 823
2767 4603 1753 577 1447 97 1117 4441 4591

$K=4754, S=21393$
Неправильная комплементарная пара (1759, 2995), формально только одна дырка - не простое число 2995.
Надо либо изменить алгоритм, либо бросить пока эту задачу. Не идёт.

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


22/03/08

7154
Саратов
Пока программа для квадрата 9-го порядка ещё крутится (с тающей надеждой на успех), покажу, что мы имеем для поиска идеального квадрата 11-го порядка.

Схема идеального квадрата 11-го порядка

Изображение

Здесь $k$ - константа ассоциативности квадрата, связана с магической константой следующим соотношением:
$S=11k/2$.
В зелёных ячейках находятся свободные элементы, их 40 из 60 при заданной константе ассоциативности квадрата.

Общая формула идеального квадрата 11-го порядка

Код:
X(1) = -(-4*X(52)-2*X(55)+3*K-4*X(16)-2*X(8)-4*X(57)-4*X(22)+2*X(23)+4*X(15) +2*X(3)-2*X(26)-4*X(27)-2*X(28)+4*X(29)-2*X(30)+4*X(10)-2*X(58) -4*X(32)-6*X(33)+4*X(34)+2*X(35)-4*X(36)+6*X(4)-2*X(38)+2*X(39) +2*X(40)+6*X(9)+4*X(59)-2*X(43)-4*X(44)+2*X(45)-4*X(46)-4*X(47) +6*X(5)+2*X(7)) /4
     
X(11) = -(4*X(53)+4*X(54)+6*X(55)-21*K-4*X(16)-2*X(8)-4*X(57)+4*X(22)+6*X(23) -4*X(15)-2*X(3)-2*X(26)-12*X(27)-2*X(28)+4*X(29)-2*X(30)+12*X(10) -2*X(58)-4*X(32)-2*X(33)+6*X(35)+6*X(4)-6*X(38)-6*X(39)+6*X(40) +2*X(9)+8*X(59)-
4*X(42)+2*X(43)+2*X(45)+8*X(47)+4*X(48)+2*X(5) +4*X(50)+6*X(7)) /4   

X(12) = (-4*X(52)+3*K-4*X(16)-2*X(8)-2*X(57)-2*X(22)+2*X(23)-4*X(27)-2*X(28) +4*X(29)+4*X(10)-4*X(32)-2*X(33)+2*X(34)+2*X(35)-2*X(36)+2*X(4) -2*X(38)+2*X(40)+4*X(9)+4*X(59)-2*X(42)-2*X(43)-2*X(44)+2*X(5) +2*X(50)+2*X(7)) /2
 
X(13) = (-2*X(52)-2*X(53)-4*X(54)-2*X(55)+11*K+2*X(16)+2*X(8)-4*X(22)-6*X(23) +4*X(15)+2*X(3)+6*X(27)+2*X(28)-2*X(29)-4*X(10)+2*X(58)-4*X(35) +4*X(38)+4*X(39)-2*X(40)-4*X(59)-2*X(44)-2*X(45)-2*X(46)-6*X(47) +2*X(5)-2*X(50)-2*X(7)+2*X(60)) /2
 
X(14) = (-2*X(55)+3*K-4*X(16)+2*X(8)+4*X(57)+2*X(23)-4*X(15)-2*X(3)-2*X(26) -2*X(28)+2*X(30)+2*X(58)+2*X(33)+2*X(35)-6*X(4)-2*X(38)-2*X(39) -2*X(40)+2*X(9)-2*X(43)+2*X(45)+4*X(46)+4*X(47)-2*X(5)+2*X(7)) /4
   
X(17) = 2*X(52)+ X(54)+ X(55)-5*K+ X(8)+ X(57)+2*X(22)+ X(23)-2*X(15)- X(3)- X(27)- X(29) +2*X(32)+ X(33)+ X(35)+ X(36)- X(4)- X(39)- X(9)+ X(42)+ X(43)+2*X(44)+ X(45) + X(46)+2*X(47)-2*X(5)- X(60)
 
X(18) = - X(52)- X(53)- X(54)- X(55)+6*K+ X(16)-2*X(22)-2*X(23)+2*X(15)+2*X(3)+3*X(27) - X(29)-2*X(10)-2*X(35)+ X(38)+2*X(39)- X(40)-2*X(59)- X(45)- X(46)-3*X(47) - X(48)+ X(5)- X(50)- X(7)+ X(60)
   
X(19) = (-2*X(52)+4*X(53)+4*X(54)+2*X(55)-7*K-4*X(16)-4*X(8)-4*X(57)+6*X(23)-2*X(15) -2*X(3)-8*X(27)-2*X(28)+4*X(29)+8*X(10)-2*X(58)-4*X(32)-2*X(33) +2*X(34)+4*X(35)-2*X(36)+4*X(4)-4*X(38)-4*X(39)+4*X(40)+2*X(9) +6*X(59)-2*X(42)-2*X(44)+2*X(45)+4*X(47)+2*X(48)+2*X(5)+4*X(50) +2*X(7)) /2 

X(2) = (2*X(54)+ K-2*X(8)-2*X(57)+2*X(23)-2*X(27)+2*X(29)+2*X(10)-2*X(58)-2*X(33) +2*X(4)-2*X(38)+2*X(40)+2*X(59)-2*X(46)) /2
 
X(20) = -(-8*X(52)-2*X(55)+ K-4*X(16)-2*X(8)-4*X(57)-8*X(22)+2*X(23)+4*X(15) +2*X(3)-2*X(26)-4*X(27)-2*X(28)+4*X(29)+2*X(30)+8*X(10)-2*X(58) -8*X(32)-6*X(33)+4*X(34)+2*X(35)-4*X(36)+6*X(4)-2*X(38)+2*X(39) +6*X(40)+6*X(9)+4*X(59)-4*X(42)-2*X(43)-4*X(44)+2*X(45)-4*X(46) -4*X(47)+6*X(5)+4*X(50)+2*X(7)+4*X(60)) /4
   
X(21) = -(-2*X(52)- K-2*X(16)-2*X(28)+2*X(58)+2*X(33)+2*X(34)-2*X(4)-2*X(40) +2*X(9)+2*X(46)) /2
 
X(24) = 2*X(52)+ X(53)+2*X(54)+ X(55)-5*K+2*X(22)+2*X(23)-2*X(15)- X(3)-2*X(27)+2*X(10) - X(58)+ X(32)- X(34)+ X(35)- X(38)-2*X(39)+ X(40)- X(9)+ X(59)+ X(43)+ X(44)+ X(45) +3*X(47)- X(5)+ X(50)+ X(7)- X(60) 

X(25) = - X(54)+5*K+ X(16)-2*X(23)+ X(15)+ X(27)- X(29)- X(30)-2*X(10)- X(35)+ X(38)+ X(39) - X(40)- X(59)+ X(42)- X(45)-2*X(47)- X(50)- X(7)
   
X(31) = (-4*X(52)-2*X(53)-2*X(54)-2*X(55)+11*K-2*X(16)-4*X(22)-2*X(23)+2*X(15) +2*X(3)-2*X(26)-2*X(28)+2*X(58)-4*X(32)-2*X(33)+2*X(34)+2*X(39) +2*X(9)-2*X(42)-2*X(43)-2*X(44)-2*X(47)+2*X(5)+2*X(60)) /2
 
X(37) = (4*X(53)+4*X(54)+2*X(55)+5*K-4*X(16)-2*X(8)-4*X(57)+6*X(23)-4*X(15)-2*X(3) -2*X(26)-8*X(27)-2*X(28)+4*X(29)+2*X(30)+8*X(10)-2*X(58)-4*X(32) -2*X(33)+2*X(35)-4*X(36)+2*X(4)-6*X(38)-6*X(39)+2*X(40)+2*X(9) +4*X(59)-4*X(42)-2*X(43)-4*X(44)+2*X(45)+4*X(47)+2*X(5)+4*X(50) +2*X(7)) /4
 
X(41) = -(4*X(53)+4*X(54)+2*X(55)-17*K-4*X(16)-2*X(8)-4*X(57)+6*X(23)-4*X(15) -2*X(3)-2*X(26)-8*X(27)-2*X(28)+4*X(29)+2*X(30)+8*X(10)-2*X(58) -4*X(32)-2*X(33)+4*X(34)+6*X(35)+2*X(4)-2*X(38)-2*X(39)+6*X(40) +2*X(9)+4*X(59)+2*X(43)+2*X(45)+4*X(47)+2*X(5)+4*X(50)+2*X(7)) /4
   
X(49) = - X(52)- X(53)- X(54)- X(55)+6*K- X(22)- X(23)+ X(15)+ X(3)+ X(27)- X(10)- X(35)+ X(39) - X(59)- X(45)- X(46)-2*X(47)- X(48)- X(50)
   
X(51) = (- K+2*X(22)+2*X(23)-2*X(15)-2*X(3)-2*X(27)+2*X(10)+2*X(35)-2*X(39) +2*X(59)+2*X(47)) /2
 
X(56) = X(52)- X(53)- X(54)- X(55)+5*K+2*X(16)+ X(8)+ X(57)-3*X(23)+2*X(15)+ X(3)+4*X(27) + X(28)-2*X(29)-4*X(10)+2*X(32)+ X(33)- X(34)-2*X(35)- X(4)+2*X(38)+2*X(39) -2*X(40)- X(9)-3*X(59)+2*X(42)+ X(44)- X(45)- X(46)-3*X(47)- X(48)-2*X(50) -2*X(7)
 
X(6) = (-2*X(52)+2*X(53)+2*X(55)+ K-4*X(16)-2*X(8)-2*X(57)+2*X(23)-2*X(3)-2*X(26) -6*X(27)-2*X(28)+2*X(29)-2*X(30)+4*X(10)-4*X(32)-2*X(33)+2*X(34) +4*X(35)-2*X(36)+2*X(4)-2*X(38)-2*X(39)+2*X(40)+2*X(9)+4*X(59) -2*X(42)-2*X(44)+2*X(45)+2*X(47)+2*X(48)+2*X(5)+2*X(50)+2*X(7)) /2

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

Покажу первое приближение к решению, плохое - 10 неправильных комплементарных пар; фактически 20 дырок, формально 16 дырок. То есть из 20 зависимых элементов ровно половина попала в нужный массив простых чисел.

Код:
* Potential scam. Censored * 941 3803 743 239 2381 4751 1499
4145* 2687* 2039 569 2129 7097* 359* 3419* 2813* 101 1163
563 3809* 1061 179 * Potential scam. Censored * 1541* 2741 4463
3389 1979 431 * Potential scam. Censored * 23 1913 4229 3533
* Potential scam. Censored * 1541* 3719 1307* 4139 5 1811 2549
* Potential scam. Censored * 2411 4691 89 1283 3911 4793
2273 3011 4817 683 3515* 1103 3281* 971 3251 1613 2003
1289 593 2909 4799 1409 773 * Potential scam. Censored * 1433
359 2081 3281* 2609 2243 1451 821 4643 3761 1013* 4259
3659 4721 2009* 1403* 4463* -2275* * Potential scam. Censored ** 677*
3323 71 * Potential scam. Censored * * Potential scam. Censored * 149

$K=4822, S=26521$
Неправильные элементы помечены звёздочкой.
Есть даже один отрицательный элемент, что совсем плохо.

Надо работатать дальше.
Пока неизвестно ни одного идеального квадрата 11-го порядка из различных простых чисел. И на конкурс никто не представил пока :wink:

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


22/03/08

7154
Саратов
Вчера опубликовала в OEIS последовательность наименьших магических констант идеальных квадратов из различных простых чисел - A257316.

maxal
большое спасибо за редактирование чернового варианта статьи.

Продолжаю поиск идельного квадрата 11-го порядка, причём сразу начала с минимального квадрата.
На основе показанного выше плохого приближения к решению написала новую программу.
Отличие её от старой следующее: в старой было зафиксировано 22 свободные переменные (взяла я их из ассоциативного квадрата); в новой программе зафиксировано только 18 свободных переменных, и взяла я их из приведённого приближения к решению.
Таким образом, осталось для перебора 22 свободные переменные (из 40) и в массиве 86 простых чисел (43 комплементарные пары). Перебор всё равно получается очень долгий. Но приближение к решению нашлось довольно быстро, оно чуть лучше первого приближения:

Код:
4709* 2441 2423 * Potential scam. Censored * 401 4751 4463
3617 3449 1361 569 809 4787 239 4655* 4379* 1493 1163
563 * Potential scam. Censored * 449 149 3761 4061* 1913 3389
179 1979 941 3413* 3671 4049 173 * Potential scam. Censored *
* Potential scam. Censored * * Potential scam. Censored * 5 1811 29
1091 911 3539 4733 131 2411 4691 89 1283 3911 3731*
4793 3011 4817 683 743 1103 3533 971 3251 1613 2003
3299 1409 2243 221 4649 773 1151 1409* 3881 2843 4643
1433 2909 761 * Potential scam. Censored * 1619 821 1019 4259
3659 * Potential scam. Censored ** * Potential scam. Censored * 1205*
359 71 * Potential scam. Censored * 4799 593 2399 2381 113

$K=4822, S=26521$

В приближении
а) 9 неправильных комплементарных пар, причём одна неправильная, потому что повторена;
б) нет отрицательных элементов;
в) формально всего 9 дырок (это не простые числа и простые повторенные числа, помечены звёздочкой).

Думаю, что этот идеальный квадрат вполне может существовать. Однако найти его непросто.
Как уже выяснили в конкурсе по пандиагональным квадратам из простых чисел, чем больше порядок квадрата, тем больше вероятность существования квадрата с минимальной магической константой.
Для идеальных квадратов, наверное, это тоже справедливо. Уже для порядка $n=8$ я нашла минимальный идеальный квадрат.

-- Ср апр 22, 2015 08:14:45 --

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

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


22/03/08

7154
Саратов
Программа крутилась целый день.
Прогресс такой: получено несколько приближений с 6 неправильными комплементарными парами. Уже из 20 зависимых переменных 14 попали в массив простых чисел; осталось 12 фактических дырок.

Пример такого приближения:

Код:
* Potential scam. Censored * * Potential scam. Censored * 4751 2909
4037* 3221 1493 569 2213 4421 149 4739* 2693 1823 1163
563 3323 3371 809 1229 821 * Potential scam. Censored * 4649
239 1979 1151 3905* 3881 4049 593 2327* 2741 3413 2243
* Potential scam. Censored * * Potential scam. Censored * 5 1811 29
1373 911 3539 4733 131 2411 4691 89 1283 3911 3449
4793 3011 4817 683 743 1103 3533 971 3251 1613 2003
* Potential scam. Censored ** 4229 773 941 917* 3671 2843 4583
173 3299 485* 359 * Potential scam. Censored * 1451 1499 4259
3659 2999 2129 83 4673 401 * Potential scam. Censored * 785*
1913 71 * Potential scam. Censored ** 4799 179 2399 1733 449

$K=4822, S=26521$

В приближении
а) 6 неправильных комплементарных пар (12 фактических дырок);
б) формально 9 дырок (помечены звёздочкой);
в) нет повторяющихся элементов;
г) все элементы в нужном диапазоне (нет отрицательных элементов).

Ну, довольно хорошее приближение, однако до полного решения, как до неба.

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


16/08/05
1130
случайно нашёл, статья из 1914 года

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1005 ]  На страницу Пред.  1 ... 63, 64, 65, 66, 67

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



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

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


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

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