Project Euler sorunu # 731

Question

Bu Poject Euler probleminde < https://projecteuler.net/problem=731 > Sonsuz serinin ondalık açılımında n'inci sayıdan itibaren 10 ondalık basamağı bulmam isteniyor: $$\sum_{k=1}^\infty\frac1{10^{3^k}3^k}$$ bu taş hacı sayısına eşittir $\alpha_{10,3}$

Benim denemem: öyle al $3^i$ > n sonra formun tüm kesirlerini al $$a_k=\frac1{3^k}$$ öyle ki [1 .. (i-1)] 'de k.

Sonra tüm kesirler için: 10 ondalık basamağı n'inci basamaktan itibaren alın ve toplayın

Bu yöntem A (100) için iyi çalışıyor, ancak büyük n için toplama sorunu nedeniyle bu yöntemin çalışmayacağı açıktır. Örneğin n =$10^{16}$: 10 ondalık basamağı toplamalıyız $10^{16}$bu kesirlerin ilerisindeki sayı: $$a_k=\frac1{3^k}$$ öyle ki [1..33] 'te k. Bu sorunu çözmenin başka bir yöntemi var mı?

N = 100 durumu için Python kodu:

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

Dur $\frac1{81}$ Çünkü $10^{243}$ paydada ondalık noktadan sonra bize 243 sıfır verir

Answer 1

İpucu: Bırak$i$ en küçük tam sayı olmak $3^i > n$. Peşinde olduğumuz şey$10$ rakamlar $n$sonlu toplamda ileriye doğru inci sayı$$ S_1 = \sum_{k=1}^i \frac{1}{10^{3^k}3^k}. $$ Aynı şekilde, sayıdaki ondalık noktadan sonraki ilk 10 haneyi istiyoruz $10^{n-1}S_1$eşittir $$ S_2 = \sum_{k=1}^i \frac{10^{n - 3^k - 1}}{3^k}. $$ Olduğunu, sadece istediğiniz fraksiyonel bölümünü arasında$S_2$ genişletildi $10$ rakamlar.

---

Aklımdaki fikri uygulayan kod:

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

Teknik olarak işe yarasa da, bu yöntem sorunludur çünkü $10^{n - 3^k - 1}$çok büyük. Bunun yerine, verimli bir şekilde hesaplayabiliriz$10^{n - 3^k - 1} \bmod 3^k$. Örneğin:

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