2014 dxdy logo

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

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




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


01/12/11

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

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

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

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


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

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


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

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


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

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


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

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

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

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



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

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


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

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