✨Hàm Kempner

thumb|right|Đồ thị hàm Kempner

Trong lý thuyết số, hàm Kempner S(n) được định nghĩa cho số nguyên dương n là số tự nhiên s nhỏ nhất sao cho n là ước của giai thừa s!. Để lấy ví dụ, số 8 không phải là ước của 1!, 2!, 3!, nhưng là ước của 4!,nên S(8) = 4.

Hàm số này có tính chất tăng trưởng tuyến tính trên các số nguyên tố nhưng lại tăng trưởng theo lôgarit tại các số giai thừa.

Lịch sử

Hàm này lần đầu được xét bởi François Édouard Anatole Lucas trong 1883, rồi theo sau bởi Joseph Jean Baptiste Neuberg trong 1887. Trong 1918, A. J. Kempner là người đầu tiên đưa ra thuật toán tính S(n).

Hàm Kempner đôi khi cũng được gọi là hàm Smarandache theo tên của Florentin Smarandache sau khi khám phá lại hàm này trong 1980.

Các tính chất

Bởi n là ước của n!, giá trị S(n) tối đa bằng n. Số n lớn hơn 4 là số nguyên tố khi và chỉ khi S(n) = n. Nghĩa là các số n sao cho giá trị S(n) lớn nhất có thể so với n là các số nguyên tố. Ngược lại, các số n sao cho giá trị S(n) nhỏ nhất có thể là các số giai thừa : S(k!) = k, với mọi k ≥ 1.

S(n) là bậc nhỏ nhất có thể của một đa thức monic với hệ số nguyên, trong đó các giá trị của đa thức đều chia hết cho n.

Độ phức tạp tính toán

Hàm Kempner S(n) của số n tùy ý là giá trị cực đại của các S(p^e), trong đó p^e là lũy thừa nguyên tố là ước của n..Khi n là lũy thừa nguyên tố p^e, giá trị hàm Kempner của nó có thể được tìm trong thời gian đa thức bằng việc kiểm tra từng bội p cho đến khi tìm thấy bội đầu tiên mà giai thừa của nó chứa đủ số  p trong đó. Thuật toán này có thể mở rộng cho bất kỳ số n nào đã được phân tích thừa số nguyên tố, bằng cách áp dụng cho mỗi lũy thừa nguyên tố là ước của n rồi chọn giá trị lớn nhất trong các giá trị tìm được.

Tham khảo và chú thích

Thể loại:Giai thừa