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

[dimkadimon]

Sorry I got confused with mod 5. I can find many solutions:

(Оффтоп)

Counts 1 11 13 12 12

(1,4,2,3,1,4,3),
(4,2,1,1,4,2,4),
(2,2,2,3,1,2,1),
(2,2,1,1,3,1,3),
(2,3,4,4,3,4,3),
(3,3,2,4,3,4,4),
(4,2,1,2,3,1,0)

(4,4,3,2,2,0,3),
(2,3,2,2,4,4,1),
(2,4,3,2,2,2,3),
(1,4,1,1,3,4,4),
(1,1,4,1,2,3,1),
(2,3,3,1,4,2,3),
(1,4,2,4,1,3,3)

(1,3,4,2,2,2,4),
(3,3,4,1,2,1,4),
(1,4,2,2,2,3,4),
(2,1,4,3,3,2,3),
(4,4,3,2,2,4,4),
(3,1,3,1,1,1,3),
(4,2,3,2,1,0,1)

(4,3,3,2,2,3,1),
(1,3,1,3,2,2,1),
(1,2,4,3,4,3,1),
(1,3,2,1,2,2,2),
(4,4,2,4,3,2,4),
(3,4,0,2,4,2,3),
(4,4,1,3,1,4,1)


Counts 1 11 12 14 11

(4,4,4,2,4,3,2),
(3,2,2,1,3,4,3),
(0,4,2,2,1,3,1),
(3,1,1,1,4,1,2),
(3,2,3,3,3,1,3),
(4,1,2,2,2,3,4),
(1,4,4,2,1,3,3)

(2,3,4,1,4,3,1),
(4,2,3,2,3,3,1),
(2,1,4,4,4,2,1),
(2,2,4,1,2,4,3),
(3,3,4,1,3,2,2),
(3,3,1,0,1,3,2),
(2,4,3,4,1,1,3)

(4,2,0,1,3,1,2),
(1,4,2,4,2,3,2),
(1,3,4,1,2,3,4),
(3,4,3,3,3,3,4),
(3,1,1,4,4,4,1),
(2,3,1,2,2,1,2),
(4,1,2,3,2,3,3)

(3,3,3,1,4,2,2),
(0,2,2,3,3,4,4),
(1,2,1,2,1,3,3),
(2,1,1,3,1,4,1),
(2,4,3,1,3,4,1),
(2,2,2,4,3,2,3),
(3,4,1,4,3,4,4)

[whitefox]

Вопрос не в том чтобы найти какие-то шаблоны, а в том чтобы найти их все (если придётся доказывать, что решения N7S733 не существует).

[dimkadimon]

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

Вопрос не в том чтобы найти какие-то шаблоны, а в том чтобы найти их все (если придётся доказывать, что решения N7S733 не существует).

Ну тогда я пас. Таких шаблонов будет миллионы!

[whitefox]

Шаблонов по модулю 3(6) всего 120.
Хотя, шаблонов по модулю 4 действительно больше миллиона (1612440 с учетом всех изоморфов, при фиксированном положении тройки).

К тому же, если решение N7S733 существует, то есть надежда обойтись меньшим числом шаблонов.

[mertz]

(Оффтоп)

I discovered the C runtime library for Linux uses a shared random number generator. There is a generator for each process, not for each thread. The code that I supplied will run poorly under Linux. The gcc compiler does generate code that is 40% faster than VS 2008.

[whitefox]

Существует всего 48 типов четвёрок попарно ортогональных точных покрытий по модулю 4:

(Оффтоп)

