jueves, 27 de diciembre de 2012

¿Cómo veo el 2013?



Comprobado ya que el mundo no se ha acabado el día 21 y que el calendario sigue cambiando cifras por ahora, saludamos a las siguientes que van a caer:


Veo al 2013…

Desde cifras panorámicas
                             
                                               2013=9*8-(2+1+0)+6+57*34
                                               2013=(5+106)*(8+7+3)+9+4+2
                                               2013=7*8*(0+2+4+6+19+5)-3
                                               2013=4*(1+2)+(50+37)*(9+6+8)

Con ideas trascendentes

                                     2013=(3+1)*(4+1+5)*9/2*(6+5)+(3+5+8+9+8)    (p)
                                     2013=2+7+1+8+(2+8+1+8+2+84)*(5+9+0+5)    (e)
                                     2013= =1*(6+1+8+0+3+39+8+8)*(7+4+9+8)-(9+4+8+4+8)+2+0  (j)

Y aspiraciones mesiánicas

                                    2013==(7+7+7)*(7+77+7+7)-(7+7*7)+77/7

Pero amistades satánicas

                                    2013==6+6+6+6+(66+6*6)*6*(6+66+6)/(6+6+6+6)

Lo dejan autoreferente

                                   2013=((2+0)^(1+3+2+0)-1*3)*(20+13)
                                   2013=20*(1+3+2+0+1+3)^(2+0)+13

A veces escala montes

                                   2013=12*(2+3+3+4+4+5+5+6+6+7+7+8+8+99)+9

Para llegar a la cima

                                   2013=(9+9+9+9+9)*(9+9+9+9+9)-(9+99)/9

Y hasta una humilde colina

                                  2013=11+(11+11)*(1+1+11)*(1+1+1+1+1+1+1)

Se lo llevan los desmontes

                                  2013=(9+9+8+8)+(77+6+6+5+5)*(4+4+3+3+2+2+1+1)-1

Acepta humilde el fracaso

                                  2013=(3+3)*(3+333)-3

Y aunque un poco más lo intente

                                  2013=11+(1+1+22)*33/(4+4)*(5+5+6+6)-(7+7+8)*8
                                  2013=-1+(1+1+2+23)*(34+4+5+5+6+6+7+7)+(8+8)

Le deja el turno al siguiente

                                  2013=(2+0+1+4)*(2+0)*(1+4+2+0+1+4)^2+(0+1)-4

Y se va marcando el paso

                                 2013=(6+1+6+1+6+1+6+1+6)*(1+6+1+6+1+6+1+6+1+6+16+1+6+1)+6+1
                                 2013=(61+6+1+6+1+6+1+6+1)*(6+16+1)-(6+1+6+1+6+1)-(6+1)-6
                                 2013=(6+1+61)*(6+16+1+6+1)-(6+1+6+1+6+1+6+1+6)+1+6
                                 2013=(6+1+6+1+6+1+6)^1*(61+6+1+6)+1+6+1+6+1
                                 2013=(61+6+1)*(6+1+6+16+1)-(6+1+6)-1-6-6-1
                                 2013=(6+1+6)*161-6-1-6-1-61-6+1
                                 2013=(6+16+16+1-6/1)*61
                                 …

Bueno, a veces lo cambia

                                 2013=(16+16+1)*61/6/1*6

O se hace capicúa

                                 2013=(16+16+1)*61

¡Feliz año nuevo!



miércoles, 19 de diciembre de 2012

Volvemos a visitar al mayor divisor impar


Participamos con esta entrada en el Carnaval de Matemáticas 3.131592653 cuyo anfitrión es el blog Que no te aburran las M@tes.

