2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 52, 53, 54, 55, 56, 57, 58 ... 67  След.
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение08.09.2013, 07:20 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Поясню, почему я писала об оптимальном решении 733.
Такое оптимальное решение, может быть, и не существует. Я отвечала YuriiS, который сообщил, что нашёл решение 733 в самом начале конкурса.

Вполне допускаю, что оптимальное решение для N=7 уже найдено Wes Sampson, это решение $S=749$. Конечно, доказать оптимальность этого решения сложно.

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


22/03/08

7154
Саратов
Хочу попробовать поискать решение $S=1168$ для N=8 с помощью алгоритма, использующего псевдокомплементарные пары чисел.

Объединённый массив для магической константы 1168 (для квадратов 8-го порядка) – все числа от 3 до 443, кроме 439 и 431, всего 83 числа:

Код:
3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97 
101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199  211  223  227  229  233  239  241  251  257  263  269  271  277  281  283  293  307  311  313  317  331  337  347  349  353  359  367  373  379  383  389  397  401  409  419  421  433  443

Всего 292 потенциальных массива из 64 различных простых чисел; нашла по программе whitefox.

-- Вс сен 08, 2013 11:24:02 --

Приближение к решению S=1168 нашлось мгновенно:

Код:
7  3  193  107  223  257  181  197
151  227  179  163  19  13  139  277
11  97  241  313  131  211  103  61
271  191  73  109  67  37  263  157
101  3  193  13  317  257  181  103
241  311  71  97  109  97  31  211
79  163  157  263  199  277  19  11
307  173  61  103  103  19  251  151

Конечно, повторений много; не простых чисел в решениях, получаемых по данному алгоритму нет, есть только повторяющиеся простые числа. Квадрат получается пандиагональным, то есть все суммы в строках, столбцах и диагоналях правильные.

Разбиение показанного выше массива на 4 группы псевдокомплементарных пар чисел в этом примере такое:

группа 1 - отклонение 32, 20 пар
Код:
7  11  13  17  31  41  43  47  53  61  67  73  83  97  101  113  127  131  151  157  167  173  193  197  211  223  227  241  251  257  263  271  277  281  283  293  307  311  313  317

группа 2 - отклонение -32, 10 пар
Код:
3  19  31  37  61  67  79  97  103  109  151  157  163  181  193  199  223  229  241  257

группа 3 - отклонение 82, 10 пар
Код:
7  37  43  61  67  97  103  151  163  181  193  211  223  271  277  307  313  331  337  367

группа 4 - отклонение -82, 19 пар
Код:
11  13  17  19  29  31  37  43  47  53  59  61  71  73  79  83  97  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199

Из этих 4-х групп выбрать 4 набора по 8 непересекающихся пар, наверное, невозможно. Поэтому в решении так много повторений.

Я не знаю, возможно ли при каких-то отклонениях от комплементарности получить "хорошее" разбиение на 4 группы. Вопрос остаётся открытым.

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


22/03/08

7154
Саратов
Ещё одно приближение к решению $S=1168$ для пандиагонального квадрата 8-го порядка:

Код:
7  3  271  139  283  241  151  73
193  307  107  103  79  47  109  223
13  43  229  317  127  211  97  131
313  199  61  31  37  53  311  163
41  19  223*  137  317*  257  103*  71
181  277  101  151*  67  17  103*  271*
83  163*  163*  193*  197  331  31*  7*
337  157  13*  97*  61*  11  263  229*

Все повторенные простые числа отметила звёздочками, 15 дырок. Многовато, конечно, но и для квадрата 7-го порядка я начинала с 35 найденных элементов (14 дырок); потом получила решения с 4-5 дырками, а для магической константы 735 даже с 3 дырками. Тут всё дело во времени выполнения программы, я сейчас долго не жду, максимум 10-15 минут. Если никакого решения не находится, изменяю исходные данные или условия перебора.

Обратите внимание, что все дырки сосредоточены в нижней половине квадрата, как и в приближении, показанном выше. В верхней половине квадрата все 32 элемента различны.

Ещё обратите внимание: в любом пандиагональном квадрате 8-го порядка выполняется правило решёток (по Россеру). В этом квадрате оно тоже выполняется (можете проверить), несмотря на то, что много одинаковых чисел.

P.S. Решение системы уравнений я, видимо, не получу уже никогда :D
Может быть, общая формула содержит меньше свободных переменных. А может и не быть. Но я этого уже никогда не узнаю...

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


01/06/12
1016
Adelaide, Australia
Последние результаты. После 6ти дней, нашёл 466 решений для 743 с одной ошибкой.

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


