Proyecto Euler problema # 731

Question

En este problema de Poject Euler < https://projecteuler.net/problem=731 > Se me pide que encuentre los 10 dígitos decimales desde el número n en adelante en la expansión decimal de la serie infinte: $$\sum_{k=1}^\infty\frac1{10^{3^k}3^k}$$ que es igual al número de Stoneham $\alpha_{10,3}$

Mi intento fue: tomar yo tal que $3^i$ > n luego toma todas las fracciones de la forma $$a_k=\frac1{3^k}$$ tal que k en [1 .. (i-1)].

Luego, para todas las fracciones: tome los 10 dígitos decimales desde el enésimo dígito en adelante y súmelos

Este método funciona bien para A (100), pero está claro que para n grandes, este método no funcionará debido a que lleva un problema de adición. Por ejemplo para n =$10^{16}$: tenemos que sumar los 10 dígitos decimales del $10^{16}$th número en adelante de esas fracciones: $$a_k=\frac1{3^k}$$ tal que k en [1..33]. ¿Existe otro método para atacar este problema?

Código Python para el 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]))

Detente en $\frac1{81}$ porque $10^{243}$ en el denominador nos da 243 ceros después del punto decimal

Answer 1

Pista: deja$i$ ser el entero más pequeño para el cual $3^i > n$. Lo que buscamos son los$10$ dígitos del $n$el número en adelante en la suma finita$$ S_1 = \sum_{k=1}^i \frac{1}{10^{3^k}3^k}. $$ De manera equivalente, queremos los primeros 10 dígitos después del punto decimal en el número $10^{n-1}S_1$, que es igual a $$ S_2 = \sum_{k=1}^i \frac{10^{n - 3^k - 1}}{3^k}. $$ Es decir, solo queremos la parte fraccionaria de$S_2$ expandido a $10$ dígitos.

---

Aquí hay un código que implementa la idea que tenía en 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))

Aunque técnicamente funciona, este método es problemático porque $10^{n - 3^k - 1}$es muy grande. En cambio, podemos calcular de manera eficiente$10^{n - 3^k - 1} \bmod 3^k$. Por ejemplo:

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