2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Непростые Фибоначчи
Сообщение08.08.2018, 00:32 
Аватара пользователя


01/12/11

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

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

2 4 9 19 41 83 169 ...

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

 Профиль  
                  
 
 Re: Непростые Фибоначчи
Сообщение08.08.2018, 03:16 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Непростые Фибоначчи
Сообщение08.08.2018, 03:25 
Заслуженный участник


23/07/08
10626
Crna Gora
$p_n-2^{n-1}+1+\sum\limits_{k=1}^{n-1} 2^{n-k-1}\;p_k$

 Профиль  
                  
 
 Re: Непростые Фибоначчи
Сообщение08.08.2018, 03:55 
Заслуженный участник


20/08/14
11061
Россия, Москва
Круто!

 Профиль  
                  
 
 Re: Непростые Фибоначчи
Сообщение08.08.2018, 09:14 


05/09/16
11461
Функция PARI/GP которая вычисляет $n$-ое непростое число Фибоначчи по формуле ув. svv
Код:
Ktina128947(n)=prime(n)-2^(n-1)+1+sum(k=1,n-1,2^(n-k-1)*prime(k))

 Профиль  
                  
 
 Re: Непростые Фибоначчи
Сообщение08.08.2018, 09:33 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Непростые Фибоначчи
Сообщение08.08.2018, 10:07 
Аватара пользователя


01/12/11

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

 Профиль  
                  
 
 Re: Непростые Фибоначчи
Сообщение08.08.2018, 12:06 


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

 Профиль  
                  
 
 Re: Непростые Фибоначчи
Сообщение08.08.2018, 12:59 
Заслуженный участник
Аватара пользователя


09/09/14
6328
wrest в сообщении #1331164 писал(а):
Но я что-то не узнаю, что это за константа.
Что-нибудь типа:
$$\pi + \frac52 \zeta(5) - \frac83 \sqrt{e}$$

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

 Профиль  
                  
 
 Re: Непростые Фибоначчи
Сообщение08.08.2018, 13:17 


05/09/16
11461
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}$$ и наверное константа эта и вылезет.
Предел, ясное дело, существует.

 Профиль  
                  
 
 Re: Непростые Фибоначчи
Сообщение09.08.2018, 00:51 
Заслуженный участник


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

 Профиль  
                  
 
 Posted automatically
Сообщение12.08.2018, 00:17 


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

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

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

Возвращено.

 Профиль  
                  
 
 Re: Непростые Фибоначчи
Сообщение14.08.2018, 21:47 


07/10/06
77
$x_{n+1}=2x_n+1+2\cdot((n+1)\bmod2)$

 Профиль  
                  
 
 Re: Непростые Фибоначчи
Сообщение14.08.2018, 23:05 
Заслуженный участник


23/07/08
10626
Crna Gora
Три А,да, Вы какую-то другую задачу решили.

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

Модератор: Модераторы



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

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


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

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