2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Длинные последовательности нулей в десятичной записи e
Сообщение15.03.2019, 03:18 


13/04/16
102
Дана десятичная запись числа Эйлера $e$. Нужно доказать, что функция $f : \mathbb{N} \to \mathbb{N}$ возвращающая $n$-ую цифру после запятой примитивно-рекурсивна.

Чтобы это доказать я планировал сложить первые $\alpha(n)$ членов ряда $\sum_{i=1}^{\infty} \frac{1}{i!}$, умножить результат на $10^n$, взять целую часть и возрадоваться. Мне казалось достаточно дождаться пока слагаемые будут меньше чем $\frac{1}{10^{n+1}}$, что можно легко гарантировать нужным $\alpha$.. но я ошибался. Вдруг складываясь частичные суммы выстроили после моего (уже казалось бы вычисленного) $n$-го разряда длинную последовательность девяток. А потом прибавление единицы от какого-то уже очень далекого $N >> \alpha(n)$ запускает цепную реакцию, которая докатывается до моего разряда и увеличивает его.

Я стал думать над тем может ли такое вообще произойти и если да, то насколько далеко. Каким нужно выбрать примитивно-рекурсивное $\alpha(n)$ чтобы метод сработал? Как оценивается длина блока $000...0$ в записи числа $e$, через номер позиции первого $0$ этого блока ?

Пока ничего не понятно. Знаю только, что неизвестно нормально ли число $e$. Вряд ли стоит рассчитывать доказать, что оно ненормально, поэтому стоит быть готовым к сколь угодно длинным последовательностям нулей.

 Профиль  
                  
 
 Re: Длинные последовательности нулей в десятичной записи e
Сообщение15.03.2019, 04:12 
Заслуженный участник


16/02/13
4179
Владивосток
Плохо помню про примитивную рекурсивность. А складывать, пока после $n$-й цифры не появится пара цифр меньше девятки не прокотит?

 Профиль  
                  
 
 Re: Длинные последовательности нулей в десятичной записи e
Сообщение15.03.2019, 04:23 


13/04/16
102
iifat алгоритм "делающий что-то пока ... " может не оказаться примитивно-рекурсивным. Для примитивной рекурсивности важно, чтобы перебор вариантов был ограничен какой-то примитивно-рекурсивной функцией. Предложенным вами способом можно доказать, что $n$-ая цифра числа $e$ вычислима -- это просто, да.

P.S. примитивно-рекурсивна $\Rightarrow$ обще-рекурсивна $\Rightarrow$ частично-рекурсивна $\Longleftrightarrow$ вычислима

 Профиль  
                  
 
 Re: Длинные последовательности нулей в десятичной записи e
Сообщение15.03.2019, 05:42 
Заслуженный участник
Аватара пользователя


08/11/11
5940
Я так понимаю, что достаточно предъявить эффективную верхнюю оценку максимальной длины цепочки из девяток, если первая девятка цепочки находится на позиции $n$.

Понятно, что это будет следовать из нижней оценки расстояния $10^n e$ до ближайшего целого (потому что очень длинная цепочка девяток означает, что $10^n e$ очень близко к целому).

Это вроде можно сделать так: $\mathrm{dist}(10^n e,\mathbb Z)\ge \frac{1}{10^n !}\mathrm{dist} (10^n! e,\mathbb Z)\ge \frac{1}{10^n!}\left(\frac{1}{(10^n+1)!}+\frac{1}{(10^n+2)!}+\ldots\right)$.

Оценка эээ грубая, но оптимизировать не просили.

 Профиль  
                  
 
 Re: Длинные последовательности нулей в десятичной записи e
Сообщение15.03.2019, 08:58 
Заслуженный участник


20/08/14
11687
Россия, Москва
Чисто для информации, в десятичной записи числа $e$ последовательности из $n=1..8$ нулей подряд первый раз встречаются на позициях $\{13,112,328,7688,89296,89296,2332682,359714\}$ после запятой.
Аналогично для $n=1..8$ девяток: $\{12,47,47,29344,290471,384340,384340,384340\}$.

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

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



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

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


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

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