关于python:Python求解谷歌高速公路招聘广告-无理数e中前十位连续的素数-com

偶然间，看到吴军老师的《浪潮之巅（第四版）》里有讲到这么一个故事。

Google已经在加州的101高速公路上用大广告牌登了这样的广告：

{ 无理数e中前十位间断的素数 }.com

你如果晓得这个答案（7427466391.com），就能够通过上述网址进入到Google的招聘网站。而可能计算出这道题，要很聪慧。

“很聪慧”？吴军老师的这句话倒是让人来趣味了，本人也凑性借助计算机的力量推敲推敲下这个证明题。

思路

大家都晓得，ｅ是无理数，换言之，有限不循环小数。世间总有些数学喜好人士乐此不疲地用计算机来推算这些无理数的小数位，π如此，ｅ更不例外。所以，

第一步，在一些权威的数学网站上找到ｅ的小数位数据；

这时候，就是谷歌大法好了，来到了ｅ的维基英文百科页面，留意到了上面ｅ的小数表达形式前面的“A001113”超链接，有蹊跷，便点进去看下。

接着便是这个OEIS站点的A001113页面了，原来是数论方面的一个很权威的数据库网站。

带着探宝的眼光在这个网页上下左右扫视，总算发现了指标。LINKS（链接）的第一个条目便是了。

N. J. A. Sloane, Table of 50000 digits of e labeled from 1 to 50000 [based on the ICON Project link below]

作者也是开办了这个OEIS组织的N.J.A Sloane，看来是个此畛域的小人物了，道歉有眼不识泰山。

点进去这个Table of 50000 digits of e labeled from 1 to 50000，页面后果让人很愉悦。间接的纯文本数据，左列为小数位数，右列为对应数值。到时候拿到数据时简略解决下即可开展后续工作，心愿这道证明题的答案就在这50000个数中，不然得扩大范围了。

到此，e无理数的小数位数据有了，便能够开展下一步工作了。

第二步，如何判断一个数是素数？

上小学的时候开始，数学老师就教诲咱们，素数的定义是指一个除了1和该数本身外，无奈被其余自然数整除的大于1的自然数。所以天然，判断思路便是对一个大于1的自然数n，顺次判断2 → n是否整除n，如果发现一个数能整除n，那么n不是素数，否则是。另外，思考到对称性，咱们也不用始终递增到n，如对于2*3和3*2，6/2和6/3皆断定6为合数，然而递增到2时就曾经是充沛了， 故不用再思考3。

Python代码如下：

def isPrime(n: int) -> bool:
  if n <= 1:
    return False
  i = 2
  # Make use of symmetry. For example, 2*3=6, 3*2=6
  while i * i < n:
    if n % i == 0:
      return False
    i += 1
  return True

在网上查阅素数相干的材料的时候，发现数论里有个素数散布法则也能够拿来判断素数。起源——素数断定算法

素数散布法则:

当 n >= 5 时，如果n为素数，那么 n % 6 = 1 || n % 6 = 5, 即 n 肯定呈现在 6x（x ≥ 1）两侧。换句话说，任意一个素数都能够被示意为 6x ± 1， x ∈ N 的模式。

证实：

把6x左近的数用以下形式示意：

……(6x – 1), 6x, 6x + 1, 2(3x + 1), 3(2x + 1), 2(3x + 2), 6x + 5, 6(x+1)……

不在6x两侧的数为：2(3x + 1), 3(2x + 1), 2(3x + 2), 它们不是素数，所以素数呈现在6x的两侧。

用Python代码实现如下，工夫复杂度上比前一种相差无几，不过对于咱们的证实来说，是够用了。

def isPrime(n: int) -> bool:
  if n <= 1:
    return False
  if n <= 3:
    return True
  # For case of 2(3x + 1), 3(2x + 1), 2(3x + 2)
  if n % 2 == 0 or n % 3 == 0:
    return False
  # For case of the multiplication of prime numbers
  i = 5
  while i * i < n:
    if n % i == 0 or n % (i + 2) == 0:
      return False
    i += 6
  return True

此外，理解到密码学外面断定素数有很大的用途，比方驰名的RSA算法。在判断素数算法方面，并没有采纳下面的工夫复杂度较高的简略取余算法，而是Fermat小定理、Miller-Rabin算法及Solovay-Strassen算法等，了解起来较为吃力，具体可参考下这篇文章——PyCrypto密码学库源码解析（一）随机数和大素数生成, 以及下面那篇。

至此，必要的资料都筹备好了，能够进行最初一步了。

第三步，for循环e的小数位数据判断第一个10位长的素数。

单刀直入，间接源码抛出来先。

具体思路：先应用requests库获取e小数位数据，而后转存为文件便于逐行读取，for循环逐行读取每一小数位数据，进行切片操作，整顿成证实所需的10位整数，失去总数量为49991的有序列表，再借助素数断定函数一一断定这些10位整数，最初失去答案——7427466391。

import requests
import re

response = requests.get('https://oeis.org/A001113/b001113.txt')

# Save sequence to a file for later use
out_file = open('digits_of_e.txt', 'w')
print(response.text, file=out_file)

queue = []

container = ''
counter = 0  
in_file = open('digits_of_e.txt', 'r')
list_in_file = list(in_file)
for index, line in enumerate(list_in_file):
  segments = list_in_file[index:index+10]
  # get lines at a batch of 10 lines
  for segment in segments:
    matchObj = re.match(r'([\d]*) (\d).*', segment, re.I)
    counter += 1
    if counter <= 10:
      container += matchObj.group(2) if matchObj != None else ''
    else:
      counter = 1
      if len(container) == 10:
        queue.append(container)
      container = matchObj.group(2) if matchObj != None else ''
in_file.close()

print(len(queue)) # 49991 indeed

def isPrime(n: int) -> bool:
  # Prime number definition version:
  '''
  if n <= 1:
    return False
  i = 2
  # Make use of symmetry. For example, 2*3=6, 3*2=6
  while i * i < n:
    if n % i == 0:
      return False
    i += 1
  return True
  '''
  # Distribution pattern of prime number version:
  if n <= 1:
    return False
  if n <= 3:
    return True
  # For case of 2(3x + 1), 3(2x + 1), 2(3x + 2)
  if n % 2 == 0 or n % 3 == 0:
    return False
  # For case of the multiplication of prime numbers
  i = 5
  while i * i < n:
    if n % i == 0 or n % (i + 2) == 0:
      return False
    i += 6
  return True

result = None
for num in queue:
  if isPrime(int(num)):
    print(num)
    result = num
    break

print(result == '7427466391')
print(isPrime(7427466391))

运行后果：

宾果！

完结

证明题解答结束，咱得走个典礼感，拜访拜访这个网站——7427466391.com。

后果是502谬误……

行吧，看来这个站点早被人家摈弃了，毕竟这个高速公路广告也是谷歌在2004年搞的恶作剧。

最初，把源码整顿了个Kaggle Notebook版本。欢送查阅！

First10DigitPrimeFoundInConsecutiveDigitsOfE | Kaggle

参考资料汇总

1. 吴军老师的《浪潮之巅（第四版）》P44
2. 无理数ｅ的维基英文百科
3. OEIS站点的A001113页面
4. Table of 50000 digits of e labeled from 1 to 50000
5. 素数断定算法
6. PyCrypto密码学库源码解析（一）随机数和大素数生成
7. What Google’s Genius Billboard From 2004 Can Teach Us About Solving Problems