Al Zimmermann: Primorial Soup

[as73251]

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

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

попытки их всяческих обрезаний с целью ускорить скорость расчета на самом деле приводили к резкому замедлению скорости расчета.

Не понятно как обрезание поиска может приводить к замедлению скорости?

Ищет, да не то.

[dimkadimon]

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

И не только он: но никто не довел его до конца.

Что вы имеете ввиду "довести до конца"? Цель этой части задачи найти хороший список потенциальных вершин (с низкой оценкой). Мне кажется это далеко не самое сложное. Список можно найти один раз, сохранить в файл и его много раз использовать, поэтому тут скорость не нужна. Для меня самое сложное это из этого списка составить полное решение и именно тут нужна скорость. Пока что вы не написали как вы это делаете.

-- 26.12.2017, 20:41 --

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

И не только он: но никто не довел его до конца. Кстати, Вы писали: "Выглядит как стандартный подход который многие использовали.".

Ну да я поэтому так и написал. Хотя сам до такого подхода не догадался, но вижу что многие лидеры его использовали.

-- 26.12.2017, 20:45 --

jcmeyrignac в сообщении #1277099 писал(а):

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 ?

Which problems would you like to see solved? Perhaps you can suggest the next problem of interest to Al. Or perhaps you would like to host your own contest (or get someone to do it for you)? I am sure the community would be more than interested in solving other problems, especially improving important mathematical results.

-- 26.12.2017, 20:48 --

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

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

Можете привести наглядный пример этого метода? Например для N=7.

[as73251]

dimkadimon
Вы так и не поняли смысл моего алгоритма.

[dimkadimon]

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

Вы так и не поняли смысл моего алгоритма.

Наверно не до конца. Приведите небольшой пример если не трудно.

[12d3]

Пара слов о моем алгоритме. Поход примерно как у всех - нагенерировать множество наборов, у которых произведение мало отличается от целевого, а потом из них выбрать $n$ штук так, что у каждой пары наборов ровно одно общее число.
Список оптимизаций такой:
1) Наборы храним в виде битовых полей. Бит с номером $k$ выставлен, если в наборе присуствует простое число с номером $k$, $0 \le k < \frac{n(n-1)}{2}$. Проверка, что ровно одно общее число у двух наборов, делается за несколько тактов:

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

bool intersects(uint64_t x, uint64_t y)
{
    uint64_t z = x & y;
    return z && !(z & (z-1));
}

