jueves, 29 de noviembre de 2012

Más pasos hacia la complejidad (1)



En estas entradas de nuestro blog

http://hojaynumeros.blogspot.com.es/2011/11/pasito-pasito-hacia-la-complejidad.html
http://hojaynumeros.blogspot.com.es/2011/11/pasito-pasito-hacia-la-complejidad_25.html
http://hojaynumeros.blogspot.com.es/2011/11/pasito-pasito-hacia-la-complejidad_29.html

estudiamos los casos en los que partiendo de un número simple, como es un primo, al avanzar o retroceder unidad a unidad iban apareciendo números con cada vez más factores primos: semiprimos, 3-casiprimos, 4-casiprimos,…hasta que se rompía esa tendencia. Dábamos el ejemplo de 807905281, que es primo y cumple que

807905282 = 2*403952641
807905283 = 3*15733*17117
807905284 = 2*2*1871*107951
807905285 = 5*11*43*211*1619
807905286 = 2*3*3*3*37*404357
807905287 = 7*7*7*7*29*41*283

Si recordamos que la función BIGOMEGA cuenta los factores primos de un número teniendo en cuenta los repetidos, la situación anterior se podría representar así:



Revisando esta entrada para su inclusión en el resumen anual, nos hemos dado cuenta de que el tema de alcanzar complejidades mayores moviendo un número hacia adelante y hacia atrás daba para más estudios, por lo que os los presentamos en esta entrada.

¿POR QUÉ AVANZAR DE UNO EN UNO?

Se dan casos en los que N es primo y N+2 semiprimo:

2, 7, 13, 19, 23, 31, 37, 47, 53, 67, 83, 89,...

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

Toma un número de la sucesión. Por ejemplo, el 53. Le sumas 2 y se convierte en 55=5*11, que es el semiprimo más cercano (esto no lo exigimos y ya lo veremos más adelante), porque 54=2*3*3*3.

Estos números son de la forma p*q-2, con p y q primos.

También puede ser N primo y N-2 semiprimo

11, 17, 23, 37, 41, 53, 59, 67, 71, 79, 89, 97, 113,...

http://oeis.org/A063638

Estos números son de la forma p*q+2, con p y q primos.

Saltos de tres unidades

Existen números p primos con p+3 semiprimo

3, 7, 11, 19, 23, 31, 43, 59, 71, 79, 83, 103,…

http://oeis.org/A092109

Son del tipo p=4k+3 (¿por qué?) y cumplen que (p+3)/2 es primo (piensa que p+3 es par y semiprimo)

Existen números p primos con p-3 semiprimo

7, 13, 17, 29, 37, 41, 61, 89, 97, 109, 137,...

http://oeis.org/A089531

Sus propiedades son simétricas de las de los anteriores

Función DISTSEMI

En lugar de seguir buscando saltos mayores podemos definir dos funciones: DISTSEMI, que medirá la distancia mínima k tal que P sea primo y P+k sea semiprimo y DISTSEMI2, que hará lo mismo por la izquierda, ver el valor mínimo k para el que P sea primo y P-k semiprimo.

El código de la primera podría ser

Function distsemi(p)
Dim d, k
Dim noess

d = 0
If esprimo(p) Then
k = 0
noess = True
While noess
k = k + 1
If essemiprimo(p + k) Then d = k: noess = False
Wend
End If
distsemi = d
End Function

Se entiende fácilmente, e igual, con dos pequeñas variaciones podemos definir DISTSEMI2.


FUNCIÓN DISTSEMI2

Los valores de esta segunda función están publicados en http://oeis.org/A121885
No se puede definir para P=2 ni para P=3. Para los siguientes a partir del 5 tenemos los valores



5
7
11
13
17
19
23
29
31
37
1
1
1
3
2
4
1
3
5
2


