Progetto Eulero problema # 731

Question

In questo Poject Euler probelm < https://projecteuler.net/problem=731 > Mi viene chiesto di trovare le 10 cifre decimali dall'ennesimo numero in poi nell'espansione decimale della serie infinita: $$\sum_{k=1}^\infty\frac1{10^{3^k}3^k}$$ che è uguale al numero di Stoneham $\alpha_{10,3}$

Il mio tentativo è stato: prendilo in questo modo $3^i$ > n quindi prende tutte le frazioni della forma $$a_k=\frac1{3^k}$$ tale che k in [1 .. (i-1)].

Quindi per tutte le frazioni: prendi le 10 cifre decimali dall'ennesima cifra in poi e sommale

Questo metodo funziona bene per A (100), ma è chiaro che per n grande questo metodo non funzionerà a causa del problema dell'addizione dei carry. Ad esempio per n =$10^{16}$: dobbiamo sommare le 10 cifre decimali dal $10^{16}$esimo numero in poi di quelle frazioni: $$a_k=\frac1{3^k}$$ tale che k in [1..33]. C'è un altro metodo per affrontare questo problema?

Codice Python per il caso 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]))

Fermarsi a $\frac1{81}$ perché $10^{243}$ al denominatore ci darà 243 zeri dopo il punto decimale

Answer 1

Suggerimento: lascia$i$ essere il numero intero più piccolo per il quale $3^i > n$. Quello che stiamo cercando sono i file$10$ cifre da $n$esimo numero in poi nella somma finita$$ S_1 = \sum_{k=1}^i \frac{1}{10^{3^k}3^k}. $$ In modo equivalente, vogliamo le prime 10 cifre dopo il punto decimale nel numero $10^{n-1}S_1$, che è uguale a $$ S_2 = \sum_{k=1}^i \frac{10^{n - 3^k - 1}}{3^k}. $$ Cioè, vogliamo solo la parte frazionaria di$S_2$ ampliato a $10$ cifre.

---

Ecco il codice che implementa l'idea che avevo in mente:

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

Sebbene tecnicamente funzioni, questo metodo è problematico perché $10^{n - 3^k - 1}$è molto grande. Invece, possiamo calcolare in modo efficiente$10^{n - 3^k - 1} \bmod 3^k$. Per esempio:

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