5

我刚刚遇到了声称被 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 中的 exp 数字不包括该数字

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)

742746639199 次迭代后返回

4

3 回答 3

3

实际e欧拉常数)值为

http://www.gutenberg.org/files/127/127.txt

2.71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642 7427466391 932003059921817413596629043572900334295260595630...

所以这个挑战的正确答案是7427466391。您无法通过以下方式以所需的精度计算 emath.exp(1)

于 2015-09-02T12:58:52.283 回答
1

这是一种方法:

使用连分数法生成 e的第 1 1000 位, @quantum 在Code to Generate e one Digit at a Time中回答,这是来自 @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

找出 e 中的前 10 位素数(我的贡献):

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 中的前 10 位素数出现在小数点后的第 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 所指出的,一种更简单的方法是直接使用 decimal 模块以必要的精度生成 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
于 2015-09-02T15:17:47.267 回答
0

问题是您的“e”在小数点后 15 位(09079 及以后)之后是错误的,原因其他人已在此处解释。但是,python 本身具有所有板载工具,可以为“e”提供几乎无限的精度。我还没有遇到这个解决方案,所以我决定在这里发布。神奇之处在于'long' 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' 代表 'approximation of e' 并很好地反映了它的简单性:-) 这个算法在我的机器上大约一秒钟内找到了 10000 位 e。

于 2015-11-23T18:37:02.610 回答