2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6, 7 ... 11  След.
 
 Re: Al Zimmermann - Sums and Products
Сообщение21.11.2015, 01:47 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
whitefox в сообщении #1075148 писал(а):
dimkadimon
Вау, похоже Вы будете третьим. :D

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

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение21.11.2015, 08:47 
Аватара пользователя


21/02/10
1594
Екатеринбург
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

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

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение21.11.2015, 09:02 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение21.11.2015, 09:07 
Аватара пользователя


21/02/10
1594
Екатеринбург
whitefox в сообщении #1075391 писал(а):
суть произведения ровно $2j$ различных простых чисел


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

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение21.11.2015, 09:15 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Pavlovsky в сообщении #1075386 писал(а):
Как то это не согласуется с экспериментальными данными, или я чего то не понял?

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

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение21.11.2015, 09:19 
Заслуженный участник
Аватара пользователя


19/12/10
1546
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.$

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение21.11.2015, 09:38 
Аватара пользователя


21/02/10
1594
Екатеринбург
dimkadimon в сообщении #1075396 писал(а):
Подозреваю что алгоритм Эрдеша не оптимален для нашей задачи. Он только работает для его оценок.


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

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

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение21.11.2015, 10:03 
Заслуженный участник
Аватара пользователя


19/12/10
1546

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

Pavlovsky в сообщении #1075398 писал(а):
Кстати числа вида из формулы (9) называются радикалом натурального числа.

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

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение21.11.2015, 11:01 
Аватара пользователя


21/02/10
1594
Екатеринбург
whitefox в сообщении #1075402 писал(а):
такие числа называются бесквадратными, а радикал натурального числа это наибольший бесквадратный делитель этого числа.


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

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

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

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение21.11.2015, 11:12 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Pavlovsky в сообщении #1075413 писал(а):
не знаю, кто из великих вывел эту формулу

Полагаю, её мог вывести тот, кто вывел формулу$$\varphi(n)=n\prod\limits_{p\mid n}\left(1-\frac{1}{p}\right),\;\;n>1$$Возможно, что сам Эйлер. :-)

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение21.11.2015, 12:00 
Аватара пользователя


21/02/10
1594
Екатеринбург
Насколько я понял, лидеры получают решение перебором. То есть задача поиска регулярного решения, остается актуальной.
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 он дает решения хуже рекордных.

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение21.11.2015, 12:16 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение21.11.2015, 12:23 
Аватара пользователя


21/02/10
1594
Екатеринбург
Нет. Я всегда иду за своими идеями. В данном конкурсе они меня ведут к поиску регулярного решения. :D

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение21.11.2015, 12:31 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение21.11.2015, 12:51 
Аватара пользователя


25/08/12
171
Germany
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}

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

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



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

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


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

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