Category 數學

《魷魚遊戲》中的無限遞迴

《魷魚遊戲2》中有這麼一幕:男主角知道三角形圖案的椪糖最簡單,胸有成竹地挑了之後,打開卻發現是極為複雜的三角形圖案。 這個圖案可不是製作單位隨便弄的,而是有所本,稱為「謝爾賓斯基三角形」,由波蘭數學家謝爾賓斯基(Wacław Sierpinski)在1915年所提出。產生這個複雜圖案的規則很簡單: 1. 畫一個正三角形; 2. 將三個邊的中點連起來,便將原來的三角形等分成四個正三角形; 3. 去除中間的三角形,針對其餘三個三角形重複步驟二到三,如此不斷往下。 這種經由簡單的方程式或演算法無限迭代,而不斷產生自我相似性的幾何圖形,便稱為「碎形」(fractal)。以謝爾賓斯基三角形來說,把再小的局部放大,都會和整體一模一樣(註)。 《魷魚遊戲》特地選用謝爾賓斯基三角形這個圖案,讓我不禁懷疑其實是有象徵意義的。還記得我之前寫過《魷魚遊戲》中的樓梯和荷蘭版畫家艾雪的關係嗎?當時我覺得是出自於〈相對論〉(Relativity)這幅版畫,但如今想來,應該是呼應艾雪的另一幅作品〈上下階梯〉(Ascending and Descending)。 〈上下階梯〉是艾雪根據英國數學家潘洛斯(Penrose)父子構想的「潘洛斯階梯」繪製而成。畫中一群僧侶(《魷魚遊戲》中的警衛穿著和他們簡直一模一樣)在構成迴圈的四座樓梯上行走,一隊順時針往上走,另一隊逆時針往下走。雖然他們以為自己不停地往上或往下走,但其實哪裡都到達不了,只是在原地繞圈圈。謝爾賓斯基三角形也是如此,你可以不斷延伸下去,但無論停在何處,都和原來一模一樣。 我認為這就是《魷魚遊戲》這兩個美術設計的背後意涵。就參賽者而言,你以為自己最後可以抵達終點,但其實到不了目的地,永遠困在爾虞我詐的輪迴中。而就魷魚遊戲本身而言,也是沒有終止的一天,因為這一場結束,總會又有另一批參賽者跳進來這個貪婪遊戲,無限延續,不會改變。 我不確定自己有沒有過度解讀,無論如何,可以從《魷魚遊戲》這部全球矚目的節目聯結到背後的數學,不是很有趣嗎? 註:有些碎形則是每次迭代所產生的圖形乍看相似,但並不完全一樣;其中又以波蘭裔的美國數學家曼德布洛(Benoit Mandelbrot),於1970年代所提出的曼德布洛集合最具代表性。 他將簡單的函數每次迭代所得出的解,對應到複數平面上(橫軸是實數,縱軸是虛數),以電腦繪圖不斷地放大更小的局部,呈現出自我相似卻又略有變化的繁複圖案,令人目眩神迷。 這不僅是數學遊戲而已,曼德布洛指出自然界處處可見碎形,例如地理樣貌、人體血管,甚至人類活動如股市線圖也是一種碎形。為什麼隨機的事件最後竟會累積成似乎存在某種規則的碎形?這過程和混沌系統有高度關聯,如今碎形和混沌理論已被應用於各種領域。

從質數到二進位計算機——萊布尼茲的創見

1676年底,三十而立的萊布尼茲離開待了四年的巴黎,返回德國。在巴黎期間,他已構思出微積分此一全新的數學方法,卻沒有公開對外發表,回國後他仍將之暫擱一旁,反而研究起質數來了。 他先在1678年2月發表一篇論文,指出任何大於5的質數減去1或5,一定能被6整除(這也可以表述成「任何大於3的質數都可以寫成6k ± 1」的形式)。隨後他又試圖證明費馬小定理,這是費馬於1640年提出的猜想: 若p為質數,a是小於p的正整數,則 aᴾ⁻¹- 1一定能被p整除。 (例如 p=7, a=2,則2⁷⁻¹ – 1 = 63 是 7 的倍數。) 倘若這真的成立,便能用來判斷一個數有沒有可能是質數。當萊布尼茲從a=2開始,也就是2ⁿ– 1這種所謂的梅森數(Mersenne number)研究起時,他注意到若是用二進位表示,梅森數依序便是1、11、111、1111、……,完全不用像十進位制那樣計算,就能直接寫出來。 接著他發現二進位也很適合用於表示完美數(perfect number)。如果一個數的真因數加總起來恰好等於它本身,例如6 = 1 + 2 + 3 或 28 = 1 +2 + 4 + 7 + 14,便稱為完美數。而歐幾里得早就證明: 若2ⁿ–…

每個孤獨的梅森質數,都伴隨一個完美的數

質數是孤獨的,它的因數就只有1和它自己,不像6還有2和3,15還有3和5,但質數卻再也沒有其它因數,就像一個沒有任何朋友的小孩,只能抱著1這個布娃娃,自己玩耍。 2p-1這種形式的梅森質數當然也是如此。不過,如果把-1挪個位置,移到指數p的後面,再和自己相乘的話,奇蹟就出現了:2p-1 x (2p-1) 會是個完美的數字(perfect number)。 什麼是完美數(也譯為完全數或完備數)?這是種很特別的自然數,它所有的真因數(即除了自身以外的因數)加起來,恰恰等於它本身。例如6的真因數有1、2、3,而1 + 2 + 3 = 6。 完美數很稀少,比日本壓縮機,比質數還稀少。第二個完美數是28(= 1 + 2 + 4 + 7 + 14),下一個是496,再來是8128,第五個就跳到8位數,到了第十個已經有54位數了。 早在西元前三百年左右,歐幾里得就證明當2p-1是質數時,2p-1 x (2p-1) 一定是完美數,例如前四個梅森質數便分別對應到前四個完美數: P = 2 ➡︎ 21(22-1) = 2 x 3 = 6 P =…