Для $n=12$ у нас уже больше 64 простых чисел, и на приходится использовать два 64-битных числа для одного набора, соответственно, чуть усложняется проверка.
Генерировать матрицу смежности было бы невыгодно(хотя я не проверял), потому что она огромная, даже в L3 не влезет, а постоянно тянуть из RAM - накладно.
2) Число два - это самое редко встречающееся в наборах число. Поэтому выгоднее стартовать с набора, содержащего двойку, а потом уже подбирать ему соседей.
3) Начало рекурсивного алгоритма таково: выбираем один набор (назовем его главным), содержащий двойку. Пусть набор состоит из чисел $a_1, ..., a_{n-1}$. Формируем $n-1$ множеств наборов (из тех, что мы нагенерировали в самом начале) таких, что $i$-ый набор содержит число $a_i$, а больше общих чисел с главным набором нет. Остальная часть алгоритма состоит в том, чтобы выбрать по одному представителю из этих $n-1$ множеств, чтобы они попарно имели ровно одно общее число.
4) Общая итерация рекурсивного алгоритма такова: пусть на очередном этапе имеется $m$ наборов, один из которых главный, у каждой пары из которых ровно одно общее число. Также у нас имеется $n-m$ множеств, в которых содержатся кандидаты на оставшиеся $n-m$ вершин. Мы смотрим, в каком из множеств меньше всего наборов. Если в нем 0 наборов, то возвращаемся на предыдущий уровень рекурсии. Иначе, в цикле перебираем каждого кандидата $X$ из этого множества, вычисляем, какие числа у него общие с имеющимися $m-1$ наборами - всеми, кроме главного (пусть это числа $b_1, ... , b_{m-1}$), фильтруем оставшиеся $n-m-1$ множеств наборов так, чтобы:
а) у каждого набора из множества было ровно одно общее число с $X$.
б) это общее число не было одним из $b_1, ... , b_{m-1}$.
И переходим на следующий уровень рекурсии.
Дополнительно следим, чтобы сумма $\sqrt{\sum\limits_{i=1}^{m+1}\alpha_i^2}$ (см сообщение #1253678 ) не превышала лимит. Потому как, если на каком-то этапе рекурсии лимит превышен, то какие наборы не добавляй к имеющимся, решение оптимальным не будет. В принципе, можно и не следить за этой суммой, тогда мы будем получать неоптимальные решения, но поиск оптимального сильно затянется.
Значит, перебирая в пункте 3 все наборы, содержащие двойку и запуская рекурсивный алгоритм для каждого из них, мы рано гарантированно найдем оптимальное решение.

[as73251]

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

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

Вы так и не поняли смысл моего алгоритма.

Наверно не до конца. Приведите небольшой пример если не трудно.

Напомню, что конкурс еще не закончен, поля "First Place" и "Second Place" еще не заполнены, поэтому примеры приводить преждевременно: всему свое время.

[dimkadimon]

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

Напомню, что конкурс еще не закончен, поля "First Place" и "Second Place" еще не заполнены, поэтому примеры приводить преждевременно: всему свое время.

Конкурс закончен просто Ал забыл обновить страницу победителей. На странице "final report" уже написаны победители. Ал разрешает посылать новые решения и Jarek уже послал несколько.

[as73251]

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

Проверка, что ровно одно общее число у двух наборов, делается за несколько тактов:

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

bool intersects(uint64_t x, uint64_t y)
{
    uint64_t z = x & y;
    return z && !(z & (z-1));
}

На 64-битных операндах __popcnt64 работает быстрей.

[Jarek]

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

Для $n=12$ у нас уже больше 64 простых чисел, и на приходится использовать два 64-битных числа для одного набора, соответственно, чуть усложняется проверка.

For $n=12$ I used one 64-bit word for bitmasking all the primes except 2 and 3, but I had 4 kinds of sets stored separately:
with 2, without 3,
without 2, with 3,
without 2, 3,
with 2, 3.
Then it was a matter of algorithm to select proper kinds of sets.

[as73251]

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

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

Напомню, что конкурс еще не закончен, поля "First Place" и "Second Place" еще не заполнены, поэтому примеры приводить преждевременно: всему свое время.

Конкурс закончен просто Ал забыл обновить страницу победителей. На странице "final report" уже написаны победители. Ал разрешает посылать новые решения и Jarek уже послал несколько.

Al никогда ничего не забывает и это связано с его заявлением: "I'm hoping that a lot of noteworthy solutions will appear at the bottom of the Final Report page. Who knows, I might even offer an impromptu prize to the person who submits the most!".

[dimkadimon]

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

Al никогда ничего не забывает и это связано с его заявлением: "I'm hoping that a lot of noteworthy solutions will appear at the bottom of the Final Report page. Who knows, I might even offer an impromptu prize to the person who submits the most!".

Я так понял что это будет добавочный приз помимо главных призов которые уже выданы.

[as73251]

Jarek
Если рассматривать случай 2*3 как отдельный, то можно обойтись и без Ваших усложнений.

-- 26.12.2017, 15:44 --

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

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

Al никогда ничего не забывает и это связано с его заявлением: "I'm hoping that a lot of noteworthy solutions will appear at the bottom of the Final Report page. Who knows, I might even offer an impromptu prize to the person who submits the most!".

Я так понял что это будет добавочный приз помимо главных призов которые уже выданы.

Поэтому Al и не закрыл соответствующие поля: он не удовлетворен результатами конкурса, а попросту считает его провальным, т.к. оптимальных решений - с гулькин нос.

P.S.

(Оффтоп)

Еще раз убедился, что человеческая неблагодарность может простираться до бесконечности. Как мне говорит моя супруга: когда же ты, старый дурак, поумнеешь

-- 26.12.2017, 15:47 --

Jarek
Вы будете переориентироваться на поиск оптимальных решений?

-- 26.12.2017, 15:57 --

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

Поход примерно как у всех - нагенерировать множество наборов, у которых произведение мало отличается от целевого...

Если не секрет, какой метод Вы использовали для генерирования наборов?

[Jarek]

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

Jarek
Вы будете переориентироваться на поиск оптимальных решений?

No, my approach is not suitable for an exhaustive search.

[as73251]

Jarek в сообщении #1278916 писал(а):

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

Jarek
Вы будете переориентироваться на поиск оптимальных решений?

No, my approach is not suitable for an exhaustive search.

Это я понимаю: я имел в виду, будете ли Вы менять свой подход - ведь Al ждет прежде всего оптимальных или близких к оптимальным решения. А жаль: Ваш талант позволил бы Вам продвинуться и по другим направлениям.

[12d3]

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

Если не секрет, какой метод Вы использовали для генерирования наборов?

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