(0430,0430),(0430,0430)
(0430,0430),(0430,0511)
(0430,0430),(0430,1240)
(0430,0430),(0430,1321)
(0430,0430),(0430,1402)
(0430,0430),(0430,2050)
(0430,0430),(0430,2131)
(0430,0430),(0430,2212)
(0430,0430),(0511,0511)
(0430,0430),(0511,1240)
(0430,0430),(0511,1321)
(0430,0430),(0511,1402)
(0430,0430),(0511,2050)
(0430,0430),(0511,2131)
(0430,0430),(1240,1240)
(0430,0430),(1240,1321)
(0430,0430),(1240,2050)
(0430,0430),(1240,2131)
(0430,0430),(1321,1321)
(0430,0430),(2050,2050)
(0430,0511),(0430,0511)
(0430,0511),(0430,1240)
(0430,0511),(0430,1321)
(0430,0511),(0430,1402)
(0430,0511),(0430,2050)
(0430,0511),(0430,2131)
(0430,0511),(0511,0511)
(0430,0511),(0511,1240)
(0430,0511),(1240,1240)
(0430,0511),(1240,1321)
(0430,0511),(1240,2050)
(0430,1240),(0430,1240)
(0430,1240),(0430,1321)
(0430,1240),(0430,2050)
(0430,1240),(0430,2131)
(0430,1240),(0511,1240)
(0430,1240),(0511,1321)
(0430,1240),(1240,1240)
(0430,1240),(1240,1321)
(0430,1240),(1240,2050)
(0430,1321),(0430,1321)
(0430,1321),(0511,0511)
(0430,1321),(0511,1240)
(0430,1321),(1240,1240)
(0430,2050),(0430,2050)
(0511,1240),(0511,1240)
(0511,1240),(1240,1240)
(1240,1240),(1240,1240)

Где шаблон точного покрытия, например, 1240 означает, что имеется 1 ряд типа "9" 2 ряда типа "13" и четыре ряда типа "17". См. http://dxdy.ru/post759141.html#p759141

[whitefox]

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

I discovered the C runtime library for Linux uses a shared random number generator. There is a generator for each process, not for each thread. The code that I supplied will run poorly under Linux.

Можно попробовать вызывать генератор псевдослучайных чисел из функции оболочки. Которая будет подсчитывать число обращений к генератору и заново его инициализировать при необходимости.

Например, так:

Используется синтаксис C++

inline int random(){
        static int count;
        if(++count > RAND_MAX / 3){
                srand(clock());
                count = 0;
        }
        return rand();
}

[mertz]

The problem is all threads use the same generator. This means a mutex has to be locked by each thread to get a single random number. Every thread has to wait in line. Locking mutex's is VERY expensive. With one thread I could do 78 searches per second. With 12 threads I was only getting 20 searches per second. Now that I replaced the rand() function, I am getting 640 searches per second with 12 threads.

[whitefox]

Функция rand() определяет последовательность из, примерно, 30000 псевдослучайных чисел. При 640 обращениях в секунду, эта последовательность будет исчерпана менее чем за минуту. Далее начнётся повтор, что никак не отвечает представлению о случайной последовательности. Теоретически это может привести к зацикливанию программы на малой доле возможных вариантов.

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

[tolstopuz]

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

Функция rand() определяет последовательность из, примерно, 30000 псевдослучайных чисел.

Боже мой, какой ужас! Это в какой библиотеке так?

[whitefox]

Имеется 42112968 шаблонов по модулю 4 с учётом всех изоморфов и при фиксированном положении тройки.

База данных занимает 5 гигабайт (650 мегабайт в сжатом виде).

[mertz]

The random number generator in C was not designed for scientific research. See the Numerical Recipes in C book for alternatives with longer sequences and different properties. Using rand() % n is incorrect usage to get a number from 0 to n-1. Using rand() and using it incorrectly has lead to many erroneous papers being published.

[whitefox]

tolstopuz в сообщении #763527 писал(а):

Боже мой, какой ужас! Это в какой библиотеке так?

Пользуюсь VC++ со стандартной библиотекой.

Насчёт 30000 это я сильно преуменьшил
Каюсь, погорячился.

Пришлось залезть в код библиотеки чтобы выяснить вопрос.
Функция такая:

$$\mathrm X_{n+1}=(\mathrm X_n\cdot214013+2531011)\bmod 2^{32}$$

$$\mathrm Y_{n+1}=(\mathrm X_{n+1}\gg16)\; \& \; 0\mathrm x7\mathrm{fff}$$

-- 13 сен 2013, 20:15 --

Более математическая запись

$$\mathrm Y_{n+1}=\lfloor\mathrm X_{n+1}/2^{16}\rfloor\bmod2^{15}$$

[whitefox]

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

Имеется 42112968 шаблонов по модулю 4 с учётом всех изоморфов и при фиксированном положении тройки.

Опечатка, читать следует "по модулю 12".

[dimkadimon]

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

Имеется 42112968 шаблонов по модулю 4 с учётом всех изоморфов и при фиксированном положении тройки.

База данных занимает 5 гигабайт (650 мегабайт в сжатом виде).

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