Dãy Euclid-Mullin

Dãy Euclid–Mullin là dãy vô hạn các số nguyên tố phân biệt, trong đó mỗi phần tử là ước nguyên tố nhỏ nhất của tổng của một và tích của các phần tử trước đó. Dãy được đặt theo nhà toán học cổ Euclid và định nghĩa của nó dựa trên bài chứng minh của Euclid rằng có vô hạn số nguyên tố, và theo Albert A. Mullin, người đặt ra câu hỏi về dãy này.

51 phần tử đầu tiên của dãy là

2, 3, 7, 43, 13, 53, 5, 6221671, 38709183810571, 139, 2801, 11, 17, 5471, 52662739, 23003, 30693651606209, 37, 1741, 1313797957, 887, 71, 7127, 109, 23, 97, 159227, 643679794963466223081509857, 103, 1079990819, 9539, 3143065813, 29, 3847, 89, 19, 577, 223, 139703, 457, 9649, 61, 4357, 87991098722552272708281251793312351581099392851768893748012603709343, 107, 127, 3313, 227432689108589532754984915075774848386671439568260420754414940780761245893, 59, 31, 211... 

Đây là các giá trị duy nhất được tính tại thời điểm tháng 9 năm 2012. Tính giá trị tiếp theo buộc phải tìm ước nguyên tố nhỏ nhất của số có 335 chữ số (được biết là hợp số).

Định nghĩa
Phần tử thứ  trong dãy,  là ước nguyên tố nhỏ nhất của

Phần tử đầu tiên là ước nguyên tố nhỏ nhất của tổng của tích rỗng cộng 1, bằng  2.  Phần tử thứ 3 là (2 × 3) + 1 = 7.  Phần tử thứ 5 với giá trị 13 được tính như sau: Tính (2 × 3 × 7 × 43) + 1 = 1806 + 1 =  1807; Giá trị 1807 thì bằng tích của hai số nguyên tố 13 × 139.  Trong hai số nguyên tố này, 13 là nhỏ nhất nên được cho vào dãy. Quan sát rằng mặc dù tích các phần tử trước đó rất lớn, vì phần tử yêu cầu phải là ước nguyên tố nhỏ nhất, giá trị các phần tử trong dãy có thể nhỏ hoặc lớn không xác định trước được.

Tính chất
Dãy dài vô hạn và không lặp lại phần tử. Ta có thể chứng minh tính chất đó bằng bài chứng minh của Euclid về tính vô hạn của số nguyên tố. Dãy số này được xây tương tự như cách xây trong bài chứng minh đó.

Giả thuyết

 đặt ra câu hỏi rằng liệu mọi số nguyên tố có xuất hiện trong dãy Euclid–Mullin không, và nếu không thì thuật toán kiểm tra xem số nguyên tố có phải phần tử trong dãy có  tính toán được không.  phỏng đoán rằng, dựa trên mặc định heuristic rằng phân phối số nguyên tố ngẫu nhiên nên mọi số nguyên tố đều xuất hiện trong dãy.
Mặc dù các dãy đệ quy tương tự trên các miền phân tích duy nhất khác không chứa hết mọi số nguyên tố,
câu hỏi về dãy Euclid-Mullin vẫn là vấn đề mở. Số nguyên tố nhỏ nhất chưa biết có phải phần tử trong dãy không là 41.

Vị trí các số nguyên tố từ 2 đến 97 à:
 2:1, 3:2, 5:7, 7:3, 11:12, 13:5, 17:13, 19:36, 23:25, 29:33, 31:50, 37:18, 41:?, 43:4, 47:?, 53:6, 59:49, 61:42, 67:?, 71:22, 73:?, 79:?, 83:?, 89:35, 97:26 
Trong đó ? nghĩa là chưa biết vị trí của số nguyên tố đó.

Một số dãy tương tự
Một dãy số tương tự khác có thể định nghĩa là ước nguyên tố lớn nhất của tổng của 1 với tích các số đi trước. Nó lớn nhanh hơn nhưng không đơn điệu. Các số trong dãy đó là
2, 3, 7, 43, 139, 50207, 340999, 2365347734339, 4680225641471129, 1368845206580129, 889340324577880670089824574922371, … .
Dãy này không chứa mọi số nguyên tố, và dãy các số nguyên tố không có trong dãy trên là,
5, 11, 13, 17, 19, 23, 29, 31, 37, 41, 47, 53, 59, 61, 67, 71, 73, ... 
được chứng minh là vô hạn.

Ta cũng có thể sinh dãy Euclid–Mullin với cùng luật đó nhưng chọn số nguyên tố bắt đầu khác 2.

Xem thêm
Số Euclid

Tham khảo

Liên kết ngoài

Chuỗi số nguyên
Số nguyên tố
Vấn đề mở trong lý thuyết số