(первое 10-значное простое число в e).com python google challenge 2004
Я только что подошел к одной из проблем, которые утверждают, что они были использованы Google 2004
(the first 10-digit prime in e).com
независимо от этого, я хотел принять вызов и решить его с помощью Python
>>> '%0.52f' % math.exp(1)
'2.71828182845904509079**5598298427**6488423347473144531250'
>>> '%0.52f' % numpy.exp(1)
'2.71828182845904509079**5598298427**6488423347473144531250'
моя программа вернулась 5598298427 который является простым числом
после просмотра в интернете правильный ответ был7427466391
но число опыта в Python не включает эти цифры, как вы можете видеть выше
import numpy
import math
def prime(a):
if a == 2: return True
if a % 2 == 0: return False
if a < 2: return False
i = 2
n = math.sqrt(a) + 1
while(i < n):
if a % i == 0:
return False
i += 1
return True
def prime_e():
e = '%0.51f' % math.exp(1)
e = e.replace("2.","")
for i in range(len(e)):
x = int(e[i:10+i])
if prime(x):
return [i, x]
print prime_e()
так что я делаю что-то не так?
РЕДАКТИРОВАТЬ: используя gmpy2
def exp():
with gmpy2.local_context(gmpy2.context(), precision=100) as ctx:
ctx.precision += 1000
return gmpy2.exp(1)
возвращается 7427466391 после 99 итераций
4 ответа
Фактическое значение e (постоянная Эйлера) равно
http://www.gutenberg.org/files/127/127.txt
2.718281828459045235360287471352662497757247093699959574966967627724076630353547596630353547594571382178525166427427466391 932003059921817413596629043572900334295260595630...
и поэтому правильный ответ на этот вызов 7427466391, Вы не можете вычислить е с требуемой точностью math.exp(1)
Вот способ сделать это:
Сгенерируйте 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, '.')
Функция для проверки простоты целого числа, выбранного для эффективности из http://rosettacode.org/wiki/Primality_by_trial_division:
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
Это означает, что первое десятизначное простое число в e встречается в 98-й позиции после десятичной точки в соответствии с http://explorepdx.com/firsten.html разделе "Расположение ответа".
Более простой способ генерирования цифр е - это расширение серии Эйлера, которое можно сделать следующим образом с помощью кода, адаптированного из числа Эйлера с точностью до 100 цифр (Python), который использует класс десятичных чисел Python для адекватной точности:
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
Проблема в том, что ваше "е" неверно после 15-го знака после запятой (09079 и далее) по причинам, которые здесь объяснили другие. Тем не менее, сам Python имеет все инструменты для обеспечения практически неограниченной точности. Я еще не сталкивался с этим решением, поэтому решил опубликовать его здесь. Магия заключена в "длинном" int, который может быть настолько длинным, насколько позволяет память вашей машины. Поскольку число с плавающей запятой - не более чем целое число, деленное на некоторую степень 10, мы можем легко вычислить (и сохранить) e_as_int=e*10**d, где d - количество требуемых десятичных дробей. Простой код ниже генерирует e из ряда для натурального логарифма:
import itertools
count = itertools.count
def ape(digits):
# e = sum(1/k! for k in count())
# calculate some extra digits to compensate for loss of precision:
r = 3
m = 10**(digits+r)
e = 2*m
f = 1 #initial value for k!
for k in count(2):
f *= k
if f>m: break
# remember, we're doing int division, so m/f = 0 for f>m
e += (m/f)
return e/10**r #truncate to required precision
"ape" означает "приближение e" и достаточно просто отражает его простоту:-) Этот алгоритм находит 10000 цифр e примерно за секунду на моей машине.
Вы знаете, я ценю всех, кто делает их суперэффективными и сложными, но если вам нужно решение проблемы для бедняков (т.е. термины ламена), вот V
def is_Prime(num):
for i in range(2, num):
if num % i == 0:
return False
return True
e = '2.7182818284590452353602874713526624977572470936999595749669676277240766303535475945713821785251664274274663919320030599218174'
value = 4
left = 1
while is_Prime(value) == False:
left += 1
value = e[left] + e[left + 1] + e[left + 2] + e[left + 3] + e[left + 4] + e[left + 5] + e[left + 6] + e[left + 7] + e[left + 8] + e[left + 9]
value = int(value)
print(value)