Задача проекта Эйлера # 731

Question

В этом проекте Эйлера проблема < https://projecteuler.net/problem=731 > Меня просят найти 10 десятичных цифр, начиная с n-го числа в десятичном расширении серии infinte: $$\sum_{k=1}^\infty\frac1{10^{3^k}3^k}$$ что равно числу Стоунхэма $\alpha_{10,3}$

Моя попытка была такой: возьми я такой, чтобы $3^i$ > n, тогда возьмем все дроби вида $$a_k=\frac1{3^k}$$ такое, что k в [1 .. (i-1)].

Затем для всех дробей: возьмите 10 десятичных цифр, начиная с n-й цифры, и просуммируйте их.

Этот метод отлично работает для A (100), но ясно, что для больших n этот метод не будет работать из-за проблемы добавления переносов. Например, для n =$10^{16}$: мы должны суммировать 10 десятичных цифр из $10^{16}$число после этих дробей: $$a_k=\frac1{3^k}$$ такое, что k в [1..33]. Есть ли другой способ решить эту проблему?

Код Python для случая 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]))

Останавливаться на $\frac1{81}$ так как $10^{243}$ в знаменателе даст нам 243 нуля после запятой

Answer 1

Подсказка: пусть$i$ быть наименьшим целым числом, для которого $3^i > n$. То, что нам нужно, это$10$ цифры из $n$число вперед в конечной сумме $$ S_1 = \sum_{k=1}^i \frac{1}{10^{3^k}3^k}. $$ Точно так же мы хотим, чтобы первые 10 цифр после десятичной точки в числе $10^{n-1}S_1$, что равно $$ S_2 = \sum_{k=1}^i \frac{10^{n - 3^k - 1}}{3^k}. $$ То есть, мы только хотим , дробную часть из$S_2$ расширен до $10$ цифры.

---

Вот код, реализующий задуманную мной идею:

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

Хотя технически это работает, этот метод проблематичен, потому что $10^{n - 3^k - 1}$очень большой. Вместо этого мы можем эффективно вычислить$10^{n - 3^k - 1} \bmod 3^k$. Например:

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