2014 dxdy logo

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

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
01/01/18 20:50 UTC: Перешли на HTTPS в тестовом режиме. О проблемах пишите в ЛС cepesh.





Начать новую тему Ответить на тему
 
 Качественные и некачественные числа
Сообщение19.11.2017, 16:56 
Аватара пользователя


01/12/11
6092
Нацерет-Иллит
Дано натуральное число. Из него вычитается самое большое простое число, не превосходящее его. С результатом снова производится такая же операция и т. д. Назовём число качественным, если из него через несколько шагов получается 1, и некачественным — если ноль. Докажите, что среди чисел от 1 до 1 000 000 качественные составляют не менее четверти, но не более половины.
(Ленинградская олимпиада)

(Читать строжайше воспрещается!)

(произносится в очень быстром темпе)
«Как я рада, как я рада, что вы все из Ленинграда!»

 Профиль  
                  
 
 Re: Качественные и некачественные числа
Сообщение19.11.2017, 19:30 


20/08/14
3788
Россия, Москва
Интересно каков предел отношения количества качественных чисел к общему их числу. Пока я вижу что он $\approx 0{,}345$.

 Профиль  
                  
 
 Re: Качественные и некачественные числа
Сообщение19.11.2017, 21:35 


20/08/14
3788
Россия, Москва
А может и $\lim\approx 0{,}34332$ (для чисел до 3 триллионов).
Интересно что вычисление количества качественных чисел свелось к генератору простых чисел и одному лишнему обращению в короткий массив (менее 1500 элементов) для каждого простого числа.
UPD. Хм, а похоже я не прав, в логарифмическом виде по X график почти прямая (с очень-очень незначительным замедлением спада), т.е. можно ожидать что предел где-то на бесконечности будет нулевым.

 Профиль  
                  
 
 Re: Качественные и некачественные числа
Сообщение19.11.2017, 22:11 
Заслуженный участник
Аватара пользователя


09/09/14
4901
Грубо говоря, каждое 14-е качественное -- вида $p+1$; $p$ и $p+2$ -- нет; $p+3$ -- редко, а $p+4$ -- почти так же часто. Дальше анализ постепенно усложняется, но нужно всего несколько шагов пройти, чтобы попасть в нужный диапазон снизу. А сверху: будут только накапливаться эти "почти", я думаю, -- нужно как-то за ними проследить в общем виде. Но лень :)

 Профиль  
                  
 
 Re: Качественные и некачественные числа
Сообщение20.11.2017, 05:12 


21/05/16
1043
Аделаида
grizzly в сообщении #1267052 писал(а):
$p+2$ -- нет

За исключением $p+2=4$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Модераторы Математики, Супермодераторы



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

Сейчас этот форум просматривают: nimepe


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

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