22/03/08

7154
Саратов
dimkadimon
какой массив простых чисел вы используете при поиске решения $S=743$?
Выше я привела объединённый массив, который надо использовать.

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


01/06/12
1016
Adelaide, Australia
Я использую програму Jarek без изменений. Даже не знаю какой массив он использует.

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


22/03/08

7154
Саратов
Jarek сообщил, что он использует массив из первых 138 нечётных простых чисел (все числа меньше 800). Это очень большой массив! Последнее простое число в этом массиве 797.

Jarek в сообщении #759399 писал(а):
Nataly-Mak в сообщении #758280 писал(а):
Jarek
вопрос к вам: какой массив простых чисел вы задействовали в вашей программе :?:
При поиске решения с магической константой 737 сейчас у меня появилось решение с двумя ошибками, в котором присутствует число 373. Это число ни в каком случае не может входить в решение с магической константой 737, так как оно слишком большое для данной магической константы.
Я определяю максимально возможный размер массива так: вычисляю сумму всех чисел для квадрата с данной магической константой; при $S=737$ сумма всех чисел в квадрате равна 5159. Далее вычисляю сумму первых 48 нечётных простых чисел - от 3 до 227 (она равна 4886) и потом смотрю на разность этих двух сумм. В данном примере $5159-4886=273$.
Очевидно, что число 373 не может входить в квадрат с магической константой 737.

I didn't do a good job here, all primes below 800 are allowed by the program. You are right, the program should not recognize as primes numbers, which are too large to be used in final solution.

В пандиагональном квадрате 7-го порядка с магической константой 743 максимальное простое число может быть 313.
mertz изменил количество чисел в массиве для магической константы 737 сначала до 75, потом до 60.
Попробуйте и вы изменить количество чисел в массиве. Перебирать так много лишних простых чисел очень нерационально. Ведь все большие числа участвуют в построении квадрата, а они не должны участвовать.
Если для магической константы 743 задать все нечётные простые числа подряд, не выбрасывая два числа (которые не входят в объединённый массив чисел), это будет массив из 64 первых нечётных простых чисел (все числа от 3 до 313). Всего 64 числа, а не 138, как в программе Jarek.

-- Пн сен 09, 2013 07:21:25 --

И вот здесь я писала о массиве для магической константы 743:

Nataly-Mak в сообщении #761060 писал(а):
Таким образом, объединённый массив для магической константы 743 состоит из 62 простых чисел:

Код:
3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97 
101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199  211  223  227  229  233  239  241  251  257  263  269  271  277  281  283  293  313

Если не выбрасывать числа 307 и 311, то есть задать все простые числа от 3 до 313, тогда надо задать 64 числа в массиве.


-- Пн сен 09, 2013 07:28:38 --

А я ломаю голову, как выбрать из 4-х групп чисел набор по 8 непересекающихся пар чисел. Что-то ничего путного в голову не лезет :? Какой-нибудь там алгоритм "танцующих связей", например... :D

Запостила задачу здесь:
post761869.html#p761869

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

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


22/03/08

7154
Саратов
Выполнила десятки экспериментов.
Пока действую наполовину вручную, точнее - визуально (при выборе 4-х групп чисел с различными отклонениями p1, p3).
Уже попробовала искать решения с магическими константами 1240 и 1232 (лучшее решение Jarek имеет магическую константу 1248).
Приближения с повторениями чисел находятся мгновенно!
Например, решение $S=1240$ (13 повторений)

Код:
11  3  167  151  367  127  131  283
157  389  109  163  19  41  223  139
229  17  103  293  193  307  37  61
271  277  67  73  89  211  55  197
53  73  199  7  409  197  163  139
181  379  67  191  43  31  181  167
97  23  163  359  61  313  97  127
241  79  365  3  59  13  353  127

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


22/03/08

7154
Саратов
Вспомнила, что у меня есть ещё зарубежные коллеги... :-) решила попросить помощи у одного их них. Помощь пришла мгновенно!
И вот оно - решение системы (сначала сама система записана):

Код:
In[4]:= Solve[x1+x9+x17+x25+x5+x13+x21+x29==S&&
x10+x2+x26+x18+x14+x6+x30+x22==S&&
x27+x19+x11+x3+x31+x23+x15+x7==S&&
x20+x28+x4+x12+x24+x32+x8+x16==S&&
x1+x10+x27+x20-x5-x14-x31-x24==0&&
x9+x2+x19+x28-x13-x6-x23-x32==0&&
x17+x26+x11+x4-x21-x30-x15-x8==0&&
x25+x18+x3+x12-x29-x22-x7-x16==0,{x25,x26,x27,x28,x29,x30,x31,x32}]//FullSimplify

