Kempner function

This function was first considered by François Édouard Anatole Lucas in 1883,

{{cite journal

| first = E. | last = Lucas | authorlink = François Édouard Anatole Lucas

| title = Question Nr. 288

| journal = Mathesis

| volume = 3

|page=232

| year = 1883

}} followed by Joseph Jean Baptiste Neuberg in 1887.

{{cite journal

| first = J. | last = Neuberg | authorlink = Joseph Jean Baptiste Neuberg

| title = Solutions de questions proposées, Question Nr. 288

| journal = Mathesis

| volume = 7

| pages = 68–69

| year = 1887

}} In 1918, A. J. Kempner gave the first correct algorithm for {{nowrap|computing $S(n)$.

{{cite journal

| jstor = 2972639

| first = A. J. | last = Kempner

| title = Miscellanea

| journal = The American Mathematical Monthly

| volume = 25

| pages = 201–210

| year = 1918

| doi = 10.2307/2972639

| issue = 5

}}}}

The Kempner function is also sometimes called the Smarandache function following Florentin Smarandache's rediscovery of the function {{nowrap|in 1980.{{cite journal

| last1 = Hungerbühler | first1 = Norbert

| last2 = Specker | first2 = Ernst | author2-link = Ernst Specker

| journal = Integers

| mr = 2264838

| page = A23, 11

| title = A generalization of the Smarandache function to several variables

| url = http://www.emis.de/journals/INTEGERS/papers/g23/g23.Abstract.html

| volume = 6

| year = 2006}}}}

Since $n$ {{nowrap|divides $n!$,}} $S(n)$ is always at {{nowrap|most $n$.}} A number $n$ greater than 4 is a prime number if and only {{nowrap|if $S(n)=n$.

{{cite journal

| author = R. Muller

| title = Editorial

| journal = Smarandache Function Journal

| url = http://www.gallup.unm.edu/~smarandache/SFJ1.pdf

| volume = 1

| issue =

|page=1

| year = 1990

| isbn = 84-252-1918-3

}}}} 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: {{nowrap|$S(k!)=k$,}} for {{nowrap|all $k\backslash ge\; 1$.}}

$S(n)$ is the smallest possible degree of a monic polynomial with integer coefficients, whose values over the integers are all divisible {{nowrap|by $n$.}}

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)=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 $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).{{cite journal|title=The smallest factorial that is a multiple of {{mvar|n}} (solution to problem 6674)|journal=The American Mathematical Monthly|volume=101|year=1994|page=179|url=http://www-fourier.ujf-grenoble.fr/~marin/une_autre_crypto/articles_et_extraits_livres/irationalite/Erdos_P._Kastanas_I.The_smallest_factorial...-.pdf|first1=Paul|last1=Erdős|author1-link=Paul Erdős|first2=Ilias|last2=Kastanas|doi=10.2307/2324376|jstor=2324376 }}.

The Kempner function $S(n)$ of an arbitrary number $n$ is the maximum, over the prime powers $p^e$ dividing $n$, of $S(p^e)$.

When $n$ is itself a prime power $p^e$, 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 {{nowrap|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$ is less than $p$, the Kempner function of $n$ is $p$. 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 a composite number, the greatest common divisor of $S(n)$ {{nowrap|and $n$}} will necessarily be a nontrivial divisor {{nowrap|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.

{{reflist}}

{{PlanetMath attribution

|id = | urlname =SmarandacheFunction

|title = Smarandache function}}

Category:Factorial and binomial topics