[翻譯][UVa][10738] Riemann vs Mertens

翻譯, UVa/ACM 本文总阅读量次

數學界中，黎曼假設 (Riemann Hypothesis)被數學家們稱之為最大為解決的難題之一：「對於所有黎曼 ζ 函數 (zeta function) 中非平凡零點 (non-trivial zeros) 的實數部分是二分之一。」那麼現在給你一個很簡單的題目：對於每個正整數 N，請輸出第 N 個零點 … 呵，開玩笑的！這樣子這道題目會變得太複雜，我們可以選擇計算比較簡單而且跟黎曼函數相關的梅登函數 (Mertens’s function)。如果有興趣想要知道的話，請參閱 Derbyshire 的書 (見後記)。

對於每個大於 1 的正整數，我們可以把它質因數分解。有些數字像 2、7、11 等只有一個因數的數，我們稱它為質數 (prime numbers)。其他數字像 4 (2×2)、15 (3×5)、144 (2^4×3^2) 我們稱它為合數 (composite numbers)。如果一個數的每個質因數都只有一個，我們稱它為 square free，有些合數像 21 (3×7)、187 (11×17) 就是 square free，而有些合數像 9 (3^2)、98 (2×7^2) 則不是。

於是我們先定義默比烏斯函數 (Möbius function) 為 mu(N)，對於每個正整數 N：

  • 定義 mu(N) = 1；
  • 如果 N 不是 square free，那 mu(N) = 0；
  • 如果 N 是 square free，而且它有偶數個質因數，那麼 mu(N) = 1；
  • 如果 N 是 square free且有奇數個質因數，那麼 mu(N) = -1。

接著，我們可以定義梅登函數 (Mertens’s function) M(N)為默比烏斯函數從 1 到 N 的級數和：
M(N) = mu(1) + mu(2) + … + mu(N)。

下列為前 20 個默比烏斯函數及梅登函數的值：

N 質因數 mu(N) M(N)
1 - 1 1
2 2 -1 0
3 3 -1 -1
4 2 2 0 -1
5 5 -1 -2
6 2 3 1 -1
7 7 -1 -2
8 2 2 2 0 -2
9 3 3 0 -2
10 2 5 1 -1
11 11 -1 -2
12 2 2 3 0 -2
13 13 -1 -3
14 2 7 1 -2
15 3 5 1 -1
16 2 2 2 2 0 -1
17 17 -1 -2
18 2 3 3 0 -2
19 19 -1 -3
20 2 2 5 0 -3

請求出對於一正整數 N 的 mu(N) 和 M(N)。

輸入

輸入每行包括一個正整數 N (N 介於 1 至 1000000)。輸入測資以 0 作為結束，這行不需被處理。

輸出

對於每個正整數 N，請依序輸出 N、mu(N)、M(N)在一行，每個輸出數字的寬度為 8。

範例輸入

1
2
3
4
5
20
1
144
73
0

範例輸出

1
2
3
4
5
6
      20       0      -3
       1       1       1
     144       0      -1
      73      -1      -4
`

後記 (不影響解題)

一個 ζ 函數 (zeta function) 可以被定義成下面的無窮級數：
zeta(s) = 1 + 2^(-s) + 3^(-s) + 4^(-s) + ……

其中s為任意複數。

ζ 函數擁有許多零點 (zeros) (註：零點代表 zeta(s) = 0)，其中有些為非平凡零點 (non-trivial ones)，黎曼在 1859 年臆測這些非平凡零點的實部恆為二分之一，而虛部可為任意值。到目前為止，許多非平凡零點都被找到，可是沒有一個人能夠證明 (或否定) 黎曼的假設是否是對的。這個著名的黎曼假設在數學上的各個領域都有其延伸定理，這些定理都是根據黎曼假設為真的情況下成立，所以如果有人能夠證明黎曼假設是錯的 (一個反例就夠了)，那麼現代數學也會因此而崩潰！

有一個方法可以證明黎曼猜想，那就是從梅登函數的定義 (Mertens’s function)，我們可以證明梅登函數與 N 的平方高度相關：M(N) = O(N^(1/2))

其中 O 代表大 O 符號 (big-oh notation)，意思是當 N 極大時，M(N)的絕對值會相當接近而不超過 N^(1/2) (譯者註：漸近)。雖然這項定理尚未證明，但如果這項定理是對的，那麼黎曼假設也會是對的 (不要問我為什麼)。

欲知更多詳情，請參閱 John Derbyshire 所著的「Prime Obsession」這本書。

翻譯, UVa/ACM