lunes, 20 de febrero de 2017

Productos cartesianos condicionados con Cartesius (1) - Variaciones


Iniciamos una serie de entradas que estará basada en “Cartesius”, una herramienta implementada en hoja de cálculo para construir productos cartesianos condicionados, no sólo las clásicas Variaciones, Combinaciones y Permutaciones, sino otros más complejos, como particiones de un número o arreglos que cumplan condiciones específicas, como que el segundo elemento sea promedio de los dos primeros.

Introducción a Cartesius

Esta herramienta la puedes descargar desde

http://www.hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#cartesius

Está implementada en Excel y LibreOffice Calc, con una fiabilidad bastante aceptable, aunque quizás necesite ligeros retoques.

Actúa sobre conjuntos numéricos (hasta doce de ellos), iguales o diferentes, que ocupan cada uno una columna. Por ejemplo, en la imagen se van a combinar dos conjuntos de números pares con otro de números primos:


Sobre ellos se construirá un producto cartesiano que, si no se añaden condiciones, estará formado en este caso por 216 arreglos de tres elementos cada uno. Aquí tienes los doce primeros, que seguirían hasta un total de 216:



Este proceso no tiene interés si no se añaden algunas condiciones. Existen gran variedad de ellas en Cartesius. Las básicas definen los conjuntos y las demás condicionan el producto cartesiano.

Por ejemplo, sobre los conjuntos de arriba se puede exigir que la suma de los elementos sea 17. Esto se consigue en la columna de condiciones, que será el objetivo principal de estas instrucciones previas:



En este ejemplo se construyen los conjuntos, se impone además que la suma sea igual a 17, y se exige, por simplificación, que los elementos estén ordenados en orden creciente. Más adelante explicaremos la sintaxis de cada tipo de condición. Con estas conseguiríamos tres soluciones:


Este es en esencia el trabajo de esta herramienta: la construcción de productos cartesianos de conjuntos numéricos y su posterior condicionamiento. En esta serie de entradas te iremos dando la explicación necesaria para cada ejemplo, remitiéndote, para un estudio más sistemático, a la Instrucciones de uso de la herramienta, que puedes descargar desde la dirección

http://www.hojamat.es/sindecimales/combinatoria/herramientas/cartesius.pdf



Productos cartesianos condicionados

Antes de construir los primeros arreglos con Cartesius (en esta entrada serán variaciones), recordamos conceptos:

Producto cartesiano

El producto cartesiano de dos conjuntos A y B es otro conjunto cuyos elementos son todos los pares posibles formados por un elemento de A y otro de B en ese orden. Se representa como A×B


Imaginemos ahora productos cartesianos de un conjunto consigo mismo o con otros, pero que puede contener varios factores. Por ejemplo, este es el producto cartesiano A×A×A siendo A={1,2}


Una definición alternativa de producto cartesiano es el conjunto de formas de elección de un elemento de cada conjunto de los que forman el producto. Estos son los conjuntos básicos sobre los que trabajaremos. Por efectividad, sólo se estudiarán conjuntos de números naturales. Si ahora les imponemos condiciones (más adelante aprenderás cómo), obtendremos, por ejemplo, combinaciones con repetición, ya estudiadas en Combinatoria:


Con otro tipo de condiciones podemos también obtener particiones de un número en sumas. Aquí tienes las particiones del número 11 en sumas de impares:


A lo largo de varias entradas aprenderemos el manejo de la hoja Cartesius mediante ejemplos, independientemente de la lectura directa de las Instrucciones de uso. Comenzaremos con la aplicación de esta herramienta a los problemas clásicos de la Combinatoria.



Recorrido por los problemas

Dedicaremos varias entradas a los arreglos básicos de la Combinatoria, pero a cada uno le añadiremos condiciones que no suelen figurar en los libros de texto. Simultáneamente nos iremos familiarizando con los formatos de las condiciones en Cartesius.

