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

[mertz]

The other 2 threads are probably still running, but stuck in a loop. My compiler produces bad programs sometimes. I will recompile and test.

[whitefox]

Сделаем тоже самое, но только по модулю 6.

Для чисел Массива №1 получим следующий комплект вычетов:

1 -- 23 шт
3 -- 1 шт
5 -- 25 шт

$733\equiv1\pmod6$

Сумма вычетов любого ряда равна одному из следующих чисел:
7, 13, 19, 25, 31.
А сумма вычетов всего квадрата равна 151.

Каждое из чисел 7, 13, 19, 25, 31 имеет единственное представление в виде суммы семи слагаемых принадлежащих множеству {1, 3, 5} среди которых не более чем одна тройка. А именно:

7=1+1+1+1+1+1+1
13=1+1+1+1+1+3+5
19=1+1+1+1+5+5+5
25=1+1+3+5+5+5+5
31=1+5+5+5+5+5+5

Пусть x -- число строк с суммой 7
y -- число строк с суммой 13
z -- число строк с суммой 19
u -- число строк с суммой 25
t -- число строк с суммой 31

Составим следующую систему уравнений:

$\begin{cases} 7x+13y+19z+25u+31t=151\\ x+y+z+u+t=7\\ 7x+5y+4z+2u+t=23\\ y+u=1\\ y+3z+4u+6t=25 \end{cases}$

После приведения получим:

$\begin{cases} 2x+y+z=5\\ y+u=1\\ x+z+t=6 \end{cases}$

Так как переменные могут принимать только целые неотрицательные значения, то эта система имеет шесть решений:

x=0, y=0, z=5, u=1, t=1
x=0, y=1, z=4, u=0, t=2
x=1, y=0, z=3, u=1, t=2
x=1, y=1, z=2, u=0, t=3
x=2, y=0, z=1, u=1, t=3
x=2, y=1, z=0, u=0, t=4

Составим строки квадрата в соответствии с последним шаблоном.
Но тогда любой столбец имеет не менее двух единиц. Это не верно, так как в любом шаблоне присутствует хотя бы один ряд типа "t", а он имеет только одну единицу. Поэтому два последних шаблона отбрасываем.

Получили, что любой ряд (и диагональ) пандиагонального квадрата должен соответствовать одному из следующих пяти шаблонов:

1 1 1 1 1 1 1
1 1 1 1 1 3 5
1 1 1 1 5 5 5
1 1 3 5 5 5 5
1 5 5 5 5 5 5

А любое из четырёх покрытий пандиагонального квадрата должно соответствовать одному из следующих четырёх шаблонов:

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

Первые пять шаблонов позволят разделить, найденную Nataly-Mak, базу данных из 393714 разбиений (393510 для Массива №2) на пять подбаз.

А вторые четыре шаблона позволят существенно ускорить поиск покрытий.

[mertz]

I recompiled. It seems to work.

https://www.dropbox.com/s/7z68fmfx7akfkth/743.jpg

Give it another try.

https://www.dropbox.com/s/pvpcyeuf9fb8355/Pan2.exe

[Pavlovsky]

mertz
Почему ваша программа ищет квадраты только до магической суммы 737? Ведь магическая сумма может быть еще 735 и 733.

[mertz]

I believe the description of his algorithm was every 6. I could be wrong. 737 - 6 = 731. Best solution possible 733.

Tried running 733 and 735. No results.

I had 7 1-fault solutions for 743 after running 2 hours.

Running 737 now.

[Nataly-Mak]

mertz в сообщении #759004 писал(а):

I recompiled. It seems to work.

mertz
видимо, причина в моём компьютере: он не может обеспечить работу 4-х потоков (в процессоре всего 2 ядра).
Запустила новую версию, по-прежнему работают 2 потока.
Извините за доставленные хлопоты.

whitefox
отличный анализ. Конечно же, простые числа лучше всего рассматривать по модулю 6.
Не совсем поняла шаблоны для покрытий.

Теперь мне надо сочинить шаблон из вычетов по модулю 6 (раньше я использовала шаблон по модулю 3). Тогда будет три группы чисел и перебор должен ещё ускориться намного, так как в каждой из трёх групп будет не так много чисел.
С другой стороны, шаблонов будет много и проверка по одному шаблону не даст ответ о существовании/несуществовании решения. Ну, буду пытаться его найти хотя бы по одному из шаблонов такого вида.

[whitefox]

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

Не совсем поняла шаблоны для покрытий.

Шаблон (0 0 5 1 1) означает, что покрытие имеет пять разбиений типа "19" и по одному разбиению типов "25" и "31".
А шаблон (1 1 2 0 3) означает, что покрытие имеет по одному разбиению типов "7" и "13", два разбиения типа "19" и три разбиения типа "31".

[Nataly-Mak]

whitefox
спасибо, теперь поняла.

Возникает такой вопрос: много ли будет шаблонов из вычетов по модулю 6 для магической константы 733
Не поможете мне сочинить хотя бы один такой шаблон?
Сейчас посмотрю на решение Jarek $S=769$. Может быть, оно даст нужный шаблон.

[whitefox]

$769\equiv1\pmod6$

Если использованный в том решении набор простых имеет тот же комплект вычетов:

1 -- 23 шт
3 -- 1 шт
5 -- 25 шт

то Вам подойдёт любой шаблон для того решения.

[Nataly-Mak]

whitefox в сообщении #759089 писал(а):

$769\equiv1\pmod6$

Если использованный в том решении набор простых имеет тот же комплект вычетов:

1 -- 23 шт
3 -- 1 шт
5 -- 25 шт

то Вам подойдёт любой шаблон для того решения.

