Al Zimmermann: Primorial Soup

[as73251]

12d3 в сообщении #1256082 писал(а):

Мой алгоритм сильно зависит от этого количества(например, для 12 потребовалось примерно в 1000 раз больше времени, чем для 11

У меня сейчас для n=11 нахождение всех решений в указанном Вами диапазоне занимает 5 секунд на одном ядре. Т.е. n=12 потребует для нахождения всех решений на одном ядре порядка двух часов?

[Herbert Kociemba]

5 seconds sounds record-breaking!
I stopped all my computation already 2 weeks ago. In the additive (logarithmic) way of seeing the problem it has much in common with magic squares. What we call a "good node" here is a "magic series" for magic squares there. This is a selection from N numbers out from $1..N^2 $ which sum up to the magic constant $(N^2+1)N/2$. We can apply almost the same considerations here. There are $Binomial(N^2, N) $ N-tupels here and the variance $\sigma^2 $ of the sums of all these N-tuples can be shown to be $N^2 (N^2+1)(N-1)/12$.
We then get approximately $Binomial(N^2, N)/\sqrt{2\pi\sigma^2} $ different magic series which is pretty close to the true value. For the exact values see Walter Trumps page http://www.trump.de/magic-squares/magic-series/exact.htm. Btw. Walter Trump and Jarek Wroblewski both worked on magic squares and I am sure they could use some of there methods for this competition.

[jcmeyrignac]

Herbert, I completely agree with you, since I realized that the problem had links with magic squares a long time ago.

@as73251, if your program is able to compute N=11 in 5 seconds, you probably have the fastest program around here.
I don't understand why you ask other people if it's interesting to search for N=12. Do you really need to be praised so much ?

In my opinion, what is important is not to finish first, but to discuss about the problem once the contest is over.
Some of your ideas may be useful for other problems or for future research.

I'm just a little bit sad that Al's contests are focused on very specific problems, involving mostly primes.
Since we have such a large pool of brilliant minds, why not trying to improve collectively some mathematical results ?

[as73251]

Herbert Kociemba в сообщении #1276875 писал(а):

I stopped all my computation already 2 weeks ago...

Я тоже приостановил свои вычисления: для n=12 программа требует модификации, т.к. n*(n-1)/2 > 64, а в конце года у меня на это нет времени. Попробую улучшить результаты в январе, когда появится свободное время.

[as73251]

Кто-то потеснил Jarek'а для n=13! Это говорит о том, что алгоритм Jarek'а далеко не совершенный и его результаты можно значительно улучшить.

[dimkadimon]

as73251, Вы обещали поделиться секретом вашей скорости. Я уверен что все с нетерпением ждут...

[as73251]

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

as73251, Вы обещали поделиться секретом вашей скорости. Я уверен что все с нетерпением ждут...

После того, как post1277391.html#p1277391

[as73251]

as73251 в сообщении #1277878 писал(а):

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

as73251, Вы обещали поделиться секретом вашей скорости. Я уверен что все с нетерпением ждут...

После того, как post1277391.html#p1277391

Но основными идеями поделюсь сразу.

[dobrichev]

My code is on https://github.com/dobrichev/PrimorialSoup

It was fun.

Congratulations to the winners.

[as73251]

Мой алгоритм основан на выделении из списка n непересекающихся подмножеств, которые строятся следующим образом: берем произвольный элемент из списка и каждому множителю этого элемента сопоставляем элементы исходного списка, которые содержат этот множитель и не содержат другие множители элемента, взятого за основу. Сейчас примитивный вариант полного расчета для n=11 занимает 13 минут, а продвинутый - порядка 5 секунд.

[as73251]

Herbert Kociemba в сообщении #1276875 писал(а):

5 seconds sounds record-breaking!

I think my method is easy to obtain the complete solution for n=13.

-- 24.12.2017, 03:38 --

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

as73251 found 14 optimal solutions for N=11.

Если Вы удосужились перевести мое замечание, то заодно и перевели бы и мои ответы на него:
post1268046.html#p1268046
post1268130.html#p1268130
т.к. Herbert Kociemba у Al'а в связи с этим замечанием выставил меня в некрасивом свете:
https://groups.yahoo.com/neo/groups/AlZ ... sages/7310

[as73251]

as73251 в сообщении #1278043 писал(а):

Мой алгоритм основан на выделении из списка n непересекающихся подмножеств, которые строятся следующим образом: берем произвольный элемент из списка и каждому множителю этого элемента сопоставляем элементы исходного списка, которые содержат этот множитель и не содержат другие множители элемента, взятого за основу. Сейчас примитивный вариант полного расчета для n=11 занимает 13 минут, а продвинутый - порядка 5 секунд.

Вношу исправления:
Мой алгоритм основан на выделении из списка n непересекающихся подмножеств, которые строятся следующим образом: берем произвольный элемент из списка и каждому множителю этого элемента сопоставляем элементы исходного списка, которые содержат этот множитель и не содержат другие множители элемента, взятого за основу. Первое подмножество состоит из одного исходного элемента. Сейчас примитивный вариант полного расчета для n=11 занимает 13 минут, а продвинутый - порядка 5 секунд.

[as73251]

as73251 в сообщении #1278215 писал(а):

Мой алгоритм основан на выделении из списка n непересекающихся подмножеств, которые строятся следующим образом: берем произвольный элемент из списка и каждому множителю этого элемента сопоставляем элементы исходного списка, которые содержат этот множитель и не содержат другие множители элемента, взятого за основу. Первое подмножество состоит из одного исходного элемента. Сейчас примитивный вариант полного расчета для n=11 занимает 13 минут, а продвинутый - порядка 5 секунд.

Все расчеты проводились на одном ядре процессора.

[as73251]

as73251 в сообщении #1277550 писал(а):

Кто-то потеснил Jarek'а для n=13! Это говорит о том, что алгоритм Jarek'а далеко не совершенный и его результаты можно значительно улучшить.

Как я и предполагал, алгоритм Jarek'а не имеет никакого отношения к поиску оптимального решения: post1256335.html#p1256335. Если кому не лень, то может воспользоваться моим алгоритмом для поиска оптимальных решений при n=13,14,15,16, а может и 17.

-- 24.12.2017, 13:16 --

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

as73251, Вы обещали поделиться секретом вашей скорости. Я уверен что все с нетерпением ждут...

Что же Вы неверное толкование вашего поста мною перевели, а описание моего алгоритма, которого Вы с нетерпением ждали, не перевели?

[as73251]

as73251 в сообщении #1278223 писал(а):

as73251 в сообщении #1278215 писал(а):

Мой алгоритм основан на выделении из списка n непересекающихся подмножеств, которые строятся следующим образом: берем произвольный элемент из списка и каждому множителю этого элемента сопоставляем элементы исходного списка, которые содержат этот множитель и не содержат другие множители элемента, взятого за основу. Первое подмножество состоит из одного исходного элемента. Сейчас примитивный вариант полного расчета для n=11 занимает 13 минут, а продвинутый - порядка 5 секунд.

Все расчеты проводились на одном ядре процессора.

А вот и перевод:
My algorithm is based on picking out from the list n nonintersecting subsets that are constructed as follows. We take an arbitrary element from the list, and to each multiplier of this element we put in correspondence elements from the initial list that contain this multiplier and do not contain other multipliers of the element taken as the base. The first subset consists of one initial element. Now the primitive procedure of complete calculation for n = 11 takes 13 minutes, and the advanced procedure takes approximately 5 seconds. All the calculations were performed on one processor core.