Последовательность $$0,\; 1,\; 3,\; 7,\; 15,\; 29,\; 55,\;\dots$$ задана формулой $%a_0=0,\; a_1=1,\; a_n=a_{n-2}+a_{n-1}+p_{n-1}$%, где $%p_k$% - простое число с порядковым номером $%k$%.

Как можно приблизительно оценить скорость возрастания этой последовательности?

задан 16 Янв '19 12:58

1

Простые числа растут достаточно медленно, примерно как n ln(n). Поэтому здесь будут слегка увеличенные числа Фибоначчи. Они растут намного быстрее (как геометрическая прогрессия), поэтому "добавка" в виде последнего слагаемого на рост существенно не повлияет. То есть асимптотика будет иметь вид Cq^n, где q=(1+sqrt(5))/2 -- golden ratio.

(16 Янв '19 15:19) falcao

@falcao, большое спасибо!

(16 Янв '19 18:39) Казвертеночка
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,364
×324
×124
×22
×3

задан
16 Янв '19 12:58

показан
168 раз

обновлен
16 Янв '19 18:39

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru