ปัญหา Project Euler # 731

Question

ในโพสต์ออยเลอร์ probelm นี้ < https://projecteuler.net/problem=731 > ฉันขอให้ค้นหาทศนิยม 10 หลักจากเลขที่ n เป็นต้นไปในการขยายทศนิยมของซีรีย์ infinte: $$\sum_{k=1}^\infty\frac1{10^{3^k}3^k}$$ ซึ่งเท่ากับจำนวนสโตนแฮม $\alpha_{10,3}$

ความพยายามของฉันคือ: เอาแบบนั้น $3^i$ > n จากนั้นนำเศษส่วนทั้งหมดของแบบฟอร์ม $$a_k=\frac1{3^k}$$ เช่นนั้น k ใน [1 .. (i-1)]

จากนั้นสำหรับเศษส่วนทั้งหมดให้นำทศนิยม 10 หลักจากหลักที่ n เป็นต้นไปแล้วสรุปรวมกัน

วิธีนี้ใช้ได้ดีสำหรับ A (100) แต่เป็นที่ชัดเจนว่าสำหรับ n ขนาดใหญ่วิธีนี้จะไม่ได้ผลเนื่องจากมีปัญหาการเพิ่ม ตัวอย่างเช่นสำหรับ n =$10^{16}$: เราต้องรวมทศนิยม 10 หลักจาก $10^{16}$เลข th เป็นต้นไปของเศษส่วนเหล่านั้น: $$a_k=\frac1{3^k}$$ เช่นนั้น k ใน [1..33] มีวิธีอื่นในการโจมตีปัญหานี้หรือไม่?

รหัส Python สำหรับกรณี 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]))

หยุดที่ $\frac1{81}$ เพราะ $10^{243}$ ในตัวส่วนจะทำให้เรามีศูนย์ 243 หลังจุดทศนิยม

Answer 1

คำแนะนำ:ให้$i$ เป็นจำนวนเต็มที่น้อยที่สุด $3^i > n$. สิ่งที่เราต้องการคือ$10$ หลักจาก $n$เลข th เป็นต้นไปในผลรวม จำกัด$$ S_1 = \sum_{k=1}^i \frac{1}{10^{3^k}3^k}. $$ ในทางเดียวกันเราต้องการให้ 10 หลักแรกหลังจุดทศนิยมในตัวเลข $10^{n-1}S_1$ซึ่งเท่ากับ $$ S_2 = \sum_{k=1}^i \frac{10^{n - 3^k - 1}}{3^k}. $$ นั่นคือเราต้องการเพียงส่วนที่เป็นเศษส่วนของ$S_2$ ขยายเป็น $10$ ตัวเลข

---

นี่คือรหัสที่ใช้ความคิดที่ฉันคิดไว้:

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

แม้ว่าจะได้ผลในทางเทคนิค แต่วิธีนี้ก็มีปัญหาเพราะ $10^{n - 3^k - 1}$มีขนาดใหญ่มาก แต่เราสามารถคำนวณได้อย่างมีประสิทธิภาพ$10^{n - 3^k - 1} \bmod 3^k$. ตัวอย่างเช่น:

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