Projekt Euler, problem nr 731

Question

W tym Poject Euler probelm < https://projecteuler.net/problem=731 > Jestem proszony o znalezienie 10 cyfr dziesiętnych od n-tej liczby dalej w dziesiętnym rozwinięciu serii infinte: $$\sum_{k=1}^\infty\frac1{10^{3^k}3^k}$$ co jest równe liczbie kamienistej $\alpha_{10,3}$

Moja próba brzmiała: weź mnie takiego $3^i$ > n, a następnie weź wszystkie ułamki formularza $$a_k=\frac1{3^k}$$ takie, że k w [1 .. (i-1)].

Następnie dla wszystkich ułamków: weź 10 cyfr dziesiętnych od n-tej cyfry wzwyż i zsumuj je

Ta metoda działa dobrze dla A (100), ale jest jasne, że dla dużego n ta metoda nie będzie działać z powodu problemu z dodawaniem. Na przykład dla n =$10^{16}$: musimy zsumować 10 cyfr dziesiętnych z $10^{16}$liczba dalej od tych ułamków: $$a_k=\frac1{3^k}$$ takie, że k w [1..33]. Czy istnieje inna metoda rozwiązania tego problemu?

Kod Pythona dla przypadku 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]))

Zatrzymaj się przy $\frac1{81}$ dlatego $10^{243}$ w mianowniku daje nam 243 zera po przecinku

Answer 1

Podpowiedź: niech$i$ być najmniejszą liczbą całkowitą, dla której $3^i > n$. To, czego szukamy, to$10$ cyfry z $n$liczba dalej w sumie skończonej$$ S_1 = \sum_{k=1}^i \frac{1}{10^{3^k}3^k}. $$ Równoważnie chcemy, aby pierwsze 10 cyfr po przecinku w liczbie $10^{n-1}S_1$, co jest równe $$ S_2 = \sum_{k=1}^i \frac{10^{n - 3^k - 1}}{3^k}. $$ Oznacza to, że tylko chcą ułamkowej części z$S_2$ rozszerzony do $10$ cyfry.

---

Oto kod, który realizuje pomysł, o którym myślałem:

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

Chociaż technicznie działa, ta metoda jest problematyczna, ponieważ $10^{n - 3^k - 1}$Jest bardzo duże. Zamiast tego możemy wydajnie obliczać$10^{n - 3^k - 1} \bmod 3^k$. Na przykład:

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