Al Zimmermann: Primorial Soup

[Herbert Kociemba]

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

[TR63]

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)?) не существует.

[as73251]

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

для 12 потребовалось примерно в 1000 раз больше времени, чем для 11...

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

[Herbert Kociemba]

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.

[dimkadimon]

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!

[Herbert Kociemba]

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.

[as73251]

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.

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

[mertz]

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.

[as73251]

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 не поддерживает.

[mertz]

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.

[Herbert Kociemba]

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?

[dimkadimon]

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.

[jcmeyrignac]

Some benchmarks on a I7-4790S at 3.2Ghz:

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

[ctac]

Цитата:

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?

[Geen]

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