Problema do Projeto Euler # 731

Question

Neste problema Poject Euler < https://projecteuler.net/problem=731 > Devo encontrar os 10 dígitos decimais do enésimo número em diante na expansão decimal da série infinita: $$\sum_{k=1}^\infty\frac1{10^{3^k}3^k}$$ que é igual ao número de stoneham $\alpha_{10,3}$

Minha tentativa foi: tomar eu de modo que $3^i$ > n, em seguida, pegue todas as frações do formulário $$a_k=\frac1{3^k}$$ de modo que k em [1 .. (i-1)].

Então, para todas as frações: pegue os 10 dígitos decimais do enésimo dígito em diante e some-os

Este método funciona bem para A (100), mas está claro que para n grande, este método não funcionará devido ao problema de adição de carregadores. Por exemplo, para n =$10^{16}$: temos que somar os 10 dígitos decimais do $10^{16}$o número em diante dessas frações: $$a_k=\frac1{3^k}$$ tal que k em [1..33]. Existe outro método para atacar este problema?

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

Pare em $\frac1{81}$ Porque $10^{243}$ no denominador nos dará 243 zeros após o ponto decimal

Answer 1

Dica: vamos$i$ seja o menor inteiro para o qual $3^i > n$. O que procuramos é o$10$ dígitos do $n$o número em diante na soma finita$$ S_1 = \sum_{k=1}^i \frac{1}{10^{3^k}3^k}. $$ Da mesma forma, queremos os primeiros 10 dígitos após a vírgula decimal do número $10^{n-1}S_1$, que é igual a $$ S_2 = \sum_{k=1}^i \frac{10^{n - 3^k - 1}}{3^k}. $$ Ou seja, queremos apenas a parte fracionária de$S_2$ expandido para $10$ dígitos.

---

Este é o código que implementa a ideia que tive em 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))

Embora funcione tecnicamente, este método é problemático porque $10^{n - 3^k - 1}$é muito grande. Em vez disso, podemos calcular com eficiência$10^{n - 3^k - 1} \bmod 3^k$. Por exemplo:

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