martes, 28 de abril de 2015

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 2k(2k-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.

viernes, 17 de abril de 2015

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

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

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

Condiciones iniciales: X0=3   X1=0  X2=2 Ecuación de recurrencia: Xn= Xn-2+Xn-3

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

X0=1   X1=1  X2=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á x3-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






martes, 7 de abril de 2015

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=k2. 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:

4p2-4p-8=8k2

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

X2-8Y2=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