Только сейчас обратила внимание на то, что вычет 3 всего один.
Так что, шаблон из вычетов по модулю 6 не имеет никакого преимущества перед шаблоном из вычетов по модулю 3, которым я пользовалась. Будут по-прежнему две большие группы чисел - с вычетом 1 и с вычетом 5. При использовании шаблона по модулю 3 имеем 1 вычет 0 и две большие группы чисел, соответствующие вычетам 1 и 2:

2 2 1 2 1 1 0
2 2 1 2 2 1 2
2 1 2 1 1 1 1
1 2 1 2 2 2 2
2 2 1 2 2 2 1
1 2 2 2 2 1 2
2 1 1 1 2 1 1

(этот шаблон для магических констант кратных 3).
Этот путь отпадает.

P.S. Шаблон из вычетов 1,3,5 (именно в указанных количествах вычетов) всё равно надо сочинить (хотя бы один), чтобы убедиться в его существовании. Конечно, ничто не мешает ему существовать, но лучше всё же удостовериться.

Разве попробовать строить квадрат по шаблону из вычетов по модулю 9. Тут будет 7 групп чисел (отсутствуют вычеты 0 и 6). Максимальное количество чисел в группе - 9. Вот это должно перебираться быстро. Фактически даже будет 6 групп, ибо в седьмой группе будет одно число 3, соответствующее вычету 3. Это число мы фиксируем. Остальные 23 свободных переменных будут полностью перебираться, каждая в своей группе.

[whitefox]

Если $n$ нечётное простое, то:

$n\equiv0\pmod3\text{ тогда и только тогда, когда }n\equiv3\pmod6$
$n\equiv1\pmod3\text{ тогда и только тогда, когда }n\equiv1\pmod6$
$n\equiv2\pmod3\text{ тогда и только тогда, когда }n\equiv5\pmod6$

Так, что Ваш вывод верен -- эти шаблоны эквивалентны.

[Nataly-Mak]

Пыхтит мой компьютер



К сожалению, решения ему не попадаются.
И моя программа тоже работает, ищет решение с магической константой 733. Пока нет даже решения с двумя дырками.
У кого-нибудь есть решения с магической константой 733 с одной или с двумя дырками? Хоть посмотреть на первые приближения к решению.

-- Пт авг 30, 2013 23:30:18 --

Попыталась вручную сочинить шаблон из вычетов 1,3,5 (в указанных количествах) и цепочек того вида, какие получил whitefox.
Оно того... вручную не получается
Вот неудавшаяся попытка:

1 1 5 5 5 5 3
5 x x 5 1 1 1
5 5 5 1 1 1 1
5 5 1 1 1 5 1
1 5 5 1 x x 1
1 1 1 5 x x 1
1 1 x 1 5 x 5

Программу надо писать.
А может, кто вручную смастерит?
А лучше бы его вообще нельзя было смастерить. Это бы означало, что такого решения не существует в природе.

[mertz]

737 - 1422 two-hole, 4 one hole solutions

f[{
{3,17,223,107,79,181,127},
{233,199,73,83,37,41,71},
{7,13,77,137,191,61,251},
{67,113,173,97,179,19,89},
{283,101,11,109,31,149,53},
{5,131,151,157,23,227,43},
{139,163,29,47,197,59,103}
}]

f[{
{3,113,89,79,67,163,223},
{107,103,199,137,11,29,151},
{61,17,127,47,227,157,101},
{229,71,173,43,191,13,17},
{269,109,53,19,97,149,41},
{37,131,23,233,139,167,7},
{31,193,73,179,5,59,197}
}]

f[{
{3,89,191,79,103,73,199},
{107,19,193,83,101,227,7},
{181,131,151,113,23,67,71},
{109,29,11,61,251,37,239},
{179,139,137,97,163,17,5},
{127,59,41,257,43,167,43},
{31,271,13,47,53,149,173}
}]

f[{
{3,107,61,167,193,79,127},
{119,151,157,19,179,71,41},
{277,29,11,23,137,97,163},
{103,149,67,281,73,47,17},
{37,89,101,211,43,173,83},
{191,13,113,31,53,139,197},
{7,199,227,5,59,131,109}
}]

[Nataly-Mak]

mertz в сообщении #759130 писал(а):

737 - 1422 two-hole, 4 one hole solutions

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

Для $S=735$ dimkadimon показал нам решение с двумя дырками; я получаю для этой магической константы решения с 3 дырками легко.

Теперь хочется увидеть приближения к решению $S=733$.
Кто покажет?

[whitefox]

Рассмотрим числа Массива №1 по модулю 4.

Получим следующий комплект вычетов:

1 -- 22 шт
3 -- 27 шт

$733\equiv1\pmod4$

Поэтому сумма вычетов одного ряда равна одному из чисел: 9, 13, 17, 21.

Каждое из этих чисел имеет единственное представление в виде суммы семи слагаемых принадлежащих множеству {1, 3}. А именно:

9=1+1+1+1+1+1+3
13=1+1+1+1+3+3+3
17=1+1+3+3+3+3+3
21=3+3+3+3+3+3+3

Сумма вычетов всего квадрата равна 103.

Пусть x -- число строк с суммой 9
y -- число строк с суммой 13
z -- число строк с суммой 17
u -- число строк с суммой 21

Составим следующую систему уравнений:

$\begin{cases} 9x+13y+17z+21u=103\\ x+y+z+u=7\\ 6x+4y+2z=22\\ x+3y+5z+7u=27 \end{cases}$

После приведения получим:

$\begin{cases} x=z+2u-3\\ y=10-2z-3u \end{cases}$

Эта система имеет десять решений:

1,4,0,2
3,1,0,3
0,5,1,1
2,2,1,2
1,3,2,1
3,0,2,2
0,4,3,0
2,1,3,1
1,2,4,0
2,0,5,0