Variaciones con repetición

Recordamos que un producto cartesiano es el conjunto de formas de elección de un elemento de cada conjunto de los que forman el producto. Así, del conjunto {1, 2, 3} multiplicado por sí mismo tres veces obtendríamos este producto cartesiano:



Hay 27 formas de elegir un elemento de cada conjunto factor. Coincide con 3^3=27. En general, si el conjunto posee m elementos y lo tomamos n veces, el número de elementos del producto cartesiano sería

Esta fórmula la conocemos desde la Enseñanza Media, y es la correspondiente a las variaciones con repetición. En efecto, la operación básica de Cartesius es formar estas variaciones, a las que también podríamos nombrar como producto cartesiano sin condicionar. Si después imponemos condiciones, obtendremos combinaciones, permutaciones, particiones, y otros subconjuntos del producto cartesiano que no reciben nombre, como sumas de cuadrados con total dado, descomposición de un número en suma de triangulares y otros similares que iremos viendo.

Al ser la operación más sencilla, se obtiene escribiendo sólo dos condiciones. Por ejemplo, para formar las variaciones con repetición del conjunto {1,2,3,4} tomadas de 3 en 3 bastarían estas:

XTOTAL=3
XT=1..4

No necesita más, pues si no le indicamos nada, repite y tiene en cuenta el orden (producto cartesiano) Es el arreglo básico en Cartesius.

Tu primer arreglo de números

Abre Cartesius. Busca su primera hoja Planteamiento. Si contiene datos, puedes usar los botones Borrar condiciones y Borrar datos, para verlo todo limpio. Escribe después en la zona de condiciones, celda N10, la condición XTOTAL=3. Significa que el conjunto que vas a definir lo combinarás consigo mismo en un producto cartesiano de tres factores. El TOTAL se refiere al número de columnas que se rellenarán.

En una celda más abajo, la N11, escribe: XT=1..4. Esto significa que trabajarás en todas las columnas con los números que van del 1 al 4.



Si ahora pulsas el botón Iniciar, se pasará automáticamente a la hoja Producto y verás el desarrollo de las 64 variaciones obtenidas (4^3). Aquí tienes las primeras:


Si vuelves a la hoja Planteamiento observarás que las columnas se han rellenado según tus deseos:



Aunque sea adelantar información, añade otra condición, XT=ETIQ(PRIMO), y tus datos cambiarán a los cuatro primeros números primos después de pulsar Iniciar.



Las variaciones seguirían siendo 64, porque no hemos condicionado el producto cartesiano, sólo los datos.

Por tanto, identificaremos las variaciones con repetición con los productos cartesianos sin condicionar. Prueba a simular la tirada simultánea de tres dados y verifica que obtienes 216 elementos en el producto cartesiano, porque las tiradas de cada dados se pueden repetir. Sólo tienes que definir XTOTAL=3 y XT=1..6. Inténtalo.

Variaciones sin repetición

No siempre deseamos elegir un elemento de cada conjunto con repetición. Podemos desear elegir elementos distintos, como ocurriría en la extracción de 3 bolas de colores de una bolsa, sin reponerlas una vez extraídas. Como Cartesius sólo maneja números, las podremos representar como 1, 2 y 3. El planteamiento podría ser:

XTOTAL=3
XT=1,2,3
NO REPITE

Aquí hemos cambiado la definición del conjunto: en lugar de usar XT=1..3, lo hemos definido como conjunto de elementos, como XT=1,2,3. Es una variante. Además, se ha añadido la condición NO REPITE, que no necesita explicación. No olvides borrar antes las condiciones si has estado trabajando con ellas.

Pulsamos el botón de Iniciar y obtenemos



Ya habrás identificado estos arreglos como variaciones sin repetición y comprendido que son 6 porque 6=3*2*1, según la conocida fórmula

Vm,n = m(m-1)(m-2)…(m-n+1)