Salvo para 2 y 3 esta función está definida para todo número natural, porque el conjunto de los semiprimos inferiores al mismo no está vacío, ya que al menos contiene al 4, y al ser un conjunto acotado de naturales tendrá un máximo Q (ver http://oeis.org/A102415) y la diferencia entre P y Q será el valor de DISTSEMI2 buscado.

Su gráfica para los primeros primos tiene este aspecto
















Si vas leyendo los valores de X que se corresponden con valores concretos de Y te resultarán sucesiones similares a las que hemos presentado al principio. Así, los mínimos se corresponden con los primos P en los que P-1 es semiprimo, contenidos en https://oeis.org/A005385 y ya tratados en este blog.

En el nivel 2 están estos números primos

17, 37, 41, 53, 67, 71, 79, 89, 97, 113, 131, 157, 163, 211, 223, 239, 251, 269, 293, 307, 311, 331, 337, 367, 373, 379, 397, 409, 419, 439, 449, 487, 491, 499,…,

en los que p-2 es el semiprimo más cercano por la izquierda Los hemos publicado en https://oeis.org/A217195 con el siguiente código:

(PARI) forprime(p=3, 9999, bigomega(p-2)==2 && bigomega(p-1)!=2 & print1(p", "))

Y en el 3

13, 29, 61, 109, 137, 149, 181, 197, 229, 257, 277, 281, 317, 349, 389, 401, 457, 461, 541, 557, 569, 617, 677, 761, 797, 821, 929, 937, 977,…

(Los publicamos en https://oeis.org/A217197)

con el código

(PARI) forprime(p=5, 9999, bigomega(p-3)==2 && bigomega(p-1)!=2 && bigomega(p-2)!=2 & print1(p", "))

Entre los máximos destacan el 103 (ver gráfico), que necesita 8 pasos hacia atrás para encontrar el primer semiprimo. Entre los primos menores que 1000 el máximo se da en el 647, que está a 12 unidades de su máximo semiprimo inferior y entre los menores de 10000 se da en el 6381, con DISTSEMI2(6581)=22
Aquí tienes una lista de los números que presentan máximos respecto a sus anteriores:

13           3
19           4
31           5
101         6
103         8
607       10
647       12
1433     15
2699     18
6581     22
17989   24
32803   26
36011   30
36013   32
36017   36

No crecen mucho los valores máximos, porque al ir aumentando el valor de P van siendo posibles cada vez más combinaciones de dos primos que podrán estar bastante cerca de P. Esto es una observación nada más, sin fundamento riguroso.

Se impone una conjetura: ¿Tenderá a cero el cociente DISTSEMI2(P)/P con P primo al tender P a infinito? Lo dejamos ahí para quien tenga más preparación en estos temas.

miércoles, 21 de noviembre de 2012

Una humilde imitación y un poco de programación



Desde hace unas semanas circula por la red un atractivo vídeo en el que se visualiza la factorización de los números como conjuntos de puntos en forma de árboles poligonales circulares muy cercanos a los conjuntos fractales.

http://miscuriosidadesmatematicas.blogspot.com.es/2012/11/diagrama-animado-sobre-factorizacion-de.html

http://www.datapointed.net/visualizations/math/factorization/animated-diagrams/

http://mathlesstraveled.com/2012/10/05/factorization-diagrams/


En la imagen se puede ver el desarrollo para el número 18, en el que los niveles están definidos por los factores 3, 3 y 2.


Como en este blog no nos salimos de los números y de la hoja de cálculo nos planteamos un reto:

¿Hasta dónde podíamos imitar estos esquemas usando tan sólo la programación de una hoja de cálculo?

Es evidente que el resultado obtenido ha de ser muy inferior al original, y que el interés de esta tarea está en la adaptación a una herramienta menos potente. Por tanto, quien no esté interesado en esta programación es mejor que disfrute del vídeo original sin embarcarse en el proceso que aquí hemos seguido.

El resultado lo tienes en http://hojamat.es/blog/arbofactor.xlsm


Ideas previas

Para imitar lejanamente el vídeo necesitaremos concretar aspectos del problema en sí mismo (representar cada factor como un polígono) y después superar las carencias de la hoja de cálculo (en esta ocasión, dado el distinto comportamiento de las mismas en los gráficos, lo hemos desarrollado sólo en Excel)

El gráfico

La única posibilidad que nos ofrece Excel para estas representaciones es el gráfico de dispersión. Tiene la ventaja de no depender del orden de los datos y adaptarse muy bien al uso de coordenadas cartesianas (X,Y). También permite dejar la zona en blanco y ocultar los ejes. Por contra, presenta gran dificultad en cambiar el tamaño de los distintos puntos según el número de factores. Todos los esquemas, pues, presentarán el mismo tamaño en los puntos



Aquí puedes ver el esquema para 1050. Se puede observar que los últimos triángulos de puntos parecen confundirse, por no haber controlado el tamaño.

Salvo este inconveniente, las figuras resultan atractivas. Las hemos  orientado circularmente en lugar de buscar siempre la vertical. En la siguiente imagen puedes observar la estructura casi fractal que presentan los números que como el 486 contienen potencias altas de primos.



Lo único que hay que explicar del gráfico es que su área de datos está formada por las columnas B y C en las que volcaremos las coordenadas adecuadas.

El algoritmo

Sacar los primos

Necesitamos, en primer lugar, la lista de factores primos del número, con repetición y en orden decreciente. Hemos aludido bastante en este blog a estas técnicas, por lo que a nuestros seguidores les resultará familiar. Normalmente se comienzan a buscar los factores pequeños, pero en este trabajo, por razones estéticas, se comienza por los mayores. Por eso al final de la rutina se invierte el orden.

Sub sacaprimos(n)
Dim f, a, indi

a = n
f = 2: nprimos = 0
indi = 0

While f * f <= a
While a / f = Int(a / f)
  indi = indi + 1
 ff(indi) = f  ‘La variable ff va recogiendo los primos
a = a / f
Wend

If f = 2 Then f = 3 Else f = f + 2
Wend
If a > 1 Then  ‘Último factor
indi = indi + 1
ff(indi) = a
End If

' se ordenan al revés

nprimos = indi
For indi = 1 To nprimos
xx(indi) = ff(nprimos - indi + 1)
Next indi
For indi = 1 To nprimos
ff(indi) = xx(indi)
Next indi

End Sub

Después de esta rutina tendremos el número de factores primos en la variable nprimos y sus valores en ff(i). En este caso no nos interesan los exponentes.

Recorrido en cada factor

Una vez obtenidos los factores primos necesitamos convertirlos en polígonos. Para cada uno harán falta las coordenadas del centro (xx(i),yy(i)), su radio rr(i) y un contador de puntos ii(i) que nos evite el problema de los decimales al final de cada polígono. En cada paso incrementaremos el ángulo de giro necesario para que se forme el polígono y el contador de lados



En la imagen hemos comenzado con ff(1)=13, por lo que los elementos se incrementarán así:

 ii(i) = ii(i) + 1
aa(i) = aa(i) + dospi / 13

Marcado el ángulo que va girando el punto pasamos de coordenadas polares a cartesianas y volcamos el punto en la columnas B y C, donde lo capturará el gráfico y aparecerá un punto nuevo.

    fila = fila + 1
    px = xx(i) + rr(i) * Cos(aa(i))
    py = yy(i) + rr(i) * Sin(aa(i))
    ActiveWorkbook.Sheets(1).Cells(fila, 2).Value = px
    ActiveWorkbook.Sheets(1).Cells(fila, 3).Value = py

Esto se repite tantas veces como indique el factor y se formará el polígono básico


Algoritmo de cambio de nivel 

Aquí reside el nudo de esta programación. Es un caso claro de procedimiento recursivo, pero como hay que gestionar bastantes parámetros lo hemos dejado para una posible extensión y se ha usado en su lugar un esquema muy sencillo que ya se ha publicado en este blog: la subida y bajada de nivel.

Procedimientos iniciales: definir primer radio, sacar los primos…

Mientras haya un nivel activo  (nivel>0)

Incrementamos el ángulo y el contador para avanzar en el polígono

Si se llega al final del polígono 
Hemos terminado y bajamos de nivel (nivel=nivel-1)

En caso contrario pueden ocurrir dos cosas:

Si hemos llegado al último factor hay que imprimir el punto volcándolo en las columnas B y C

Si no hemos llegado hay que subir de nivel(nivel=nivel+1)
Esto significa que hay que determinar nuevos centro y radio

Fin del Mientras
Fin de la rutina

No incluimos el código y preferimos que las personas interesadas lo estudien en el archivo de Excel.

Animación

Para conseguir la animación basta con una estructura repetitiva tipo FOR-NEXT y la creación de pausas para conseguir el efecto de transición continua. El problema radica en que cualquier operación aparentemente sencilla puede borrar el gráfico y perderse su persistencia en nuestra retina. Hemos tenido que acudir al recálculo para refrescarlo y que no desaparezca.

La pausa se consigue leyendo el reloj e introduciendo a la hoja en un bucle continuo hasta que transcurra la pausa. Queda así:

Call arbol  ‘se construye el árbol de factores
t1 = Timer ‘ leemos el reloj y tomamos nota en t1 y t2
t2 = t1
While t2 - t1 < pausa: t2 = Timer: Calculate: Wend  ‘bucle continuo de recálculo
Call borrar ’terminada la pausa se borra el gráfico

Controles

Nos gusta tener todo el poder posible sobre la hoja de cálculo. Por eso se han añadido los controles de Reducción, que se puede cambiar (no en la animación) para mejorar la estética del gráfico y Pausa, que ralentiza o acelera la animación.


A quienes hayan llegado hasta aquí les recomendamos el estudio de los detalles del código y les invitamos a intentar mejorarlo.






martes, 13 de noviembre de 2012

¿Quieres publicar en OEIS?



Las descomposiciones de números en sumas de otros conocidos son muy populares en la Red.  Puedes encontrarlas en

http://maanumberaday.blogspot.com

http://primes.utm.edu/curios/

y especialmente en

http://oeis.org/

además de en otros blogs y páginas especializadas.

En esta última, OEIS, puedes encontrar muchas secuencias de números destacados por poder expresarse como suma de elementos de una lista, ya sea de cuadrados, primos o números de Fibonacci, tanto con sumandos repetidos como con sumandos distintos.

Así por ejemplo, podemos encontrar las siguientes:

A033461 Número de particiones en diferentes cuadrados

1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0,0, 0, 2, 2, 0, 0, ...

Con la herramienta que estamos usando en las últimas entradas, (a la que llamaremos PARTLISTA),

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

podemos comprobar algún valor o reproducir la lista. En la imagen la tienes. Recuerda que en OEIS a veces comienza por el 0 y no por el 1, por lo que hay un pequeño desajuste.



A001156 Número particiones en cuadrados que se pueden repetir

1, 1, 1, 1, 2, 2, 2, 2, 3, 4, 4, 4, 5, 6, 6, 6, 8, 9, 10, 10, 12, 13, 14, 14,...

Podemos comprobar el primer 4, que corresponde a 9 usando PARTLISTA. En efecto,

9=9=1+4+4=1+1+1+1+1+4=1+1+1+1+1+1+1+1+1

Igualmente tienes los dos tipos de descomposición en números primos:

A000607 Particiones en primos con repetición

1, 0, 1, 1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 9, 10, 12, 14, 17, 19, 23, 26, 30, 35,...

A000586 Particiones en primos distintos

1, 0, 1, 1, 0, 2, 0, 2, 1, 1, 2, 1, 2, 2, 2, 2, 3, 2, 4, 3, 4, 4, 4, 5, 5,...

Comprobamos el último 5, que corresponde a 24 =11+ 13 = 7+ 17 = 5+ 19 = 2+ 5+ 17 = 2+ 3+ 19

Para no cansar, damos algunas secuencias más por si quieres comprobar alguna o investigar: A024940 y A007294 para descomposiciones en números triangulares. A003107    y   A000119     para números de Fibonacci, A000041 para las particiones ordinarias, A000009 para las que no admiten repetición.

¿Cómo saber si una secuencia que has logrado con PARTLISTA figura o no en OEIS?

Lo vemos con un ejemplo que hemos publicado desde este blog. Elegimos los números pentagonales (http://oeis.org/A000326)

0, 1, 5, 12, 22, 35, 51, 70, 92, 117, 145, 176, 210, 247, 287, 330, 376, 425,…

¿Cómo se descompondrá un número en suma de ese tipo de números?

Con PARTLISTA se ve fácil:

Para conseguir la lista de los 50 primeros escribimos como sumandos los pentagonales 1, 5, 12, 22, 35 y en  la confección de la lista fijamos en 1 el inicio, en 50 el final y con un salto de 1. También dejamos libre la repetición. Nos resultó esta lista (parcial):



¿Estaría en OEIS?

Para verlo seleccionamos la columna de resultados, la segunda, y la copiamos con CTRL+C. Abrimos http://oeis.org . Para saber si una secuancia está o no publicada se debe pulsar en la línea de búsqueda y pegar con CTRL+V




Pero esta no es la forma buena de consultar. Ahora debes escribir una coma detrás de cada número y pulsar el botón Search. Así lo hicimos, con el resultado que ves en la imagen:












La secuencia estaba inédita.

Puede ocurrir que te indique que esa secuencia no está publicada, pero no te alegres tan pronto: quítale un par de elementos del principio y alguno del final, y después repite todo con más elementos o con los últimos en lugar de los primeros. Puede ocurrirte también que tu lista sea una subsecuencia de otra publicada, pero eso no es negativo.

Cuando tengas la seguridad de que tu secuencia está inédita, regístrate en OEIS y publícala. Esta parte te la dejamos, pues no entra dentro de los objetivos de este blog. Está muy bien explicada en OEIS.

En nuestro caso seguimos el protocolo y las particiones en números pentagonales fueron publicadas con el número A218379



Se le añadió el código en el lenguaje PARI que ves en la imagen para una mejor comprobación.

Y ya puestos, publicamos también las particiones sin repetición en la siguiente secuencia A218380

¿Te atreves a intentarlo?

Elige un tipo de números: los oblongos, los del tipo n2 - 1 o n2 + 1 o los hexagonales. Unos estarán publicados y otros no.

Si descubres una descomposición inédita y los editores la ven adecuada, puedes conseguir publicarla.

jueves, 8 de noviembre de 2012

¿Es el 2013 suma de cubos distintos?



La herramienta de descomposición de un número en sumandos (a la que llamaremos PARTLISTA para entendernos en lo que sigue)

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

 presentada en la entrada anterior nos es útil también para resolver problemas.

Proponemos algunos:

(a) ¿Es el 2013 suma de cubos distintos?

Resulta que la respuesta es negativa, pero manualmente es muy difícil demostrarlo. Tenemos los siguientes candidatos a sumandos: 1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331, 1728
Para intentar dar respuesta podríamos comenzar por 1728 e irle sumando cubos hasta desecharlo: 1728+1331 se pasa. Con 1000 también se pasa. Llegaríamos a 1728+216=1944, con lo que nos faltarían 69, que rellenaríamos con el 64: 1278+216+64=2008, con una diferencia de 5 que no sabemos rellenar.

Al llegar a este punto iríamos hacia atrás: sustituir 216 por otro menor, como 125 y tendríamos 1728+125+64=1917, al que le faltan 96 para llegar a 2013 y no sabemos cómo rellenarlos.  Iríamos fracasando con el 1278 y tendríamos que sustituirlo por 1331 y vuelta a empezar. En la hoja que estamos usando se ha optado por crear todas las combinaciones posibles de 0 y 1 y asignar a cada una la suma de cubos correspondiente. Es un camino largo, pues son muchas combinaciones, pero seguro.
Dale los datos del 2013 y te devolverá 0 resultados.

Si el 2013 no es suma de cubos distintos, ¿lo será algún otro año próximo? Plantea una lista a ver qué encuentras. Te damos uno: 2010= 1+ 64+ 216+ 729+ 1000. Sólo te diremos que un poco más adelante aparecerán cuatro seguidos.

(b) El 1729 de Ramanujan

Este popular número incluido en una anécdota de Ramanujan (busca, busca…) se caracteriza por ser el primero en poderse expresar como suma de dos cubos de dos formas diferentes: 1729=12^3+1^3 = 9^3+10^3

¿Hay otras formas de expresarlo como suma de cubos pero de más sumandos? Usa la hoja de cálculo para encontrarlas.

(c)  Una distancia con varillas

Disponemos de un número suficiente de varillas con tres longitudes distintas, que son 12 cm. 17 cm. y 35 cm. ¿Podemos formar con ellas una longitud de 100 cm. tomando las que queramos de cada clase? La respuesta es afirmativa, pero para más detalles echa a andar la máquina. También sería bueno lograrlo sin ella.

Si la varilla mayor fuera de 31 cm. no se podría. Compruébalo.

(d) Multidescompuesto

El número 9 es suma de cuadrados distintos, también de cubos y también de primos, siempre distintos: 9=9=1+8=2+7 ¿Cuál es el siguiente número con esa propiedad?

(e) El número de Frobenius

¿Recuerdas el número de Frobenius? Lo puedes repasar en

(http://hojaynumeros.blogspot.com.es/2010/02/frobenius-y-los-mcnuggets.html)

Pues la idea es que encuentres empíricamente el número de Frobenius del conjunto {7, 11, 19}

(f) Particiones de un número

Con PARTLISTA puedes también averiguar el número de particiones de un número en sumandos cualesquiera, con o sin repetición ¿Qué números escribirías en la lista? Calcula bien, no te vayas a pasar.

Por ejemplo, el número 7 se descompone así (con repetición)

7=7=6+1=5+2=4+3=5+1+1=4+2+1=4+1+1+1=3+3+1=3+2+2=3+2+1+1=3+1+1+1+1=2+2+2+1=2+2+1+1+1=2+1+1+1+1+1=1+1+1+1+1+1+1

En total son 15 particiones ¿Sabrías reproducirlas?

Sin embargo, si eliminamos repeticiones quedan 5 (basta con que taches aquellas en las que se repite) Intenta también reproducir este número.

(g) Fieles a sí mismos

(a) Encuentra un número primo N que se puede descomponer exactamente en N sumas distintas de números primos (con repetición y contando con él mismo)

(b) Encuentra un número triangular N que se puede descomponer exactamente en N sumas distintas de números triangulares.

Que te diviertas.

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