Hàm Kempner

Đồ thị hàm Kempner

Trong lý thuyết số, hàm Kempner S(n)[1] đượ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,[2] rồi theo sau bởi Joseph Jean Baptiste Neuberg trong 1887.[3] Trong 1918, A. J. Kempner là người đầu tiên đưa ra thuật toán tính S(n).[4]

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.[5]

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.[6] 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.[1] Xét ví dụ sau, Vì S(6) = 3 nên có một đa thức bậc ba mà các giá trị của nó đều chia hết cho 6, ví dụ như đa thức sau:

Là một trong những bài toán khó của American Mathematical Monthly, được đặt vào trong 1991 và được giải vào 1994, Paul Erdős chỉ ra rằng các giá trị của S(n) trùng với ước nguyên tố lớn nhất của n với "hầu hết" tất cả các giá trị n (nghĩa là mật độ tiệm cận của tập các ngoại lệ bằng không).[7]

Độ 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(pe), trong đó pe là lũy thừa nguyên tố là ước của n.[4].Khi n là lũy thừa nguyên tố pe, 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

  1. ^ a b Called the Kempner numbers in the Online Encyclopedia of Integer Sequences: see Sloane, N. J. A. (biên tập). “Dãy A002034 (Kempner numbers: smallest number m such that n divides m!)”. Bảng tra cứu dãy số nguyên trực tuyến. Tổ chức OEIS.
  2. ^ Lucas, E. (1883). “Question Nr. 288”. Mathesis. 3: 232.
  3. ^ Neuberg, J. (1887). “Solutions de questions proposées, Question Nr. 288”. Mathesis. 7: 68–69.
  4. ^ a b Kempner, A. J. (1918). “Miscellanea”. American Mathematical Monthly. 25 (5): 201–210. doi:10.2307/2972639. JSTOR 2972639.
  5. ^ Hungerbühler, Norbert; Specker, Ernst (2006), “A generalization of the Smarandache function to several variables”, Integers, 6: A23, 11, MR 2264838
  6. ^ R. Muller (1990). “Editorial” (PDF). Smarandache Function Journal. 1: 1. ISBN 84-252-1918-3.
  7. ^ Erdős, Paul; Kastanas, Ilias (1994), “The smallest factorial that is a multiple of n (solution to problem 6674)” (PDF), American Mathematical Monthly, 101: 179, doi:10.2307/2324376.

Bài viết này có sử dụng tài liệu từ Smarandache function tại PlanetMath, với giấy phép sử dụng Creative Commons Attribution/Share-Alike License.