Projekt Euler Problem # 731

Question

In diesem Poject Euler probelm < https://projecteuler.net/problem=731 > Ich werde gebeten, die 10 Dezimalstellen ab der n-ten Zahl in der Dezimalerweiterung der Infinte-Serie zu finden: $$\sum_{k=1}^\infty\frac1{10^{3^k}3^k}$$ Das ist gleich der Stoneham-Nummer $\alpha_{10,3}$

Mein Versuch war: nimm ich so $3^i$ > n dann nimm alle Brüche der Form $$a_k=\frac1{3^k}$$ so dass k in [1 .. (i-1)].

Dann für alle Brüche: Nehmen Sie die 10 Dezimalstellen ab der n-ten Stelle und fassen Sie sie zusammen

Diese Methode funktioniert gut für A (100), aber es ist klar, dass diese Methode für großes n aufgrund von Übertragungsproblemen nicht funktioniert. Zum Beispiel für n =$10^{16}$: Wir müssen die 10 Dezimalstellen aus dem summieren $10^{16}$Die Zahl ab diesen Brüchen: $$a_k=\frac1{3^k}$$so dass k in [1..33]. Gibt es eine andere Methode, um dieses Problem anzugreifen?

Python-Code für den Fall 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]))

Halte bei $\frac1{81}$ da $10^{243}$ im Nenner ergibt sich 243 Nullen nach dem Dezimalpunkt

Answer 1

Hinweis: Lassen Sie$i$ sei die kleinste ganze Zahl für die $3^i > n$. Was wir suchen, sind die$10$ Ziffern aus dem $n$th Zahl weiter in der endlichen Summe$$ S_1 = \sum_{k=1}^i \frac{1}{10^{3^k}3^k}. $$ Entsprechend wollen wir die ersten 10 Stellen nach dem Dezimalpunkt in der Zahl $10^{n-1}S_1$, was gleich ist $$ S_2 = \sum_{k=1}^i \frac{10^{n - 3^k - 1}}{3^k}. $$Das heißt, wir wollen nur den Bruchteil von$S_2$ erweitert auf $10$ Ziffern.

---

Hier ist Code, der die Idee umsetzt, die ich mir vorgestellt hatte:

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

Obwohl es technisch funktioniert, ist diese Methode deshalb problematisch $10^{n - 3^k - 1}$es ist sehr groß. Stattdessen können wir effizient rechnen$10^{n - 3^k - 1} \bmod 3^k$. Zum Beispiel:

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