Imagina que deseamos encontrar todas las variaciones de 6 elementos tomados de 4 en 4 en las que el segundo elemento sea un 2. Acudiríamos a este planteamiento:

XTOTAL=4
XT=1..6
X2=2..2

Con este ejemplo aprenderás una característica importante de Cartesius, y es que una condición puede anular parte de las anteriores. En XT=1..6 obligábamos a que todos los elementos recorrieran del 1 al 6, pero después hemos añadido algo contradictorio, que X2 (el segundo) sólo pueda pertenecer a 2..2. Pues bien, esta es la condición que prevalece (en pantalla pueden seguir apareciendo 3, 4, 5, 6, pero no tendrán validez).

Borra las condiciones, escribe estas nuevas y observarás que obtienes, en lugar de 1296=6^4, 216=6^3, ya que el segundo elemento permanece constante. Si no deseas ver los elementos, sino sólo el número de arreglos, en la hoja Producto puedes acudir a los controles y especificar que no quieres ver el desarrollo:



De esa forma los cálculos serán mucho más rápidos, pero sólo figurará el número total 216 arriba a la derecha del conjunto:



Podías haber escrito estas otras condiciones:

XTOTAL=4
X1=1..6
X2=2..2
X3=1..6
X4=1..6

Ya te habrás dado cuenta de que XT define para todos y X1, X2,… para cada uno en particular.

Importante: El programa se puede confundir si encuentra una celda con un espacio en blanco en lugar de estar vacía. Por eso, es conveniente borrar las condiciones antes de escribir las nuevas.

En la siguiente entrada procederemos a incluir diversos condicionamientos a las variaciones, con lo que adquirirás más dominio de la hoja Cartesius.


jueves, 9 de febrero de 2017

Divisores de los números 3-friables


En la entrada anterior presentamos los números 3-friables, que son aquellos que sólo tienen como factores primos el 2 y/o el 3, con expresión 2^p*3^q. Conviene leerla previamente para entender lo que sigue. Puedes pulsar el enlace "Entrada antigua" al final de esta entrada.

Las funciones dependientes de divisores serán en este caso muy simples, ya que sólo manejaremos los exponentes de 2 y 3. Vemos algunas:

Número de divisores (función TAU)

Nos basaremos en la expresión general de estos números, sea


