Masalah Proyek Euler # 731

Question

Dalam masalah Poject Euler ini < https://projecteuler.net/problem=731 > Saya diminta untuk mencari 10 digit desimal dari angka ke-n dan seterusnya dalam perluasan desimal dari infinte serie: $$\sum_{k=1}^\infty\frac1{10^{3^k}3^k}$$ yang sama dengan angka stoneham $\alpha_{10,3}$

Percobaan saya adalah: bawa saya seperti itu $3^i$ > n kemudian ambil semua pecahan dari bentuk tersebut $$a_k=\frac1{3^k}$$ sedemikian rupa sehingga k in [1 .. (i-1)].

Kemudian untuk semua pecahan: ambil 10 angka desimal dari digit ke-n dan seterusnya dan jumlahkan

Metode ini berfungsi dengan baik untuk A (100), tetapi jelas bahwa untuk n besar, metode ini tidak akan berfungsi karena membawa masalah penambahan. Misalnya untuk n =$10^{16}$: kita harus menjumlahkan 10 digit desimal dari $10^{16}$nomor ke depan dari pecahan itu: $$a_k=\frac1{3^k}$$ sehingga k dalam [1..33]. Apakah ada metode lain untuk mengatasi masalah ini?

Kode Python untuk kasus 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]))

Berhenti di $\frac1{81}$ karena $10^{243}$ di penyebut akan memberi kita 243 angka nol setelah koma desimal

Answer 1

Petunjuk: Biarkan$i$ menjadi bilangan bulat terkecil yang $3^i > n$. Apa yang kita kejar adalah$10$ digit dari $n$nomor ke depan dalam jumlah yang terbatas$$ S_1 = \sum_{k=1}^i \frac{1}{10^{3^k}3^k}. $$ Sama halnya, kami menginginkan 10 digit pertama setelah koma desimal dalam bilangan tersebut $10^{n-1}S_1$, yang sama dengan $$ S_2 = \sum_{k=1}^i \frac{10^{n - 3^k - 1}}{3^k}. $$ Artinya, kami hanya menginginkan bagian pecahan dari$S_2$ diperluas menjadi $10$ digit.

---

Inilah kode yang mengimplementasikan ide yang ada dalam pikiran saya:

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

Meskipun secara teknis berhasil, metode ini bermasalah karena $10^{n - 3^k - 1}$sangat besar. Sebaliknya, kami dapat menghitung secara efisien$10^{n - 3^k - 1} \bmod 3^k$. Contohnya:

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