不發一語卻滿堂喝采的數學演講

上一篇〈追尋更大的質數〉提到法國神父梅森在1644年提出一系列質數,認為將它們代入Mₚ = 2ᵖ-1,所得出的答案也是質數,結果其中有些數字他搞錯了,例如1876年法國數學家盧卡斯便證明了M₆₇不是質數。 既然M₆₇是合數,那麼它的因數是什麼?盧卡斯並沒有找出來,畢竟要靠紙筆做21位數的因數分解實在太耗費時間了。 1903年10月31日,美國數學學會舉辦的研討會中,有一場是由42歲的美國數學家寇爾(Frank N. Cole)主講。寇爾20年前曾赴德國,接受著名的數學家克萊茵(Felix Klein)指導,返美後先後在哈佛大學、密西根大學、哥倫比亞大學任教,自1896年起還兼任美國數學學會秘書長。 這場演講的主持人簡單說完引言,介紹寇爾上台後,只見他走到黑板的一邊,什麼都沒說就拿起粉筆,逐步計算2⁶⁷-1的值,最後得出: 147 573 952 589 676 412 927 接著他走到黑板另一邊,寫上: 193 707 721 x 761 838 257 287 = 然後算起這兩個數字的相乘,結果等於: 147 573 952 589 676 412 927 正是黑板左邊的數字。 寇爾寫完後仍一句話都沒說,放下粉筆就回到自己的座位。台下聽眾隨即爆出熱烈掌聲,並紛紛起立致意,因為他們終於目睹了M₆₇的因數,而這成果背後不知要投入多少心血。 的確,後來寇爾表示共花了他三年的每個星期天。而這場史無前例、全程近一小時完全不發一語的「演講」,也成為數學史上的一個傳奇。 參考資料:

追尋更大的質數

很多人應該知道幾天前這則新聞了:一位前NVIDIA工程師發現迄今所知最大質數: 2136279841-1 它共有41,024,320 位數,如果比照之前有本印出π的前100萬位數的書,每頁1萬個數字的話,那麼這個質數可以印成41冊。 前一個最大質數是2018年發現的282589933-1,「只能」印成25冊,再前一個則是2017年發現的277232917-1,兩者相差160萬位數,這次一下子多了1,600萬位數,無疑是很大的躍進。 梅森質數 你或許有注意到這幾個質數都是2n-1的形式(而且n都是質數),難道質數都長這樣嗎?當然不是,不過目前所發現特別大的質數,很多都是如此。這最早是17世紀的法國神父梅森(Marin Mersenne)所提出,因此2p-1(p代表質數)這種形式的質數便稱為「梅森質數」。他在1644年列出下列幾個數字: 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 認為將它們代入Mp = 2p-1,得出的都會是質數(M2=3, M3=7, M5=31,……)。 當時只知道到19都是質數無誤,但31之後就是梅森自己的猜測了,結果直到1772年,大數學家歐拉才證明M31是質數,然後再過一百年,M127才被證明是質數。至於M67和M257,梅森猜錯了,它們並非質數,另一方面,他反而漏掉了61, 89, 107這幾個會得出梅森質數的數字。 當數字越來越大時,要驗證是否為質數就是這麼困難,尤其是在只能用紙筆計算的年代。法國數學家盧卡斯(Édouard Lucas)於1857年,以15歲之齡發明一種較快速的檢驗法,不需一一試除質因數,仍然花了19年的時間才證明有39位數的M127是質數。若繼續靠人工計算,可能窮極一生也找不到更大的質數,想要再有所突破,只能等待電腦出現了。 電腦驗算 二次大戰後,英美紛紛開發基於馮紐曼架構的可程式化數位電腦,英國曼徹斯特大學的「曼徹斯特一號」也是其中之一。負責開發測試程式的圖靈便在1949年中寫了一支程式,用來逐一驗算梅森質數,不過受限於曼徹斯特一號的硬體規格,在發現更大的質數之前便終止測試了。 雖然圖靈的程式未發現新的質數,卻從此開啟了用電腦尋找質數的時代。1951年,劍橋大學用EDSAC電腦發現180×(M127)2+1 也是質數。第二年,美國數學家羅賓遜(Raphael Robinson)用國家標準局的電腦,在一年內就發現五個梅森質數:M521、M607、M1279、M2203、M2281,並證明到22303-1為止,再無其它梅森質數。 隨著電腦運算能力的提升,更多質數陸續被找到,但隨著數字越來越大,質數也越來越稀少,到了1994年,也不過又多發現17個更大的質數(其中16個是梅森質數)。有鑒於此,美國電腦科學家沃特曼(George Woltman)於1996年初發起「網際網路梅森質數大搜尋」(Great Internet Mersenne Prime Search,簡稱GIMPS)計畫,讓有興趣的人下載程式到個人電腦,集群體之力一起驗算梅森質數。…