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.^[1]

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... (dãy số A000945 trong bảng OEIS)

Đâ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[sửa | sửa mã nguồn]

Phần tử thứ $n$ trong dãy, $a_{n}$ là ước nguyên tố nhỏ nhất của

{\Bigl (}\prod _{i<n}a_{i}{\Bigr )}+1\,.

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[sửa | sửa mã nguồn]

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[sửa | sửa mã nguồn]

Vấn đề mở trong toán học:

Có đúng rằng mọi số nguyên tố xuất hiện trong dãy Euclid–Mullin?

(các vấn đề mở khác trong toán học)

Mullin (1963) đặ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. Daniel Shanks (1991) 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.^[2] 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ố,^[3] câu hỏi về dãy Euclid-Mullin vẫn là vấn đề mở.^[4] 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 (dãy số A056756 trong bảng OEIS)

Trong đó ? nghĩa là chưa biết vị trí của số nguyên tố đó.

Một số dãy tương tự[sửa | sửa mã nguồn]

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.^[5] Các số trong dãy đó là

2, 3, 7, 43, 139, 50207, 340999, 2365347734339, 4680225641471129, 1368845206580129, 889340324577880670089824574922371, … (dãy số A000946 trong bảng OEIS).

Dãy này không chứa mọi số nguyên tố,^[6] 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, ... (dãy số A216227 trong bảng OEIS)

được chứng minh là vô hạn.^[7]^[8]

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.^[9]

Xem thêm[sửa | sửa mã nguồn]

Số Euclid

Tham khảo[sửa | sửa mã nguồn]

^ Mullin, Albert A. (1963), “Recursive function theory (A modern look at a Euclidean idea)”, Research problems, Bulletin of the American Mathematical Society, 69 (6): 737, doi:10.1090/S0002-9904-1963-11017-4.
^ Shanks, Daniel (1991), “Euclid's primes”, Bulletin of the Institute of Combinatorics and Its Applications, 1: 33–36, MR 1103634.
^ Kurokawa, Nobushige; Satoh, Takakazu (2008), “Euclid prime sequences over unique factorization domains”, Experimental Mathematics, 17 (2): 145–152, doi:10.1080/10586458.2008.10129035, MR 2433881, S2CID 12924815.
^ Booker, Andrew R. (2016), “A variant of the Euclid-Mullin sequence containing every prime”, Journal of Integer Sequences, 19 (6): Article 16.6.4, 6, arXiv:1605.08929, MR 3546618.
^ Naur, Thorkil (1984), “Mullin's sequence of primes is not monotonic”, Proceedings of the American Mathematical Society, 90 (1): 43–44, doi:10.2307/2044665, JSTOR 2044665, MR 0722412.
^ Cox, C. D.; Van der Poorten, A. J. (1968), “On a sequence of prime numbers”, Journal of the Australian Mathematical Society, 8 (3): 571–574, doi:10.1017/S1446788700006236, MR 0228417
^ Booker, Andrew R. (2012), “On Mullin's second sequence of primes”, Integers, 12 (6): 1167–1177, arXiv:1107.3318, doi:10.1515/integers-2012-0034, MR 3011555, S2CID 119144088.
^ Pollack, Paul; Treviño, Enrique (2014), “The primes that Euclid forgot”, American Mathematical Monthly, 121 (5): 433–437, doi:10.4169/amer.math.monthly.121.05.433, MR 3193727, S2CID 1335826.
^ Sheppard, Barnaby (2014), The Logic of Infinity, Cambridge University Press, tr. 26, ISBN 9781139952774

Liên kết ngoài[sửa | sửa mã nguồn]

Weisstein, Eric W., "Euclid–Mullin Sequence" từ MathWorld.

[1] Mullin, Albert A. (1963), “Recursive function theory (A modern look at a Euclidean idea)”, Research problems, Bulletin of the American Mathematical Society, 69 (6): 737, doi:10.1090/S0002-9904-1963-11017-4.

[2] Shanks, Daniel (1991), “Euclid's primes”, Bulletin of the Institute of Combinatorics and Its Applications, 1: 33–36, MR 1103634.

[3] Kurokawa, Nobushige; Satoh, Takakazu (2008), “Euclid prime sequences over unique factorization domains”, Experimental Mathematics, 17 (2): 145–152, doi:10.1080/10586458.2008.10129035, MR 2433881, S2CID 12924815.

[4] Booker, Andrew R. (2016), “A variant of the Euclid-Mullin sequence containing every prime”, Journal of Integer Sequences, 19 (6): Article 16.6.4, 6, arXiv:1605.08929, MR 3546618.

[5] Naur, Thorkil (1984), “Mullin's sequence of primes is not monotonic”, Proceedings of the American Mathematical Society, 90 (1): 43–44, doi:10.2307/2044665, JSTOR 2044665, MR 0722412.

[6] Cox, C. D.; Van der Poorten, A. J. (1968), “On a sequence of prime numbers”, Journal of the Australian Mathematical Society, 8 (3): 571–574, doi:10.1017/S1446788700006236, MR 0228417

[7] Booker, Andrew R. (2012), “On Mullin's second sequence of primes”, Integers, 12 (6): 1167–1177, arXiv:1107.3318, doi:10.1515/integers-2012-0034, MR 3011555, S2CID 119144088.

[8] Pollack, Paul; Treviño, Enrique (2014), “The primes that Euclid forgot”, American Mathematical Monthly, 121 (5): 433–437, doi:10.4169/amer.math.monthly.121.05.433, MR 3193727, S2CID 1335826.

[9] Sheppard, Barnaby (2014), The Logic of Infinity, Cambridge University Press, tr. 26, ISBN 9781139952774

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]