Kempner function

From Quire, the open reference·Arithmetical function·2 min read

In number theory, the Kempner function ${\displaystyle S(n)}$ ^[1] is defined for a given positive integer ${\displaystyle n}$ to be the smallest number ${\displaystyle s}$ such that ${\displaystyle n}$ divides the factorial ${\displaystyle s!}$ . For example, the number ${\displaystyle 8}$ does not divide ${\displaystyle 1!}$ , ${\displaystyle 2!}$ , or ${\displaystyle 3!}$ , but does divide ${\displaystyle 4!}$ , so ${\displaystyle 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

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 ${\displaystyle 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

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

{{mathimg|896aa95cb194816f48a89fecd7e304d4b7f1af71|width=4.703ex|height=2.843ex|va=-0.838ex|alt={\displaystyle S(n)}}} is the smallest possible degree of a monic polynomial with integer coefficients, whose values over the integers are all divisible by ${\displaystyle n}$ .^[1] For instance, the fact that ${\displaystyle S(6)=3}$ means that there is a cubic polynomial whose values are all zero modulo 6, for instance the polynomial ${\displaystyle x(x-1)(x-2)=x^{3}-3x^{2}+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 ${\displaystyle S(n)}$ coincides with the largest prime factor of ${\displaystyle n}$ for "almost all" ${\displaystyle n}$ (in the sense that the asymptotic density of the set of exceptions is zero).^[7]

Computational complexity#edit

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

References and notes#edit

^ 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.
^ Lucas, E. (1883). "Question Nr. 288". Mathesis. 3: 232.
^ Neuberg, J. (1887). "Solutions de questions proposées, Question Nr. 288". Mathesis. 7: 68–69.
^ a b c Kempner, A. J. (1918). "Miscellanea". The American Mathematical Monthly. 25 (5): 201–210. doi:10.2307/2972639. JSTOR 2972639.
^ Hungerbühler, Norbert; Specker, Ernst (2006). "A generalization of the Smarandache function to several variables". Integers. 6: A23, 11. MR 2264838.
^ R. Muller (1990). "Editorial" (PDF). Smarandache Function Journal. 1: 1. ISBN 84-252-1918-3.
^ 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.

Categories Factorial and binomial topics

This article is mirrored from “Kempner function” on English Wikipedia, revision 1370496414, written by Wikipedia's contributors and licensed CC BY-SA 4.0. Editing it here creates a Quire copy with its own history.

Synced with Wikipedia revision 1370496414 · just now

Kempner function

History#edit

Properties#edit

Computational complexity#edit

See also#edit

References and notes#edit