Función de Kempner

Gráfica de la función de Kempner

En teoría de números , la función de Kempner ^[1] se define para un entero positivo dado como el número más pequeño que divide el factorial . Por ejemplo, el número no divide a , , o , pero sí divide a , por lo que . ${\displaystyle S(n)}$ ${\displaystyle n}$ ${\displaystyle s}$ ${\displaystyle n}$ ${\displaystyle s!}$ ${\displaystyle 8}$ ${\displaystyle 1!}$ ${\displaystyle 2!}$ ${\displaystyle 3!}$ ${\displaystyle 4!}$ ${\displaystyle S(8)=4}$

Esta función tiene la propiedad de que tiene una tasa de crecimiento altamente inconsistente : crece linealmente en los números primos pero sólo crece sublogarítmicamente en los números factoriales.

Historia

Esta función fue considerada por primera vez por François Édouard Anatole Lucas en 1883, ^[2] seguido por Joseph Jean Baptiste Neuberg en 1887. ^[3] En 1918, AJ Kempner dio el primer algoritmo correcto para calcular . ^[4] ${\displaystyle S(n)}$

La función Kempner también se denomina a veces función Smarandache, en honor al redescubrimiento de la función por Florentin Smarandache en 1980. ^[5]

Propiedades

Como divide , es siempre como máximo . Un número mayor que 4 es un número primo si y solo si . ^[6] Es decir, los números para los que es lo más grande posible en relación con son los primos. En la otra dirección, los números para los que es lo más pequeño posible son los factoriales: , para todo . ${\displaystyle n}$ ${\displaystyle n!}$ ${\displaystyle S(n)}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle S(n)=n}$ ${\displaystyle n}$ ${\displaystyle S(n)}$ ${\displaystyle n}$ ${\displaystyle S(n)}$ ${\displaystyle S(k!)=k}$ ${\displaystyle k\geq 1}$

${\displaystyle S(n)}$es el grado más pequeño posible de un polinomio mónico con coeficientes enteros, cuyos valores sobre los enteros son todos divisibles por . ^[1] ${\displaystyle n}$ Por ejemplo, el hecho de que significa que hay un polinomio cúbico cuyos valores son todos cero módulo 6, por ejemplo el polinomio pero que todos los polinomios cuadráticos o lineales (con coeficiente principal uno) son distintos de cero módulo 6 en algunos enteros. ${\displaystyle S(6)=3}$ $${\displaystyle x(x-1)(x-2)=x^{3}-3x^{2}+2x,}$$

En uno de los problemas avanzados de The American Mathematical Monthly , creado en 1991 y resuelto en 1994, Paul Erdős señaló que la función coincide con el factor primo más grande de para "casi todos" (en el sentido de que la densidad asintótica del conjunto de excepciones es cero). ^[7] ${\displaystyle S(n)}$ ${\displaystyle n}$ ${\displaystyle n}$

Complejidad computacional

La función de Kempner de un número arbitrario es el máximo, sobre las potencias primas que dividen a , de . ^[4] Cuando es en sí mismo una potencia prima , su función de Kempner puede encontrarse en tiempo polinomial escaneando secuencialmente los múltiplos de hasta encontrar el primero cuyo factorial contenga suficientes múltiplos de . El mismo algoritmo puede extenderse a cualquiera cuya factorización prima ya se conozca, aplicándolo por separado a cada potencia prima en la factorización y eligiendo la que conduzca al valor más grande. ${\displaystyle S(n)}$ ${\displaystyle n}$ ${\displaystyle p^{e}}$ ${\displaystyle n}$ ${\displaystyle S(p^{e})}$ ${\displaystyle n}$ ${\displaystyle p^{e}}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle n}$

Para un número de la forma , donde es primo y es menor que , la función de Kempner de es . ^[4] De esto se deduce que calcular la función de Kempner de un semiprimo (un producto de dos primos) es computacionalmente equivalente a encontrar su factorización prima , que se cree que es un problema difícil. De manera más general, siempre que es un número compuesto , el máximo común divisor de y será necesariamente un divisor no trivial de , lo que permite factorizarlo mediante evaluaciones repetidas de la función de Kempner. Por lo tanto, calcular la función de Kempner en general no puede ser más fácil que factorizar números compuestos. ${\displaystyle n=px}$ ${\displaystyle p}$ ${\displaystyle x}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle S(n)}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

Referencias y notas

1. Se denominan números de Kempner en la Enciclopedia en línea de secuencias enteras : véase Sloane, N. J. A. (ed.). "Secuencia A002034 (Números de Kempner: ¡el número más pequeño m tal que n divide a m!)". La Enciclopedia en línea de secuencias enteras . Fundación OEIS.
2. Lucas, E. (1883). "Pregunta N° 288". Mathesis . 3 : 232.
3. Neuberg, J. (1887). "Soluciones de preguntas propuestas, Pregunta nº 288". Mathesis . 7 : 68–69.
4. Kempner, AJ (1918). "Miscelánea". The American Mathematical Monthly . 25 (5): 201–210. doi :10.2307/2972639. JSTOR  2972639.
5. Hungerbühler, Norbert; Specker, Ernst (2006). "Una generalización de la función Smarandache a varias variables". Enteros . 6 : A23, 11. MR  2264838.
6. R. Müller (1990). «Editorial» (PDF) . Diario de funciones de Smarandache . 1 : 1. ISBN 84-252-1918-3.
7. Erdős, Paul ; Kastanas, Ilias (1994). "El factorial más pequeño que es un múltiplo de n (solución al problema 6674)" (PDF) . The American Mathematical Monthly . 101 : 179. doi :10.2307/2324376. JSTOR  2324376..

Este artículo incorpora material de la función Smarandache en PlanetMath , que se encuentra bajo la licencia Creative Commons Attribution/Share-Alike License .