Существует ли способ найти заданную цифру в дроби?

[maravan]

Добрый вечер, возник вопрос, сущесвует ли способ быстро посчитать заданную цифру в дроби?

Например,

$\frac{1}{7} = 0,(142857)$

можно ли быстро, желательно за $O(1)$, получить 3-ую цифру после запятой, т.е. 2?

[Deggial]

За $O(1)$ Вы, очевидно, не сможете получить произвольную $k$-ю цифру дроби, поскольку за $O(1)$ можно вычислить лишь конечное, не зависящее от $k$, число цифр дроби.
Если обозначить период дроби $T$, то достаточно $O(T)$ операций. Однако, если $n$ - простое, то $T=n-1$ тогда и только тогда, когда $10$ (основание $10$-ичной системы счисления) - первообразный корень по модулю $n$. Согласно гипотезе Артина, таких простых $n$ бесконечно много. Предполагая истинной гипотезу Артина, получаем $O(T)=O(n)$.
Короче говоря, я не вижу ничего лучше, чем просто вычислить десятичную дробь с точностью $10^{-k}$ и взять $k$-ю цифру числа.

[Joker_vD]

Разумеется. Считаем цифры в периоде — определяем длину периода — профит.