第 48 個梅森質數確認

在「Great Internet Mersenne Prime Search - PrimeNet」這邊看到 GIMPS 確認了 M_{57885161} (也就是 2^{57885161}-1) 是第 48 個梅森質數:

All tests smaller than the 48th Mersenne Prime, M(57885161), have been verified

第 47 個梅森質數是 M_{43112609},但一直都沒有確認完到 M_{57885161} 中間是否還有梅森質數,這次宣佈全部都算完,而且雙重確認過,所以可以確認第 48 個梅森質數。

下一個要確認的是第 49 個梅森質數,目前已知的下一個是 M_{74207281},也就是要看到 M_{74207281} 中間是否還有其他的梅森質數...

各種反直覺的項目

前陣子看到「The most counterintuitive facts in all of mathematics, computer science, and physics」這篇,講各種反直覺的項目,有空的時候拉一兩個來讀還蠻有趣的...

第一個提到的是 Homomorphic encryption。在密碼學的保護概念中,密文是不能被操作的,但我們可以透過重新設計密碼學系統,讓密文可以被運算:

1. It is possible to compute over encrypted data without access to the secret key: https://en.wikipedia.org/wiki/Homomorphic_encryption

2009 年的時候第一個 FHE (fully homomorphic encryption) 演算法被提出來後就被大量討論,這代表你可以把資料加密後丟上雲端,利用雲端的大量運算資源運算完後,再把資料拉回地端解密,得到運算後的結果。這算是 Lattice-based cryptography 的一個很重大的應用。

其他的主題也蠻有趣的,先丟著找機會翻...

在 Hacker News 上看到選擇公理

沒想到會在 Hacker News 的首頁上看到這麼硬核的主題,選擇公理 (Axiom of choice,通常縮寫成 AC):「What is the Axiom of Choice?」,對應的討論在「What is the Axiom of Choice? (jaydaigle.net)」。

出自「xkcd: Set Theory

應該是大一教集合論的時候學到的,算是一個非常重要的公設,雖然的確有些數學系統是可以假定 AC 不成立,但用起來會不太好用,主要是因為「對於集合 S,取出任意一個元素」這類用法太常出現,在沒有 AC 的情況下這件事情就不一定能操作了...

我們目前常用的數學一般是建立在 Zermelo-Fraenkel Set Theory (ZF) 這個公理系統加上 AC,簡寫變成 ZFC。而 AC 在集合論常常會被拿出來說明,主要還是因為在歷史上花了不少力氣才證明 ZF 與 AC 的相對協調性 (ZF 與 AC 不衝突),以及 ZF 與 AC 獨立性 (ZF 無法推導出 AC)。

有了 AC 後就會再解釋連續統假設 (Continuum hypothesis,簡稱 CH),也就是 \mathbb{N}2^{\mathbb{N}} 之間存不存在一個集合 S 使得 |\mathbb{N}| < |S| < |2^{\mathbb{N}}|

然後再打臉一次,說明 ZFC 與 CH 的協調性 (ZFC 與 CH 不衝突),與獨立性 (ZFC 無法推導出 CH)。

當時學的時候的確是很頭痛,不過現在回頭看倒是覺得很有趣:在數學上你可以證明「某個敘述無法被證明」,這點應該是以前沒想過的...

證明圓周率 π 是無理數

前陣子在 Michael Penn 教授的 YouTube 頻道上看到的證明:

這個證明方式在其他人的 YouTube 頻道也有做過,像是 MindYourDecisions 在 2019/3/14 (Pi Day) 發表的影片:

這兩篇使用的方法是 Ivan M. Niven 在 1946 年提出來的方法 (發表在 1947 年 AMS 的期刊,第 53 期的 Bulletin of the American Mathematical Society 上):「A simple proof that π is irrational」。

先不討論證明方法本身,我把這份 PDF 印出來慢慢看,當年用打字機打的字型讀起來超有味道的... (這份 PDF 看起來是掃描檔)

從 PDF 可以看出證明超級短,只有一頁,但畢竟這是大師丟出來的證明,裡面其實省了很多步驟。這接步驟不難推導,但是是屬於考試作答時不能省略的部份,如果加上去的話應該會兩到三頁 (還是非常短)。

