2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 6, 7, 8, 9, 10, 11, 12  След.
 
 Re: Al Zimmermann: Primorial Soup
Сообщение19.12.2017, 09:58 


04/10/17

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

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

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение21.12.2017, 00:32 
Аватара пользователя


25/08/12
167
Germany
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.

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение21.12.2017, 10:52 


20/01/13
62
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 ?

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение21.12.2017, 21:09 


04/10/17

153
Herbert Kociemba в сообщении #1276875 писал(а):
I stopped all my computation already 2 weeks ago...


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

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение22.12.2017, 09:28 


04/10/17

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

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение22.12.2017, 15:57 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение23.12.2017, 01:35 


04/10/17

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

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

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение23.12.2017, 03:10 


04/10/17

153
as73251 в сообщении #1277878 писал(а):
dimkadimon в сообщении #1277636 писал(а):
as73251, Вы обещали поделиться секретом вашей скорости. Я уверен что все с нетерпением ждут...

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

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

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение23.12.2017, 19:06 


01/11/17
40
My code is on https://github.com/dobrichev/PrimorialSoup

It was fun.

Congratulations to the winners.

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение23.12.2017, 19:11 


04/10/17

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

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение24.12.2017, 02:51 


04/10/17

153
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

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение24.12.2017, 05:03 


04/10/17

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

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

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение24.12.2017, 08:55 


04/10/17

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

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

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение24.12.2017, 12:40 


04/10/17

153
as73251 в сообщении #1277550 писал(а):
Кто-то потеснил Jarek'а для n=13! Это говорит о том, что алгоритм Jarek'а далеко не совершенный и его результаты можно значительно улучшить.

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

-- 24.12.2017, 13:16 --

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

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

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение24.12.2017, 19:57 


04/10/17

153
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.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 177 ]  На страницу Пред.  1 ... 6, 7, 8, 9, 10, 11, 12  След.

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



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

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


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

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