Al Zimmermann - Sums and Products

[whitefox]

Herbert Kociemba
Как вы для конкретного $N$ определяете $p_N?$

[Herbert Kociemba]

whitefox в сообщении #1075436 писал(а):

Herbert Kociemba
Как вы для конкретного $N$ определяете $p_N?$

For N1>=N2 we have p1>=p2, so if N increases you just have to look if the next prime gives a better result.

[whitefox]

Понятно, спасибо.

[Pavlovsky]

Увы в этом конкурсе еще никто не опубликовал whitefox формулы. Расчет количества уникальных сумм и произведений занимает 99% времени работы алгоритма.

[dimkadimon]

whitefox в сообщении #1075427 писал(а):

А вы свои решения улучшаете? Каким-нибудь hill climbing, например.

Я именно это использую. Вообще то считаю что многие могут найти 25 если потратят достаточно времени. Нашел только одну хорошую теоретическую идею (Herbert намекнул на нее) и одну достаточно стандартную оптимизацию.

[Pavlovsky]

http://oeis.org/A263996

Ссылка взята из поста в дискуссионной группе конкурса.

N=40 348

Это открытый источник, нарушений правил нет никаких.

[whitefox]

А ещё в дискуссионной группе был задан вопрос: "Каким образом была доказана оптимальность решений A263996? Ведь для брутфорса нужно знать верхнюю границу наибольшего числа в оптимальном порождающем множестве".

[Yadryara]

Pavlovsky в сообщении #1075911 писал(а):

http://oeis.org/A263996

Спасибо. А я-то думаю, почему Hugo Pfoertner'a нет среди участников. А он, оказывается, автор.

Pavlovsky в сообщении #1075911 писал(а):

N=40 348

Ну это-то давно понятно Значения для самых нижних N вычисляются из начисленных конкурсных баллов.

Кстати, извиняюсь, если говорю банальности. В дискуссионную группу пока не заглядывал.

[Vitaly12]

Herbert Kociemba

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

For N=20 for example the best choice is $p_N=5$ and we get
{1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36}

I've tried to extend this method to N=40 using various prime factors - Alas the results are worse then half of the known best

Obviously I'm missing something, but what it might be?

[dimkadimon]

Vitaly12
To reach the optimal solutions it is not enough to take the first N values that fit Herbert's criteria.

[Vitaly12]

dimkadimon

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

Vitaly12
To reach the optimal solutions it is not enough to take the first N values that fit Herbert's criteria.

That I see now. What mislead me is Herbert words:

Цитата:

you can get about 0.98 points for each problem of size N if you just compute the list $\{1,2,..,a_N\}$ of the first N numbers with all prime factors smaller than a maximal prime $p_N$.

[Pavlovsky]

Возникла вот такая вспомогательная задачка:


Дано множество A положительных целых чисел. Для $a\in A, x < a\le\frac{x^2}{2}$. G(A,x) число различных произведений 2-х чисел (не обязательно различных) из A.
Найти для заданных n,x множество A (|A|=n), такое что G(A,x) минимально.

Никак не могу оценить насколько задача сложная.

[12d3]

DEL. Ерунду написал.

[Pavlovsky]

Вы немного не поняли.
Надо:
для заданных n,x найти множество A (|A|=n), такое что G(A,x) минимально.

А не:
Для заданного A посчитать G(A,x).

Слово Дано в первом предложении сбивает.

Уточненный вариант:
Пусть A множество положительных целых чисел. Для $a\in A, x < a\le\frac{x^2}{2}$. G(A,x) число различных произведений 2-х чисел (не обязательно различных) из A.
Найти для заданных n,x множество A (|A|=n), такое что G(A,x) минимально.

[whitefox]

Pavlovsky
Вас интересует следующая задача?

Для множества целых чисел $A$ обозначим через $A^2$ множество всех попарных произведений элементов множества $A$ (не обязательно различных).

Пусть даны вещественное число $x>2$ и целое неотрицательное число $n,$ не превышающее числа целых чисел в интервале $\left(x,\frac{x^2}2\right].$ Требуется найти множество целых положительных чисел $A$ мощности $n,$ удовлетворяющее условию $\forall a\in A(x<a\leqslant\frac{x^2}2),$ и с наименьшим $|A^2|.$