Problème du projet Euler # 731

Question

Dans ce probelm Poject Euler < https://projecteuler.net/problem=731 > On me demande de trouver les 10 chiffres décimaux à partir du nième nombre dans le développement décimal de la série infinte: $$\sum_{k=1}^\infty\frac1{10^{3^k}3^k}$$ qui est égal au nombre de Stoneham $\alpha_{10,3}$

Mon essai était: prends-moi tel que $3^i$ > n prend alors toutes les fractions de la forme $$a_k=\frac1{3^k}$$ tel que k dans [1 .. (i-1)].

Puis pour toutes les fractions: prenez les 10 chiffres décimaux à partir du nième chiffre et additionnez-les

Cette méthode fonctionne bien pour A (100), mais il est clair que pour un grand n, cette méthode ne fonctionnera pas en raison d'un problème d'ajout de transport. Par exemple pour n =$10^{16}$: nous devons additionner les 10 chiffres décimaux de la $10^{16}$ème nombre de ces fractions: $$a_k=\frac1{3^k}$$ tel que k dans [1..33]. Existe-t-il une autre méthode pour attaquer ce problème?

Code Python pour le cas 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]))

Arrêté à $\frac1{81}$ car $10^{243}$ dans le dénominateur nous donnera 243 zéros après la virgule décimale

Answer 1

Indice: laissez$i$ être le plus petit entier pour lequel $3^i > n$. Ce que nous recherchons, ce sont les$10$ chiffres du $n$ème nombre en avant dans la somme finie$$ S_1 = \sum_{k=1}^i \frac{1}{10^{3^k}3^k}. $$ De manière équivalente, nous voulons que les 10 premiers chiffres après la virgule décimale dans le nombre $10^{n-1}S_1$, qui est égal à $$ S_2 = \sum_{k=1}^i \frac{10^{n - 3^k - 1}}{3^k}. $$ Autrement dit, nous ne voulons que la partie fractionnaire de$S_2$ étendu à $10$ chiffres.

---

Voici le code qui met en œuvre l'idée que j'avais en tête:

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

Bien que cela fonctionne techniquement, cette méthode est problématique car $10^{n - 3^k - 1}$est très grand. Au lieu de cela, nous pouvons calculer efficacement$10^{n - 3^k - 1} \bmod 3^k$. Par exemple:

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