头条新闻

Mathematica 的 Google 天赋

作者：Ed Pegg Jr. 和 Eric W. Weisstein

附加贡献者：Daniel Lichtblau, Adam Strzebonski, Oyvind Tafjord, 和 Michael Trott

10 月 13 日 -- 许多互联网居民都听说过 Sergey Brin，google.com 的技术总裁。他们可能不知道的是，在 1998 年共同创立 Google 的前身并随后成为亿万富翁之前，Brin 曾在（Mathematica 的制造商，也是的赞助商）实习。

广告牌

因此，谷歌利用异常地以数学为导向的招聘技巧可能并不令人惊讶。事实上，在 2004 年 7 月在加利福尼亚州 Ralston 附近的 101 号高速公路南行方向竖立数学广告牌后，这些做法在过去几周和几个月里受到了广泛报道。该广告牌提出了一个问题，即找出数学常数 e（一个超越数，其前几位数字是 2.7182818284....）的连续数字（即十进制展开）中出现的第一个 10 位素数。该广告牌的非同寻常的性质促使包括美国国家公共广播电台、波士顿环球报 和 奥克兰论坛报 以及（当然）互联网在内的众多主流媒体进行了报道。

Ed 于 2004 年 7 月 13 日在他的 MathPuzzle 网站上提到了这个谜题。在发布几分钟后，的 CEO 和 一种新的科学 的作者 Stephen Wolfram 发送了解决方案，只有一行 Mathematica 代码

Select[FromDigits/@Partition[First[RealDigits[E,10,1000]],10,1],PrimeQ,1] {7427466391}

广告牌，第二级

在确定了这个值并将相应的 URL http://7427466391.com 输入到 Web 浏览器后，潜在的 Google 员工（或好奇的新闻故事读者）会被带到一个网页，该网页祝贺他（或她）并提供第二个级别谜题的说明，该谜题涉及找到以下序列的下一个项

f(1)= 7182818284 f(2)= 8182845904 f(3)= 8747135266 f(4)= 7427466391 f(5)= __________

如果前两项看起来很熟悉，那是因为它们是上面给出的 e 的十进制展开的 10 位部分。事实上，稍微额外的分析表明，它们正是那些总和为 49 的 10 位部分。在确定了这一点之后，很容易再次使用 Mathematica 找到下一个数字

