imported>David Eppstein: Undid revision 1231003508 by Jayy V (talk) wikilinking and formatting disimprovements

2024-06-25T23:35:26Z

Undid revision 1231003508 by Jayy V (talk) wikilinking and formatting disimprovements

New page

[[File:SmarandacheFunction.PNG|thumb|374px|right|Graph of the Kempner function]]

In [[number theory]], the '''Kempner function''' <math>S(n)</math><ref name="oeis">Called the Kempner numbers in the [[Online Encyclopedia of Integer Sequences]]: see {{Cite OEIS|sequencenumber=A002034 |name=Kempner numbers: smallest number ''m'' such that ''n'' divides ''m''<nowiki>!</nowiki>}}</ref> is defined for a given [[positive integer]] <math>n</math> to be the smallest number <math>s</math> such that <math>n</math> [[divides]] the {{nowrap|[[factorial]] <math>s!</math>.}} For example, the number <math>8</math> does not divide <math>1!</math>, <math>2!</math>, {{nowrap|or <math>3!</math>,}} but does {{nowrap|divide <math>4!</math>,}} {{nowrap|so <math>S(8)=4</math>.}}

This function has the property that it has a highly inconsistent [[Asymptotic analysis|growth rate]]: it [[linear function|grows linearly]] on the [[prime number]]s but only grows [[Logarithmic growth|sublogarithmically]] at the factorial numbers.

==History==
This function was first considered by [[François Édouard Anatole Lucas]] in 1883,<ref name="history1">
{{cite journal
| first = E. | last = Lucas | authorlink = François Édouard Anatole Lucas
| title = Question Nr. 288
| journal = [[Mathesis (journal)|Mathesis]]
| volume = 3
|page=232
| year = 1883
}}</ref> followed by [[Joseph Jean Baptiste Neuberg]] in 1887.<ref name="history2">
{{cite journal
| first = J. | last = Neuberg | authorlink = Joseph Jean Baptiste Neuberg
| title = Solutions de questions proposées, Question Nr. 288
| journal = [[Mathesis (journal)|Mathesis]]
| volume = 7
| pages = 68–69
| year = 1887
}}</ref> In 1918, [[Aubrey J. Kempner|A. J. Kempner]] gave the first correct algorithm for {{nowrap|computing <math>S(n)</math>.<ref name="history3">
{{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
}}</ref>}}

The Kempner function is also sometimes called the '''Smarandache function''' following Florentin Smarandache's rediscovery of the function {{nowrap|in 1980.<ref>{{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}}</ref>}}

==Properties==
Since <math>n</math> {{nowrap|divides <math>n!</math>,}} <math>S(n)</math> is always at {{nowrap|most <math>n</math>.}} A number <math>n</math> greater than 4 is a [[prime number]] if and only {{nowrap|if <math>S(n)=n</math>.<ref>
{{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
}}</ref>}} That is, the numbers <math>n</math> for which <math>S(n)</math> is as large as possible relative to <math>n</math> are the primes. In the other direction, the numbers for which <math>S(n)</math> is as small as possible are the factorials: {{nowrap|<math>S(k!)=k</math>,}} for {{nowrap|all <math>k\ge 1</math>.}}

<math>S(n)</math> is the smallest possible [[Degree of a polynomial|degree]] of a [[monic polynomial]] with integer coefficients, whose values over the integers are all divisible {{nowrap|by <math>n</math>.<ref name="oeis"/>}}
For instance, the fact that <math>S(6)=3</math> means that there is a [[cubic polynomial]] whose values are all zero [[Modular arithmetic|modulo]] 6, for instance the polynomial
<math display=block>x(x-1)(x-2)=x^3-3x^2+2x,</math>
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 <math>S(n)</math> coincides with the largest [[prime factor]] of <math>n</math> for "almost all" <math>n</math> (in the sense that the [[asymptotic density]] of the set of exceptions is zero).<ref>{{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 }}.</ref>

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

{{PlanetMath attribution
|id = | urlname =SmarandacheFunction
|title = Smarandache function}}

[[Category:Factorial and binomial topics]]

Kempner function - Revision history

imported>David Eppstein: Undid revision 1231003508 by Jayy V (talk) wikilinking and formatting disimprovements