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

[Nataly-Mak]

Ну что ж, коллеги, кажется, проект распределённых вычислений у нас организовался.
Jarek, dimkadimon, mertz - вы молодцы! Спасибо вам.

Пока стесняются подключиться к проекту мои русские коллеги
Верно как-то заметил Pavlovsky: иностранцев организовать намного проще, чем русских. Иностранцы сами организуются без каких-либо усилий с моей стороны

Уважаемые коллеги: maxal, Pavlovsky, svb, 12d3, alexBlack, whitefox, dmd - вы тоже можете принять участие в этом замечательном проекте.
Да и другие форумчане вполне могут. Здесь ведь, наверное, каждый второй программист

[Nataly-Mak]

Решения с 3 дырками моя программа находит легко. Это с магической константой 741:

17  239  139  131  31  181  3 
 197  29  37  23  257  19  179 
 5  241  233  7  73  103  79 
 13  71  0  251  0  191  137 
 173  107  157  41  47  53  163 
 109  11  263  59  149  67  83 
 227  43  0  229  89  127  97 

А вот дальше пока дело не идёт.

[Jarek]

I am on 2-week vacation right now, with internet sessions from time to time. I have found 755 and will try to answer questions right now.

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

Hi Jarek. I might have found a program error

   if(bad&&number[*t[r][c]]!=3);
   {
      ImproveRing(HalfRandomRing(r+N,c+N),(rand()%3)?1:-1);
#if (N%2)==0   
      if(bad&&number[*t[r][c]]!=3)ImproveRing(HalfRandomRing2(r+N,c+N),(rand()%3)?1:-1);
#endif   
   }

the ; at the end of the statement would cause the code inside the braces to be executed every time.

Can you tell me how to change the program to find 761 or higher ( something quickly ). I want to make sure the program is running correctly.

Indeed, it is a bug. The effect is even worse than you write, since it causes the the triple-for loop just before that to be practically ignored. I have this bug in all my programs, so it is not critical - without testing I cannot be sure what would happen after fixing it.

The simplest way to alter the program to search for a larger magic constatnt is to change -6 to a positive multiple of 6 on line 35 of Main7-755.c
It is also good to change SUM on line 7, but this is used for filenames only and does not affect the search.

-- Пн авг 26, 2013 18:30:09 --

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

I changed the sum to 767 and changed the -=6 to +=12.

I quickly had 1 fault results. I ran with the ; removed in the above code.

changed to 773 and += 18 and got a result.

https://www.dropbox.com/s/rddu003k1au0qkz/869.jpg

Not the correct sum, but it is a solution

$+=12$ should give $773=761+12$ and $+18$ should give 779. I have no clue where 869 came from.

-- Пн авг 26, 2013 18:47:01 --

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

The results are the same with and without the ;. without finds solutions much faster.

Removing the ; reverts the code to what I have intended to do. The only problem is that I have done some tuneup of the program picking C300, C10, B10 on lines 16-18 of Main7-755.c
I made the tuneup with the bug - perhaps without the bug program is the fastest with some other constants.

For a tuneup or tests you can also do the following:

Alter line 1 of log.h changing SEED%100000 to SEED%smallernumber to increase frequency of logging - program records numbers of 1, 2, 3-fault solutions found.

Alter line 56 of Tab-ini.h
if(bad<=1)
changing 1 to a larger number - that way solutions with that number of faults will be stored in a file (format convenient for Mathematica) and can be verified.

[Nataly-Mak]

Ура, у Jarek есть $S=755$!

(3,43,103,11,197,241,157), 
(173,181,71,109,167,13,41), 
(19,139,251,101,5,127,113), 
(73,47,53,163,61,131,227), 
(97,107,17,151,67,137,179), 
(79,89,223,191,59,83,31), 
(311,149,37,29,199,23,7)

[mertz]

Almost ready. The duplicate errors and the non-prime errors are highlighted. The size of the image is 303x509. I tried jpeg, gif and png. Could not get image tag to work.

https://www.dropbox.com/s/o7got0a60tz7qq2/result.jpg

[dimkadimon]

Yay for 755!

Small update on 749. I don't have a full solution, but I have 145 1-error solutions. I will keep running the search.

[Nataly-Mak]

dimkadimon в сообщении #758048 писал(а):

Small update on 749. I don't have a full solution, but I have 145 1-error solutions.

Всего одна дырка для $S=749$? Отлично!
Моя программа находит решения только с 3 дырками.

-- Вт авг 27, 2013 05:33:00 --

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

Almost ready. The duplicate errors and the non-prime errors are highlighted. The size of the image is 303x509. I tried jpeg, gif and png. Could not get image tag to work.

https://www.dropbox.com/s/o7got0a60tz7qq2/result.jpg

В этом случае не знаю причину, почему не удаётся вставить изображение.
Попробуйте другой хостинг. Я загрузила вашу картинку на http://www.imageup.ru

Что означает
1-fault - 1
2-fault - 4


С нетерпением жду вашу программу. Мне тоже хочется принять участие в поиске.
Я пока пытаюсь совершенствовать свою программу, экспериментирую.

-- Вт авг 27, 2013 05:49:20 --

