2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6, 7, 8 ... 12  След.
 
 Re: Al Zimmermann: Primorial Soup
Сообщение24.10.2017, 00:21 
Аватара пользователя


25/08/12
171
Germany
dimkadimon в сообщении #1258302 писал(а):
Now I realise that it helps for the dots (on a given green line) to be roughly symmetric around the vertical red line.

Interesting, I did not realize yet that symmetry in my point of view of the problem could lead to good solutions. When I look at the minial solution only X1 is the result of such a symmetry, so I am not sure if this really is the key to good solutions. But surely I will think more about symmetry in my representation.

Btw. I wrote $ |X_i-X| \ll 1 $. Looking at my derivation this is not correct. It must be $ |n(X_i-X)| \ll 1 $.

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение24.10.2017, 22:48 


03/03/12
1380
TR63 в сообщении #1256297 писал(а):
На Math Help Planet в качестве оптимального варианта при $n=4$ приведен результат $\{11,3,7\}$, $\{11,5,7\}$, $\{3,5,13\}$, $\{7,2,13\}$, $E=718$


Здесь опечатка. Должно быть
TR63 в сообщении #1256297 писал(а):
при $n=4$ приведен результат $\{11,3,7\}$, $\{11,5,2\}$, $\{3,5,13\}$, $\{7,2,13\}$, $E=718$.

Можно переписать в другом виде
$\{2,5,11\}$
$\{2,7,13\}$
$\{3,7,11\}$
$\{3,5,13\}$
$E=718$
Эту матрицу построили с учётом отрицания свойств матрицы при $n=3$.
При $n=5$ матрицу строим по аналогии с $n=4$ с учётом $n=3$. Получаем матрицу
TR63 в сообщении #1256297 писал(а):
при $n=5$ получилось $\{2,5,29,17\}$, $\{2,7,13,19\}$, $\{3,7,17,23\}$, $\{3,11,19,29\}$, $\{5,13,23,11\}$, $E=51227$.

Здесь ещё есть различия в свойствах. Не хватает комбинации с двумя смежными элементами. Достаточно поменять местами двойку с тройкой. Получим
$\{3,5,29,17\}$
$\{3,7,13,19\}$
$\{2,7,17,23\}$
$\{2,11,19,29\}$
$\{5,13,23,11\}$
$E=46623$
Для получения нужной структуры пришлось поменять местами $29$ и $11$ в первой и последней строке соответственно. Возможно это повлияет на результат.
Нужен алгоритм, позволяющий находить точное (?) значение минимума E для $n=4$, $n=5$, если таковой существует (без перебора). Или доказать, что такого алгоритма (для всех (n)?) не существует.

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение28.10.2017, 22:33 


04/10/17

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

У меня для 8 на одном ядре время 1.7 с. Получается, что с моим алгоритмом даже для 11 ничего не добиться за разумное время? Правда, для 8 время можно немного подсократить, т.к. я использовал unsigned __int64, но принципиально это ничего не решает.

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


25/08/12
171
Germany
as73251 в сообщении #1260017 писал(а):
У меня для 8 на одном ядре время 1.7 с

N=8 takes 0.12 s for me on one core. The result for N=11 I get after a couple of hours. But for N=12 it seems hopeless with my algorithm to get any result and I am short before giving up since I have no idea how to do the computation faster.

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


01/06/12
1016
Adelaide, Australia
Herbert Kociemba в сообщении #1260104 писал(а):
But for N=12 it seems hopeless with my algorithm to get any result and I am short before giving up since I have no idea how to do the computation faster.

I am in the same situation. $N=12$ seems exponentially harder than $N=11$ and I have already made my algorithm a few orders faster, but it seems not enough. It seems that I need a completely different approach to crack $N=12$. This is what I love about this contest - each new $N$ I have to come up with a new idea!

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


25/08/12
171
Germany
dimkadimon в сообщении #1260127 писал(а):
$N=12$ seems exponentially harder than $N=11$

With my algorithm which searches the optimal solution the computation time seems even to increase more than exponentially. With some additional optimization a full search for N= 5, 6, 7, 8, 9, 10 now takes 16, 16, 31, 62, 188, 297000 milliseconds.

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение29.10.2017, 22:39 


04/10/17

153
Herbert Kociemba в сообщении #1260104 писал(а):
as73251 в сообщении #1260017 писал(а):
У меня для 8 на одном ядре время 1.7 с

