Al Zimmermann - Sums and Products

[dimkadimon]

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

dimkadimon
Вау, похоже Вы будете третьим.

Эх хотелось бы хоть раз в жизни побывать на подиуме, но боюсь не получится. Пропустил одно из оптимальных решений и не знаю какое. Программа крутится на кластере на работе, а на работу приду только через 5 дней. Поэтому за это время меня точно обгонят :(

[Pavlovsky]

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

Посмотрите Теорему 1 из третей ссылки dimkadimon

Алгоритм Эрдёша:

Числа в последовательности описываются формулой (9).
Примеры:
Простые числа (2,3) 1,2,3,6
Простые числа (2,3,5) 1,2,3,5,6,10,15,30
Простые числа (2,3,5,7) 1,2,3,5,6,7,10,14,15,21,30,35,42,70,245,490

Как то это не согласуется с экспериментальными данными, или я чего то не понял?

[whitefox]

Да, эта формула не соответствует тексту доказательства. Элементы последовательности суть произведения ровно $2j$ различных простых чисел, каждое из которых не больше $(\ln x)^3.$ Но, как легко убедиться, это не влияет на общую оценку.

[Pavlovsky]

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

суть произведения ровно $2j$ различных простых чисел

Не. суть произведения меньше или ровно $2j$ различных простых чисел. Ведь там эпсилон равное 1 или 0.

[dimkadimon]

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

Как то это не согласуется с экспериментальными данными, или я чего то не понял?

Подозреваю что алгоритм Эрдеша не оптимален для нашей задачи. Он только работает для его оценок.

[whitefox]

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

Ведь там эпсилон равное 1 или 0.

Поэтому я и написал

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

эта формула не соответствует тексту доказательства

ибо далее в тексте говорится

Эрдёш писал(а):

Their number clearly equals

$$t_x=\binom{s}{2j}$$

Да и $p_i<(\ln x)^3$ надо бы заменить на $p_i\leqslant(\ln x)^3.$

[Pavlovsky]

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

Подозреваю что алгоритм Эрдеша не оптимален для нашей задачи. Он только работает для его оценок.

Мои эксперименты показывают: оптимальное решение содержит много последовательностей вида $ka^n$. где $a$ удовлетворяет формуле (9).

Кстати числа вида из формулы (9) называются радикалом натурального числа.

[whitefox]

(увы, занудство сильнее меня)

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

Кстати числа вида из формулы (9) называются радикалом натурального числа.

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

[Pavlovsky]

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

такие числа называются бесквадратными, а радикал натурального числа это наибольший бесквадратный делитель этого числа.

Спасибо, вот и текущий конкурс оказался полезным для получения новых знаний.

С бесквадратными числам сталкиваюсь уже третий раз.

1) В предыдущем конкурсе. Тогда же вывел формулу:
$\frac{n}{rad(n)}=\frac{\varphi(n)}{\varphi(rad(n))}$ не знаю, кто из великих вывел эту формулу, но я ее вывел независимо от них.
2) «Японский Перельман» согласился объяснить главнейшую тайну математики
http://lenta.ru/news/2015/10/08/shinichimochizuki/
3) И вот в этом конкурсе, опять появляются эти неквадратные числа.

[whitefox]

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

не знаю, кто из великих вывел эту формулу

Полагаю, её мог вывести тот, кто вывел формулу

$$\varphi(n)=n\prod\limits_{p\mid n}\left(1-\frac{1}{p}\right),\;\;n>1$$

Возможно, что сам Эйлер.

[Pavlovsky]

Насколько я понял, лидеры получают решение перебором. То есть задача поиска регулярного решения, остается актуальной.

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

оптимальное решение содержит много последовательностей вида $ka^n$.

Будем строить решение из последовательностей $A_i=\{k2^i, k=[1,c_i]\},i=[0.t]$

Гипотеза. В оптимальном решении:

$c_i\ge$c_{i+1}$

Если постараться, то можно для оптимального решения вычислить числа $\{c_i\}$ за полиномиальное время. А так же вывести оценку алгоритма.

Собственно это и есть мой текущий алгоритм. Увы уже для N=40 он дает решения хуже рекордных.

[whitefox]

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

[Pavlovsky]

Нет. Я всегда иду за своими идеями. В данном конкурсе они меня ведут к поиску регулярного решения.

[whitefox]

Имхо, для этой задачи должен подойти генетический алгоритм. Базовое множество это генотип, а множество сумм и произведений — фенотип, мощность фенотипа даёт оценку приспособленности.

[Herbert Kociemba]

What makes the contest uninteresting in a certain way is that 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$. In the range $40 \leqslant N\leqslant 1000 $ we have $7\leqslant p_N\leqslant 19$.

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}