【附開源碼】集結 40 萬台電腦算力,數學家算出 x³+y³+z³=3 的第三組整數解

sums-of-three-cubes

【我們為什麼挑選這篇文章】三立方數和始終是困擾數學界的難題之一,前年(2019 年)數學家利用電腦算力終於解出 x³+y³+z³=33、 x³+y³+z³=42 這兩個 1 到 100 間遲遲未解的題目,而近日數學家破解了  x³+y³+z³=3 的第三組解,怎麼做到的?會有第四組解出現嗎?(責任編輯:賴佩萱)

本文經 AI 新媒體量子位(公眾號 ID:QbitAI)授權轉載,轉載請連繫出處
作者:量子位

你在看到標題的時候,一定會想:

這個問題我知道答案:x、y、z 都等於 1。

如果再多算幾步,你還能發現 4、4、-5 也是一組整數解。

注意審題,以上只是方程 x³+y³+z³=3 的前兩組整數解,第 3 組整數解是多少,你知道嗎?

1953 年,數學家 Louis Mordell 提出一個疑問:這個第 3 組整數解,它存在嗎?

最近,這組解終於被找到了。

警告一下,千萬別嘗試用窮舉法編程!

因為這 3 個數遠遠超出了長整型的範圍,但數學家還是動用了 40 萬台電腦把答案找出來了。

另外,這兩位數學家還把程式碼開源了。

開源碼 GitHub 傳送門

當然,他們並非暴力搜索。這時候數學的作用就來了:它能為你提供算法,告訴你搜索範圍,大大縮小搜索空間。

一個關於正整數表示成三整數立方和的假設

一個正整數能否表示成三個整數的立方之和(x³+y³+z³=k),關於它的每次發現都能引起不小的轟動。

這個看似沒技術含量的問題,其實困擾了數學界很久。

1992 年,數學家 Roger Heath-Brown 提出了一個猜想:對於一個正整數 k,如果它除以 9 的餘數不是 4 或 5(k 不等於 9n±4),那麼 k 就可以表示成三個整數的立方之和

而且每個 k 都有無窮多組整數解。

對於 k 小於 100 的情況,2019 年之前只有 k=33、42 沒有找到整數解。

2019 年 3 月,33 告破:

33 = 8866128975287528³ + (-8778405442862239)³ + (-2736111468807040)³

2019 年 9 月,麻省理工的 Andrew Sutherland 和布里斯託大學 Andrew Booker 的兩位安德魯找到了 42 的答案:

42 = (-80538738812075974)³ + 80435758145817515³ + 12602123297335631³

當時,菲爾茲獎得主、劍橋大學教授 Timothy Gowers 還轉推「祝賀」。

TO 相關文章>>>集結 50 萬台電腦算力,數學家終於破解困擾 65 年的難題:三立方數和

雖然 100 以內的數皆告破,但幾十年間卻沒有關於 k=3 的新解,許多人開始相信這個所謂的新解根本不存在,Heath-Brown 猜想也是錯的。

但是,在找到 42 的答案之後,這兩位安德魯很快就出乎意料找到了 k=3 的第三組整數解:

3 = 569936821221962380720³ + (-569936821113563493509)³ + (-472715493453327032)³

怎麼解出來的?從簡化公式開始

為了找到 42 和 3 的解決方案,兩位數學家從現有算法開始,將立方和公式轉化為他們認為更容易求解的形式:

他們將 x+y 看做一個參數 d,進一步修改了算法,然後將兩邊都除以 d 求餘數(數學中記作 mod d)

這樣問題就變成 k 除以 d 的餘數是 z³。

這樣,只需尋找 d 和 z 的值,即可保證找到對應於 k=3 的 x、y、z。

即便如此,搜索的數字空間也是無限大的。因此,他們通過使用數論中的「篩法」,極大地減少了 d 範圍,將 xyz 的搜索範圍降到 10 的 15 次方以內。

任務太龐大,耗上 40 萬台電腦一起解題

兩位安德魯還開發了將搜索演算法拆分成幾十萬個並行處理流的方法。

如果僅在一台電腦上運行該演算法,則要花幾百年的時間才能找到答案。而透過將工作分為幾十萬個較小的任務,就可以在個人電腦上運行,進一步加快搜索速度。

在 2019 年 9 月,研究人員通過 Charity Engine 實施了這項計劃,借用普通用戶的家用電腦資源,共同解決難題。

當時,全球加入 Charity Engine 分佈式計算項目的電腦超過 40 萬台。兩位安德魯將他們的演算法部署在平台上。

(注:Charity Engine 專案還幫助科學家解決了一個蛋白質折疊問題,發了一篇 Science。)

最終,這項工作被分為大約 40 萬個任務,每個任務需要一台電腦花費大約 3 個小時才能完成。

很快,全球各地的電腦返回的 k=42 的第一個整數解。

而僅僅兩週後,他們已經發現,k=3 的第 3 個整數解就找到了,他們還把這組解印在了 T 恤上。

至此,Mordell 在 68 年前的問題終於得到解答。

那麼問題又來了 x³+y³+z³=3 的第 4 組解是多少?

可能有生之年很難見到了,因為求下一組解需要的計算量是現在的 1000 萬倍,需要 4 萬億台電腦才能算出,而且可能還不夠。

論文作者之一 Andrew Sutherland

Sutherland 說:「我不知道我們是否會知道第四個解,但是我確信它存在。」

參考資料

phys.org》、《pnas.org》、《GitHub

(本文經 AI 新媒體量子位 授權轉載,並同意 TechOrange 編寫導讀與修訂標題,原文標題為 〈x³+y³+z³=3 第三組整數解是多少?這個 58 年難題被 40 萬台電腦算出來了 〉;首圖來源:piqsels。)

你可能會有興趣


點關鍵字看更多相關文章: