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.

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


viernes, 27 de marzo de 2015

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)=(p2+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=2k, entonces sigma(N)=1+2+4+8+…2k=(2k+1-1)/(2-1)=2k+1-1. Aplicamos la relación fundamental y nos queda:
Antisigma(2k)=2k(2k+1)/2-(2k+1-1)=(22k+2k-2*2k+1+2)/2=(22k-3*2k+2)/2
(2k-2)(2k -1)/2=(N-1)(N-2)/2  y también (2k-1-1)(2k -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+p2+p3+…+ pr, 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

jueves, 19 de marzo de 2015

Autonúmeros (2)


En la entrada anterior descubrimos que todos los números se pueden clasificar en generados por la digitadición de Kaprekar y autonúmeros, que no pueden ser generados. Nos dedicaremos en primer lugar a los generados, y con ellos descubriremos algo más sobre los autonúmeros.

Números generados

Señalamos que los números 2, 4, 6, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 21, 22, 23, 24, 25, 26, 27, 28,… (http://oeis.org/A176995) son los complementarios de los autonúmeros. Todos ellos se pueden expresar como N+SUMACIFRAS(N), por lo que Kaprekar les llamó “generados”. A este número N le podemos llamar generador del mismo, pero desafortunadamente no es único, por lo que no podemos considerarlo una función dependiente del número. En efecto, existen números, como el 103, que poseen más de un desarrollo de este tipo, ya que 103=92+9+2 y también 103=101+1+1.

Podíamos definir una función GENERADOR si para cada N eligiéramos el mayor K que cumple que K+SUMACIFRAS(K)=N, y asignar el valor 0 como generador de los autonúmeros. Así sí sería una función. La función AUTO descrita más arriba y debidamente adaptada nos servirá para este propósito:

Public Function generador(n)
Dim k, g

g = 0
While k < n
If k + sumacifras(k) = n Then g = k
k = k + 1
Wend
generador = g
End Function

En esta tabla puedes comprobar que si a cada número de la derecha le sumas la suma de sus cifras, resulta el de la izquierda, salvo el caso del autonúmero 97 al que le hemos asignado un cero.



Si construimos un diagrama de dispersión entre N y su generador, obtenemos un resultado similar a este:



Abajo los puntos de valor 0 representan a los autonúmeros, y los de arriba parecen presentar pautas lineales escalonadas, pero es una ilusión, ya que esos tramos no se podrían solapar. Lo que ocurre es que en este proceso los números consecutivos aparecen muy cercanos, y dan la impresión de sucederse. Analizaremos estos números con más detalle.

Si representamos un número N de k+1 cifras en base 10, lo estamos generando mediante un polinomio del tipo


Si ahora le sumamos sus cifras (digitadición) se convertirá en


Todos los números generados se podrán expresar de esta forma, y los autogenerados, no.
Según esta fórmula, los dobles de las cifras 1…9 serán todos números generados, y si dos generadores se diferencian sólo en una unidad en las decenas, sus generados se diferenciarán en 11, como ya hemos observado. Si se diferencian en una unidad de las centenas, sus generados se diferenciarán en 101, y así. Estas correspondencias también se dan en casi todos los autonúmeros, pues van la par de estos. No se da en todos.

En este gráfico hemos descompuesto cada autonúmero en relación con los menores de 100, y vemos una repetición de tramos lineales a unas alturas de 1001, 2002, 3003 y 4004. Esto es consecuencia de la fórmula que hemos desarrollado.



Fundamento del algoritmo de Kaprekar


La fórmula

nos da una forma paralela a la de Kaprekar para decidir si N es autonúmero en pocos pasos (es el mismo proceso con otra orientación). Observa que todos los coeficientes son congruentes con 2 módulo 9, con lo que si llamamos G al posible generador de N y SC(G) a la suma de sus cifras, se cumplirá que Nº2SC(G) (mod 9. Para saber esto no hacía falta la fórmula, pues como G es congruente con SC(G) módulo 9 y se cumple que N=G+SC(G), es evidente que N será congruente con el doble de SC(G).

Como 2 es primo con 9, en la ecuación Nº2SC(G) (mod 9 se podrá encontrar una solución S, con lo que G=9*k+S para valores de k no superiores al número de cifras. Lo vemos con el 30: Si N=30, será 30º3º2*SC(G). En este caso SC(G)º6, porque 6+6º3 (mod 9. De esta forma G puede ser 6, 15 0 24. Recorremos de mayor a menor y descubrimos que el 24 vale, porque 24+2+4=30, luego 30 no es autonúmero, sino generado.

Probamos con un número mayor, como 4327, del que ya sabemos por otros medios que es autonúmero:

Hallamos el resto módulo 9 de 4327 (puedes dividir mentalmente o usar la función RESIDUO de Excel) y resulta ser 7. Planteamos 7º2SC(G) (mod 9. También, mentalmente, vemos que SC(G) º8 (mod 9. Por tanto, vamos restando de 4327 números del tipo 9*k+8 hasta ver si la suma de las cifras de la diferencia es ese número:

K=0: 4327-8=4321, y su suma de cifras no es 8.
K=1: 4327-17=4310 y no suman 17
K=2: 4327-26=4301. No suman 26,
K=3: 4327-35=4292. No vale
Acabamos con k=4, porque la suma de cifras ya no puede ser mayor:
K=4: 4327-44=4283, de suma 17, luego tampoco es válido.

Hemos comprobado, con la misma técnica de Kaprekar y distinta presentación, que 4327 es autonúmero. No puede ser generado.

Para los aficionados a la programación, esta es la función que podemos usar:

Public Function esauto3(n)
Dim nc, a, r, h, k
Dim es As Boolean

'número de cifras
a = 1: nc = 0
While a <= n
a = a * 10: nc = nc + 1
Wend
'módulo 9
r = n Mod 9
For k = 0 To 8: If (r - 2 * k) Mod 9 = 0 Then h = k
k = 0: es = True
While k <= nc And es
If sumacifras(n - 9 * k - h) = 9*k+h Then es = False
k = k + 1
Wend
esauto3 = es
End Function

Hemos construido un esquema de hoja de cálculo en el que vemos la equivalencia de las tres funciones que hemos programado en estas entradas. En la imagen tienes un ejemplo:



Sucesiones recurrentes de números generados

Kaprekar estudió también las sucesiones que se forman si a un número cualquiera le vamos aplicando la digitadición tanto a él como a los resultados sucesivos. Por ejemplo, si comenzamos con el 12 tendríamos la sucesión 12, 15, 21, 24, 30,…Evidentemente es infinita, creciente y todos sus elementos, salvo quizás el primero, son generados. Kaprekar destacó que si restamos el último del primero y sumamos las cifras del último, resulta la suma de cifras de todos ellos. Por ejemplo, aquí, 30-12+3=21=1+2+1+5+2+1+2+4+3+0

Aunque el autor le dio mucha importancia, basta recorrer la generación para darse cuenta de su validez: 12+3+6+3+6=30, luego al restar resultarán las sumas de cifras menos la del último. Es una obviedad.