En una entrada ya algo antigua

 (http://hojaynumeros.blogspot.com.es/2009/03/la-hoja-de-calculo-ayuda-razonar.html)

resolvimos una cuestión muy elegante sobre el mayor divisor impar de un número (le llamaremos MDI).

Al revisar ahora esta cuestión nos hemos encontrado con que desde entonces se han desarrollado en este blog muchos estudios que nos podrían ayudar a estudiar con más profundidad esta función. Algunos de los temas que trataremos los hemos encontrado en http://oeis.org/A000265, pero sin desarrollar.

Definición y cálculo

Llamaremos mayor divisor impar (MDI) de un número natural N al mayor número impar (eventualmente igual a 1) que es divisor de N

Es evidente que si N es impar, MDI(N)=N y que si es potencia de 2, MDI(N)=1

Esto nos da una idea muy simple para calcularlo en un caso concreto: dividimos entre 2 todas las veces posibles y al final llegaremos al MDI:

144/2=72; 72/2=36; 36/2=18; 18/2=9, que será el MDI(144)

Visto de otra forma, hemos eliminado la mayor potencia de 2 posible. El exponente correspondiente, en este caso 4, recibe el nombre de valuación de N respecto a 2, V2(N) (definición tomada de los números p-ádicos).

Podemos descomponer N como N=MDI(N)* V2(N)

Esto nos lleva a códigos muy sintéticos para calcularlo:

En el Basic de las hojas:

Public Function mdi(n)  'mayor divisor impar
Dim s
s = n
While s/2=int(s/2): s = s / 2: Wend ‘ Divide entre 2 mientras se pueda.
mdi = s
End Function

No requiere explicación. Basta leerlo.

En PARI, como ya tiene implementada la función VALUATION, el código es aún más simple:

mdi(n)= {m=n / 2^valuation(n, 2);return(m)}

Existen otras formas elegantes de cálculo, pero más lentas:


Aquí hay un exceso: no es necesario llegar a 2N. Es claro que el denominador es la valuación de N respecto a 2.Intenta razonarlo.

La sucesión de los mayores divisores impares la tienes en http://oeis.org/A000265:

1, 1, 3, 1, 5, 3, 7, 1, 9, 5, 11, 3, 13, 7, 15, 1, 17, 9, 19, 5,21, 11, 23, 3, 25, 13, 27, 7, 29, 15, 31, 1, 33, 17, 35, 9, 37, 19, 39,…

Razona una propiedad muy sencilla y compruébala en la lista:

MDI(N)=MDI(2N)

Basándonos en esta propiedad podemos calcular MDI mediante recursividad, pues definiremos MDI(N) como el mismo N si es impar y MDI(N/2) si es par.

Es una solución muy elegante. Podemos usar la recursividad en las hojas de cálculo, ya explicada en http://hojaynumeros.blogspot.com.es/2012/03/funciones-recursivas-en-las-hojas-de.html:

Public Function mdirecu(n)
Dim d
If n = 2 * Int(n / 2) Then d = mdirecu(n / 2) Else d = n
mdirecu = d
End Function

Propiedades

(1) Es multiplicativa

En efecto, si m y n son coprimos, se cumple que MDI(m*n)=MDI(m)*MDI(n)

Casi podríamos dejarlo como ejercicio: Si m y n son coprimos tendrán diferentes factores primos. Es más, si m es par, n será impar. Hallarles el MDI equivale a eliminarle todas las potencias de 2 al que sea par, pero los demás factores no cambiarán y serán distintos en ambos números, luego al multiplicarlos se multiplicarán también sus MDI.

Como todas las multiplicativas (ver http://hojamat.es/publicaciones/multifun.pdf) para definir MDI basta hacerlo en el caso N=pk, siendo p un factor primo de N. En este caso es trivial: si p=2, MDI(2k)=1 y en caso contrario, MDI(pk)= pk

(2) El MDI representa la pauta de unos en su representación binaria

Ya nos referimos a esta propiedad en la anterior entrada: si N=MDI(N)* V2(N), el paso de MDI(N) a N consistirá en añadir ceros a la derecha, luego la pauta de unos se conserva. Lo vemos con un ejemplo:

N=2664=101001101000(2  y MDI(2664)=333=101001101(2

Coinciden las pautas de unos

(3) Los conjuntos {MDI(N+1), MDI(N+2),…MDI(2N)} y {1,3, 5, 7…(n elementos)…} son idénticos.

También nos referimos a ella en su momento.

1.- Los elementos del primer conjunto son todos distintos, pues si dos fueran iguales, MDI(K)=MDI(J), uno de los números, por ejemplo K debería cumplir K=J*2r y entonces, si J pertenece al rango N+1,…2N, K sería mayor que 2N y no pertenecería a ese rango.

2.- Todos los N primeros números impares deben pertenecer al segundo conjunto. Lo que es seguro es que pertenecen al intervalo 1..2N. Si pertenecen al intervalo N+1..2N ya está demostrado. Si no, M£N, y entonces existe un múltiplo suyo del tipo M*2h que pertenece al rango N+1..2N. Supongamos que no, que existen dos exponentes consecutivos tales que M*2£ N < 2N < M*2h+1 (h eventualmente igual a la unidad). Dividiendo resultaría M*2h+1/ M*2h > 2N/N, es decir 2>2, luego esta situación es imposible. Debe existir un exponente tal que M*2r pertenezca a N+1..2N y por tanto su MDI estará en el segundo conjunto.

(3.1) Consecuencia: MDI(N+1)+MDI(N+2)+,…+MDI(2N) = N2, por ser suma de los primeros impares.

(3.2) Otra consecuencia: Si llamamos U(n) a la suma de los MDI de los n primeros números naturales, se obtendrá que

U(2n) = n2+U(n)

(lo tienes en http://arxiv.org/pdf/1103.2295v1.pdf)

(4) La suma de los 2N primeros términos de la sucesión de MDI equivale a (4N+2)/3

Es consecuencia de la propiedad anterior. Lo vemos por inducción (recorre la sucesión presentada más arriba) 1+1=(41+2)/3=2;  1+1+3+1 = (42+2)/3 = 6, 1+1+3+1+5+3+7+1 = (43+2)/3=22,… luego podemos suponer cierta la igualdad para N. Sea

MDI(1)+MDI(2)+…+MDI(2N) = (4N+2)/3

Para 2N+1, según la propiedad anterior, la suma sería: MDI(1)+MDI(2)+…+MDI(2N+1) = (4N+2)/3)+4N = (4*4N+2)/3 = (4N+1+2)/3 y queda demostrado.

Y dejamos para el final la propiedad más elegante:

(5) Si sumamos los valores que toma la función j(N) (indicatriz de Euler) para todos los divisores impares de N, el resultado es el mayor divisor impar.

Es sabido que esa suma extendida a todos los divisores de N da como resultado N
(ver http://es.wikipedia.org/wiki/Funci%C3%B3n_%CF%86_de_Euler)



Por ejemplo, para el número 576, en la siguiente tabla tienes la comprobación de esta propiedad, los valores de la indicatriz también suman 576.



Como la función j es multiplicativa, la suma de la parte derecha se puede dividir en dos factores, uno para todos los divisores que son potencia de 2 y otro con los impares. Así, los 21 sumandos se pueden expresar así:
S = (j(1)+ j(3)+ j(9))*(j(1)+ j(2)+ j(4)+ j(8)+ j(16)+ j(32)+ j(64)) = 9*64 = 576

Vemos que la suma de la primera parte es 9, el MDI(576), como habíamos afirmado.

Esta descomposición se puede efectuar en cualquier número: por una parte incluimos las potencias de 2 y por la otra los coprimos con dos. La segunda suma dará la máxima potencia de 2 que divide a N y la primera tendrá como resultado MDI(N).

Extensión

Al igual que hemos definido el mayor divisor impar podíamos haberlo hecho con el mayor divisor no múltiplo de 5 (lo podemos representar como MD_5) que está estudiado en http://oeis.org/A132739, o no múltiplo de 10 (http://oeis.org/A132740) Puedes trasladar todo lo que se ha expuesto al caso en el que en lugar de 2 se use otro número.

También puedes pensar si siempre se cumplirá que MD_K(MD_L(N)) = MD_L(MD_K(N))

miércoles, 12 de diciembre de 2012

Propiedades del 2013 (y mucho más)



Como viene siendo habitual desde 2010,  nuestro colaborador y amigo Rafael Parra Machío saluda al nuevo año con otro de sus interesantes documentos. En esta ocasión, además de un recorrido exhaustivo por las propiedades del número 2013, nos documenta sobre

* Historia de la Cronología
* Los diversos calendarios
* La medida del tiempo
* Conversión entre calendarios

Lo podéis descargar desde

http://hojamat.es/parra/prop2013.pdf

Descubriréis muchos hechos y datos sobre la medida del tiempo a lo largo de la Historia.

Y si queréis repasar los años anteriores:

http://hojamat.es/parra/prop2012.pdf

http://hojamat.es/parra/prop2011.pdf

http://hojamat.es/parra/p2010.pdf



Mayor divisor propio con la misma suma de cifras



A partir de una cuestión simple (que no sencilla) desarrollaremos varias técnicas y conceptos, ejercicio que nos agrada mucho en este blog.

¿Qué números poseen la misma suma de cifras que su mayor divisor propio?

Uno de ellos es el 12673 que se descompone como 12673=19*23*29, luego su mayor divisor propio es 23*29=667 y, en efecto la suma de las cifras de 12673 es 19 y la de 667 también es 19.

No hay que irse tan lejos: el mayor divisor de 18 es 9 y también se cumple esta propiedad. Puede que hayas pensado que la cumplen todos los múltiplos de 9 y no es así, porque 45 tiene como mayor divisor 15 y ahí no coinciden las sumas, y tampoco en 63. Sin embargo sí se cumple en 18, 27, 36, 54,…

Esto se complica, porque tienen la propiedad números no múltiplos de 9 y entre los que sí lo son, unos la cumplen y otros no. Reflexionemos:

Relación entre un número y su mayor divisor propio

Si B es el mayor divisor propio de A se tendrá que A/B será el menor divisor de A (mayor que 1 pues si no B no sería propio), pero por uno de los más elegantes teoremas sobre divisores, ese cociente A/B ha de ser primo. Por tanto

Si B es el mayor divisor propio de A se cumple A=Bp siendo p primo (igual o menor que B)

Condición de igualdad de sumas

Si dos números presentan la misma suma de cifras es que son congruentes módulo 9, como bien se sabe en Aritmética Modular (recuerda el criterio de divisibilidad por 9).

Por tanto tendremos, con la notación anterior, que AºB (mod 9, es decir BºBp (mod 9 y por tanto Bp-B=B(p-1) deberá ser múltiplo de 9. Ten cuidado, que esta condición es necesaria pero no suficiente.

Esto nos lleva a tres posibilidades: (a) B es múltiplo de 9 (b) B es múltiplo de 3 pero no de 9 (c) B no es múltiplo de 3

(a) Si B es múltiplo de 9, el número primo p sólo puede ser 2 o 3. Si fuera mayor no se cumpliría, porque entonces B no sería el mayor divisor, ya que el menor sería 3 y por tanto el mayor sería A/3. Esto divide a los múltiplos de 9 en dos clases:

(a1) Los números en los que un múltiplo de 9 está multiplicado por 2 o 3 (y por otros), sí pueden cumplir la igualdad de sumas. De hecho son estos:

18, 27, 36, 54, 72, 81, 90, 108, 126, 135, 144, 162, 180, 198, 216, 234, 243,…

No sé si echas de menos alguno. No estará el 288, a pesar de cumplir el contener el factor 2, pero es que sus cifras suman 18 y las de su mayor divisor 144 sólo 9.

Aquí tienes la trampa: dijimos que la condición era necesaria pero no suficiente. Por eso hemos usado la palabra “pueden ser”. Lo que sí ocurrirá es que las sumas sean congruentes módulo 9 (razónalo)

(a2) Aquellos que tienen la forma 9p con p producto de primos mayores que 3. Estos no tienen que cumplir la igualdad de sumas. Por ejemplo 873=9*97. Sus cifras suman 18. Su mayor divisor es 873/3=291 y sus cifras suman 12.

(b) Para que B(p-1) sea múltiplo de  9 también puede ocurrir que B sea múltiplo de 3 pero no de 9, luego el otro factor 3 debe pertenecer a p-1, de donde se deduce que p tiene la forma de 3k+1 con k>0, luego p será un primo mayor que 3 y entonces B no será el mayor divisor de A sino A/3. No se puede dar este caso.

(c) Si B no es múltiplo de 9, lo será p-1. Así que si A no es múltiplo de 9, tampoco lo será B y  si se cumple la igualdad de suma de cifras, ha de ser divisible entre un número primo del tipo 9k+1 con k>0. Más exigente aún: como p-1 es par, p será del tipo 18k+1

Efectivamente, a continuación presentamos los números que cumplen la propiedad que estamos exigiendo y que no son múltiplos de 9. En todos ellos figura un factor primo del tipo 18k+1. En la factorización el primer número de cada corchete es el factor primo y el segundo su exponente.

361    [19,2]
551    [19,1][29,1]
703    [19,1][37,1]
1007  [19,1][53,1]
1273  [19,1][67,1]
1691  [19,1][89,1]
1843  [19,1][97,1]
2033  [19,1][107,1]
2071  [19,1][109,1]
2183  [37,1][59,1]
2413  [19,1][127,1]
2603  [19,1][137,1]
2641  [19,1][139,1]
2701  [37,1][73,1]
2831  [19,1][149,1]
2923  [37,1][79,1]
3071  [37,1][83,1]
3173  [19,1][167,1]
3293  [37,1][89,1]
3743  [19,1][197,1]
3781  [19,1][199,1]

No creas que todos son semiprimos. Hay otros que no lo son: 18791 está en la lista y se descompone como 19*23*43.

Recuerda también que la condición no es suficiente aquí tampoco.

Hemos publicado esta lista en OEIS con la referencia https://oeis.org/A219340

El código PARI que engendra esta secuencia lo tienes a continuación, aunque en este blog la primera búsqueda se efectúa con hoja de cálculo y después se comprueba con PARI, Wmaxima o Wiris cuando es posible.

digsum(n)={local (d,p); d=0; p=n; while(p,d+=p%10;p=floor(p/10)); return(d)}
largdiv(n)=if(n==1, 1, n/factor(n)[1, 1]) \\ Charles R Greathouse IV, Jun 15 2011
{ k=0; for (n=2, 10^5,  if(digsum(n)==digsum(largdiv(n))&&n%9>0, k=k+1;write("B219340.txt",k,", ",n))); } 

Sí, esta era una cuestión menor, pero nos ha divertido estudiarla. Se puede aprender mucho con este tipo de planteamientos.



miércoles, 5 de diciembre de 2012

Más pasos hacia la complejidad (2)



Función DISTSEMI

Igual que hemos hecho para semiprimos inferiores en la anterior entrada lo podemos intentar para los superiores. Definiremos DISTSEMI(P) para P primo como la diferencia con el menor semiprimo superior a él

Esta función también está definida para todo número primo, incluidos el 2 y el 3, porque todo primo P es inferior al semiprimo 2P, luego el conjunto de semiprimos mayores que P no está vacío y poseerá un mínimo, que será el buscado.

Sus primeros valores son



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



Una lista más completa es 2, 1, 1, 2, 3, 1, 4, 2, 2, 4, 2, 1, 5, 3, 2, 2, 3, 1, 2, 3, 1, 3, 2, 2, 9, 5…

Esta sucesión no estaba publicada en OEIS, por lo que la hemos incorporado con el número A217612

http://oeis.org/A217612

Sí figuran en el catálogo los valores de los semiprimos en los que se convierte P al sumarle DISTSEMI(P) (ver http://oeis.org/A102414).

Sus valores también crecen muy lentamente. Su máximo para primos menores que 10000 es de 23, que se alcanza en P=8819. Estos son los primeros máximos:

2              2
11            3
17            4
41            5
97            9
599        12
1423      14
2683      18
6563      20
8819      23
32779    28
35983    36

También podemos conjeturar que DISTSEMI(P)/P tiende a cero al crecer P indefnidamente.


Otras cuestiones

Puede ocurrir que DISTSEMI(N)=DISTSEMI2(N), con lo que N sería la media aritmética de dos semiprimos (ver http://oeis.org/A103654)

También que DISTSEMI(N)=1 con lo que N y (N+1)/2 son ambos primos (ver http://oeis.org/A005383)  (¿por qué?)

Para  DISTSEMI(N)=2 resultan estos números

2, 7, 19, 23, 31, 47, 53, 67, 83, 89, 109, 113, 127, 131, 139, 167, 181, 199, 211, 233, 251, 257, 263, 293, 307, 317, 337, 353, 359, 379, 389, 401, 409, 443, 449, 467, 479, 487, 491, 499, 503, 509, 557, 563, 571, 577, …

Esta sucesión es una subsucesión de  http://oeis.org/A063637

En ella están aquellos en los N y N+2 son semiprimos, pero N+1 no. Así, el 13 está en http://oeis.org/A063637 pero DISTSEMI(13)=1 y por eso no está en nuestra sucesión.

NOTA: Existen pares y tríos de semiprimos consecutivos, pero no conjuntos de 4, porque uno de ellos sería múltiplo de 4.

Podríamos seguir buscando más valores, pero hay que respetar el cansancio de los lectores.

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

martes, 30 de octubre de 2012

Publicaciones temáticas



Las entradas que publicamos en este blog se suceden de forma espontánea, sin ningún orden temático y con sujeción a la actualidad. Esto produce que cuando una de ellas se basa en otra anterior pueda existir entre ambas una gran distancia temporal. A veces al mismo autor se le olvida el tratamiento dado a cualquier tema. Por otra parte, muchas de ellas presentan orientación teórica, lo que facilita su agrupamiento por temas.

Estas circunstancias nos han animado a iniciar publicaciones temáticas con algunas entradas. El resultado dista mucho de ser un manual ni una explicación sistemática de conceptos. Quien busque un instrumento académico de estudio debe hacerlo en otra parte. Simplemente se reúnen en un solo documentos los textos afines. En una primera entrega ofreceremos tres:

Sigmas y omegas

Funciones multiplicativas

Números y cifras

Estos documentos irán creciendo en sucesivas ediciones al irles incorporando nuevos temas. Por ello, cada título estará anunciado en este blog y en http://hojamat.es junto a su última edición. Si constituyen una pequeña ayuda para la mejor comprensión de los conceptos daremos por bien empleado nuestro trabajo.

domingo, 28 de octubre de 2012

Sumas de impares (2)

Esta entrada participa en la edición 3.1415926 del Carnaval de Matemáticas, alojado en el blog Series divergentes

-----------------------

Conjuntos de sumas de impares

Esta propuesta invita a seguir pensando en sumas de números impares consecutivos a trozos, o mejor todavía, todas las sumas posibles de impares en las que no se repita ningún sumando. Todo número distinto de 2 se puede descomponer en suma de impares distintos, pues, si es impar, la suma la compondría él mismo, y si es par bastaría escribir N=(N-1)+1, suma de dos impares distintos, salvo que N=2.

Podemos representar estas sumas de varias formas. La entrada anterior nos sugiere una forma, y es considerar gnomones situados cada uno en su número de orden dejando huecos. Por ejemplo, la descomposición 15=1+5+9 se puede representar así:




Más compacta y conocida es la de no dejar hueco alguno y adosar las representaciones de los impares para conseguir un diagrama de Ferrers-Young simétrico.



Estos diagramas ayudan a entender las particiones de un número
 (ver http://mathworld.wolfram.com/FerrersDiagram.html)

El que nos ha resultado parece una escalera, pero no ha de ser siempre así. En la siguiente imagen puedes ver el correspondiente a 32=1+3+13+15


¿De cuántas formas se puede descomponer un número en suma de impares distintos?

Si acotamos el problema, por ejemplo a sumas de números inferiores o iguales a 2K-1 tendremos la posibilidad de considerar hasta 2K – 1 sumas diferentes, que son las formadas por los distintos subconjuntos de {1, 3, 5, … 2K-1} que son en total 2K  y a los que hay que quitar el conjunto vacío, por lo que quedan 2K – 1 sumas diferentes. Sin embargo, los posibles resultados de esas sumas son como mucho K2, porque la suma más pequeña es 1 y la mayor 1+3+5+ … +2K-1= K2.

El análisis anterior nos indica que a partir de K=5 existen más sumas posibles que resultados, luego a algunos de estos se les puede asignar dos o más sumas distintas. Esto era de esperar. Por ejemplo, 8=1+7=3+5

Hemos organizado con hoja de cálculo la búsqueda de todas las S(N) formas posibles de descomponer un número N en sumas de impares distintos. Esencialmente ha consistido en

(1) Calcular K, el orden del mayor impar que puede pertenecer a esas sumas. que para cada número N, que es ENTERO((N+1)/2)

(2) Formar un conjunto de K dígitos binarios, con valores 0,1. Sobre ellos se construyeron todas las variaciones con repetición posibles, que representaban los subconjuntos de {1, 3, 5, 7, … 2K+1}

(3) De las sumas construidas sobre esos subconjuntos se eligieron aquellas cuyo resultado fuera N para acumularlas a un contador y obtener S(N).

De esta forma hemos conseguido la sucesión de la imagen, que coincide con http://oeis.org/A000700



En ella vemos, por ejemplo, que el 16 admite cinco descomposiciones en suma de impares distintos:

16=7+9=5+11=3+13=1+15=1+3+5+7

y 17 otras cinco:

17=17=3+5+9=1+7+9=1+5+11=1+3+13

¿Ves una posible relación empírica?

Parece ser, según la tabla, que un número par y su siguiente suelen presentar el mismo número de descomposiciones, pero algunas otras veces no. Por eso hablamos de algo empírico y aproximado. Puede ser instructivo encontrar las sumas de cada uno para descubrir algunas coincidencias.

Hemos exigido que los números impares sean distintos, pero podríamos permitir repeticiones del tipo 17=1+3+3+3+7. Esto complicaría la cuestión y nos llevaría a las particiones de un número. Puedes consultar

http://hojaynumeros.blogspot.com.es/2011/02/particiones-de-un-numero.html 

y

http://hojaynumeros.blogspot.com.es/2011/02/funciones-de-particion-de-un-numero.html

En este caso usaríamos la función “partición en números impares”, que, según demostró Euler, coincide con la partición en partes distintas. (Ver http://oeis.org/A000009) En una entrada posterior comprobaremos esta propiedad.

Estas descomposiciones son casos particulares de la llamada representación de un número según una lista, que ya tratamos en otra entrada (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, como hemos hecho en esta entrada. Si los dejamos libres pasaremos al caso general del problema, también llamado “de las monedas”.

Este problema bien merece otra entrada en la que presentemos una herramienta en hoja de cálculo para resolverlo.



martes, 23 de octubre de 2012

Las sumas de impares (1)

Esta entrada participa en la edición 3.1415926 del Carnaval de Matemáticas, alojado en el blog Series divergentes

-----------------------------

Una entrada del curso pasado la terminamos con esta propuesta

¿Qué opinas de esta serie de igualdades?






¿Son verdaderas? ¿Se pueden prolongar indefinidamente?¿Cuál es su valor común?

Al analizarla vemos que se manejan sumas de impares consecutivos. En cada una de las fracciones se han sumado varios impares consecutivos, se han “saltado” otros y después se han comenzado a sumar los siguientes.

En los numeradores se han saltado tantos impares como se han sumado cada vez (dos). La expresión de las sumas será entonces: (1+3+…2k-1)+(6k+1+6k+3+…)

que equivale a m2+9m2-4m2=6m2

En los denominadores se va formando m2+16m2-9m2=8m2

Luego los cocientes son equivalentes a 3/4

Gráficamente en los numeradores se da esta situación (imagen 1):


En ella vemos perfectamente que la suma equivale a 6 cuadrados como el pequeño de arriba a la izquierda, es decir, 6m2



En los denominadores se da esta otra (imagen 2), en la que podemos contar 8 cuadrados, que equivalen a 8m2, luego el cociente siempre será 6/8=3/4, que es la solución.

¿Ocurrirá siempre así? ¿Todas las configuraciones de este tipo representarán un múltiplo del cuadrado menor?. Lo vemos:


Sumas de impares consecutivos

Al sumar varios impares consecutivos se formaría un conjunto de gnomones adosados como el de la imagen. Su fórmula depende del gnomon inicial, que siendo k su número de orden (en la imagen 7, porque 13 es el séptimo)  viene dado por 2k-1 y el número de sumandos h. Si sumamos todos resultará 2k-1+2k+1+2k+3+…2k+2h-3 Acudimos a la suma de una progresión aritmética y daría (2k-1+2k+2h-3)*h/2=(2k+h-2)*h


En el caso de la imagen 3 el número de cuadraditos generado sería (2*7+4-2)*4=64=4h2 No debes interpretar esta cantidad en el sentido geométrico, pues el cuarto cuadrado, si observas la imagen, está formado por dos mitades, una en cada brazo del gnomón.

Este último resultado es casual, porque en general no resulta un múltiplo de h2. Lo puedes comprobar para k=8 y h=3, en el que (2*8+3-2)*3=51, que no es múltiplo de 9. Por tanto, no todos los gnomones adosados pueden representarse como un múltiplo del cuadrado de su anchura.

Serán descomponibles los que cumplan que 2k-2 sea múltiplo de h, pues entonces

(2k+h-2)*h=(Mh+h)*h=(M+1)*h2

Eso ocurre en este caso, en el que k=7 y h=3, con lo que 2*7-2=12 es múltiplo de 3. Calculando, el número engendrado sería (2*7+3-2)*3=45=5*32

Lo puedes verificar en la imagen 4


Otra forma de verlo es que esta suma de impares es una diferencia de cuadrados: (k+h-1)2 – (k-1)2 =2kh+h2-2k-2h+2k=(2k+h-2)*h y llegamos a la misma expresión.

A la inversa, si exigimos que el resultado sea del tipo Mh2, se dará (2k+h-2)*h= Mh2, lo que lleva a 2k+h-2=Mh y a 2k-2=(M-1)h, es decir a la condición sugerida de que 2k-2 sea múltiplo de h.

Las sumas con las que comenzamos este análisis (imágenes 1 y 2), no sólo lo cumplen, sino que de forma más fuerte: k-1 es múltiplo de h. Si este valor es impar, ambas condiciones son equivalentes, pero si es par no lo son.

Si exigimos que k-1 sea múltiplo de h, lo que logramos es que la partición en cuadrados tenga sentido físico, que se “vean” los cuadrados, como ocurre en la imagen 4 (y en las dos primeras si te imaginas los cuadrados troceados)

¿Y qué ocurre con el número de cuadrados?

Te proponemos una demostración:

Si exigimos la condición fuerte, que k-1 sea múltiplo de h, el número será par, e impar en el caso contrario.