FromDigits/@Select[Partition[First[RealDigits[E,10,1000]],10,1],Total[#]==49&,5] {7182818284,8182845904,8747135266,7427466391,5966290435}

这是尼尔·斯隆的 A095926 序列，在 整数序列在线百科全书 中。

虽然我们很可能至少可以继续讨论下去，但我们宁愿在此刻将广告牌谜题的更多级别留给有进取心的读者。

广告牌之子：Google 实验室能力倾向测试

9 月 30 日，Google 炮制了一个更具挑战性的招聘设备：Google 实验室能力倾向测试。该测试的纸质副本也分发给了伊利诺伊大学的学生，在 10 月 12 日的 The Daily Illini 版中。虽然测试中的一些问题更多地与计算机知识和一般创造力有关，但其中许多问题都是高度数学化的。对于这些问题，Mathematica 清楚地表明了其极高的数学才能，可以轻松解决这些问题，尤其是在和其他在线资源（如整数序列在线百科全书）的少量研究指导下。

我们感谢我们以前的实习生为将有趣的数学问题带入新闻中所做的贡献。该测试的 Mathematica 版本，带有答案，可在下面下载。

文件	格式	大小
AptitudeTest.nb	笔记本	92 K

Google 实验室能力倾向测试部分解答

1. 解决这个隐秘方程，当然要意识到 M 和 E 的值可以互换。不允许前导零。

WWWDOT - GOOGLE = DOTCOM

这可以通过系统地应用逻辑来解决。例如，不能等于 0，因为。这将使，但，这是不可能的。

这是一个缓慢的暴力破解方法，在相对快速的机器上需要几分钟

这给出了两个解决方案

777589 - 188106 == 589483
777589 - 188103 == 589486

这是另一个使用 Mathematica 的 Reduce 命令的解决方案

eqn = "wwwdot" - "google""dotcom"/.s_StringFromD ... eqs&&#, vars, Integers] &/@eqs, (Unequal @@ vars/.ToRules[#]) =!= False&]//Timing

一个更快（但稍微更晦涩）的代码如下

$cf = Compile[Evaluate[{#, _Integer} &/@{c, d, e, g, l, m, o, t, w, x}], Module[ {& ... {d, o, t, c, o} . S ; A - B - mC + e&&A - B - eC + m] ] ;$

Transpose[{{c, d, e, g, l, m, o, t, w}, Most[#]}] &/@Module[{perms = Developer`ToPackedArray/@Take[Permutations[Range[0, 9]], All]}, Select[perms, cf @@ #1&]]//Timing

使用相同的方法更快（并且需要约 300 MB 的内存）

Transpose[{{c, d, e, g, l, m, o, t, w}, Most[#]}] &/@Compile[{}, Module[{perms = Take[Perm ... d, o, t, c, o} . S ; A - B - mC + e&&A - B - eC + m]]]]][]//Timing

使用相同的方法甚至更快（不排除解决方案中的前导零，但可以在最后轻松地将其剔除）

$eq = Simplify["wwwdot" - "google" - "dotcom"/.s_StringFr ... ers[s]], 10]] ; Join[CoefficientList[eq, #][[2]] &/@Union[Cases[eq, _Symbol, Infinity]], {0}]$

Transpose[{{c, d, e, g, l, m, o, t, w}, Most[#]}] &/@Compile[{}, Select[Permutations[Range ... , 9]], {-100, -99900, -1, -100100, -10, -1, -21000, -999, 111000, 0} . #0&]][]//Timing

这是一个使用分支和修剪技术的独立解决方案方法

wwwdot = {w, w, w, d, o, t} ; google = {g, o, o, g, l, e} ; dotcom = {d, o, t, c, o, m} ; vars ... en[{eqn, vareqns, zeroOneConstraints, noLeadingZeros, mustSumToOneConstraints, distinctDigits}] ;

$wwwdotgoogledotcom[constraints_, vars_, zeroOneVars_] := Module[{allvars = Join[vars, zeroOneV ... zeroOneVars[[badpos]] 1], stack} ;] ;] ; Sort/@Map[Reverse, solns, {2}] ]$

以及整体最快的获胜者

$enforceUniqueDigits[l_, k_] := If[Length[Union[Take[l, -k]]] =!= k, Sequence @@ {}, l] <br/> ... &/@Select[dgclotem, dotcom[#, 6] + google[#, 6] wwwdot[#, 6] &])//Timing$

2. 写一首俳句来描述预测搜索流量季节性的可能方法。

的搜索引擎
五月似乎变慢了。大学生
为期末考试做准备。

3.       1
         1 1
         2 1
      1 2 1 1
   1 1 1 2 2 1

下一行是什么？

312211. 这是“看和说”序列，其中第一个术语之后的每个术语都描述了前一个术语：一个 1 (11)；两个 1 (21)；一个 2 和一个 1 (1211)；一个 1，一个 2 和两个 1 (111221)；等等。有关完整描述以及称为康威常数的有趣相关量的代数形式，请参阅上的看和说序列条目。

$RunLengthEncode[x_List] := (Through[{First, Length}[#1]] &)/@Split[x] LookAndSay[n_, d_:1] := NestList[Flatten[Reverse/@RunLengthEncode[#]] &, {d}, n - 1]$

4. 你身处一个曲折的小通道迷宫中，所有通道都一样。  这里有一台布满灰尘的笔记本电脑，无线连接很弱。  周围漫步着迟钝、毫无生气的地精。  你会怎么做？

    A) 漫无目的地游荡，撞到障碍物，直到你被格鲁吃掉。
    B) 使用笔记本电脑作为挖掘设备，挖掘到下一层。
    C) 玩 MPoRPG 直到电池没电，你的希望也随之破灭。
    D) 使用计算机绘制迷宫的节点图，并找到出口路径。
    E) 将你的简历通过电子邮件发送给 Google，告诉领头的地精你辞职了，然后发现自己身处一个完全不同的世界 [原文如此]。

一般来说，制作一个状态图。但是，此方法在某些病态情况下不起作用，例如，分形迷宫。有关此示例和评论，请参阅 Ed Pegg 的专栏关于状态图和迷宫。

5. Unix 有什么问题？

它们的繁殖能力。

你将如何修复它？

[此练习留给读者完成。]

6. 在你加入 Google 的第一天，你发现你的隔间同事写了你研究生一年级主要参考书的教科书。你会

    A) 谄媚地奉承，并询问是否可以签名。
    B) 完全静止地坐着，只使用轻柔的按键声，以免打扰她的注意力
    C) 每天从食物箱中给她留下格兰诺拉麦片和英式太妃糖。
    D) 引用你最喜欢的教科书公式，并解释它现在如何成为你的座右铭。
    E) 向她展示如何用少 34 行代码解决示例 17b。

[此练习留给读者完成。]

7. 以下哪项表达了 Google 的总体哲学？

    A) “手气不错”
    B) “不作恶”
    C) “哦，我已经修复了”
    D) “你不应该离食物超过 50 英尺”
    E) 以上所有

[此练习留给读者完成。]

8. 你可以用三种颜色中的一种颜色为二十面体的每个面着色，有多少种不同的方法？

对于不对称的 20 面体，有种可能的 3 着色。对于对称的 20 面体，可以使用 Pólya 枚举定理来获得不同着色的数量。这是一个简洁的 Mathematica 实现

Off[General :: "shdw", General :: "spell1"] <<DiscreteMath`Combinato ... GroupFaces = KSubsetGroup[GroupI, Sort/@f] ; Polya[GroupFaces, colors] ]

你会选择什么颜色？

[此练习留给读者完成。]

9. 此处有意留空。请用一些可以改善空虚感的东西填充它。

有关近 10,000 个数学函数的图像，请参阅 Wolfram 函数站点可视化画廊。

10. 在无限的二维 1 欧姆电阻矩形晶格上，相隔骑士步的两节点之间的电阻是多少？

$R[m_, n_] := 1/(2π) Integrate[1/t (1 - ((t - I)/(t + I))^(m + n) ((t - 1)/(t + 1))^Abs[m - n]), {t, 0, ∞}]$

J. Cserti 1999 年的 arXiv 预印本中讨论了这个问题。 Michael Trott 的 GuideBook 系列的第四卷（即将出版的 The Mathematica GuideBook for Symbolics）中也讨论了这个问题，该系列的前两卷刚刚在上周由 Springer-Verlag 出版。所有四个 GuideBook 的内容，包括尚未出版的两本，都可以在与前两本 GuideBook 一起分发的 DVD 上找到。

11. 现在是湾区阳光明媚的星期日下午 2 点。你距离太平洋、红杉森林远足径和世界一流的文化景点只有几分钟的路程。你做什么？

[此练习留给读者完成。]

12. 你认为有史以来最美丽的数学方程式是什么？

显然有很多候选者。以下列表给出了作者最喜欢的十个

1. 阿基米德递推公式: , , ,
2. 欧拉公式:
3. 欧拉-马歇罗尼常数:
4. 黎曼猜想: 和意味着
5. 高斯积分:
6. 拉马努金素数积公式:
7. Zeta 正则化积:
8. 曼德勃罗集递归:
9. BBP 公式:
10. 柯西积分公式:

Daniel Z. Freedman 的“数学物理学中的一些美丽方程”是一篇讨论物理学中最美丽方程的优秀论文。请注意，物理学对方程之美的看法不如数学统一。引用理论物理学家 P.A.M. Dirac 的非标准观点：“方程中拥有美比让它们符合实验更重要。”

13. 以下哪项不是 Google 员工组成的真实兴趣小组？

    A. 女子篮球
    B. Buffy 粉丝
    C. 板球运动员
    D. 诺贝尔奖获得者
    E. 葡萄酒俱乐部

[此练习留给读者完成。]

14. 搜索技术的下一个重大改进将是什么？

数学公式的语义搜索。请参阅 https://functions.wolfram.com/About/ourvision.html，了解目前正在进行的工作，该工作将在不久的将来提供。

15. 项目团队的最佳规模是多少？超过这个规模，额外的成员对生产力的贡献就不等于员工人数增加的百分比？

    A) 1
    B) 3
    C) 5
    D) 11
    E) 24

[此练习留给读者完成。]

16. 给定一个三角形 ABC，你将如何仅使用圆规和直尺找到一个点 P，使得三角形 ABP、ACP 和 BCP 具有相等的周长？（假设已构建 ABC 以便存在解决方案。）

这是等周点，它位于较大的索迪圆的中心。它与阿波罗尼斯问题相关。三个相切圆很容易构造：围绕的圆的直径为，这给出了另外两个圆。 David Gisch 和 Jason M. Ribando 在 “阿波罗尼斯问题：解决方案及其联系的研究” 中可以找到外索迪圆的圆规和直尺构造的摘要。

17. 考虑一个函数，对于给定的整数 n，该函数返回写出 0 到 n 之间的所有数字时所需的 1 的数量。例如，f(13)=6。请注意，f(1)=1。下一个最大的 n 是多少，使得 f(n)=n？

以下 Mathematica 代码计算了 [高达 n 的正整数中 1 的累积数] 与 [ n 本身的值] 之间的差值，当 n 从 1 到 500,000 变化时

[Graphics:HTMLFiles/AptitudeTest_58.gif]

然后，该问题的解是第一个位置（大于第一个位置），在该位置 data 等于 0

这些是整数序列在线百科全书中的序列 A014778 的前几个项。

手动检查证实，从 1 到 199981 的数字总共包含 199981 个 1

18. 你写过的最酷的黑客程序是什么？

虽然没有“正确”答案，但解决 SIAM 百元百位数挑战中第一个问题的漂亮黑客程序可以通过将极限转换为强发散级数来实现

$Sum[(-1)^k (2k)^(2k - 1), {k, ∞}]$

然后使用 Mathematica 的数值函数 SequenceLimit 可以轻松获得正确的答案（精确到六位数字），

$Off[SequenceLimit :: "seqlim"] SequenceLimit[FoldList[Plus, 0, N[#, 1000] & @ Table[-(-1)^k (2k)^(2k - 1), {k, 300}]], WynnDegree20]$

你必须稍微调整参数或编写自己的序列限制才能获得所有 10 位数字。

[其他黑客程序留给读者完成。]

19. 众所周知，在精致的公司中，从 N 件物品中选择 K 件物品的方法与从 N 件物品中选择 N 减 K 件物品的方法一样多：我选择 K 件，你选择剩下的。

这只是简单地陈述了二项式系数恒等式。

但是，找到一个更酷的双射，在那里你展示了令人难以置信的诀窍，使你的选择包含我的所有 K 个选择。哦，为了卖弄学问：让 K 不超过 N 的一半。

从这段特殊的措辞中理清精确的语义含义更加成问题。

20. 序列中下一个数字是什么：10, 9, 60, 90, 70, 66, ?

    A) 96
    B) 1000000000000000000000000000000000\
         0000000000000000000000000000000000\
         000000000000000000000000000000000
    C) 以上任一
    D) 以上都不是

可以查找它，并发现它是整数序列在线百科全书中的序列 A052196，它给出了英文名称具有 n 个字母的最大正整数。例如，前几个术语是 ten、nine、sixty、ninety、seventy、sixty-six、ninety-six、…。更正确的序列可能是 ten、nine、sixty、googol、seventy、sixty-six、ninety-six、googolplex。并且还要顺便注意，数学术语“googol”的正确拼写与制定此能力倾向测试的公司的名称不同。

可以使用 Eric Weisstein 的包中的 NumberName 函数计算前几个