Consultamos nuestra publicación sobre funciones multiplicativas (http://www.hojamat.es/publicaciones/multifun.pdf) y vemos que TAU se expresa respecto a los exponentes como

En este caso D(N)=(1+p)(1+q). Por tanto, nunca tendrán un número de divisores primo si son múltiplos de ambos 2 y 3, pero sí pueden serlo si sólo son múltiplos de uno de ellos. En otros casos podrá ser semiprimo el número de divisores, como en el caso 2^2*3^6 cuyo número de divisores es 3*7, semiprimo.

También se puede dar la casualidad, al tener pocos factores, de que el número 3-friable sea múltiplo de TAU. Pues bien, resultan muchos números con esta propiedad. Los primeros son:

1, 2, 8, 9, 12, 18, 24, 36, 72, 96, 108, 128, 288, 384, 864, 972, 1152, 1944, 3456, 6144, 6561, 6912, 7776, 13122, 18432, 26244, 31104, 32768, 52488, 55296, 62208, 69984, 98304,...

Los puedes conseguir con PARI:

m23(n)={local(m,v);m=n;while(m/2==m\2,m=m/2);while(m/3==m\3,m=m/3);if(m==1,v=1,v=0);v}
for(i=1,10^5,if(m23(i)&&i%sigma(i,0)==0,print1(i,", ")))


Función SIGMA

La función SIGMA suma todos los divisores de un número, al igual que la anterior los cuenta. Su expresión es

Es fácilmente adaptable a nuestro caso. Sería así:

Por ejemplo, el elemento 384=2^7*3 tendrá (1+7)(1+1)=16 divisores. En efecto, son estos: 384, 192, 128, 96, 64, 48, 32, 24, 16, 12, 8, 6, 4, 3, 2, 1. Su suma, la función SIGMA, tendrá el valor (2^8-1)(3^2-1)/2=255*4=1020, como puedes comprobar sumando los 16 divisores.

¿Puede ser prima la sigma de estos números?

Para ello, uno de los factores debería ser primo, y el otro la unidad. Si observas los paréntesis de la fórmula de arriba, sólo valdrán 1 si p=0 o q=0. Sólo pueden tener sigma prima aquellos elementos que sólo sean múltiplos de 2 o de 3. En concreto son los siguientes:

2, 4, 9, 16, 64, 729, 4096, 65536, 262144,…

Los puedes conseguir con este algoritmo en PARI

m23(n)={local(m,v);m=n;while(m/2==m\2,m=m/2);while(m/3==m\3,m=m/3);if(m==1,v=1,v=0);v}
for(i=1,300000,a=m23(i);if(a&&isprime(sigma(i)),print1(i,", ")))


Vemos que aparecen números de la forma 2^p, como 2, 4, 16, 64, 4096, y otros del tipo 3^q, que serían 9 y 729. Los vemos por separado:

Los elementos del tipo 2^p serán aquellos en los que 2^(p+1)-1 sea primo, pero esos son los  primos de Mersenne: 3, 7, 31, 127, 8191,…, por lo que serán los únicos casos posibles, según la tabla siguiente:



Aquí tienes la lista de los primeros casos del tipo 2^p:

2, 4, 16, 64, 4096, 65536, 262144, 1073741824, 1152921504606846976, 309485009821345068724781056, 81129638414606681695789005144064, 85070591730234615865843651857942052864,…

Es fácil ver que en esta tabla sigma(sigma(n))=2n. En efecto, los primeros de la tabla son fácilmente comprobables: sigma(sigma(4))=sigma(7)=7+1=2*4,…Mediante cálculos tendríamos que

sigma(sigma(2^p))=sigma(2^(p+1)-1)=2^(p+1)-1+1,

por ser prima la sigma, luego

Sigma(sigma(2^p))=2^(p+1)=2*2^p

Por tener esta propiedad, a estos números se les llama superperfectos, y están publicados en http://oeis.org/A019279

Los del tipo 3^q tendrán sigma prima si (3^(q+1)-1)/2 es primo, lo que obliga a que q sea par, como ocurre en los casos vistos de 9=3^2 y 729=3^6 y podemos añadir 3^12=531441. Esta es la lista de los primeros:

9, 729, 531441, 2503155504993241601315571986085849, 4638397686588101979328150167890591454318967698009,…

Están publicados en http://oeis.org/A255510


¿Podría ser semiprima?

La sigma de los números 3-friables también puede ser semiprima. Basta exigir en los algoritmos que bigomega(N) sea igual a 2, si recordamos que BIGOMEGA cuenta los factores primos con repetición. Si unimos las funciones solo23 (o m23 en PARI) con bigomega obtendremos las soluciones. En la tabla puedes estudiar los primeros ejemplos, obtenidos con hoja de cálculo




La primera columna contiene los números (3-friables), la segunda su sigma y la última los dos factores de la misma que la convierten en semiprima.

Podemos ampliar la lista usando PARI:

m23(n)={local(m,v);m=n;while(m/2==m\2,m=m/2);while(m/3==m\3,m=m/3);if(m==1,v=1,v=0);v}
for(i=2,10^11,if(m23(i)&&bigomega(sigma(i))==2,print1(i,", ")))

Obtendremos:

3, 8, 18, 36, 81, 144, 256, 576, 1024, 1458, 2916, 6561, 11664, 36864, 46656, 59049, 589824, 1062882, 2125764, 2359296, 2985984, 4194304, 8503056, 34012224, 43046721, 47775744, 191102976, 387420489, 2176782336, 9663676416, 31381059609, 34828517376, 68719476736, 139314069504,…

Este algoritmo es muy lento, por lo que podemos usar la idea del producto cartesiano que desarrollamos en la anterior entrada. Sólo hay que ordenar al final la lista que creemos término a término. Quedaría así:


l=List();for(i=0,40,for(j=0,25,a=2^i*3^j;if(bigomega(sigma(a))==2,listput(l,a))));listsort(l);print(l)

Nos da más términos de una forma muy rápida:

3, 8, 18, 36, 81, 144, 256, 576, 1024, 1458, 2916, 6561, 11664, 36864, 46656, 59049, 589824, 1062882, 2125764, 2359296, 2985984, 4194304, 8503056, 34012224, 43046721, 47775744, 191102976, 387420489, 2176782336, 9663676416, 31381059609, 34828517376, 68719476736, 139314069504, 782757789696, 1099511627776, 570630428688384,…

Y los que son sólo potencias de 2

8, 256, 1024, 4194304, 68719476736, 1099511627776, 281474976710656, 288230376151711744, 73786976294838206464, 4835703278458516698824704, 79228162514264337593543950336, 1267650600228229401496703205376, 5070602400912917605986812821504, 324518553658426726783156020576256,

Se encuentran fácilmente con PARI:

for(n=1,120,a=2^n;if(bigomega(sigma(a))==2,print1(a,", ")))

Se corresponden con los exponentes 3, 8, 10, 22, 36, 40, ,48, 58, 66, 82, 96, 100, 102, 108,…


Indicatriz de Euler

Para estos números N es muy fácil obtener la indicatriz, número de números coprimos con N y menores que él. Disponemos de una fórmula sencilla, publicada en muchos medios

En este caso:

j(N)=j(2^p*3^q)=2^p*3^q*(1-1/2)(1-1/3)=2^p*3^(q-1)

Existen relaciones muy sencillas en este caso entre N y j(N)

(a) Si q>0 y p>0 , la indicatriz es un tercio del número, como es fácil de ver por su expresión.

(b) Si q=0 tenemos que usar j(N)=j(2^p)=2^p*(1-1/2)=2^(p-1) y sería la mitad.

(c) Si p=0 tenemos j(N)=j(3^q)=3^q*(1-1/3)=3^(q-1)*2 y equivaldría a los dos tercios de N.

En la siguiente tabla lo puedes comprobar: los cocientes entre N y su Indicatriz siempre son 3, 2 o 1,5, según si son potencias dobles de 2 y 3 o sólo de 2 o sólo de 3:


Consecuencia importante: La indicatriz de un número 3-friable es también 3-friable.

Las propiedades que hemos estudiado se pueden unificar en una sola fórmula:

j(6N)=2N
Recorremos los casos:

Si q>0 y p>0 , 6N=2^(p+1)*3^(q+1), luego la indicatriz valdrá un tercio, es decir 2^(p+1)*3^q, que equivale a 2N

Si q=0, 6N=2^(p+1)*3, y la indictariz también será un tercio, es decir 2^(p+1)=2N

Si p=0, 6N=2*3^(q+1). La indicatriz vuelve a ser un tercio, y queda 2*3^q=2N

Divisores unitarios

Un divisor k de N es unitario si es primo con el cociente N/k, que por tanto también sería unitario. Los unitarios forman pares, comenzando con (N,1). Es sencillo razonar que en los números 3-friables 2^p*3^q con p>0 y q>0 sólo existirá otro par, el (2^p,3^q). Por tanto, la función USIGMA, suma de unitarios, valdrá en este caso

Usigma(n)=2^p*3^q+2^p+3^q+1=(2^p+1)(3^q+1).

Podemos interpretarlo como que se incrementan en una unidad las componentes 2^p y 3^q y después se multiplican, siempre que p>0 y q>0. Hemos construido una tabla en la que se confirma que usigma es igual a ese producto.