Radko Nachev живо интересуется, какое минимальное решение найдено на конкурсе для N=7. Я отправила ему недавно два решения Jarek - 769 и 761.
Вчера получила ответ:

Цитата:

Now you see how far you stood with 1597, don't you?
A gap less of the sub-case brings it down by 8: 753 of two over 229, perhaps?
759 - 735 = 24 and 24/2 = 12, therefore there are 13 levels to be checked out with the computer, in order to prove the 761 minimal, if none found there.

К сожалению, не могу понять его рассуждения о дальнейшем поиске минимального решения Может, кто-нибудь поймёт.

Кстати, ещё до конкурса он интересовался, какое у меня есть наименьшее решение для пандиагонального квадрата 7-го порядка из различных простых чисел. Я отправила ему своё решение $S=1597$. Он ответил, что это должно быть далеко от минимального решения. И был прав!

-- Вт авг 27, 2013 05:55:01 --

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

Что означает
1-fault - 1
2-fault - 4

Предполагаю следующее: в предпоследнем проходе было найдено решение с 4 ошибками, в последнем проходе - с 1 ошибкой, полное решение (без ошибок) не найдено

[dimkadimon]

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

К сожалению, не могу понять его рассуждения о дальнейшем поиске минимального решения Может, кто-нибудь поймёт.

Он говорит что надо 12 S проверить чтобы доказать оптимальность 761. Конечно у нас уже есть 755 и скоро будет 749, плюс мы не будем все нечётные подряд проверять.

[Nataly-Mak]

dimkadimon
спасибо.
Я сейчас ему написала, отправила решение Jarek $S=755$ и дала ссылку на страницу результатов, чтобы он сам мог следить.

Вы думаете, что решение S=749 тоже существует?

Возникает такой интересный вопрос: если существуют некоторые решения S1 и S2, значит ли это, что должны существовать все промежуточные решения S1<S<S2

[mertz]

the 1-fault count is the number of solutions found with a duplicate prime or a non-prime.
the 2-fault count is the number of solutions found with 2 errors. The program outputs a log file, a file with 1-fault solutions, a file with 2-fault solutions and one with no faults. All this is the default behavior of Jarek's code. His program uses a fixed set of numbers to seed the random number generator. Each thread gets 100 million seeds to process. This means the results will be the same every time you run the program. It also means that everyone that uses the same operating system will run the same search. This needs to fixed. Here is the initial version for testing. It is 64-bit windows.


https://www.dropbox.com/s/utxwf45xo83ry6l/Pan.exe

[Nataly-Mak]

Работает



mertz
как я увижу, что программа закончила работать?

Второй раз запускать поиск решения с магической константой 743 не имеет смысла?
А если с другим количеством потоков?

[mertz]

You can track the progress by looking at the LOG file. It updates every 100000 loops. It will run for a long time.

There are 2 errors. 119 is not prime. prime number 29 used twice.

[Nataly-Mak]

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

You can track the progress by looking at the LOG file. It updates every 100000 loops. It will run for a long time.

А где этот файл? Он есть в той папке, где программа? Сейчас посмотрю.
Его можно открывать во время работы программы?

Да, файл вижу. Вот что в нём в данный момент:

 100000000  0    0 0
 300000000  0    0 0
 100000000  0    0 0
 200000000  0    0 0
 400000000  0    0 0
 200000000  0    0 0
 300000000  0    0 0
 100000000  0    0 0
 400000000  0    0 0

-- Вт авг 27, 2013 08:06:10 --

Есть одна дырка



Двойняшки. Здорово! Нужна удача

Подключайтесь, коллеги!

[Pavlovsky]

Может есть смысл посмотреть в сторону алгоритмов построения обычных магических квадратов?
A164843

Ведь становится очевидным, что минимальная магическая сумма для пандиагональных квадратов очень близка к магической сумме обычных магических квадратов. А значит становится возможным формирование всевозможных наборов из N^2 простых чисел и построение из них пандиагонального квадрата.

[Nataly-Mak]

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

Может есть смысл посмотреть в сторону алгоритмов построения обычных магических квадратов?
A164843

Для обычных магических квадратов всё намного проще. Сразу формируем массив из 49 чисел, который даёт нименьшую возможную магическую константу; только один массив формируем, как правило, этого достаточно: квадрат строится уже из первого массива. Мой алгоритм построения я уже описала выше.

Цитата:

Ведь становится очевидным, что минимальная магическая сумма для пандиагональных квадратов очень близка к магической сумме обычных магических квадратов. А значит становится возможным формирование всевозможных наборов из N^2 простых чисел и построение из них пандиагонального квадрата.

К сожалению, совсем не значит.

Обратимся к истории. Когда мы искали наименьший пандиагональный квадрат 6-го порядка из чисел Смита, я тоже всё пыталась убедить alexBlack, что надо составлять все возможные массивы из 36 чисел и проверять отдельно каждый такой массив, так как массив из 36 чисел проверяется в разы быстрее, чем, скажем, массив из 43 чисел. Увы, мне пришлось согласиться с alexBlack, что составить все возможные массивы нереально. Поэтому и svb и alexBlack делали программу поиска из массива максимально допустимого размера. Обе программы работают очень долго, но изменить ничего нельзя.