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

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:

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 $(p1-)!+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ó$\displaystyle \frac {(j-1)!+1}{j}$ là số nguyên khi khi và 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 bằng xảy ra khi $F(x)$là số nguyên, vì thế khi $x=1$ hoặc $x$ là số nguyên tố thì $\lfloor(\cos \pi F(x))^2 \rfloor = 1$, ngược lại thì $\lfloor(\cos \pi F(x))^2 \rfloor=0$

Từ đó ta nhận thấy rằng $\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 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)<n$ khi $m<p_n$ và

• $\pi(n) \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ác giá trị của $m$ sao cho $\pi(m) \lt n$ là $p_n - 1$.

Vậy nếu gọi hàm số

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

Đị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 <p<2n$.

Từ định đề này, 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 công thức tính $p_n$ thành:

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

Hàm số $C(m,n)$ chưa đủ "đẹp" vì nó đang ở 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:

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

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

• Với $x<y$, ta có $\displaystyle 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ó $\displaystyle 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 có thể thấy rằng $C(m,n)$ tương vưới $L(\pi(m),n)$.

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

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.