sábado, 3 de noviembre de 2012

Descomposición de un número según una lista


Hoy presentamos una herramienta de hoja de cálculo que nos permitirá descomponer un número en sumandos extraidos de una lista. Ya la anunciamos en anteriores entradas y tratamos el tema en
 (http://hojaynumeros.blogspot.com.es/2010/02/frobenius-y-los-mcnuggets.html)

El concepto es el siguiente: dado un conjunto de números enteros positivos a1, a2, a3,…an, diremos que otro entero positivo N es representable según ese conjunto si existen coeficientes enteros no negativos x1, x2, x3,…xn tales que

 N= a1*x1+a2*x2+…an*xn

Si exigimos que los coeficientes sólo puedan valer 0 o 1, obtendremos la descomposición en elementos distintos. Si los dejamos libres pasaremos al caso general del problema, también llamado “de las monedas”.

Herramienta

Hemos preparado una herramienta de hoja de cálculo. La tienes en

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

 y resuelve este problema para números no demasiado grandes. Tiene dos variantes, que explicaremos por separado.

(1) Descomposición de un sólo número

Para descomponer un número según una lista, es evidente que esos son los datos necesarios que habrá que aportar a la herramienta: el número, la lista y si deseamos o no repeticiones de sumandos. Es importante que se entienda esto bien, pues si por ejemplo deseamos expresar un número como suma de primos, será responsabilidad nuestra escribir la lista de números primos correctamente y tener una idea clara de hasta dónde debe llegar, dentro de las limitaciones de la hoja que estamos usando.

Por ejemplo, deseamos expresar el número 30 de todas las formas posibles como suma de cuadrados con repetición.

Para ello habrá que decidir el número a descomponer (30), la lista de cuadrados (1,4,9,16,25). En la imagen puedes ver el planteamiento
















Además hay que indicar con un SI que deseamos repetición en los sumandos, es decir, que los coeficientes puedan ser números enteros positivos, no necesariamente 0 y 1. Hay que escribir en mayúsculas y sin tilde SI o NO.




Con el botón Iniciar se comienza la búsqueda de coeficientes. A cada sumando se le asigna un tope, que es el cociente entero por exceso entre 30 y él, para evitar cálculos inútiles. A la derecha de los topes verás de forma muy animada la búsqueda de coeficientes. El hecho de que aparezcan ralentiza el proceso, pero le da más vida y aquí nos interesa más la comprensión que la velocidad.

Los resultados se expresan como combinaciones lineales, que son más compactos que la lista de sumandos. En nuestro ejemplo han aparecido 27 formas distintas de expresar el número 30 como combinación lineal del tipo

30 = 1*x1+4*x2+9*x3+16*x4+25*x5




Estas combinaciones las puedes interpretar como sumas con elementos repetidos:

2*1+7*4 = 1+1+4+4+4+4+4+4+4 = 30

27 sumas son muchas. Si el número fuera mayor la lista también tenía que crecer. Por eso no debe extrañar que los tiempos de cálculo se acerquen a 10 o 20 minutos en números pequeños, o más si se le exige mucho. Si te cansas del cálculo, pulsa ESC si usas Excel o Ctrl+Maúscula+Q si estás con OpenOffice o LibreOffice.

La variante sin repetición, al sólo admitir 0 y 1 como coeficientes es mucho más rápida y con menos resultados. Aquí tienes todas las descomposiciones del número 50 en sumas de números primos no repetidos. Al ser extensa la lista de primos, a un ordenador, si no es muy rápido, puede costarle más de diez o quince minutos encontrarlos.



Resultan 23 formas de expresar 50 como suma de primos no repetidos. Puedes comprobarlo en la lista contenida en http://oeis.org/A000586. Intenta reproducir algún resultado más de la misma, pero si el número es mayor, deja al ordenador trabajando solo y al cabo de media hora vuelves.

(2) Elaboración de una lista

Hemos señalado que la página http://oeis.org/A000586 contiene las descomposiciones de los números enteros en sumas de primos distintos. Sus primeros valores son 1, 0, 1, 1, 0, 2, 0, 2, 1, 1, 2, 1, 2, 2, 2, 2. Eliminamos el primer 1, que corresponde al cero y no tiene sentido en nuestra tarea. Intentaremos reproducirla.

Para obtener una lista pasamos a la parte derecha de la hoja sin borrar la lista de sumandos, pero sí eliminando los primos que no vayamos a usar. Por ejemplo, se podían preparar los 20 primeros números con la lista {2, 3, 5, 7, 11, 13, 17, 19}. En esa parte derecha concretamos el inicio, final y salto de la lista. Aquí serían 1, 20 y 1 respectivamente.

Al pulsar en el botón Lista observaremos que las búsquedas no presentan a la izquierda ni los coeficiente ni los resultados parciales, para aumentar la velocidad, y sólo aparecerán los números y sus resultados.



Reproduce la búsqueda en tu equipo y compara estos resultados con los de  http://oeis.org/A000586 para comprobar su exactitud. Puedes realizar más comprobaciones, pero lo dejamos para otro día