N=8 takes 0.12 s for me on one core. The result for N=11 I get after a couple of hours. But for N=12 it seems hopeless with my algorithm to get any result and I am short before giving up since I have no idea how to do the computation faster.


Herbert Kociemba в сообщении #1260246 писал(а):
With my algorithm which searches the optimal solution the computation time seems even to increase more than exponentially. With some additional optimization a full search for N= 5, 6, 7, 8, 9, 10 now takes 16, 16, 31, 62, 188, 297000 milliseconds.


Спасибо: понял свой ляп.

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


02/11/12
141
Used simulated annealing for N=4 to N=7.

Went brute force for N=8 to N=12. I hope to get N=12 soon. N=13 is possible with this method. I am working the problem backwards. Even N has a large jump in search space. Odd N has a similar search space as N-1, just one more loop. Odd N gets an extra product that is less then the average.

Always a fun contest when you get to play with bit arrays. Really disappointed there is not a popcnt instruction for _m128i.

N=11 solution found in less than 20 minutes, once all the constraint parameters are determined. I have a ten year old 6 core machine.

With Jareks's perfect scores in Perfect Determinices, I figured he would dominate this contest. I will have to revisit that contest when this one is over.

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение31.10.2017, 04:54 


04/10/17

153
mertz в сообщении #1260599 писал(а):
Always a fun contest when you get to play with bit arrays. Really disappointed there is not a popcnt instruction for _m128i.

Есть алгоритмы и побыстрей popcnt: https://www.researchgate.net/publicatio ... structions
Но Ваш процессор инструкции AVX2 не поддерживает.

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


02/11/12
141
After testing a few options, it was just easier to use two 64-bit registers for N=12. Loading and storing overhead and multiple instructions needed for popcnt, made using _m128i slower.

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


25/08/12
171
Germany
Finding optimal solutions is strongly related to the clique problem https://en.wikipedia.org/wiki/Clique_problem.
For N=12 for example I have a list of about 45000 vertices, each vertex is an 11-tuple of prime numbers. Two vertices are connected if they share exactly one prime number.
Now finding a valid solution for N=12 is equivalent to finding a 12-clique in this large graph. The list of 45000 vertices is complete in the sense that it contains all vertices which have a vertexrawscore of less than 101.517.569. So I know that each 12-clique has a rawscore less than 12*101.517.569. The optimal solution is definitely among these 12-cliques. There exist algorithms for finding all maximal cliques within a graph but is this really usefull in a graph with 45000 vertices?

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


01/06/12
1016
Adelaide, Australia
Herbert Kociemba в сообщении #1260819 писал(а):
For N=12 for example I have a list of about 45000 vertices, each vertex is an 11-tuple of prime numbers

Yep that's pretty much what I am doing, except that I only look at 32000 vertices. Also the last vertex can be found from the first 10 vertices. I don't think we can solve much more than $N=14$ using standard max-clique finding algorithms. There must be another way to get good approximate solutions...

-- 31.10.2017, 22:02 --

In fact our problem is even harder than max-clique. Instead of finding the maximum clique in the graph we are looking for ALL cliques of size N in the graph and selecting the one that has the best score.

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


20/01/13
62
Some benchmarks on a I7-4790S at 3.2Ghz:

N=10, 18 seconds with 3523 vertices
N=11, 16114 seconds with 11589 vertices

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение04.11.2017, 14:50 


09/03/16
34
Цитата:
the target energies for n = 1, 2, 3 and 4 are 1, 4, 29 and 694, respectively


Could anybody list here target energies for the rest of n values?
I just cannot find a good routine for computing n-roots.
This request doesn't look as a violation of contest rules does it?

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение04.11.2017, 15:35 
Заслуженный участник
Аватара пользователя


01/09/13
4318
ctac в сообщении #1262179 писал(а):
Could anybody list here target energies for the rest of n values?

You could try WolframAlpha http://www.wolframalpha.com/input/?i=Ceiling%5B9*Prod%5BPrime%5Bi%5D,%7Bi,1,9*(9-1)%2F2%7D%5D%5E(2%2F9)%5D
Just replace 9 (in four places) with any desired number.

-- 04.11.2017, 15:42 --

For example, for 29 it will be 364872222835819203297507274924640170192262206124510057215315294057123401768242181469 :D

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

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



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

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


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

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