整個證明的過程很巧妙的設計了兩個函數搭配反證法。裡面有用到微積分,但只用到最基本的微積分,其中微分的部份用到的公式就這三個,其中是三角函數的微分公式:

\frac{d}{dx} sin(x) = cos(x)\newline\newline\frac{d}{dx} cos(x) = -sin(x)

然後是兩個函數相乘後的微分公式:

\frac{d}{dx} f(x)g(x) = f'(x)g(x) + f(x)g'(x)

積分的部份只用了定義的部份 (主要是在微分的部份證完)。

然後證明是圍繞在「整數」上面做文章,夾擠出一個不可能的情況,因此得到矛盾,證明了 π 是無理數。

整個證明可以在高三範圍 (如果現在高三還有教微積分的話) 或是大一教過微積分之後的程度證完,作者講的 "Simple" 主要是出自這邊...

四個機率問題

在「Some Useful Probability Facts for Systems Programming」這邊看到的四個機率問題,而且都有接近解:

  • 每一次有 \frac{1}{N} 成功的機率,跑 N 次後最少成功一次的機率。
  • N 個球隨機丟到 N 個籃子後有空籃子的機率。
  • N 個數字在隨機排序後有數字不改變位置的機率。
  • N 種 coupon 平均隨機出現,要抽中一套 N 種都有的 coupon 需要抽幾次的期望值。

會想要寫這篇是因為發現最後一題就是「大人買」抽卡問題的簡化版本 (這邊簡化成機率相同,一般的情境下應該是不同的)。

可以看到歐拉常數 e 與自然對數 \ln{} (i.e. 以 e 為底的對數) 滿天飛 XDDD

用程式解數學邏輯問題...

Hacker News Daily 上看到的數學邏輯問題:「“Which answer in this list is the correct answer to this question?”」。

問題是這樣:

Which answer in this list is the correct answer to this question?

  • All of the below.
  • None of the below.
  • All of the above.
  • One of the above.
  • None of the above.
  • None of the above.

accepted 的那個是推演的答案,但最高分的那個是寫程式窮舉 XDDD (不得不說大家都很愛這味...)

Miles 換算 KM 的方式

Twitter 上看到很有趣的方式:

這邊可以這樣算是因為 1.609 跟黃金比率很接近,而 Fibonacci number 的也有黃金比率的特性,所以可以直接拿來用...

二戰時德國坦克製造速度的估算問題

看到「The German Tank Problem」這篇在講二戰很有名的統計應用。這個主題在中文的維基百科寫得還蠻完整的,讀起來應該會更快一些:「德國坦克問題」:

在統計學理論的估計中,用不放回抽樣來估計離散型均勻分布最大值問題中著名的德國坦克問題(英語:German tank problem),它因在第二次世界大戰中用於估計德國坦克數量而得名。

如同上面所說的,這個方法是因為估算的準確度極高而知名:

對坦克車輪的分析產生了對使用中的車輪模具數量的估計。在與英國車輪製造商討論過後,他們估計了這麼多的模具可以生產多少車輪,進而是每個月可生產的坦克數量。對兩輛坦克(每輛32個車輪,總計64個車輪)車輪的分析的結果是1944年2月的生產數量估計在270左右,大大超出此前預期。

德國戰後公布的記錄顯示,1944年2月一個月的生產量是276輛。統計方法結果的精確度是常規情報收集方法所遠遠不能達到的,而「德國坦克問題」這個詞也成為了這種統計分析問題的標誌。

而且之後被拿來推敲經典的 Commodore 64 的數量也還蠻準的:

該公式在非軍事中也有使用,如估計Commodore 64計算機的總數,其結果(1.25億)與官方數字相當匹配。

打數學式子的工具

看到 Mathcha 這個網站,除了可以輸入 TeX 的公式外,也有 WYSIWYG 的方式輸入,而最後可以輸出成各種格式 (包括 TeX),或是直接丟連結給其他人:

輸入的部份,對於不知道的符號葉可以用畫的 XD

然後網站上的標示寫沒有支援 IE 與 Edge,不知道是真得不支援還是沒列上去而已... XD

計算圓周率 Pi 的公式...

Twitter 上看到這個:

利用這個公式 (Bailey–Borwein–Plouffe formula),可以直接對二進位 (四進位、八進位、十六進位、...) 直接計算出某個位數的值...