In number theory, the Kempner function [1] is defined for a given positive integer to be the smallest number such that divides the factorial . For example, the number does not divide , , or , but does divide , so .

Graph of the Kempner function

This function has the property that it has a highly inconsistent growth rate: it grows linearly on the prime numbers but only grows sublogarithmically at the factorial numbers.

History

edit

This function was first considered by François Édouard Anatole Lucas in 1883,[2] followed by Joseph Jean Baptiste Neuberg in 1887.[3] In 1918, A. J. Kempner gave the first correct algorithm for computing  .[4]

The Kempner function is also sometimes called the Smarandache function following Florentin Smarandache's rediscovery of the function in 1980.[5]

Properties

edit

Since   divides  ,   is always at most  . A number   greater than 4 is a prime number if and only if  .[6] That is, the numbers   for which   is as large as possible relative to   are the primes. In the other direction, the numbers for which   is as small as possible are the factorials:  , for all  .

  is the smallest possible degree of a monic polynomial with integer coefficients, whose values over the integers are all divisible by  .[1] For instance, the fact that   means that there is a cubic polynomial whose values are all zero modulo 6, for instance the polynomial   but that all quadratic or linear polynomials (with leading coefficient one) are nonzero modulo 6 at some integers.

In one of the advanced problems in The American Mathematical Monthly, set in 1991 and solved in 1994, Paul Erdős pointed out that the function   coincides with the largest prime factor of   for "almost all"   (in the sense that the asymptotic density of the set of exceptions is zero).[7]

Computational complexity

edit

The Kempner function   of an arbitrary number   is the maximum, over the prime powers   dividing  , of  .[4] When   is itself a prime power  , its Kempner function may be found in polynomial time by sequentially scanning the multiples of   until finding the first one whose factorial contains enough multiples of  . The same algorithm can be extended to any   whose prime factorization is already known, by applying it separately to each prime power in the factorization and choosing the one that leads to the largest value.

For a number of the form  , where   is prime and   is less than  , the Kempner function of   is  .[4] It follows from this that computing the Kempner function of a semiprime (a product of two primes) is computationally equivalent to finding its prime factorization, believed to be a difficult problem. More generally, whenever   is a composite number, the greatest common divisor of   and   will necessarily be a nontrivial divisor of  , allowing   to be factored by repeated evaluations of the Kempner function. Therefore, computing the Kempner function can in general be no easier than factoring composite numbers.

References and notes

edit
  1. ^ a b Called the Kempner numbers in the Online Encyclopedia of Integer Sequences: see Sloane, N. J. A. (ed.). "Sequence A002034 (Kempner numbers: smallest number m such that n divides m!)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
  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 c Kempner, A. J. (1918). "Miscellanea". The 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). The American Mathematical Monthly. 101: 179. doi:10.2307/2324376. JSTOR 2324376..

This article incorporates material from Smarandache function on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.