Project Euler problem #731

Question

In this Poject Euler probelm < https://projecteuler.net/problem=731 > I'm asked to find the 10 decimal digits from the nth number onward in the decimal expansion of the infinte serie : $$\sum_{k=1}^\infty\frac1{10^{3^k}3^k}$$ which is equal to the stoneham number $\alpha_{10,3}$

My try was : take i such that $3^i$ > n then take all the fractions of the form $$a_k=\frac1{3^k}$$ such that k in [1..(i-1)] .

Then for all the fractions : take the the 10 decimal digits from the nth digit onward and sum them up

This method works fine for A(100) , but it is clear that for large n , this method will not work due to carries addition issue . For example for n=$10^{16}$: we have to sum the 10 decimal digits from the $10^{16}$th number onward of those fractions : $$a_k=\frac1{3^k}$$ such that k in [1..33] . Is there another method to attack this problem ?

Python code for the case n = 100 :

a='3' # repeating decimal of 1/3

a*=200

b='1' # repeating deciaml of 1/9

b*=200

c='037' # repeating deciaml of 1/27

c*=200

d='012345679' repeating decimal of 1/81 

d*=120

for k in range(99,99+10):

     print(int(a[k])+int(b[k])+int(c[k])+int(d[k]))

Stop at $\frac1{81}$ because $10^{243}$ in the denominator will gives us 243 zeros after the decimal point

Answer 1

Hint: Let $i$ be the smallest integer for which $3^i > n$. What we are after are the $10$ digits from the $n$th number onward in the finite sum $$ S_1 = \sum_{k=1}^i \frac{1}{10^{3^k}3^k}. $$ Equivalently, we want the first 10 digits after the decimal point in the number $10^{n-1}S_1$, which is equal to $$ S_2 = \sum_{k=1}^i \frac{10^{n - 3^k - 1}}{3^k}. $$ That is, we only want the fractional part of $S_2$ expanded to $10$ digits.

---

Here's code that implements the idea I had in mind:

import math

n = 10**8

m = int(math.log(n,3))
tot = 0
for k in range(1,m+1):
    phi = 2*3**(k-1)
    exp = n - 3**k - 1
    exp %= phi
    num = 10**exp
    num %= 3**k
    tot += num/3**k
tot -= int(tot)
print(int(tot*10**10))

Although it technically works, this method is problematic because $10^{n - 3^k - 1}$ is very large. Instead, we can efficiently compute $10^{n - 3^k - 1} \bmod 3^k$. For instance:

import math

# SET VALUE OF n HERE
n = 10**8

m = int(math.log(n,3))
tot = 0
for k in range(1,m+1):
    den = 3**k
    exp = n - den - 1
    num = pow(10,exp,den)
    tot += num/den       # python 2: tot += float(num)/den
tot -= int(tot)
print(int(tot*10**10))