Вот как это сделать:
Сгенерируйте 1-ю 1000 цифр числа e, используя метод непрерывных дробей с ответом @quantum в Код для генерации одной цифры за раз, который взят из ответа @wnoise в Генерация цифр квадратного корня из 2, что "адаптация кода Haskell... которая циркулирует вокруг":
def z(contfrac, a=1, b=0, c=0, d=1):
for x in contfrac:
while a > 0 and b > 0 and c > 0 and d > 0:
t = a // c
t2 = b // d
if not t == t2:
break
yield t
a = (10 * (a - c*t))
b = (10 * (b - d*t))
# continue with same fraction, don't pull new x
a, b = x*a+b, a
c, d = x*c+d, c
for digit in rdigits(a, c):
yield digit
def rdigits(p, q):
while p > 0:
if p > q:
d = p // q
p = p - q * d
else:
d = (10 * p) // q
p = 10 * p - q * d
yield d
def e_cf_expansion():
yield 1
k = 0
while True:
yield k
k += 2
yield 1
yield 1
def e_dec():
return z(e_cf_expansion())
gen = e_dec()
e = [str(gen.next()) for i in xrange(1000)]
e.insert(1, '.')
Функция для проверки простоты целого числа, выбранного для эффективности из Rosetta Code Primality_by_trial_division#Python:
def isprime(a):
if a < 2: return False
if a == 2 or a == 3: return True # manually test 2 and 3
if a % 2 == 0 or a % 3 == 0: return False # exclude multiples of 2 and 3
maxDivisor = a**0.5
d, i = 5, 2
while d <= maxDivisor:
if a % d == 0: return False
d += i
i = 6 - i # this modifies 2 into 4 and viceversa
return True
Найдите первое 10-значное простое число в e (мой вклад):
for i in range(len(e[2:])-10):
x = int(reduce(operator.add,e[2:][i:i+10]))
if isprime(x):
print x
print i
break
Это печатает:
7427466391
98
Это означает, что первое 10-значное простое число в e находится на 98-м месте после запятой в соответствии с http://explorepdx.com/firsten.html в разделе "Местоположение ответа".
Более простой способ сгенерировать цифры e – использовать расширение ряда Эйлера, которое можно делается следующим образом с кодом, адаптированным из Число Эйлера со 100-значной точностью (Python), использующее класс Python Decimal для обеспечения достаточной точности:
import operator
import decimal as dc
def edigits(p):
dc.getcontext().prec = p
factorial = 1
euler = 2
for x in range(2, 150):
factorial *= x
euler += dc.Decimal(str(1.0))/dc.Decimal(str(factorial))
return euler
estring = edigits(150).to_eng_string()[2:]
for i in range(len(estring)-10):
x = int(reduce(operator.add,estring[i:i+10]))
if isprime(x):
print x
print i
break
Это печатает:
7427466391
98
Как указал @MarkDickinson, еще более простым методом является использование десятичного модуля напрямую для генерации e с необходимой точностью. Например:
import operator
import decimal
decimal.getcontext().prec = 150
e_from_decimal = decimal.Decimal(1).exp().to_eng_string()[2:]
for i in range(len(e_from_decimal)-10):
x = int(reduce(operator.add,e_from_decimal[i:i+10]))
if isprime(x):
print x
print i
break
Это печатает:
7427466391
98
person
Community
schedule
02.09.2015
decimal: например,decimal.getcontext().prec = 1000; e = decimal.Decimal(1).exp(). - person Mark Dickinson schedule 02.09.2015bigfloatиgmpy2. Я столкнулся с проблемами при компиляции обоих в Windows, но у gmpy2 уже была скомпилированная версия для Windows. - person Elteroooo schedule 03.09.2015bigfloatдля Windows. Из этих двухgmpy2определенно правильный выбор. - person Mark Dickinson schedule 03.09.2015