miércoles, 18 de diciembre de 2013

Resultados curiosos de la suma de divisores cuadrados

Engendramos cuadrados

La siguiente sucesión presenta varias propiedades respecto a la suma de los divisores cuadrados (ver entrada anterior) que merece la pena destacar

1764, 60516, 82369, 529984, 2056356, 2798929, 3534400, 18181696, 38900169, 96020401, 97121025, 335988900, 455907904, 457318225, 617820736, 1334513961, 1599200100, 2176689025, 3279852900, 4464244225, 8586616896…(publicada en https://oeis.org/A232554)

Todos ellos son cuadrados tales que la suma de sus divisores cuadrados, incluidos ellos mismos, también es un cuadrado. Sí, puedes volver a leerlo si no lo has captado. En la siguiente tabla puedes comprobar esta propiedad:



En la primera columna figuran los elementos de la sucesión. Hemos prescindido del 1, que también cumpliría la misma propiedad. En la siguiente su descomposición en factores primos, que ya analizaremos. Como en la entrada anterior sugeríamos sumar los divisores cuadrados mediante la función sigma_2 aplicada a la raíz interna, hemos calculado dicha suma en las siguientes columnas, comprobando mediante su raíz cuadrada que se trata de cuadrados perfectos. Finamente también se han calculado los factores de esas raíces.

Se pueden generar con este código en lenguaje PARI:

{for(n=1,10^5,m=n*n;k=sumdiv(m,d,d*issquare(d));if(issquare(k)&&k>>1,print(m)))}

Factorización

Podemos observar que ningún término de la sucesión es potencia de un solo primo.

Con dos factores primos distintos sólo se dan tres casos, que puedes buscar en la tabla, y los primos que intervienen son 7, 41 y 239, curiosamente pertenecientes a la sucesión de primos  p para los que p^2+1 no está libre de cuadrados (ver el documento de Rafael Parra http://hojamat.es/parra/NumerosLDC.pdf y la sucesión https://oeis.org/A224718). En el caso de los tres citados, 7^2+1=2*25^2, 41^2+1=2*29^2 y 239^2+1=2*13^4. Si ahora los multiplicamos dos a dos, obtendremos un factor 2*2=4 multiplicado por dos cuadrados, luego será cuadrado perfecto, como se pedía.

Otra curiosidad es que las sumas de cuadrados son todas pares y muchas de ellas múltiplos de 100. Sus raíces son pares hasta donde hemos buscado. Queda ahí abierta una cuestión para estudiarla con más ciencia que nosotros.

Sucesión derivada

Si multiplicamos los términos de esta sucesión por otro número libre de cuadrados resultará otra sucesión formada por números no cuadrados con suma de divisores cuadrados propios que resulta ser cuadrada:

3528, 5292, 8820, 10584, 12348, 17640, 19404, 22932, 24696, 26460, 29988, 33516, 37044, 38808, 40572, 45864, 51156, 52920, 54684, 58212, 59976, 61740, 65268, 67032, 68796, 72324, 74088, 75852, 81144, 82908, 89964, 93492, 97020……(publicada en https://oeis.org/A232555)

Podemos construir todos los múltiplos de ese tipo hasta una cota, por ejemplo un millón y después ordenarlos en sucesión. Así lo hemos hecho y casi todos los primeros son múltiplos de 1764.

En realidad esta sucesión es parte de otra más amplia en la que aparecen todos los casos, y no sólo estos múltiplos que hemos considerado. Son estos:

Números cuya suma de divisores cuadrados propios es otro cuadrado mayor que 1

900, 3528, 4900, 5292, 8820, 10404, 10584, 12348, 17640, 19404, 22932, 24696, 26460, 29988, 33516, 37044, 38808, 40572, 45864, 51156,  52920, 54684, 58212, 59976, 61740, 65268, 67032, 68796, 72324, 74088, 75852, 79524, 81144, 81796, 82908, 89964, 93492, 97020………(publicada en https://oeis.org/A232556)

En ellos la suma de divisores cuadrados propios es otro cuadrado. Por ejemplo, la suma en el caso de 5292 es  1764+441+196+49+36+9+4+1=2500=50^2, que también es un cuadrado.

Aunque los hemos buscado con funciones de hoja de cálculo, se puede intentar también con PARI. Prueba si quieres este código:

{for(n=1,10^5,k=sumdiv(n,d,d*issquare(d)*(d<n));if(issquare(k)&&k>>1,print(n)))}

Todos los encontrados son múltiplos de 4 y al menos poseen tres factores primos distintos. De ellos, algunos son también cuadrados:

900, 4900, 10404, 79524, 81796, 417316, 532900, 846400, 1542564, 2464900, 3232804, 3334276, 3496900, 12432676, 43850884, 50836900, 51811204, 71470116, 107453956, 236975236, 253892356, 432889636, 544102276, 864948100, 1192597156, 1450543396, 1554094084, 2024820004, 2165413156………(publicada en https://oeis.org/A232557)

No son cuadrados el resto: 3528, 5292, 8820, 10584, 12348,…que resultan ser los múltiplos de la primera sucesión que ya tratamos.

Resumimos:

Sucesiones de cuadrados

(1) Pueden formar un cuadrado sumándoles todos sus divisores cuadrados propios. Nos resultaría la primera sucesión: 1764, 60516, 82369, 529984,…(A232554)

(2) Forman un cuadrado sólo la suma de divisores propios, sin sumarles el número dado. Tendríamos la sucesión: 900, 4900, 10404, 79524, 81796,…(A232557)

Sucesiones de no cuadrados

(3) Números cuyos divisores cuadrados suman otro cuadrado. Son 3528, 5292, 8820, 10584,…(A232555) Son múltiplos de elementos de la sucesión (1)

Sin condicionamiento

(4) La unión de la sucesión (2) con la (3) (A232556)
   
Formamos palindrómicos

Con la suma de divisores cuadrados podemos formar números palindrómicos. Es una simple curiosidad, pero está inédita, que sepamos. Hay dos formas, con divisores cuadrados propios o con todos:

Con divisores propios

Estos son los números en los que la suma de divisores cuadrados propios es un número palindrómico de al menos dos cifras (para eliminar casos triviales):

144, 324, 1089, 1936, 5929, 13225, 30752, 46128, 58564, 76880, 92256, 107632, 125316, 138384, 149769, 153760, 154449, 169136, 199888, 215264, 230640, 261392, 292144, 322896, 338272, 342225, 353648, 378225, 399776, 405769, 445904, 461280, 476656, 507408, 522784, 538160, 568912, 584288, 599664
(Los hemos publicado en https://oeis.org/A232892)

Si expresamos el resultado en una tabla de dos columnas, vemos los resultados palindrómicos a la derecha:

Llama la atención la frecuencia con la que aparece el valor 20202, y prolongando la tabla veríamos muchos más. La razón de esto es que el primer caso, 30752=25*312,  tiene como divisores cuadrados  15376+3844+961+16+4+1=20202, que provienen de los factores 24*312 =15376 y entonces, si multiplicamos ese número por factores libres de cuadrados se volverá a dar el mismo caso. En efecto, según la tabla, los siguientes son: 46128=15376*3, 76880=15376*5, 92256=15376*6, 107632=15376*7,…

La pregunta es por qué no funciona este razonamiento en los primeros casos de la tabla. La respuesta es que esos números son cuadrados y si los multiplicamos por un libre de cuadrados, se convertirían ellos mismos en divisores cuadrados propios, y eso alteraría la suma.

Un código PARI para encontrarlos puede ser

reverse(n)=concat(Vecrev(Str(n)))
palind(n)=(Str(n)==reverse(n)&&n>10)
{for(n=1,10^5,k=sumdiv(n,d,d*issquare(d)*(d<n));if(palind(k),print(n)))}

Con todos los divisores cuadrados

Los primeros números con esta propiedad son

15376, 30752, 46128, 76880, 92256, 107632, 153760, 169136, 199888, 215264, 230640, 261392, 292144, 322896, 338272, 353648, 399776, 445904, 461280, 476656, 507408, 522784, 538160, 568912, 584288, 599664, 630416, 645792, 661168, 707296, 722672, 784176, 814928, 845680, 876432, 891808, 907184, 937936, 953312, 999440,…
(Los hemos publicado en https://oeis.org/A232893)

Todos producen la suma de cuadrados 20202, que ya vimos, y todos son múltiplos del primero 15376 con cociente libre de cuadrados. Esta situación llega hasta el número 2217121, que ya no es múltiplo de 15376 y la suma palindrómica que produce es 2217122, ya que sus únicos divisores cuadrados son él mismo y la unidad.

Código PARI:

reverse(n)=concat(Vecrev(Str(n)))
palind(n)=(Str(n)==reverse(n)&&n>10)
{for(n=1,10^5,k=sumdiv(n,d,d*issquare(d));if(palind(k),print(n)))}

Otras sumas

Podemos intentar lograr números de otros tipos, como triangulares u oblongos, pero los resultados son tan abundantes que pierden su interés. En el caso de los oblongos los primeros resultados son múltiplos de 144. Ahí tienes una exploración.

martes, 10 de diciembre de 2013

Divisores cuadrados


Consideremos el conjunto de divisores de un número natural N que son cuadrados perfectos. Sabemos que el mayor de ellos es la parte cuadrada del número

(ver http://hojaynumeros.blogspot.com.es/2011/05/parte-cuadrada-y-parte-libre.html),

a la que designaremos como PC(N). Si descomponemos N en factores primos


para encontrar la parte cuadrada basta elevar a cada factor primo al mayor número par contenido en cada uno de los exponentes, es decir
(2)

Así, por ejemplo, para encontrar la parte cuadrada de 26460=22*33*5*72 bastará truncar cada exponente a un número par, con lo que quedaría PC(26460)= 22*32*72=1764. A la raíz cuadrada de esa parte se le suele llamar Raíz Interna del número N (ver http://hojaynumeros.blogspot.com.es/2011/12/emparedado-de-cuadrados-2.html)

En este caso la raíz interna de 26460 sería 42=2*3*7.

Todo esto lo recordamos para poder estudiar mejor los divisores cuadrados de un número. Se pueden considerar las siguientes afirmaciones:

Los divisores cuadrados de N coinciden con los de su parte cuadrada.

Si k es divisor cuadrado de N, todos sus exponentes en (1) serán pares, pero ninguno sobrepasará al correspondiente en PC(N), luego será también divisor de esa parte cuadrada. Inversamente, todo divisor de PC(N) lo es también de N.

El número de divisores cuadrados de N coincide con el de los divisores de la raíz interna de N.

Esto es así porque si extraemos la raíz cuadrada a todos los divisores cuadrados de N, es claro que permanecerán los mismos factores primos, pero con sus exponentes reducidos a la mitad, que es la misma operación sufrida por la raíz interna.

En el ejemplo elegido, si esa raíz interna es 42, poseerá ocho divisores, por ser igual a 2*3*7 (aplicando la fórmula del número de divisores resultaría (1+1)(1+1)(1+1)=8). Efectivamente, si buscamos todos los divisores cuadrados de 26460 nos resultan estos ocho: 1764, 441, 196, 49, 36, 9, 4 y 1, que son los cuadrados de los divisores de 42: 42, 21, 14, 7, 6, 3, 2 y 1

Existe una correspondencia biyectiva entre los divisores cuadrados de N y los divisores de su raíz interna, de forma que cada uno de los primeros es el cuadrado de otro del segundo conjunto.

Por ejemplo, para N=1200, su parte cuadrada es 400, su raíz interna 20, y se da la correspondencia entre los divisores de 20 y los divisores cuadrados de 20.



Esto nos da, como hemos visto, un procedimiento para contar los divisores cuadrados de un número, pero también para sumarlos, si recordamos la fórmula de la función sigma_2, que suma los cuadrados de los divisores (ver http://hojaynumeros.blogspot.com.es/2011/03/la-familia-de-las-sigmas-2.html)


Aplicamos esa fórmula a la raíz interna. Esto es importante, porque esa raíz determina el número de divisores cuadrados. En nuestro ejemplo lo haríamos así:

SDC(26460)=(2^4-1)/(2^2-1)* (3^4-1)/(3^2-1)* (7^4-1)/(7^2-1)=5*10*50=2500

Comprueba: 1764+441+196+49+36+9+4+1=2500

Si deseas comprobar este resultado con otros números, con este codigo PARI puedes sumar todos los divisores cuadrados:

print(sumdiv(26460,d,d*issquare(d)))

Sustituyes el ejemplo 26460 por otro número cada vez que lo desees.

Con el Basic de las hojas de cálculo también lo puedes calcular mediante esta función:

public function sumdivcuad(n)
dim i,p,a,s

p=1
s=0
for i=1 to sqr(n)
a=i*i
if n/a=n\a then s=s+a
next i
sumadivcuad=s
end function

Comprueba de varias formas que el número 84000 posee sólo seis divisores cuadrados cuya suma es 546. Usa también la fórmula basada en sigma_2 ((2^6-1)/(2^2-1)*(5^4-1)/(5^2-1)=21*26=546)

Como otras variantes de la función sigma, esta suma de divisores cuadrados es una función multiplicativa, por lo que basta definirla para pr, siendo p un factor primo. Para ello, según (2) tomamos como exponente de su raíz interna (r – r MOD 2)/2, con lo que la suma de los divisores cuadrados será




Por ejemplo, la suma de divisores cuadrados de 2048=211 será igual a (2^12-1)/(2^2-1)=4095/3=1365. Comprobamos: 1024+256+64+16+4+1 = 1365.

En el caso particular de que r sea igual a 2 o a 3 la suma de divisores cuadrados será p2+1. Es muy fácil razonarlo.
Otro caso particular se da cuando la raíz interna está libre de cuadrados, tipo RI(N)=p*q*r*s…, la suma buscada será (1+p2)(1+q2)(1+r2)(1+s2)…Sería el caso, por ejemplo, del número 60500, cuya parte cuadrada es 12100 y la raíz interna 110=2*5*11, libre de cuadrados, por lo que la suma de divisores cuadrados de 60500 debería ser (1+22)(1+52)(1+112)=5*26*122=15860. En efecto, los divisores cuadrados de 60500 suman 12100+3025+484+121+100+25+4+1=15860

En la siguiente entrada encontraremos algunos resultados curiosos sobre esta suma.

martes, 3 de diciembre de 2013

Una curiosidad: permutaciones obtenidas por simulación


El estudio que emprendemos hoy se parece bastante al problema de completar una colección de cromos, que ya tratamos hace unos meses (http://hojaynumeros.blogspot.com.es/2012/05/este-cromo-lo-tengo-repe-1.html)

Pertenece al tipo de problemas de llenado aleatorio de un conjunto, como el de una línea o un cartón de bingo. Estos ejemplos se caracterizan porque la probabilidad de obtención de un nuevo elemento del conjunto depende del número de los ya obtenidos, en el sentido negativo, de ir disminuyendo la probabilidad conforme se llena el conjunto.

Hoy lo experimentaremos con permutaciones. Hace días, jugando con las cifras del número 19913 con el fin de obtener todos los números primos posibles, acudí a la herramienta Combimaq, de hojamat.es (http://hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#combimaq), que me proporcionó la solución exacta, elemental, de 30 permutaciones, 30=5!/(2!2!)=120/4



Me pregunté entonces por la posibilidad de obtener esos resultados mediante simulación. Elegí este procedimiento:

(1) Se fija un conjunto cualquiera de unos pocos elementos, por ejemplo el dado 1, 9, 9, 1, 3, con o sin repetición de elementos.

(2) Lo sometemos reiteradamente a transposiciones aleatorias de sus elementos. Como una permutación se puede  descomponer en dichas transposiciones, cada vez que efectuemos esta operación estaremos creando una permutación del conjunto primitivo. Como es de suponer, después de varios intentos las permutaciones comenzarán a repetirse.

(3) Cada permutación nueva la comparamos con las anteriores, y si es distinta a todas ellas, la incorporamos a la lista de las formadas y seguimos el proceso. Nada nos garantiza que esto agote el conjunto de todas las permutaciones posibles, al igual que una colección de cromos en la que no se intercambian ni se compran puede no llegar a completarse nunca.

(4) El proceso parará si le incluimos un tope, que podría ser el número total de permutaciones que conozcamos previamente. Por ejemplo, en el caso de 19913 serían 30 permutaciones. Si no se indica ningún tope, puede que el proceso llegue a completar el catálogo de permutaciones o bien, cosa improbable, que nunca lo haga, se inicie un ciclo sin fin y haya que interrumpir el proceso (en realidad, esto también puede ocurrir fijado un tope de resultados). Esta interrupción se logra con la pulsación de la tecla ESC (en Excel) o Ctrl+May+ Q en OpenOffice y LibreOffice.

Descripción de la herramienta

Hemos incluido este simulador en http://hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#simulpermu

Funcionamiento

La  hoja principal presenta esta estructura



Escribes los elementos del conjunto en la fila de color verde. En la imagen se  ha elegido aaabbb.

Fijas el número de elementos, porque en esa fila puede haber otros residuales más a la derecha.

Después concretas el tope, o número de permutaciones esperado. En el ejemplo hemos escrito un 0 para que sea el simulador el que llegue al número de permutaciones totales, en este caso 20.

En la parte izquierda verás aparecer los intentos y los resultados. Es normal que se necesiten muchos intentos, y en este caso sin tope, la tardanza nuestra en interrumpir el proceso añadirá más. Por eso, para recuentos o estadísticas es preferible fijar previamente el número esperado de permutaciones.

Junto a cada permutación figura el número de intentos que ha necesitado.

Podemos usar el simulador para reproducir un resultado que ya conocemos. Imaginemos que en un curso de Combinatoria al alumnado le cuesta entender el número de permutaciones que se pueden construir con las letras REDADA. Iniciamos la simulación y observamos que la creación de permutaciones se estabiliza en el número 180













Para entender mejor el proceso, ordenamos la tabla completa mediante las columnas D, E, F,… (no olvides desactivar la opción de “Mis datos tienen encabezados”). De esta forma se entenderá mejor cómo se crean las distintas permutaciones:



En un segundo paso se puede demostrar la fórmula 6!/(2!2!)=720/4=180

Por el contrario, si sabemos, por ejemplo, que el conjunto 17767 presenta 5!/3!=20 permutaciones, planteamos la generación aleatoria con tope 20, y posteriormente ordenamos la tabla:



Podemos observar que las permutaciones se han ordenado de forma creciente (como si fueran cifras de un número) y demuestran mediante formación ordenada que el número de permutaciones vale 20.

Estadísticas de la simulación

Lo anterior presenta un interés relativo, es un mero ejercicio de simulación. Le dotaremos de más potencia realizando algunas estadísticas mediante la inclusión de un generador de series, que repite el proceso cuantas veces deseemos y nos devuelve las estadísticas.

Recuerda que cada permutación viene acompañada de los intentos que se han necesitado para encontrarla. En la imagen figura el desarrollo para generar las permutaciones del conjunto 1234.



Se han necesitado 64 intentos, repartidos como se ve en la imagen, con bastantes oscilaciones aleatorias, aunque con tendencia a crecer. Si deseamos estudiarlos mejor deberemos acudir a series de simulaciones.

La primera permutación sólo ha necesitado un intento. Siempre es así si el conjunto básico no presenta repeticiones (¿por qué?). Aquí el segundo también ha salido a la primera, pero el tercero ya necesita a 2 intentos. Así van aumentando hasta llegar al último, que requirió 16 intentos. Estamos ante una sucesión creciente de incrementos también crecientes.

Para estudiarla mejor pasamos a la segunda hoja de cálculo, en la que disponemos del botón para crear series, y lanzamos una de 1000 repeticiones, para obtener unas medias que se puedan confrontar con una posible teoría o realizar el ajuste a una función. El resultado de esta serie ha sido el siguiente:



¿Se podrá confrontar esto con alguna teoría? En realidad sí, porque el caso de los intentos necesarios para obtener unos éxitos se estudia con la distribución binomial negativa o de Pascal (http://www.uv.es/ceaces/base/modelos%20de%20probabilidad/binegativa.htm).

En nuestro ejemplo sólo se pretende conseguir un éxito y no varios, por lo que la fórmula de los intentos medios es muy simple M=1/p, siendo p la probabilidad de obtener, en nuestro caso, una permutación nueva, y que será del tipo 3/24, 4/24, …

En la imagen se han añadido los resultados que se esperarían según la teoría. Parecen muy ajustados, pero en otros muchos experimentos que hemos realizado se advierte un sesgo, en el sentido de que el número de intentos medios es algo superior a lo esperado, lo que nos hace dudar de la absoluta aleatoriedad del proceso.

En esa misma segunda hoja aparecerán los valores máximos y mínimos del número de intentos. El mínimo, si no hay repeticiones, siempre será 1 y el máximo oscila tanto que no tiene interés una estadística sobre él.

Pues a ver si descubres algo más o amplías el modelo.