the formula for n-th prime

💡

Trước khi đọc đến paper vô cùng thú vị này, mình vẫn đinh ninh tin rằng không hề tồn tại một công thức toán học để tính ra giá trị của số nguyên tố thứ n bất kỳ và các hiểu biết của con người về số nguyên tố còn rất sơ khai với rào cản của giả thuyết Riemann…

Năm 1964, C.P. Willans đã đưa ra công thức để tính giá trị số nguyên tố thứ $n$ như sau:

$$p_n = 1+ \sum_{m=1}^{2^n}\left \lfloor \sqrt[n]{\frac n { \sum_{j=1}^m \left \lfloor \left(\cos \pi \frac {(j-1)! + 1} j \right)^2 \right \rfloor} }\right \rfloor$$

Với:

$p_n$ là số nguyên tố thứ $n$. Ví dụ: $p_1 = 2, p_2 = 3, \dots$
$\lfloor x \rfloor$là giá trị làm tròn dưới của $x$. Ví dụ: $\lfloor 1.23 \rfloor = 1, \lfloor \pi \rfloor = 3$

💡

Thực ra, công thức này không có nhiều giá trị thực tiễn vì độ phức tạp tính toán quá nặng, không hợp lý. Tuy nhiên, mình muốn giới thiệu đến các bạn cách tác giả xây dựng lên công thức này vì nó chứa đựng rất nhiều sự xử lý vô cùng tinh tế.

Định lý Wilson

Cho $p \in \mathbb N, p>1$ khi đó $p$ là số nguyên tố khi và chỉ khi $(p-1)! + 1 $ chia hết cho $p$.

Mình không chứng minh định lý này, các bạn có thể tham khảo chứng minh định lý này ở wiki.

Xét $\sum_{j=1}^m \lfloor (\cos \pi \frac {(j-1)! + 1} j)^2 \rfloor$

Theo định lý Wilson, ta có $\frac {(j-1)! + 1} j$ là số nguyên khi vào chỉ khi $j=1$ hoặc $j$ là số nguyên tố. Tạm đặt $F(x) = \frac {(x-1)! + 1} x$, ta có $-1 \le \cos \pi F(x) \le 1$, dấu $=$ xảy ra khi $F(x)$ là số nguyên vì thế khi $x = 1$ hoặc $x$ là số nguyên tố thì $(\cos \pi F(x))^2 = 1$, ngược lại $(\cos \pi F(x))^2 =0$.

Từ đó ta suy ra $\sum_{j=1}^m \lfloor (\cos \pi \frac {(j-1)! + 1} j)^2 \rfloor$ thực chất là một hàm số để đếm số các số nguyên tố nhỏ hơn hoặc bằng $m$. Đặt:

$$\pi(m) = \sum_{j=1}^m \lfloor (\cos \pi \frac {(j-1)! + 1} j)^2 \rfloor$$

Ta có vài nhận xét sau:

$n = \pi(p_n)$
$\pi(m) \lt n$ khi $m < p_n$ và
$\pi(m) \ge n$ khi $m \ge p_n$

Từ đây ta lại có thêm một nhận xét nữa đó là số lượng cái giá trị của $m$ sao cho $\pi(m) \lt n$ là $p_n -1$. Vậy nếu gọi hàm số

$$C(x, n) = \begin{cases} 1, & \text{ if } \pi(x) < n \\ 0 &\text{ otherwise } \end{cases}$$

Thì ta có thể tính $p_n$ theo công thức như sau:

$$p_n = 1 + \sum_{m=1}^{\infty} C(m,n)$$

Định đề Bertrand (Bertrand’s postulate)

Định đề này đã được chứng minh và xem như một định lý phát biểu rằng với mọi số nguyên $n > 1$, luôn tồn tại ít nhất một số nguyên tố $p$ sao cho $n \lt p \lt 2n$.

💡

Hẹn các bạn một bài chứng minh định đề nổi tiếng này ở một bài viết khác.

Từ định đề Bertrand, ta suy ra một nhận xét rằng có ít nhất $n$ số nguyên tố bé hơn $2^n$, hay nói cách khác: $\pi(2^n) \ge n$. Từ đó ta cập nhật biên công thức tính $p_n$ thành:

$$p_n = 1 + \sum_{m=1}^{2^n} C(m,n)$$

Xử lý hàm số $C(m,n)$

Hàm số $C(m,n)$ chưa đủ “đẹp” vì nó đang ở dạng biểu thức vị ngữ (predicate expression). Tuy nhiên, C.P Willans đã khéo léo thay thế bằng một hàm số tương đương:

$$L(x,y) = \left \lfloor \sqrt[y] {\frac y {1 + x}} \right \rfloor$$

Với $y=1,2,3,\dots$ và $x=0,1,2,\dots$

Rõ ràng vói hàm số $L(x,y)$, ta có các tính chất:

Với $x \lt y$, ta có $1 \le \frac y {1+x} \implies 1 \le \sqrt [y] {\frac y {1+x}} \le \sqrt[y] y \lt 2 \implies L(x,y)= \lfloor \sqrt [y] {\frac y {1+x}} \rfloor = 1$
Với $x \ge y$, ta có $0 \lt \frac y {1+x} \lt 1 \implies 0 \le \sqrt [y] {\frac y {1+x}} \le \sqrt[y] y \lt 1 \implies L(x,y)= \lfloor \sqrt [y] {\frac y {1+x}} \rfloor = 0$

Như vậy ta có thể thấy rằng $C(m,n) $ tương đương với $L(\pi(m),n)$.

Cuối cùng, thay mảnh ghép vào công thức ta có:

$$\begin{align*} p_n &= 1 + \sum_{m=1}^{2^n}L(\pi(m), n)\\ &= 1+ \sum_{m=1}^{2^n} \left \lfloor \sqrt[n] {\frac n {1 + \pi(m)}} \right \rfloor \end{align*}$$

Với $\pi(m) = \sum_{j=1}^m \lfloor (\cos \pi \frac {(j-1)! + 1} j)^2 \rfloor$. Và đó chính là công thức ban đầu.

Công thức tính số nguyên tố thứ n của C. P. Willans

Định lý Wilson

Xét \(\sum_{j=1}^m \lfloor (\cos \pi \frac {(j-1)! + 1} j)^2 \rfloor\)

Định đề Bertrand (Bertrand’s postulate)

Xử lý hàm số \(C(m,n)\)