Project Euler problem # 731

Question

Trong thăm dò Poject Euler này < https://projecteuler.net/problem=731 > Tôi được yêu cầu tìm 10 chữ số thập phân từ số thứ n trở đi trong phần mở rộng thập phân của chuỗi infinte: $$\sum_{k=1}^\infty\frac1{10^{3^k}3^k}$$ bằng với số stoneham $\alpha_{10,3}$

Cố gắng của tôi là: lấy tôi như vậy $3^i$ > n thì nhận tất cả các phân số có dạng $$a_k=\frac1{3^k}$$ sao cho k trong [1 .. (i-1)].

Sau đó, đối với tất cả các phân số: lấy 10 chữ số thập phân từ chữ số thứ n trở đi và cộng lại

Phương pháp này hoạt động tốt đối với A (100), nhưng rõ ràng là đối với n lớn, phương pháp này sẽ không hoạt động do vấn đề cộng mang. Ví dụ cho n =$10^{16}$: chúng ta phải tính tổng 10 chữ số thập phân từ $10^{16}$số thứ trở đi của các phân số đó: $$a_k=\frac1{3^k}$$ sao cho k trong [1..33]. Có phương pháp nào khác để tấn công vấn đề này không?

Mã Python cho trường hợp 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]))

Dừng lại ở $\frac1{81}$ bởi vì $10^{243}$ ở mẫu số sẽ cho chúng ta 243 số không sau dấu thập phân

Answer 1

Gợi ý: Hãy$i$ là số nguyên nhỏ nhất mà $3^i > n$. Những gì chúng ta đang theo đuổi là$10$ các chữ số từ $n$số thứ trở đi trong tổng hữu hạn$$ S_1 = \sum_{k=1}^i \frac{1}{10^{3^k}3^k}. $$ Tương tự, chúng tôi muốn 10 chữ số đầu tiên sau dấu thập phân trong số $10^{n-1}S_1$, bằng $$ S_2 = \sum_{k=1}^i \frac{10^{n - 3^k - 1}}{3^k}. $$ Đó là, chúng tôi chỉ muốn phần nhỏ của$S_2$ mở rộng thành $10$ các chữ số.

---

Đây là đoạn mã thực hiện ý tưởng mà tôi đã nghĩ đến:

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))

Mặc dù nó hoạt động về mặt kỹ thuật, nhưng phương pháp này có vấn đề vì $10^{n - 3^k - 1}$rất rộng. Thay vào đó, chúng tôi có thể tính toán một cách hiệu quả$10^{n - 3^k - 1} \bmod 3^k$. Ví dụ:

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))