Kempner function

Uses your system voice; voice and rate in settings.

Snapshot

≈ 6 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In number theory, the Kempner function S(n)[1] is defined for a given positive integer n to be the smallest number s such that n divides the factorial s!. For example, the number 8 does not divide 1!, 2!, or 3!, but does divide 4!, so S(8)=4.

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

History

edit edit source

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 an algorithm for computing S(n) without trials.[4]

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

Properties

edit edit source

Since n divides n!, S(n) is always at most n. A number n>4 is prime if and only if S(n)=n.[6] That is, the numbers n for which S(n) is as large as possible relative to n are the primes. In the other direction, the numbers for which S(n) is as small as possible are the factorials: S(k!)=k, for all k≥1.

S(n) is the smallest possible degree of a monic polynomial with integer coefficients, whose values over the integers are all divisible by n.[1] For instance, the fact that S(6)=3 means that there is a cubic polynomial whose values are all zero modulo 6, for instance the polynomial x(x−1)(x−2)=x3−3x2+2x, 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 S(n) coincides with the largest prime factor of n for "almost all" n (in the sense that the asymptotic density of the set of exceptions is zero).[7]

Computational complexity

edit edit source

The Kempner function S(n) of an arbitrary number n is the maximum, over the prime powers pe dividing n, of S(pe).[4] When n is itself a prime power pe, its Kempner function may be found in polynomial time by sequentially scanning the multiples of p until finding the first one whose factorial contains enough multiples of p. The same algorithm can be extended to any n 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 n=px, where p is prime and x<p, the Kempner function of n is p.[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 n is composite, the greatest common divisor of S(n) and n will necessarily be a nontrivial divisor of n, allowing n 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.

See also

edit edit source
  • Ruler function, a simpler integer function with an inconsistent growth rate

References and notes

edit edit source
  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.{{cite journal}}: CS1 maint: periodical has ISBN (link)
  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..
Factorial and binomial topicsCombinatorial principlesCoreAddition principle · Rule of product · Binomial coefficient · Pascal's triangle · Central binomial coefficient · Vandermonde's identity · Binomial theorem · Binomial series · Binomial transform · Binomial type ·Twelvefold way · Abel's binomial theorem · Trinomial expansion · Pigeonhole principle · Inclusion–exclusion principleCombinatorics basicsCombination · Permutation · Multiset · Combinatorial number system · List of permutation topics · Antichain · Stars and bars (combinatorics)Identities, numbers, sequencesHockey-stick identity · Stirling number · Stirling transform · Catalan number · Fuss–Catalan number · Narayana numbers · Lah number · Gould's sequence · Jordan–Pólya number · Kempner function · Gaussian binomial coefficientMultinomial generalizationsMultinomial coefficient · Multinomial formula/theorem · Multinomial distribution · Pascal's pyramid · Pascal's simplex · Trinomial triangleDistributionsBinomial distribution · Negative binomial distribution · Hypergeometric distribution · Poisson distribution · Gamma distributionSpecial functions (connections)Gamma function · Beta function · Incomplete beta function · Incomplete gamma function · Pochhammer symbol (rising/falling) · Digamma function · Polygamma function · Multivariate gamma function · Hypergeometric series · Hypergeometric function identitiesFactorials & approximationsFactorial · Bhargava factorial · Exponential factorial · Hyperfactorial · Alternating factorial · Factorial moment · Factorial number system · Subfactorial · Superfactorial · Primorial · Lanczos approximation · Stirling's approximationStructures & arraysLozanić's triangle · Sierpinski triangle · Pascal matrix · Multiplicities of entries in Pascal's triangleOperators & calculus linksDifference operator · Difference polynomials · Table of Newtonian series · Faà di Bruno's formula · Taylor seriesTheorems & resultsStar of David theorem · Erdős–Ko–Rado theorem · Carlson's theorem · Mahler's theorem · Proof of Bertrand's postulate · Wilson's theorem · Wilson prime · De Polignac's formulaMethods & integralsEgorychev method · Nörlund–Rice integral · q-binomial identities · Binomial QMF

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

Text derived from https://en.wikipedia.org/w/index.php?oldid=1370496414 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

3 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.