Длинные последовательности нулей в десятичной записи e

[ArshakA]

Дана десятичная запись числа Эйлера $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$. Вряд ли стоит рассчитывать доказать, что оно ненормально, поэтому стоит быть готовым к сколь угодно длинным последовательностям нулей.

[iifat]

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

[ArshakA]

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

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

[g______d]

Я так понимаю, что достаточно предъявить эффективную верхнюю оценку максимальной длины цепочки из девяток, если первая девятка цепочки находится на позиции $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)$.

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

[Dmitriy40]

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