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 499 19 487 463 67 467 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-х квадрантов)

Код:
7 499 19 487 31 467 67 463
53 421 233 409 71 379 157 317
61 347 239 401 79 373 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  11  19  23  31  43  47  53  61  67  71  79  89  101  109  113  127  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
337 89 383 397 79 281 233 241
269 277 229 431 113 127 421 173
409 353 61 11 373 179 193 461
53 19 283 479 503 151 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
62 11 14 20 21 36 37 59
4 30 27 46 43 53 52 5
63 33 40 17 24 10 15 58
7 50 55 41 48 25 32 2
60 13 12 22 19 38 35 61
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 283 101 457 379 89 71
143* 241 313 347 113 47 499 337
331 281 233 151 19 443 79 503
7 431 67 491 359 277 229 179
173 11 463 397 163 197 269 367
439 421 131 53 409 227 317 43
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 89 359 443 193 491 61
157 463 119* 503 331 199 71 197
499 109 431 101 239 43 281 337
269 131 283 163 113 487 137 457
53 373 23 397 347 227 379 241
173 229 467 271 409 79 401 11
313 439 311 179 7 391* 47 353
449 19 317 67 151 421 233 383

$K=510, S=2040$

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

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

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

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

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


20/08/14
11065
Россия, Москва
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 1951 4651 4591 1723 4567 631 2161
2677 1171 4363 2647 3823 5101 127 1321 1783
4903 4231 1801 1567 283 37 4441 1093 4657
157 1423 937 4327 4261 5011 163 3373 3361
4051 2143 2803 1237 2557 3877 2311 2971 1063
1753 1741 4951 103 853 787 4177 3691 4957
457 4021 673 5077 4831 3547 3313 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 1951 4651 4051 5101 4567 631 883
2677 1597 3547 3571 4363 3121 523 2521 1093
4801 5011 1999* 1723 691 37 1861 4507 2383
157 4831 937 1381 4987 3823 163 3373 3361
1471 2143 1237 3313 2557 1801 3877 2971 3643
1753 1741 4951 1291 127 3733 4177 283 4957
2731 607 3253 5077 4423 3391 3115* 103 313
4021 2593 4591 1993 751 1543 1567 3517 2437
4231 4483 547 13 1063 463 3163 5107 3943

$K=5114, S=23013$

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

Код:
7 13 37 103 127 157 163 181 211 283 313 331 457 463 523 547 601 607 631 673 691 751 757 787 853 883
937 1021 1063 1087 1093 1171 1237 1291 1321 1381 1423 1471 1483 1531 1543 1567 1597 1657 1723 1741
1753 1783 1801 1861 1933 1951 1993 2053 2113 2143 2161 2281 2311 2347 2383 2437 2467 2521 2593 2647
2677 2731 2767 2803 2833 2953 2971 3001 3061 3121 3163 3181 3253 3313 3331 3361 3373 3391 3457 3517
3547 3571 3583 3631 3643 3691 3733 3793 3823 3877 3943 4021 4027 4051 4093 4177 4231 4261 4327 4357
4363 4423 4441 4483 4507 4513 4567 4591 4651 4657 4783 4801 4831 4903 4933 4951 4957 4987 5011 5077 5101 5107

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

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


22/03/08

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

Код:
163 313 3637 4657 3307 4177 3001 151 1987
3931 1951 2671 2287 1291 2203 4021 2161 877
3331 643 2995* 1381 2371 751 3187 2137 4597
2473 3631 4297 1213 4357 271 3967 523 661
601 811 2953 241 2377 4513 1801 3943 4153
4093 4231 787 4483 397 3541 457 1123 2281
157 2617 1567 4003 2383 3373 1759* 4111 1423
3877 2593 733 2551 3463 2467 2083 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 зависимых элементов ровно половина попала в нужный массив простых чисел.

Код:
4673 3449 2423 1619 941 3803 743 239 2381 4751 1499
4145* 2687* 2039 569 2129 7097* 359* 3419* 2813* 101 1163
563 3809* 1061 179 4001 3371 2579 2213 1541* 2741 4463
3389 1979 431 1493 2069 4049 3413 23 1913 4229 3533
2819 3209 1571 3851 1541* 3719 1307* 4139 5 1811 2549
29 911 3539 4733 131 2411 4691 89 1283 3911 4793
2273 3011 4817 683 3515* 1103 3281* 971 3251 1613 2003
1289 593 2909 4799 1409 773 2753 3329 4391 2843 1433
359 2081 3281* 2609 2243 1451 821 4643 3761 1013* 4259
3659 4721 2009* 1403* 4463* -2275* 2693 4253 2783 2135* 677*
3323 71 2441 4583 4079 1019 3881 3203 2399 1373 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 4229 23 2549 101 431 401 4751 4463
3617 3449 1361 569 809 4787 239 4655* 4379* 1493 1163
563 3803 4001 3203 1229 449 149 3761 4061* 1913 3389
179 1979 941 3413* 3671 4049 173 4601 2579 3413 1523
2819 3209 1571 3851 1289 3719 4079 4139 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 1061 4673 4373 3593 1619 821 1019 4259
3659 3329 443 167 4583 35* 4013 4253 3461 1373 1205*
359 71 4421 4391 4721 2273 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 фактических дырок.

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

Код:
4373 3089 2423 4643 23 2417 101 431 1361 4751 2909
4037* 3221 1493 569 2213 4421 149 4739* 2693 1823 1163
563 3323 3371 809 1229 821 1433 4463 4337 1523 4649
239 1979 1151 3905* 3881 4049 593 2327* 2741 3413 2243
2819 3209 1571 3851 1289 3719 4079 4139 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
2579 1409 2081 2495* 4229 773 941 917* 3671 2843 4583
173 3299 485* 359 3389 4001 3593 4013 1451 1499 4259
3659 2999 2129 83 4673 401 2609 4253 3329 1601 785*
1913 71 3461 4391 4721 2405* 4799 179 2399 1733 449

$K=4822, S=26521$

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

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

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


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

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

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



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

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


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

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