Project Euler Problem 731
Define A(n) to be the 10 decimal digits from the nth digit onward.
Solution
Answer: 6086371427
Let
$$A=\sum_{i=1}^{\infty} \frac{1}{3^i 10^{3^i}}$$
and define $A(n)$ as the 10 decimal digits starting at the $n$-th digit after the decimal point.
We use the identity
$$A(n)=\left\lfloor 10^{n+9}A \right\rfloor \bmod 10^{10}.$$
Since
$$10^{n+9}A = \sum_{i\ge1}\frac{10^{n+9-3^i}}{3^i},$$
only terms with $3^i \le n+9$ contribute.
For $n=10^{16}$, this means only $i\le 33$.
Write
$$10^{m}=3^i q_i+r_i, \qquad 0\le r_i<3^i,$$
where $m=n+9-3^i$. Then
$$\frac{10^m}{3^i}=q_i+\frac{r_i}{3^i}.$$
Hence
$$\left\lfloor \sum_i \frac{10^m}{3^i}\right\rfloor = \sum_i q_i + \left\lfloor \sum_i \frac{r_i}{3^i}\right\rfloor .$$
The residues $r_i$ are computed efficiently using modular exponentiation:
$$r_i \equiv 10^m \pmod{3^i}.$$
Using this method reproduces the examples:
- $A(100)=4938271604$
- $A(10^8)=2584642393$
and for $n=10^{16}$ gives:
Answer: 6086371427