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=p₁p₂p₃…p_k con p_i primo y p₁<p₂<p₃<…<p_k,   S(n)= p_k

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=p^k con k<=p, S(n)=p*k

Si n es potencia de un primo p_k, é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=p^k 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, 2² en el 4, 2¹ en 6 y 2³ 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 p^k 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(p^k), 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.

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.

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(p²)=p²+p+1. Si esta expresión ha de ser un cuadrado, se cumplirá p²+p+1=m², con m>p. De ahí deducimos que p+1=m² - p² = (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=m² y p=m²-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 k²-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.

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

La función SIGMA(N), en su versión más simple, equivale al resultado de sumar todos los divisores de N. A lo largo de los años de existencia de este blog hemos acudido muchas veces a ella, pero hoy la vamos a relacionar con los números poligonales. Muchos resultados están ya publicados, y otros los presentaremos por primera vez.

Sigma triangular

Es fácil que SIGMA(N) sea un número triangular. Los números que cumplen esto los tienes publicados en http://oeis.org/A045746

1, 2, 5, 8, 12, 22, 36, 45, 54, 56, 87, 95, 98, 104, 116, 152, 160, 200, 212, 258, 328, 342, 356, 393, 427, 441, 473, 492, 531, 572, 582, 588, 660, 668, 672, 726, 740, 800, 843, 852, 858, 879, 908, 909, 910, 940, 962, 992,…

Es un estudio curioso el ver cómo son los números cuya sigma es triangular. Encontrando sus factores primos descubrimos que pueden ser de muchos tipos. Vemos algunos casos:

N número primo

Sólo existen dos casos de número primo con sigma triangular, el 2 y el 5. No hay más. Analizamos:

En el caso de P primo, SIGMA(N)=P+1. Si esta expresión es triangular, se deberá cumplir que t=m(m+1)/2 -1 debe ser primo, es decir: t=(m^2+m-2)/2=(m-1)(m+2)/2, con m>1, ha de serlo. En ese caso debe quedar un solo factor en el producto del numerador.

Puede ocurrir uno de estos hechos: (a) m-1=1, m=2 y t=1*4/2=2, que sería el primer caso. (b) m-1=2, m=3, t=2*5/2=5, que sería la otra solución (c) Cualquier otro valor positivo de m, 4, 5, 6,…produciría dos factores mayores que 2, uno de ellos par, que al dividir entre 2, seguirían teniendo dos factores y t no sería primo.

Puedes comprobarlo con este programa en PARI:

{n=2;while(n<10^8,if(ispolygonal(sigma(n,1),3),print(n);n=nextprime(n+1))}

Esto no demuestra nada, pero sólo obtendrías como soluciones 2 y 5.

N número triangular

Se han encontrado muchas soluciones de este caso, en el que un número triangular produce una sigma también triangular. Están publicadas en http://oeis.org/A083674

1, 36, 45, 23220, 105111, 135460, 2492028, 5286126, 6604795, 14308575, 45025305, 50516326, 54742416, 99017628,…

Entre ellos se presenta un caso muy curioso, y es que los números triangulares

2492028=2232*2233/2 y 6604795=3634*3635/2 tienen la misma suma de divisores, el triangular 8386560=4095*4096/2

Puedes reproducir la sucesión con PARI:

{(for (n=1,n=10^8,if(ispolygonal(n, 3) && ispolygonal(sigma(n), 3),print(n))))}

N número cuadrado

Este caso no estaba publicado, y lo hemos hecho en https://oeis.org/A256149 . Estos son los cuadrados cuya sigma es triangular:

1, 36, 441, 5625, 6084, 407044, 8444836, 17388900, 35070084, 40729924, 57790404, 80138304, 537822481, 588159504, 659821969, 918999225, 1820387556, 2179862721, 2599062361, 5110963081, 28816420516, 36144473689, 46082779561, 55145598561, 147225690000, 163405126756, 216560860321, 406452151296, 919585102500,...

Por ejemplo, el cuadrado 441=21^2 tiene como suma de divisores el triangular 741=441+147+63+49+21+9+7+3+1=38*39/2.

Hemos comprobado los primeros con Excel y después completado con este programa PARI

{for(i=1,10^6,n=i*i;if(ispolygonal(sigma(n), 3),print1(n,", ")))}

Un comentario de Alonso del Arte a propósito de la abundancia de múltiplos de 3 me dio la idea de tratar los distintos tipos de múltiplos como un perfil de frecuencias, como se obtiene, por ejemplo al estudiar la distribución de proteínas o de los genes. He aquí el resultado para los seis primeros primos:

Vemos que los más abundantes son los múltiplos de 2 y de 3, con sólo un caso para el 11. Interpreto que esta es una configuración típica de cuando el resultado es casual en gran parte. Cuanta menos teoría lo respalde, más abundarán los factores pequeños, que se prestan más a casualidades.
Una situación similar nos descubre la gráfica de los divisores mínimos de cada elemento:

En este caso llama la atención el valor de 41, 36144473689=41^2*4637^2, cuya suma de divisores es el triangular 272233*272234/2. Son hechos que aparecen porque todos los factores encajan, sin que nosotros podamos adivinarlo.

N número oblongo

Esta posibilidad tiene su interés, porque nos encontraremos con los dobles de los números perfectos. No estaba publicada y la hemos presentado en  https://oeis.org/A256150.

2, 12, 56, 342, 992, 16256, 17822, 169332, 628056, 1189190, 2720850, 11085570, 35599122, 67100672, 1147210770, 1317435912, 1707135806, 7800334080, 11208986256, 13366943840, 17109032402, 17179738112, 46343540900, 58413331032, 83717924940, 204574837700, 274877382656, 445968192672, 589130699852, 632523563282, 718650391556, 772888018740,…

Hemos comprobado los primeros con Excel y después ampliado con este programa PARI porque resultan números demasiado grandes para una hoja de cálculo.

{for (i=1,i=10^6,n=i*(i+1);if(ispolygonal(sigma(n), 3),print(n)))}

Es rápido por la forma de generar los oblongos n=i*(i+1) durante el proceso.

Entre ellos están los dobles de los perfectos, 12, 56, 992, 16256, 67100672,…que tienen la forma 2^k(2^k-1)  con el paréntesis un primo de Mersenne, y son oblongos. Para calcular su función sigma basta recordar que es una función multiplicativa y que al ser el paréntesis primo, su único divisor propio es 1:

Como ambos paréntesis representan primos entre sí, podemos multiplicar:

Este resultado es triangular, luego pertenecerán a esta sucesión todos los dobles de perfectos.
Les hemos hecho el análisis de los múltiplos de los primeros primos con este resultado:

Los valores están de acuerdo con un proceso fuertemente influido por el azar. El valor para el 2 es lógico, porque todos los oblongos son pares.

Sucesión de Padovan

En una entrada anterior estudiamos la sucesión de Perrin

(http://hojaynumeros.blogspot.com.es/2014/11/sucesion-de-perrin.html).

La de hoy, de Padovan, es muy parecida, por lo que se recomienda leer antes la entrada enlazada. Recordamos:

La sucesión de Perrin es recursiva de tercer orden homogénea, por lo que necesita tres valores iniciales y que X(n) dependa de los tres valores anteriores X(n-1), X(n-2) y X(n-3) mediante la relación

X_n= A*X_n-1+B*X_n-2+C*X_n-3

En este caso particular sólo depende de los dos últimos, y no de X(n-1). Concretando:

Condiciones iniciales: X₀=3   X₁=0  X₂=2 Ecuación de recurrencia: X_n= X_n-2+X_n-3

Pues bien, la sucesión de Padovan es similar, pero con distintos valores iniciales:

X₀=1   X₁=1  X₂=1

Como con la anterior, podemos construirla con nuestra herramienta de hoja de cálculo adaptada a las sucesiones recurrentes de tercer orden.

(http://hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#recurre2)

Escribimos los coeficientes 0, 1,1 y los valores iniciales 1, 1, 1:

Y obtenemos:

Son los números espirales de Padovan contenidos en http://oeis.org/A134816. Existen otras variantes de esta sucesión, pero nos dedicaremos en esta entrada a la que comienza con 1, 1, 1. Por el carácter de este blog, omitiremos propiedades gráficas, como la espiral de triángulos, que puedes consultar en otras páginas.

Relaciones recurrentes

Para abreviar a los términos de esta sucesión los identificaremos como P(n).

En muchas páginas web podrás encontrar otras relaciones recurrentes además de la de la definición, P(n)=P(n-2)+P(n-3). Aquí sólo comentaremos alguna dejando como ejercicio el análisis de las demás.

(1)  P(n)=P(n-1)+P(n-5)

Se puede verificar por inducción: Se cumple en los primeros términos, como puedes comprobar con la misma hoja de cálculo:

Extensión a P(n+1)

P(n+1)=P(n-1)+P(n-2)=P(n-2)+P(n-6)+P(n-3)+P(n-7)=P(n)+P(n-4), luego se cumple la inducción completa.

(2) P(n)= P(n-2)+P(n-4)+P(n-8)

Sólo veremos los primeros términos con hoja de cálculo y dejaremos la demostración por inducción como ejercicio.

Hay más relaciones de este tipo. Las tienes en

http://es.wikipedia.org/wiki/Sucesi%C3%B3n_de_Padovan

Una interesante es la que relaciona la sucesión de Perrin con la de Padovan:

Perrin(n)=P(n+1)+P(n-10)

Con nuestra hoja hemos construido este esquema para que compruebes que se cumple para los primeros términos. El justificarlo por inducción es fácil por compartir ambas sucesiones la misma fórmula de recurrencia.

Ecuación característica

La ecuación característica correspondiente será x³-x-1=0, es decir, la misma que para la sucesión de Perrin. Con el botón Resolver de esa hoja obtienes las tres soluciones de la ecuación, una real y dos complejas

La solución real 1,32471… es el número plástico y,  que ya presentamos en el estudio de la sucesión de Perrin. También la sucesión de Padovan se acerca progresivamente a las potencias de este número, como puedes ver en este cálculo realizado con nuestra hoja:

Función generatriz

Usando procedimientos similares a los que explicamos para las recurrentes de segundo orden, se puede demostrar que la función generatriz es

Puedes comprobar que esta es la F.G. adecuada efectuando este desarrollo en PARI

write("sucesion.txt",taylor((3-x^2)/(1-x^2-x^3),x,20))

Crea un archivo de texto “sucesión.txt” en la misma carpeta de PARI y verás cómo te reproduce la sucesión:

x + x^2 + x^3 + 2*x^4 + 2*x^5 + 3*x^6 + 4*x^7 + 5*x^8 + 7*x^9 + 9*x^10 + 12*x^11 + 16*x^12 + 21*x^13 + 28*x^14 + 37*x^15 + 49*x^16 + 65*x^17 + 86*x^18 + 114*x^19 + O(x^20)

Los coeficientes del polinomio reproducen la sucesión de Padovan, con el índice desfasado en 1 porque hemos comenzado con el valor 0.

Relación con cuestiones combinatorias

Todas las sucesiones recurrentes suelen tener relación con particiones y composiciones (particiones con orden), porque su generación a partir de elementos anteriores puede coincidir. En el caso de la sucesión de Padovan también existen esas relaciones. Veamos:

P(n) coincide con las composiciones de n+2 en sumandos 2 y 3

En efecto, P(0)=P(1)=P(2) valen 1, que son las formas de descomponer 2, 3 y 4 en sumandos ordenados 2 y 2. P(3)=2 porque 5=2+3=3+2. P(4)=2, ya que 6=3+3=2+2+2.

Con nuestra hoja Cartesius (aún no publicada) se pueden comprobar estos desarrollos. Por ejemplo, para el caso de 8, plantearíamos:

Aunque no conozcas su sintaxis, basta explicarte que hemos pedido que desde 1 hasta 8, usando el conjunto {2,3} busque todas las sumas iguales a 8 con repetición.

Efectivamente, resultan 4=P(6)

En general, cualquier suma correspondiente a N resultará de añadir un 2 a las composiciones de N-2 y un 3 a las de N-3, por lo que su generación es idéntica a la de la sucesión de Padovan. Tal como nos ocurrió con la sucesión de Narayana (http://hojaynumeros.blogspot.com.es/2015/01/sucesion-de-las-vacas-de-narayana.html), esta descomposición da lugar a la expresión de los números de Padovan como suma de números combinatorios. En http://en.wikipedia.org/wiki/Padovan_sequence tienes uno de ellos:

Así, por ejemplo, en el desarrollo para k=11 con Cartesius vemos clara la descomposición en números combinatorios (recuerda que las permutaciones con repetición y dos elementos equivalen a esos números)

Para quienes apreciáis las técnicas de programación, insertamos esta función por si queréis implementarla en vuestra hoja de cálculo:

Public Function padovan(n)
Dim p, q, t, s, i, nn

 nn = n + 2: p = Int(nn / 2): q = nn - 2 * p: t = 0

While p >= q
s = 1: For i = 0 To q - 1: s = s * (p - i) / (q - i): Next i 'Calcula el número combinatorio
t = t + s 'Suma los números combinatorios
p = p - 1: q = q + 2
Wend
padovan = t
End Function

Algunas curiosidades sobre la antisigma

Se ha publicado algo, no mucho, sobre algunas propiedades y curiosidades acerca de la antisigma. Destacamos algunas y aportaremos otras.

Antisigmas cuadradas

La antisigma de un número puede ser un cuadrado. Esto ocurre en los siguientes números:

1, 2, 5, 6, 14, 149, 158, 384, 846, 5065, 8648, 181166, 196366, 947545, 5821349, 55867168, 491372910, 4273496001, 40534401950,… http://oeis.org/A076624

En el caso de números primos, como el 2 y el 5, deberemos resolver una ecuación diofántica de segundo grado, ya que (p+1)(p-2)/2=k². Donovan Johnson ha encontrado la recurrencia que genera otros casos en la página de OEIS enlazada. El siguiente primo sería 8946229758127349.

Nosotros también nos aproximaremos al tema mediante una ecuación de Pell. Transformamos la igualdad multiplicando todo por 4 y desarrollando:

4p²-4p-8=8k²

 Completamos un cuadrado y queda: (2p-1)²-8k²=9 Cambiamos de variables haciendo X=(2p-1)/3  Y=k/3, obteniendo la ecuación de Pell

X²-8Y²=1

Tenemos una herramienta para resolver esta ecuación, en la dirección

http://www.hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#pell

Aplicándola para el caso D=8 obtenemos varias soluciones para X e Y

Si a ellas añadimos la solución trivial X=1, Y=0 y deshacemos el cambio X=(2p-1)/3 mediante p=(3X+1)/2, obtendremos todas las soluciones para p. En la imagen que sigue hemos añadido una columna para saber si son primos o no los valores obtenidos, y vemos (los de color rojo) que coinciden con los valores primos de la sucesión:

Con una herramienta más potente podemos seguir con las iteraciones y llegar a la siguiente solución prima dada por Donovan Johnson e incluso sobrepasarla. No damos muchos detalles por no alargar.

La iteración de Pell en este caso es
(ver la teoría en http://hojaynumeros.blogspot.com.es/2010/02/ecuacion-de-pell.html)

La aplicamos reiteradamente en PARI comenzando con X=1 Y=0, y tomamos nota de las soluciones de X que son primas. Obtendremos un listado en el que aparecerán los cuatro primos obtenidos aquí, más el propuesto por Donovan Johnson, 8946229758127349, y alguno más.

Programa en PARI

{x=1;y=0;for(n=1,60,m=(3*x+1)/2;if(isprime(m),print1(m,", "));p=3*x+8*y;q=x+3*y;x=p;y=q)}

Resultado obtenido:

2, 5, 149, 5821349, 8946229758127349, 13748537282247342677718149, 828287615476676026361062299923143963349, 32470531080787945457870876690417952137154149,

Aparecen tres nuevas y enormes soluciones. Este tipo de descubrimientos hacen que sigamos con estos temas a pesar del cansancio de los años.

Antisigmas triangulares

Sólo hemos encontrado el caso ya estudiado de las potencias de 2. No parece que haya ningún número que no sea potencia de 2 y tenga antisigma triangular.

Antisigmas primas

Estos son los números con antisigma prima:

3, 4, 10, 21, 34, 46, 58, 70, 85, 93, 118, 129, 130, 144, 178, 201, 226, 237, 262, 298, 310, 322, 324, 325, 333, 334, 346, 382, 406,... http://oeis.org/A200981

Sólo figura entre los primos el 3, porque si (p+1)(p-2)/2 ha de ser primo, si p es mayor que 3 aparecerían dos factores al menos en la antisigma.

Llama la atención la abundancia de semiprimos. Según la fórmula que vimos en la entrada anterior, deberá darse la casualidad de que si N=pq, se dé que pq(pq+1)/2-(p+1)(q+1) sea primo. Por ejemplo, 46=2*23 y su antisigma sería 46*47/2-3*24=1009, que es primo.

Antisigma y sigma coprimas

Terminamos por ahora con otra curiosidad: Números en los que sigma y antisigma son primos entre sí:

4, 9, 10, 16, 21, 22, 25, 34, 36, 46, 49, 57, 58, 64, 70, 81, 82, 85, 93, 94, 100, 106, 118, 121, 129, 130, 133, 142, 144,…

Al principio parece que pertenecerán a ella los cuadrados, pero a partir de 196 hay muchos que no cumplen esta propiedad: 441, 1521, 1764, 3249, 3600,...

En esta sucesión todos son compuestos, pues un primo p tiene como sigma p+1 y como antisigma (p+1)(p-2)/2, con lo que el factor (p+1)/2 divide a ambas para un primo mayor que 2. Y en el caso del 2, su sigma es 3 y su antisigma 0, que no tiene divisores

Antisigma de un número natural

Al igual que se ha definido la función SIGMA(N) como la suma de todos los divisores de N (incluido él mismo), podemos definir la ANTISIGMA(N), que es la suma de los números menores que N y que no lo dividen, Por ejemplo, la antisigma de 8 sería la suma de 3+5+6+7=21, y sigma(8) es igual a 1+2+4+8=15.

Los valores de esta función antisigma son los siguientes, que están incluidos en https://oeis.org/A024816

0, 0, 2, 3, 9, 9, 20, 21, 32, 37, 54, 50, 77, 81, 96, 105, 135, 132, 170, 168, 199, 217, 252, 240, 294, 309, 338, 350,…

Comprueba que para el 8 se da el valor de 21, que es el que hemos calculado.

No se debe confundir con la indicatriz de Euler, que cuenta los números primos con N. En la suma correspondiente al 8 figura el 6, que no divide al 8, pero tampoco es primo con él. Con estos números primos con N se puede formar también una suma. Nosotros, para entendernos, la llamaremos S_EULER. Puedes consultar la página https://oeis.org/A023896. En el caso del 8, la suma sería 1+3+7=11 (por convención, se considera el 1 primo con todos los demás números. Esto facilita los cálculos). Es evidente que S_EULER(N) será siempre menor o igual que ANTISIGMA(N), porque sus sumandos están incluidos en la otra suma.

La suma de SIGMA(N) y ANTISIGMA(N) es muy fácil de calcular, ya que se trata de sumar todos los números desde 1 hasta N, y esto sabemos que es igual a N(N+1)/2.

Relación fundamental: SIGMA(N)+ANTISIGMA(N)=N(N+1)/2

Si no se dispone de la función SIGMA, también se puede encontrar ANTISIGMA. Por ejemplo, puedes usar este código Basic de Excel:

Public Function antisigma(n) 'suma los no divisores
Dim i, a

a = 0
For i = 1 To n
If n / i <> n \ i Then a = a + i  ‘no es divisor de n, y se suma
Next i
End If
antisigma = a
End Function

Si ya tienes implementada SIGMA, el desarrollo es mucho más simple:

Public Function antisigma(n)
antisigma = n * (n + 1) / 2 - sigma(n)
End Function

Así lo haremos en PARI

antisigma(x)=x*(x+1)/2-sigma(x)

Antisigmas calculables mediante una fórmula 

Nos referimos a una fórmula sencilla, sin tener que proceder a una descomposición complicada en factores primos.

Antisigma de un número primo

Si p es primo, es posible encontrar una fórmula para la antisigma. En efecto, por la relación anterior, antisigma(p)=p(p+1)/2-sigma(p)=p(p+1)/2-(p+1)=(p²+p-2-2p)/2=( p2-p-2)/2=(p+1)(p-2)/2, Hemos usado el hecho de que la sigma de un primo p equivale a p+1, como es evidente.

Así que si p es primo, es válida la fórmula

Por ejemplo, antisigma(7)=8*5/2=20, antisigma(13)=14*11/2=77

Es curioso el hecho de que esta función sea evaluable directamente en este caso. Constituye una relación cuadrática, y su diagrama conjunto forma una parábola.

En los números compuestos hay que descomponer en factores primos previamente, y se pierde así una relación tan directa.

Antisigma de una potencia de 2

Si N=2^k, entonces sigma(N)=1+2+4+8+…2^k=(2^k+1-1)/(2-1)=2^k+1-1. Aplicamos la relación fundamental y nos queda:
Antisigma(2^k)=2^k(2^k+1)/2-(2^k+1-1)=(2^2k+2^k-2*2^k+1+2)/2=(2^2k-3*2^k+2)/2
(2^k-2)(2^k -1)/2=(N-1)(N-2)/2  y también (2^k-1-1)(2^k -1) (ver http://oeis.org/A134057)

La antisigma de una potencia de 2 es un número triangular. Si la potencia es N, su antisigma hemos visto que es (N-1)(N-2)/2, el triangular de orden N-1. Lo puedes comprobar en este listado:

Antisigma de semiprimos con factores diferentes

Un caso también sencillo es el de semiprimos producto de dos primos diferentes. Si N=pq, con p y q primos, es posible encontrar una fórmula sencilla para la antisigma. Los valores son los siguientes:

N      Antisigma(N)
6 9
10 37
14 81
15 96
21 199
22 217
26 309
33 513r
34 541
35 582
38 681

Busquemos la fórmula que los genera: La sigma de un número primo p es p+1, luego de q será q+1. Como es una función multiplicativa, la sigma del producto equivaldrá a (p+1)(q+1) y por tanto la antisigma pq(pq+1)/2-(p+1)(q+1). Parece que queda mejor así sin intentar simplificarla. La comprobamos: 35=5*7, luego su antisigma será 35*36/2-6*8=35*18-48=582

Antisigma de la potencia de un primo

Es otro caso sencillo. La sigma de una potencia de primo pr viene dada por 1+p+p²+p³+…+ p^r, es decir:

Por tanto, la antisigma vendrá dada por

Lo comprobamos: según el primer listado, la antisigma de 27 es 338, y según esta fórmula se obtendría

Asig(33)=27*28/2-(81-1)/2=338