Непростые Фибоначчи

[Ktina]

Пусть у нас имеется бесконечная влево последовательность единиц. Правую часть последовательности будем строить следующим образом. Первое число равно сумме двух предыдущих, второе - сумме трёх предыдущих, третье - сумме пяти предыдущих, 4-е равно сумме 7 предыдущих, ... энное равно сумме $p_n$ предыдущих, где $p_n$ - энное простое число.

Вот как выглядит начало правой части этой последовательности, назовём её "Непростые Фибоначчи":

2 4 9 19 41 83 169 ...

Для обычных чисел Фибоначчи формула найдена давно. Как и для некоторых обобщений Фибоначчи (Трибоначчи и др.) А как найти формулу для "Непростых Фибоначчи"?

[Dmitriy40]

Интересно что среди этих чисел попадаются и простые, в первом десятке их 5 штук (2, 19, 41, 83, 1367), в первой сотне 12 штук, в первой тысяче 17 штук, в первых 10 тысячах простых 20 штук.
Сотое число имеет 31 знак: 1695257014455536462535335314103; тысячное число 302 знака: 1432...5857; десятитысячное уже 3011 знаков: 2668...0603. Похоже количество знаков примерно 30% от номера числа.

Насчёт формулы n-го члена сомневаюсь, ведь нет формулы простого числа, а она понадобится. Рекурсивная итерационная же проблемы не представляет (через спецфункцию nextprime(x), формулы которой тоже нет).

[svv]

$p_n-2^{n-1}+1+\sum\limits_{k=1}^{n-1} 2^{n-k-1}\;p_k$

[Dmitriy40]

Круто!

[wrest]

Функция PARI/GP которая вычисляет $n$-ое непростое число Фибоначчи по формуле ув. svv

Ktina128947(n)=prime(n)-2^(n-1)+1+sum(k=1,n-1,2^(n-k-1)*prime(k))

[g______d]

Формулы без значка суммирования, скорее всего, нет, потому что (обозначу функцию через $K$) $K(n+1)-2K(n)+1=p_{n+1}-p_n$, так что если бы она была, то была бы и формула для разности между соседними простыми, что сомнительно.

[Ktina]

svv
Большое спасибо!

[wrest]

Приближенная формула: $K(n)\approx 2^n\cdot 1,337321983005664$
Но я что-то не узнаю, что это за константа. Если взять достаточно знаков после запятой (я брал 1000), то абсолютная ошибка меньше 20 до чисел $K(3000)$ (дальше не смотрел, точности не хватает).

[grizzly]

wrest в сообщении #1331164 писал(а):

Но я что-то не узнаю, что это за константа.

Что-нибудь типа:

$$\pi + \frac52 \zeta(5) - \frac83 \sqrt{e}$$

Вот так когда-нибудь кто-то ткнёт случайно пальцем в дурацкую формулу, а потом окажется, что открыт новый закон природы

[wrest]

grizzly в сообщении #1331167 писал(а):

Что-нибудь типа:

Да не, должно быть попроще что-то, мне кажется. Либо вообще не "выражающееся в элементарных функциях". Но точность у приближенной формулы действительно очень высокая, потому что $2^n$ растет немного побыстрее всего остального что там в формуле.
Тут собсно надо бы предел посчитать\оценить

$$\lim \limits_{n \to \infty}\dfrac{p_n-2^{n-1}+1+\sum\limits_{k=1}^{n-1} 2^{n-k-1}\;p_k}{2^n}=-\dfrac{1}{2}+\dfrac{1}{2}\lim \limits_{n \to \infty}\sum\limits_{k=1}^{n-1} 2^{-k}\;p_k}$$

и наверное константа эта и вылезет.
Предел, ясное дело, существует.

[svv]

Про число
$\sum\limits_{k=1}^\infty 2^{-k}p_k=3.674643966...$
есть в OEIS. Последовательность A098990 — его десятичное разложение.

[Lia]

Тема перемещена из форума «Загадки, головоломки, ребусы» в форум «Карантин»
по следующим причинам:

Для редактирования.

Исправьте все и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

Возвращено.

[Три А,да]

$x_{n+1}=2x_n+1+2\cdot((n+1)\bmod2)$

[svv]

Три А,да, Вы какую-то другую задачу решили.