miércoles, 27 de mayo de 2015

La función de Smarandache y los números de Kempner (2)

Propiedades de la función S(n)

En la anterior entrada evaluamos la función de Smarandache con hoja de cálculo y PARI sin usar la descomposición en factores primos del número. Ahora investigaremos su comportamiento respecto a la descomposición factorial.

Comenzaremos con casos particulares de valores de S(n):

S(p)=p si p es primo

Para que p divida a un factorial, este ha de contenerlo como factor, y en los p-1 números anteriores no figura, luego hay que llegar a p y su factorial.

Recorre los valores de orden primo de los números de Kempner y observarás que el valor de la función de Smarandache en ellos coincide con el orden. Lo señalamos en rojo:

1, 2, 3, 4, 5, 3, 7, 4, 6, 5, 11, 4, 13, 7, 5, 6, 17, 6, 19, 5, 7, 11, 23, 4, 10, 13, 9, 7, 29,…

S(n!)=n

Es muy sencillo razonarlo. Observa que S(3!)=3, S(4!)=S(24)=4,…

Si n=p1p2p3…pk con pi primo y p1<p2<p3<…<pk,   S(n)= pk

En efecto, si tomamos el factorial del mayor primo, este incluirá como factores a todos los anteriores, y será el menor que sea divisible entre n. Elige números libres de cuadrados y lo comprobarás:

S(15)=S(3*5)=5, S(30)=S(2*3*5)=5, S(70)=S(2*5*7)=7

Si n=pk con k<=p, S(n)=p*k

Si n es potencia de un primo pk, éste deberá figurar k veces en S(n), pero la única forma de lograrlo es tomar p*p*p… k veces. Pero si k fuera mayor que p podrían aparecer más factores “p” y hay que tratarlo aparte.

Por ejemplo, S(49) ha de ser un factorial que contenga el 7 dos veces, pero el primero que cumple esto es el 14, que contiene el factor 7 en el mismo 7 y en el de 14, luego S(49)=7*2=14.

Caso n=pk con k>p

En este caso pueden aparecer más factores antes de llegar a k. Lo vemos con un ejemplo: S(27)=S(128). Aquí no hay que llegar a 2*7, porque aparecen 7 factores con valor 2 mucho antes. Construimos un factorial: 1*2*3*4*5*6*7*8*9…En él aparece un 2 en el mismo 2, 22 en el 4, 21 en 6 y 23 en el 8, con lo que ya tenemos el 7: 1+2+1+3=7. Por tanto S(128)=8 y no 14.

El objetivo será, pues, ver qué exponente de p será el adecuado para acumular al menos el valor de k. En este ejemplo, con llegar a 2*4 ya conseguimos el 7.

Si conoces el tema, te habrás acordado de la Fórmula de Polignac para encontrar los exponentes de un factor primo dentro de un factorial

(ver http://hojaynumeros.blogspot.com.es/2009/02/formula-de-polignac.html)


Todo lo que sigue es de aplicación sólo al caso S(pk), con p primo y k>p

Algoritmo con la fórmula de Polignac

Hace tiempo que implementamos esta fórmula para hoja de cálculo:

Public Function polignac(n, p)
Dim pol, pote
pol = 0
If esprimo(p) Then
pote = p
While pote <= n
pol = pol + Int(n / pote)
pote = pote * p
Wend
End If
polignac = pol
End Function

Podemos usarla y plantear que para un número dado vamos aplicando esa fórmula desde 1 hasta N, deteniéndonos cuando el exponente k de pk sea inferior a lo que nos dé la fórmula de Polignac. Lo planteamos como una función de dos variables, el primo p y el exponente k. No analizaremos si p es primo y si k es entero.

Public Function smar3(p, k) ‘Dos parámetros, el primo p y el exponente k
Dim n, s
Dim sigue As Boolean
If k <= p Then smar3 = p*k: Exit Function ‘caso sencillo
n = 1: sigue = True: s = 1
While sigue And n <= p ^ k
If polignac(n, p) >= k Then sigue = False: s = n ‘paramos cuando se sobrepase el exponente
n = n + 1
Wend
smar3 = s
End Function

Aquí tienes una tabla con casos en los que k>p, comparando con los resultados de SMAR2



Kempner desarrolló un algoritmo para esta situación, pero como no lo hemos encontrado bien explicado y es complejo (téngase cuenta que se creó antes de la existencia del cálculo automático), nos quedamos con los tres nuestros.

Lo puedes consultar en http://mathworld.wolfram.com/SmarandacheFunction.html

Caso general

Si se ha resuelto el cálculo de S(pk), para calcular la función en un número cualquiera es fácil entender que se calculará para todas las potencias de primos contenidas en él, tomando después el máximo de los valores.

Esto supone mucha complicación, y como estamos muy satisfechos con nuestro algoritmo del MCD, nos quedamos con él.

Gráfica de la función de Smarandache

Nos quedamos con nuestra función SMAR2 para crear un gráfico, por otra parte muy conocido, de la función de Smarandache:



Vemos que es lineal para los números primos, que la función está acotada por el valor de N, y que es totalmente oscilante. Algunos máximos intermedios se corresponden con dobles de primos y, en general, los semiprimos y libres de cuadrados suelen presentar valores altos en su entorno.