（e.com 中第一个 10 位素数 python google challenge 2004

Question

我刚刚提出了一项声称由 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)

returns 7427466391 99 次迭代后

Answer 1

实际e（欧拉常数）值为

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

2.718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921817413596629043572900334295260595630...

因此挑战的正确答案是 7427466391。你无法计算 e 需要精度 by math.exp(1)

Answer 2

这里有一个方法：

使用 continued fractions method with answer by @quantum in Code to Generate e one Digit at a Time, which is from answer by @wnoise in Generating digits of square root of 2 生成 e 的第一个 1000 位数字，这是一个 "adaptation of Haskell code ... that has been floating around":

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位，与'The location of the answer'下的http://explorepdx.com/firsten.html一致。

生成 e 数字的更简单方法是使用 Euler's series expansion which can be done as follows with code adapted from Euler's Number with 100 Digit Precision (Python)，它使用 Python 的十进制 class 以获得足够的精度：

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

Answer 3

问题是您的 'e' 在小数点后第 15 位（09079 及以后）是错误的，原因已在此处解释。然而，python 本身拥有所有工具，可以为 'e' 提供几乎无限的精度。我还没有遇到过这个解决方案，所以我决定在这里post。神奇之处在于 'long' int，只要您的机器内存允许，它就可以。由于 float 只不过是 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' 并且很好地反映了它的简单性:-) 这个算法在我的机器上大约一秒钟内找到了 e 的 10000 位数字。

（e.com 中第一个 10 位素数 python google challenge 2004

(the first 10-digit prime in e).com python google challenge 2004

python

math

exp

gmpy