Код:
Out[4]=
{{x25->1/2 (S-x1-x12-x13+x16-x17-x18-x21+x22-x3-x5+x7-x9),
x26->1/2 (S-x10-x11-x14+x15-x17-x18-x2+x21-x22-x4-x6+x8),
x27->1/2 (S-x1-x10-x11+x14-x15-x19-x20-x23+x24-x3+x5-x7),
x28->1/2 (S-x12+x13-x16-x19-x2-x20+x23-x24-x4+x6-x8-x9),
x29->1/2 (S-x1+x12-x13-x16-x17+x18-x21-x22+x3-x5-x7-x9),
x30->1/2 (S-x10+x11-x14-x15+x17-x18-x2-x21-x22+x4-x6-x8),
x31->1/2 (S+x1+x10-x11-x14-x15-x19+x20-x23-x24-x3-x5-x7),
x32->1/2 (S-x12-x13-x16+x19+x2-x20-x23-x24-x4-x6-x8+x9)}}

И мы имеем общую формулу пандиагонального квадрата 8-го порядка, построенного из псевдокомплементарных пар чисел.

Herbert Kociemba, спасибо большое!

Так значит, свободных переменных все-таки 24, при заданной магической константе (раньше я была умнее :D ибо как раз и свела перебор к 24 свободным переменным; старею и глупею).

Теперь надо переписать программу, потому что сейчас у меня в программе 25 свободных переменных; уменьшение даже на одну свободную переменную даст несомненнный выигрыш во времени.

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


22/03/08

7154
Саратов
И программа нашла решение $S=1240$ c 10 дырками:

Код:
11  3  173  211  337  103  131  271
127  379  277  67  37  71  193  89
229  13  139  307  283  179  43  47
313  181  31  19  23  223  253  197
83  97  199  19  409  197  157  79
163  349  97  241  73  41  13  263
7  151  157  373  61  317  61  113
307  67  167  3  17  109  389  181

Повторены (по одному разу) числа: 3,13,19,61,67,97,157,181,197,307.

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


22/03/08

7154
Саратов
Изображение

Будет ли последовательность отношений p/m строго убывающей последовательностью при возрастании порядка квадрата N :?:
Пока это не так. Можно предположить, что решения для N=8,9 подлежат улучшению.

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #762222 писал(а):
Будет ли последовательность отношений p/m строго убывающей последовательностью при возрастании порядка квадрата N


Новая проблема века? Добавлю к этой гипотезе еще одну гипотезу.

Существует $N_0$. такое что для всех $N>N_0$ $p/m=1$.

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


01/06/12
1016
Adelaide, Australia
Pavlovsky в сообщении #762225 писал(а):
Новая проблема века? Добавлю к этой гипотезе еще одну гипотезу.

Существует $N_0$. такое что для всех $N>N_0$ $p/m=1$.


Я на 99% уверен что эта гипотеза верна. Для больших N растёт количество возможностей и должно быть возможно приблизить p и m. В самом начале темы Jarek обсуждает эту гипотезу.

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


19/12/10
1546
Пофиксил ещё один баг.
Он не влиял на работу программы, но не позволял задать разность между max и min в одну единицу.
Ссылка прежняя: http://yadi.sk/d/Qr1NDjYR8q67V

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


22/03/08

7154
Саратов
Начала писать программу построения пандиагонального квадрата 8-го порядка из псевдокомплементарных пар чисел по общей формуле, показанной выше.
Написала первый этап, выполнила его, красиво всё получилось :roll:

Код:
19  7  269  277  223  157  149  139
0  0  0  59  0  0  0  199
0  0  0  103  0  0  0  11
0  0  0  37  0  0  0  127
197  43  181  151  401  193  61  13
0  0  0  131  0  0  0  271
0  0  0  409  0  0  0  317
0  0  0  73  0  0  0  163

Магическая константа 1240. Пока различных чисел хватило, ну, это только 28 элементов. Здесь уже задействован перебор 12 свободных переменных и две переменных зависимые (вычисляются). Это 14 элементов, и ещё 14 элементов вычисляются по псевдокомплементарности.
Первый этап выполнился в малую долю секунды.

Красивый этюд, честное слово :D Такие вот чудесные этюды я сочиняю на своей клавиатуре. Пошла разыгрывать второй этюд (то бишь этап) :wink:

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1005 ]  На страницу Пред.  1 ... 52, 53, 54, 55, 56, 57, 58 ... 67  След.

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



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

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


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

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