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.

lunes, 18 de mayo de 2015

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

La función de Smarandache se define, para un número natural n, como el menor entero tal que su factorial es divisible entre n. La designaremos como S(n). Por ejemplo, para n=12, el menor valor de k tal que k! sea divisible entre 12 es el 4, ya que 4!=24 es el menor factorial divisible entre 12. Lo expresaremos como S(12)=4. Es fácil que entiendas que S(6)=3 o que S(7)=7. Plantéate otros ejemplos.

Esta función fue estudiada por Lucas y Kempner antes de que Smarandache le asignara su propio nombre. Por eso, la sucesión de sus valores recibe el nombre de “números de Kempner”, y es esta:

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, 5, 31, 8, 11,… (http://oeis.org/A002034)

Aprovecha estos valores para comprobar la definición de la función en cada uno de ellos. Pronto descubrirás casos particulares, que podrás ampliar en la próxima entrada de este blog. Por ejemplo, adelantamos que el valor de S(p) para un número primo p es el mismo número: S(p)=p para p primo, o que S(n!)=n. Lo veremos más adelante.

En las dos primeras entradas de esta serie nos dedicaremos sólo a intentar construir algoritmos que reproduzcan los valores de la función. Comenzaremos por el más ingenuo y seguiremos con otros que contienen más artificio. Ante todo hay que notar que S(N)<=N, ya que todo número es divisor de su propio factorial. Esto nos beneficia, porque las búsquedas terminan en N.

Algoritmo “ingenuo”

Para encontrar el valor de S(n) bastará recorrer todos los factoriales desde 1 hasta n! y detenernos en el primero que sea múltiplo de n. El gran inconveniente de este procedimiento es que pronto se sobrepasará la capacidad de cálculo de la herramienta que usemos, especialmente si es una hoja de cálculo. Lo intentamos para Excel:

Public Function smar1(x)
Dim n, f
Dim seguir As Boolean

If x < 3 Then smar1 = x: Exit Function ‘Para x=1,2 S(x)=x
n = 1: f = 1  ‘Recorremos naturales desde 2 hasta x y f es su factorial
seguir = True  ‘variable para controlar el WHILE-WEND
While n <= x And seguir  ‘mientras no se llegue a n (cota natural) ni a la solución
n = n + 1: f = f * n  ‘se incrementa n y su factorial
If f = Int(f / x) * x Then seguir = False  ‘se ha llegado a un factorial divisible entre n
Wend
smar1 = n  ‘el valor de la función es el entero cuyo factorial es divisible
End Function

El algoritmo es sencillo, pero como se usan factoriales, aunque sea de forma indirecta, comete errores muy pronto (en Excel): De hecho, los valores para n=23 y n=29 ya son erróneos (destacados en rojo en la imagen):



Así no llegaremos muy lejos. Podíamos intentarlo en PARI a ver si funciona mejor (hemos eliminado los casos x=1,2):

smar1(x)={local(n=1,f=1,s=1);while(n<=x&&s,n+=1;f*=n;if(f(x==f\x,s=0));return(n)}
{for(i=3, 90, print1(smar1(i), ", "))}

Es el mismo algoritmo traducido a PARI. Para los 90 primeros casos funciona bien:

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, 5, 31, 8, 11, 17, 7, 6, 37, 19, 13, 5, 41, 7, 43, 11, 6, 23, 47, 6, 14, 10, 17, 13, 53, 9, 11, 7, 19, 29, 59, 5, 61, 31, 7, 8, 13, 11, 67, 17, 23, 7, 71, 6, 73, 37, 10, 19, 11, 13, 79, 6, 9, 41, 83, 7,…

Hemos probado el algoritmo para valores mayores y parece funcionar, pero nosotros deseamos mejorar el proceso para hoja de cálculo.

Algoritmo con el MCD

Este algoritmo lo hemos creado para el blog, pero es posible que ya esté publicado con anterioridad. Así que no se reclamará ninguna autoría.

La idea base es la de que el número dado va tomando factores de los elementos del conjunto 1, 2, 3, 4, 5,… hasta agotarlos todos. Por ejemplo, para encontrar S(18) necesitamos contar con los factores 2, 3, 3. Si tomamos los primeros números, el 18 podrá tomar de cada uno de ellos el MCD. La idea que lo simplifica todo es que una vez encontrado un factor, dividimos entre él para ir disminuyendo el valor primitivo (en este caso el 18).

Lo vemos en esta tabla:



Repetimos la idea: Elegimos un número, lo comparamos con 1, 2, 3, 4, 5,… dividiendo entre el MCD de ambos. Cuando el número llegue a 1, hemos terminado, y la solución será el último término de 1, 2, 3, 4, … probado. Lo explicamos de nuevo con n=250. Si el MCD es 1, lo saltamos:

MCD(250,2)=2, luego dividimos entre 2 y nos queda N=125
El MCD con 3 y 4 es 1, luego los saltamos
MCD(125,5)=5, dividimos N=25
Saltamos a 10: MCD(25,10)=5 y dividimos N=5
Saltamos al 15: MCD(5,15)=5, y al dividir obtenemos N=1. Ya hemos terminado: la solución es 15: S(250)=15

La ventaja de este método estriba en que no se multiplica, sino que se divide, con lo que los valores disminuyen hasta 1, evitando el desbordamiento en hoja de cálculo. Aunque se puede usar el cálculo manual con la misma hoja (sería muy pedagógico intentarlo en la Enseñanza), hemos implementado la función SMAR2, mucho más rápida, al disminuir los datos y poder eliminar una sentencia IF:

Public Function smar2(x)
Dim n, x1, m

If x < 3 Then smar2 = x: Exit Function
n = 1: x1 = x ‘la variable x1 recoge los cocientes entre x y el MCD con 1, 2, 3, 4,…
While x1 > 1 ‘se sigue mientras el cociente no llegue a 1
n = n + 1 ‘nuevo valor para los primeros números
m = mcd(n, x1) ‘encontramos el MCD
x1 = x1 / m ‘no hay que usar un IF porque es divisible con seguridad
Wend
smar2 = n
End Function

Con esta nueva implementación podemos calcular S(x) para valores mayores. Lo hemos intentado para comprobar que S(200001)=409 y se ha conseguido de forma prácticamente instantánea. Coincide con el resultado obtenido con PARI.

El problema está en que necesitas la función MCD. Aquí tienes una:

Public Function mcd(a1, b1)
Dim a, b, r

'Halla el MCD de a1 y b1

r = 1
a = a1
b = b1
If b = 0 Then b = 1
If a = 0 Then a = 1
While r <> 0
r = a - b * Int(a / b)
If r <> 0 Then a = b: b = r
Wend
mcd = b
End Function

Puedes estudiar esta versión muy sintética en PARI:

a(n)={local(m=1,x=n);while(x>1,m++;x=x/gcd(x,m));m}

En la siguiente entrada experimentaremos con algoritmos basados en la descomposición factorial, siguiendo las ideas de Kempner y basados en las propiedades de la función que estudiamos.

viernes, 8 de mayo de 2015

Relaciones entre un número y su sigma (2)

En la anterior entrada estudiamos casos curiosos de números poligonales con sigma triangular.
Seguimos hoy con otros casos:

Sigma cuadrada

Busquemos ahora los casos en los que SIGMA(N) sea un número cuadrado.
La lista de todos ellos ya está publicada en https://oeis.org/A006532. Son  estos:

1, 3, 22, 66, 70, 81, 94, 115, 119, 170, 210, 214, 217, 265, 282, 310, 322, 343, 345, 357, 364, 382, 385, 400, 472, 497, 510, 517, 527, 642, 651, 679, 710, 742, 745, 782, 795, 820, 862, 884, 889, 930, 935, 966, 970, 1004, 1029, 1066, 1080, 1092,…

Por ser SIGMA una función multiplicativa, y como el producto de dos cuadrados es otro cuadrado, se cumplirá (ver A006532) que si dos términos de esta sucesión son primos entre sí, su producto pertenecerá también a la sucesión. Por ejemplo, 3  y 70 son primos entre sí, y su producto, 210, también pertenece a las sucesión.

Nosotros ahora distinguiremos algunos casos y presentaremos sucesiones no publicadas.

En primer lugar nos preguntaremos si un número cuadrado puede tener su sigma también cuadrada. La respuesta es afirmativa.

Números cuadrados con sigma cuadrada

Se conocen todos los casos, que están recogidos en https://oeis.org/A008848

1, 81, 400, 32400, 1705636, 3648100, 138156516, 295496100, 1055340196, 1476326929, 2263475776, 2323432804, 2592846400, 2661528100, 7036525456, 10994571025, 17604513124, 39415749156, 61436066769, 85482555876, 90526367376, 97577515876, 98551417041,…

Aquí se ve que son muy escasos, porque estamos exigiendo una condición fuerte.

En esta sucesión no hay cuadrados de números primos. Todos tienen al menos dos factores  distintos. La razón es la siguiente: Si p es primo, SIGMA(p2)=p2+p+1. Si esta expresión ha de ser un cuadrado, se cumplirá p2+p+1=m2, con m>p. De ahí deducimos que p+1=m2 - p2 = (m+p)(m-p), pero esto es imposible porque con tomar sólo m+p ya es mayor que p+1.

El caso contrario sí se puede dar: la sigma de 81 es 112 y la de 400, 312. Es probable que sólo se den esos dos casos.

Tal como procedíamos en la anterior entrada, intentaremos buscar términos de la sucesión que sean triangulares, oblongos o de otro tipo. Primos no pueden ser porque sigma(p)=p+1 si es primo, y tendríamos p+1=m2 y p=m2-1=(m+1)(m-1) y no sería primo salvo el caso de 3.

Triangulares con sigma cuadrada

Este caso no estaba publicado y hemos procedido a ello  en https://oeis.org/A256151

1, 3, 66, 210, 820, 2346, 4278, 22578, 27966, 32131, 35511, 51681, 53956, 102378, 169653, 173755, 177906, 223446, 241860, 256686, 306153, 310866, 349866, 431056, 434778, 470935, 491536, 512578, 567645, 579426, 688551, 799480, 845650, 893116, 963966, 1031766, 1110795, 1200475, 1613706, 1719585, 1857628, 1991010,…

Los hemos obtenido con Excel y con este programa de PARI:

PARI {for(i=1,2*10^3,n=i*(i+1)/2;if(issquare(sigma(n)),print1(n,", ")))}

Algunos de ellos son libres de cuadrados



Como SIGMA es una función multiplicativa y todos los factores son primos, si un número es el producto de primos N=p*q*r*s*…, SIGMA(N)=(p+1)(q+1)(r+1)(s+1)… y deberá tener los factores primos “emparejados”, a fin de que se forme un cuadrado.

Lo vemos con un ejemplo: 210=2*3*5*7,
SIGMA(N)=(2+1)(3+1)(5+1)(7+1)=3*4*6*8=3*3*2*2*2*2*2*2=24^2

Casi todos ellos son múltiplos de 2 o de 3, e incluso de ambos, como puedes ver en su perfil para los primeros primos:


Un caso curioso que no es múltiplo de estos dos primos es el de 32131, producto de los primos 11, 23 y 127, que es triangular porque 32131=11*23*127=253*127=253*254/2, y su sigma, por la propiedad multiplicativa, será Sigma(32313)=12*24*128=212*32, número cuadrado. Se produce el emparejamiento de factores que vimos en anteriores párrafos.

Semiprimos con sigma cuadrada

Si los semiprimos tienen los dos factores primos iguales, no presentan interés, ya que son cuadrados y hemos estudiado ese caso. Si sus factores son distintos,  N=p*q y SIGMA(N)=(p+1)(q+1) ha de ser un cuadrado. Esto exige que las partes libres de cuadrados de p+1 y q+1 sean iguales.
Los números que cumplen esto son:

22, 94, 115, 119, 214, 217, 265, 382, 497, 517, 527, 679, 745, 862, 889, 1174, 1177, 1207, 1219, 1393, 1465, 1501, 1649, 1687, 1915, 1942, 2101, 2159, 2201, 2359, 2899, 2902, 2995, 3007, 3143, 3383, 3401, 3427, 3937, 4039, 4054, 4097, 4315, 4529, 4537, 4702, 4741, 5029, 5065, 5398, 5587, 5729, 6167, 6169, 6457, 6539, 6739, 6769, …

Se pueden reproducir con PARI

{for(i=1,10^4,if(omega(i)==2&&issquarefree(i)&&issquare(sigma(i)),print1(i,", ")))}

También se encuentran con Excel si se dispone de las funciones adecuadas.

Los hemos publicado en https://oeis.org/A256152

En su gráfico de múltiplos vemos que ningún elemento lo es de 3.



Ningún término es múltiplo de 3, por las razones que expondremos en el siguiente párrafo. Llama la atención el predominio de los múltiplos de 7. Una causa probable es que su sigma es 50, el doble de un cuadrado.

Esto nos invita a definir un primo asociado de otro si es el primero que multiplicado por él da un producto con sigma cuadrada. El 3 no tiene asociado, porque es el único primo del tipo k2-1, ya que otro primo de ese tipo sería el producto de dos factores (k+1)(k-1) ambos mayores que 1. Esto nos lleva a que sigma(3) es cuadrada, y su único asociado sería él mismo, pero entonces el semiprimo 3*3 no entrarían en nuestro estudio.

Aquí tienes los primeros (el 3 no tiene y se ha asignado un 1)



Hemos probado a encontrar otro más además del 3 que no tenga asociado. Hemos usado PARI y nos ha resultado que hasta 10000 todos tienen asociado algún primo. Aquí tienes algunos cuyo asociado sobrepasa 10^6:



Llama la atención el asociado a 7603

Es probable que sea cierta la conjetura de que todo primo mayor que 3 posee un asociado tal que su producto tenga sigma cuadrada.

Otros casos

Podemos intentar buscar situaciones nuevas. Nosotros no lo haremos, pero aquí tienes alguna propuesta por si deseas completarla y publicarla en OEIS:

Oblongos con sigma cuadrada

210, 930, 2652, 26082, 34782, 42642, …

Triangulares con sigma oblonga

6, 28, 55, 496, 666, 780, 1540, 2145, 6441, 6903, 8128,…

Entre ellos están los números perfectos.

Intenta completarlas a más términos.