Re:A formula for the nβth digit of π and π^n
by kdkdk on Sunday January 15, 2023 @01:45PM
(#34391852)
Even rational numbers which have repeating digits at the end are not O(1) because in order to calculate the n-th digit you need to calculate n modulo k where k is the length until the number repeats its digits, which needs to read the entire input number n (thus runs in O(log(n)).
The only exception are rational numbers with k being a power of two.
Take 0.1010101010β¦, you can get the n-th digit by reading off the smallest digit of n and checking whether it is a 0 or a 1.
There are transcendental numbers where the n-th digit can be computed in O(log n) like Champerowne constant though.
There are transcendental numbers where the n-th digit can be computed in O(log n) like Champerowne constant though.