頭條新聞

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 函式計算前幾個