Sumas del tipo m+n+mn

Como en otras ocasiones, cualquier comentario o reto aparecido en las redes sociales nos sirve de excusa para emprender un estudio. Hoy nos dedicaremos al número de descomposiciones del tipo k=m+n+mn (m>0 y n>0) que puede presentar un número k. A efectos prácticos podemos suponer que n es mayor o igual a m.

El número 99, por ejemplo, admite cuatro descomposiciones:

99=3+24+3*24
99=4+19+4*19
99=9+9+9*9
99=1+49+1*49

Otros números tan populares como el 30 no admiten ninguna descomposición de este tipo.

¿De cuántas formas se puede descomponer un número determinado? Como en ocasiones similares, comenzaremos con procedimientos de “fuerza bruta”, para ir después refinando el estudio hasta llegar al planteamiento teórico.

Con el Basic de Excel y Calc

En primer lugar debemos considerar que el valor mínimo para m y n es 1, luego el valor máximo será:

Si k=m+n+mn y damos a m el valor 1, despejando n resulta:

K=1+n+n, luego n<=(k-1)/2 y este valor sería la cota para m y n. Por otra parte, al despejar n en general, n=(k-m)/(m+1), este valor ha de ser entero y mayor que m (si queremos evitar repeticiones). Con esto ya podemos construir un algoritmo para contar el número de descomposiciones de este tipo que presenta un número dado.

Public Function numsumamn(k)
Dim m, n,  p

p = 0 ‘Contador de éxitos
For m = 1 To (k - 1) / 2 ‘m recorre el rango desde 1 hasta la cota
n = (k - m) / (m + 1) ‘El valor de n se despeja respecto a m
If n >= m And n = Int(n) Then p = p + 1 ‘Si es entero y mayor o igual a m, vale
Next m
numsumamn = p
End Function

Con este algoritmo podemos confeccionar tablas para esta función. La siguiente corresponde a los 20 primeros números:

Vemos que, por ejemplo, el 15 debe descomponerse de dos formas. Aquí las tienes:

1+7+1*7=15; 3+3+3*3=15

Algoritmo con el lenguaje PARI

Este algoritmo se traduce con facilidad al lenguaje PARI:

numsumamn(k)=local(p=0);for(m=1,(k-1)/2,n=(k-m)/(m+1);if(n==truncate(n)&&n>=m,p+=1));p

Con él y una estructura repetitiva puedes encontrar un listado de enteros con un número de descomposiciones fijado. El siguiente código nos devuelve los primeros números que admiten tres descomposiciones:

numsumamn(k)=local(p=0);for(m=1,(k-1)/2,n=(k-m)/(m+1);if(n==truncate(n)&&n>=m,p+=1));p
for(i=1,200,if(numsumamn(i)==3,print1(i,", ")))

Veamos el caso del 55: 1+27+1*27=3+13+3*13=7+6+7*6=55

Se obtienen las tres descomposiciones previstas.

Puedes experimentar con estos algoritmos, aunque al final de la entrada aprenderás un método mucho más eficiente.

Comprobación con Cartesius

Nuestra hoja de cálculo Cartesius (http://www.hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#cartesius),que desarrolla productos cartesianos condicionados, nos puede servir para comprobar los valores de la función numsumamn. Como sabemos que la cota para m y n es (k-1)/2, (o k/2 para simplificar), bastará combinar los distintos valores de ambos y destacar tan solo aquellos en los que m+n+mn=k. Quedaría así en el caso de k=71:

En primer lugar se fijan 2 elementos (serían m y n). Después se hacen recorrer el rango 1..36, que es la cota aproximada por exceso. La parte importante es la de exigir es x1+x2+x1*x2=71, según la cuestión que estamos resolviendo, y, por último, pedimos arreglos crecientes para eliminar duplicidades. Nos deberían dar 5 soluciones, según el valor de numsumamn(71), y, en efecto, los resultados son:

Lo podemos calcular: 1+35+1*35=36+35=71; 2+23+2*23=25+46=71; 3+17+3*17=20+51=71;
5+11+5*11=16+55=71; 7+8+7*8=15+56=71.

Puedes comprobar así cualquier valor de numsumamn(k)

Estudio teórico

Todo lo anterior se basa en un estudio “ingenuo”, en el que no se analiza la cuestión y sólo se pretende obtener resultados. Ahora veremos que los mismos tienen un fundamento teórico muy simple, que nos llevará a una fórmula para el número de descomposiciones del tipo m+n+mn=k

Basta darse cuenta de que la expresión estudiada equivale a (m+1)(n+1)-1. Por ejemplo, 2+35+2*35=37+70=107 es igual a (2+1)(35+1)-1=3*36-1=108-1=107.

Esto nos aclara la situación, porque el número de descomposiciones del tipo m+n+mn para un número k coincide con el de los pares de divisores cuyo producto es k+1. Así, las cuatro descomposiciones del número 99 (3+24+3*24, 4+19+4*19, 9+9+9*9, 1+49+1*49) coinciden con todos los pares de divisores (m+1)(n+1) del número k+1, en este caso 100. En efecto, los pares son: 2*50, que da lugar a 1+49+1*49, 4*25, que produce 3+24+3*24, 5*20 para 4+19+4*19 y 10*10, que se empareja con 9+9+9*9

El número de descomposiciones de k en expresiones m+n+mn coincide con el del número de pares de productos p*q=k+1 con p>1 y q>1.

El número de pares de este tipo está relacionado con la función TAU de k+1, que cuenta el número de divisores que posee k+1, y que tiene la expresión

En ella los valores de a₁, a₂,, a₃,,…son los exponentes de los factores primos de k+1. Si el valor de esa función es par, el número de productos p*q=k+1 será la mitad, y si es impar, la mitad más 1. A ese resultado habrá que restarle 1, porque el par 1*(k+1) no nos sirve. Así que quedaría:

Podemos comprobarlo con ejemplos concretos:

K=23; 24=2³*3; TAU(24)=(1+3)(1+1)=8; 8/2-1=3. Los pares válidos de divisores serán 2*12, 3*8, 4*6. Así que 23 debe admitir tres descomposiciones. Es fácil ver que son estas: 1+11+1*11, 2+7+2*7 y 3+5+3*5. Aquí tienes la comprobación con Cartesius:

En el caso de k+1=144, cuadrado perfecto, su función TAU es impar, lo que da sentido al hecho de que usemos la parte entera. Lo vemos:

K=143; k+1=144; 144=2⁴*3²; TAU(144)=(1+4)(1+2)=15; INT((15+1)/2)=8; 8-1=7.

Deberán aparecer 7 soluciones para los productos de divisores:2*72, 3*48, 4*36, 6*24, 8*18, 9*16, 12*12. Existirán, pues, 7 soluciones para nuestro problema. Las conseguimos con Cartesius:

Puedes irlas comprobando: 1+71+1*71=72+71=143; 2+47+2*47=49+94=143,…

Casos particulares

K+1 primo

Según lo anterior, los valores de k tales que k+1 sea primo, no admitirán la descomposición en m+n+mn.

Recuerda que entre los primeros 20 números tenemos (ver tabla de arriba) que 1, 2, 4, 6, 10, 12, 16, y 18 no admiten descomposiciones m+n+mn. Súmales una unidad y te resultarán los primeros primos: 2, 3, 5, 7, 11, 13,…

K+1 semiprimo

Los semiprimos poseen sólo dos factores primos, luego en ellos TAU=(1+1)(1+1)=4, y como 4/2-1=1, resultará que k sólo admitirá una descomposición. Es el caso de 3, 5, 8, 9,…en los que k+1 es semiprimo: 4=2*2, 6=2*3, 9=3*3, 10=2*5.

La propiedad contraria no es cierta, ya que 7 sólo admite la descomposición 1+3+1*3 y 8 no es semiprimo.

K+1 cuadrado

Si k+1 es cuadrado, k presentará una suma en la que m=n, como es fácil ver. Si k+1=p*p, k será igual a p-1+p-1+(p-1)(p-1). Es el caso, por ejemplo de 48, ya que 49=7*7 y 48=6+6+6*6.

Lo dejamos aquí. Este tipo de cuestiones elementales que dan lugar a experimentaciones sencillas se pueden abordar en las clases de Matemáticas de la Enseñanza Media. Sería divertido lanzar la idea en un trabajo por grupos y ver cada uno qué caminos emprende en sus búsquedas. No sería extraño que alguno diera con el truco del k+1.

Cartesius(6) – Particiones (2)

Condicionamientos sobre las particiones de un conjunto

En la entrada anterior de esta serie (http://hojaynumeros.blogspot.com.es/2017/06/cartesius-5-particiones-1.html) procedimos a crear particiones en un número, y en algunas condicionamos los sumandos, para que fueran primos, triangulares o cuadrados.  Ahora condicionaremos los resultados, y más adelante repasaremos los condicionamientos clásicos.

Condicionamientos sobre resultados

Las particiones de un número las hemos definido a partir de todas las sumas posibles, pero estas podrían ser condicionadas, en el sentido de suprimir algunas de ellas. Lo vemos con un ejemplo:

¿De cuántas formas podemos descomponer el número 7 en particiones con los dos sumandos menores iguales? 

Si no condicionamos los sumandos, existen, según vimos, 15 particiones. Al obligar a que los dos menores sean iguales, restringiremos ese número. Podemos plantearlo así:

XRANGO=7
XT=1..7
CRECIENTE
ES X1=X2
SUMA=7

Es el mismo planteamiento de la entrada anterior sobre el tema de particiones, con el añadido ES X1=X2, que obliga a que los dos primeros sumandos sean iguales. Como hemos decidido que los arreglos sean crecientes, estos dos primeros serán también los menores. El resultado es:

Resultan ocho particiones en lugar de 15.

Podemos introducir muchos más condicionamientos: fijar la suma parcial de los tres menores o exigir que el tercer sumando sea mayor que el segundo, y otros parecidos.

Particiones condicionadas

Todos estos condicionamientos se suelen expresar como función así:
P(N/condicionamiento)
De esta forma, el anterior ejemplo se escribiría como P(7/x1=x2)

Otro ejemplo

Imaginemos que deseamos que el tercer sumando sea a su vez suma de los dos anteriores. Procederíamos así:

XRANGO=7
XT=1..7
CRECIENTE
ES X3=X1+X2
SUMA=7

Al desarrollar veríamos que es un ejemplo sin interés, porque sólo existe una suma así (siendo sumandos crecientes)

En efecto, si los valores iniciales son 1, 1, 2, ya no admiten para suma 7 nada más que un 3.

Condicionamientos clásicos

Ya vimos en entradas anteriores sobre particiones que históricamente se han planteado algunos condicionamientos especiales a las particiones. Los recorremos de nuevo:

Función de partición Pk(N) 

Es la misma función P(N) condicionada a que sólo intervenga un número K de sumandos:

Pk(N)= P(N / k sumandos): Particiones con un número k de sumandos fijado.
Con la hoja Cartesius es fácil programar esta función, ya que basta con definir XTOTAL=K, dejando el resto de condiciones igual.
Por ejemplo, evaluamos las particiones del número 12 en 4 sumandos, es decir p4(12):

xtotal=4 
xt=1..12 
creciente 
suma=12

Resultan 15 particiones.

Función de partición Q(N)

Como la anterior, cuenta el número de particiones, pero en este caso se exige que los sumandos sean todos distintos. Por ejemplo, el entero 7 admite las siguientes particiones como números distintos: 7 = 6+1 = 5+2 = 4+3 = 4+2+1, luego Q(7)=5

Euler demostró que esta función coincide con el número de particiones de n en partes impares. Lo veremos más adelante.

La programación de esta función se consigue añadiendo la condición NO REPITE, para que todos los sumandos sean iguales. En el caso del 7 podríamos escribir:

xrango=7
xt=1..7
suma=7
creciente
no repite

Tendríamos el resultado siguiente:

Sólo son posibles las cinco particiones.

Particiones en partes impares P(N/Impar)

Introducimos este condicionamiento porque da lugar a un resultado obtenido por Euler:

El número de particiones de un número en sumandos distintos coincide con el de particiones en sumandos impares

Con Cartesius el planteo se limita a exigir que los sumandos sean impares. Basta condicionar los sumandos como una sucesión del tipo 2*n-1:

Obtenemos cinco particiones, el mismo número que nos dio el de sumandos distintos.

Podíamos haber usado un filtro, para que los sumandos sean impares:

Resultaría más rápido que el planteamiento anterior. Por último, otra posibilidad es definir los sumandos como un conjunto:

También es más rápido.

En otra futura entrada seguiremos condicionando las particiones de un número.

Números figurados e interpolación polinómica

Las entradas sobre números piramidales publicadas en este blog contenían siempre una fórmula polinómica para expresar cada término de la sucesión. Por ello parece conveniente presentar un método general para la obtención de esas fórmulas. Disponemos para ello de la teoría de la interpolación polinómica, en la que elegiremos el método de Newton, y una hoja de cálculo que nos facilitará las cosas.

Teoría

Los conceptos y métodos de la interpolación polinómica los puedes encontrar en cualquier texto del primer ciclo de estudios universitarios. Todos se basan en el cálculo con diferencias sucesivas. En nuestro caso nos limitaremos a la suma de funciones enteras definidas sobre los primeros números naturales, lo que simplifica mucho los cálculos.

Por ejemplo, imaginemos que deseamos sumar los primeros números oblongos: 1*2, 2*3, 3*4, 4*5, 5*6,…o bien, 2, 6, 12, 20, 30,…Queremos obtener una expresión para 2+6+12+20+30+…

En las técnicas de interpolación que usaremos, la primera operación es la obtención de las diferencias sucesivas, es decir, diferencias entre los elementos, diferencias entre las diferencias, y así sucesivamente hasta (en el caso polinómico) que sean todas iguales. Lo intentamos con el ejemplo. En primer lugar encontramos las sumas parciales de oblongos: 2, 2+6=8, 2+6+12=20,…que serían 2, 8, 20, 40, 70, 112, 168, 240,…

Lo puedes organizar con una hoja de cálculo:

La siguiente imagen, tomada de nuestra hoja newton.xls, puedes entender muy bien el concepto de diferencias sucesivas. En primer lugar hemos escrito nuestra sucesión: 2, 8, 20, 40, 70, 112, 168,…Después hemos ido restando cada elemento con el siguiente: 6, 12, 20, 30, 42, 56,…(resultan ser los oblongos). A continuación hemos restado esas diferencias: 6, 8, 10, 12, 14,…entre sí, y al final en otra resta, hemos llegado a 2, 2, 2,…Esa es la señal de que esos números siguen una expresión polinómica, el que las diferencias se hagan iguales y las siguientes nulas.

Como aquí las diferencias constantes se alcanzan en tres pasos, la fórmula que buscamos será un polinomio de tercer grado. Lo repasamos en teoría:

Fórmula de interpolación de Newton

Cuando en un proceso se llega a diferencias constantes, sabemos que es posible expresar la sucesión dada mediante un polinomio dependiente del número de orden. La fórmula hallada por Newton es algo compleja en el caso general, en el que hay que usar diferencias divididas, pero se simplifica bastante en el caso de un polinomio aplicado al conjunto 1, 2, 3, 4,…Sería esta:

En ella a₀ es el primer término, d₁ la primera diferencia, d₂ la primera de las segundas diferencias, y así sucesivamente. En nuestro caso sería:

P(x)=2+6(x-1)+6(x-1)(x-2)/2!+2(x-1)(x-2)(x-3)/3!

Reduciendo a común denominador y simplificando:

Lo hemos comprobado con la hoja de cálculo. Observa la coincidencia de los valores en rojo:

Como ves, lo que es más complicado es la simplificación, pero el método es simple: encontrar diferencias sucesivas hasta que se estabilicen, y aplicar la fórmula de interpolación simplificada para los puntos de apoyo 1, 2, 3, 4,…
Todo esto puedes reproducirlo con nuestra hoja de cálculo newton, que puedes descargar desde

http://www.hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#newton

Recuerda que sólo te vale para sumas definidas sobre los primeros naturales.

Basta escribir los valores de la sucesión en la segunda fila

y leer los coeficientes (en forma de fracción) más abajo:

Es fácil de interpretar (de derecha a izquierda): 2/1 es el coeficiente de 1, 6/1 el de (x-1), 6/2 para (x-1)(x-2) y, finalmente, 2/6 para (x-1)(x-2)(x-3). Después vendría la simplificación, pero si quieres ahorrártela, la hoja dispone del cálculo para un valor concreto. Por ejemplo, ¿cuánto suman los diez primeros oblongos?

Para ello dispones de las celdas adecuadas

La respuesta es 440. Hay que advertir que puede producir pequeños errores para índices grandes, por lo que se aconseja comprobar.

Si deseas evitarte la simplificación puedes acudir a un CAS. Nosotros hemos usado wxMaxima para obtener el resultado previsto:

Otro paso sería el intentar, si es posible, buscar una interpretación al resultado obtenido. En nuestro caso es fácil ver que, para x mayor o igual a 3, se reduce a

Este proceso se puede repetir para números poligonales, piramidales o poligonales centrados (y otros similares que nos inventemos), porque todos se basan en sus definiciones en la acumulación de sumas, lo que garantiza que la fórmula buscada es de tipo poligonal.

Otro ejemplo

Sabemos que los números piramidales triangulares se construyen sumando los triangulares, y estos, a su vez, acumulando los naturales. Con un sencillo esquema los identificamos:

Luego los primeros piramidales son 1, 4, 10, 20,….Los volcamos en la hoja newton para descubrir sus diferencias y los coeficientes de interpolación:

Las diferencias son 1, 3, 3 y 1, y con ellas se construyen los coeficientes 1/1, 3/1, 3/2 y 1/6. Rellenamos la fórmula de interpolación y queda:

P(x)=1+3(x-1)+3/2(x-1)(x-2)+1/6(x-1)(x-2)(x-3)

Simplificamos con wxMaxima:

Coincide con la que se obtuvo en la entrada correspondiente a los números tetragonales (o piramidales triangulares)

http://hojaynumeros.blogspot.com.es/2017/04/numeros-piramidales-2-tetraedros.html

Con lo aprendido hoy estamos preparados para saltar a la cuarta o quinta dimensión, y sumar números piramidales consecutivos. Lo dejamos para otra entrada.

Números piramidales (5) Hexágonos

Quienes sigáis esta serie sobre números piramidales adivinaréis que los de tipo hexagonal son suma de los primeros números poligonales hexagonales, 1, 6, 15, 28, 45, 66, 91, 120, 153, 190, 231, 276, 325,… Ve acumulando sumas y obtendrás los piramidales hexagonales (PHEX):

1, 7, 22, 50, 95, 161, 252, 372, 525, 715, 946, 1222, 1547, 1925, 2360, 2856, 3417, 4047, 4750, 5530, 6391, 7337, 8372,… http://oeis.org/A002412

Con nuestra calculadora Calcupol puedes también recorrerlos. Descárgala desde

http://www.hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#figurados

Fija el tipo en Piramidal de orden 6, escribe un 1 en pantalla y pulsa reiteradamente la tecla PROX. Así los obtendrás uno a uno. En la imagen hemos llegado hasta el 525.

Como todos los números piramidales, estos poseen una expresión polinómica que los genera. En este caso es

PHEX(n) = n(n + 1)(4n - 1)/6

Esta fórmula se obtiene particularizando para 6 la general de los piramidales:

Lo podemos comprobar, por ejemplo, para n=6, y nos queda:
PHEX(6)=6*7*23/6=161, como era de esperar.

Recurrencias

Estos números presentan varias formas de generación por recurrencia. La más práctica es la siguiente:

a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) + 4.

Podemos organizarlo según esta tabla, que iniciamos con 1, 7, 22. En cada fila añadimos un elemento nuevo calculado mediante la recurrencia:

Como suma

De diferencias de cuadrados

La definición de los números figurados mediante acumulación de otros más simples hace que sean frecuentes las generaciones mediante sumas de elementos. En el caso de los piramidales hexagonales basta acumular diferencias de cuadrados entre un número natural N y todos los menores que él. Lo puedes ver en esta tabla:

Por ejemplo, 50 es igual a 4^2-0^2+4^2-1^2+4^2-2^2+4^2-3^2

Se puede desarrollar algebraicamente, si recuerdas la fórmula para la suma de los primeros cuadrados:

S = n²-0²+n²-1²+n²-2²+n²-3²+…n²-(n-1)² = n³-n(n-1)(2n-1)/6 = n(n+1)(4n-1)/6

Hemos desembocado en la fórmula de los piramidales hexagonales, lo que demuestra la propiedad.

De números naturales impares

Todos los números piramidales hexagonales son suma de triangulares impares. Así, el tercero a(3) = t(1)+t(3)+t(5) = 1+6+15 = 22

Algebraicamente:

1*2/2+3*4/2+5*6/2+…(2n-1)n, expresada como sumatorio queda:

Si desarrollas llegarás a la fórmula del piramidal hexagonal: PHEX(n)=n(n+1)(4n-1)/6

Relación con números combinatorios

El denominador 6 de la fórmula de los piramidales hexagonales sugiere su relación con números combinatorios de índice inferior igual a 3, y, en efecto, existen esas relaciones:

Lo desarrollamos:

C(n+2,3)+3C(n+1,3)=(n+2)(n+1)n/6+3(n+1)n(n-1)/6=n(n+1)/6*(n+2+3n-3)=n(n+1)(4n-1)/6

Es un simple identidad algebraica.

Otra relación:

Es también una identidad algebraica sencilla.

Fin de la serie

No podemos extender en demasía la exposición de números piramidales. Terminamos con una breve referencia a los octogonales.

Como todos los anteriores, los piramidales octogonales resultan de la suma de los poligonales del mismo número de lados. Por ejemplo, la pirámide octogonal de índice 5 resultará de la suma: 1+8+21+40+65=135

Los primeros octogonales son:

1, 9, 30, 70, 135, 231, 364, 540, 765, 1045, 1386, 1794, 2275, 2835, 3480, 4216, 5049, 5985, 7030, 8190, 9471, 10879,… http://oeis.org/A002414

Su fórmula: a(n)=n(n+1)(2n-1)/2

Por ejemplo, a(7)=7*8*13/2=28*13=364

En una próxima entrada justificaremos este tipo de fórmulas mediante interpolación polinómica sobre el conjunto {1, 2, 3, 4,…, n}

Fin de temporada

Con esta entrada damos fin a la temporada 2016-17 de este blog. Como todos los años, aprovecharemos el verano para resumir y ordenar materiales, así como actualizar otros pertenecientes a hojamat.es. Nos volveremos a encontrar en septiembre. Feliz verano.

Cartesius (5) - Particiones (1)

El tema de las particiones ya ha sido tratado en este blog desde el punto de vista de las funciones generatrices, y también con la ayuda de nuestra herramienta “Cartesius”. Como esta ha sido mejorada sustancialmente, volveremos a tratar el tema incluyendo nuevas prestaciones.

Si deseas contar con las funciones generatrices recorre las entradas de este blog relativas al tema, a las que puedes acceder mediante la etiqueta “Funciones generatrices” en el panel derecho de este blog

No trataremos ese tema en esta nueva serie.

También puedes repasar el tema de particiones con la etiqueta correspondiente:

En esta serie repasaremos conceptos y se añadirán condicionamientos interesantes.

Particiones de un número

Se llaman particiones de un número natural N a las distintas formas de descomponerlo en sumandos enteros positivos sin tener en cuenta el orden y admitiendo repetición de sumandos.  Para no tener en cuenta el orden se puede exigir que los sumandos sean decrecientes en sentido amplio (o crecientes).  Así es más fácil representarlos.

Por ejemplo, el 9 se puede descomponer en estas sumas:

9,   8+1,  7+2,   7+1+1,   6+3,   6+2+1,   6+1+1+1,   5+4,   5+3+1, 5+2+2  5+2+1+1,   5+1+1+1+1,   4+4+1,  4+3+2,  4+3+1+1,   4+2+2+1,   4+2+1+1+1  4+1+1+1+1+1,   3+3+3,  3+3+2+1,   3+3+1+1+1, 3+2+2+2,   3+2+2+1+1,   3+2+1+1+1+1 3+1+1+1+1+1+1, 2+2+2+2+1, 2+2+2+1+1+1, 2+2+1+1+1+1+1, 2+1+1+1+1+1+1+1  1+1+1+1+1+1+1+1+1

Son 30 en total

Al número total de particiones de N lo representaremos por la función P(N). Por tanto la afirmación anterior se puede representar como P(9)=30. En muchos lenguajes de programación se representa como partitions(n), y si solo se desea contar las particiones, como #partitions(n).

Particiones con Cartesius

La nueva versión de nuestra herramienta la puedes descargar desde

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

Con ella es más sencillo el desarrollo de particiones, gracias a la condición XRANGO, que recorre todos los números de sumandos de la partición. Hay que advertir que los desarrollos pueden resultar lentos, y casi imposibles para números grandes (Cartesius solo usa hasta 12 elementos), especialmente en LibreOffice Calc. Si se tiene a la vista el desarrollo se puede observar que la lentitud aparece en el tramo final, cuando casi todos los sumandos tienen el valor 1. En ese momento se puede adivinar el resultado aunque no haya terminado. Cada equipo y versión de hoja de cálculo tiene una forma de interrumpir la ejecución de una macro, pero a veces no es fácil encontrar ese dato. En el equipo del autor y con Excel 2010 funciona la combinación de pulsar la tecla de Windows y ESC.

Repasa en las entradas anteriores sobre Cartesius su funcionamiento básico, Debes abrir la hoja Planteamiento, borrar las condiciones si las hay y escribir las nuevas. Con el botón Iniciar obtienes las particiones. El planteamiento mínimo para una partición, como para el caso 7, es:

Si la usas, no tengas prisa, que tarda. Resultan 15 particiones:

Puedes comprobarlo en la página de WolframAlpha, que además te ofrece los diagramas de Ferrer

El lenguaje PARI también te puede servir para comprobar:

O bien consigues el desarrollo

O bien el número. Estudia el planteamiento de la primera línea:

Llegados a este punto, la pregunta es obvia, y es que para qué usar Cartesius si disponemos de estas herramientas. La respuesta está en los condicionamientos.

Particiones sobre números de un tipo determinado

Imagina que deseamos saber cuántas formas existen de expresar el número 12 como suma de primos. En este caso deberemos exigir que todos los sumandos en Cartesius sean de ese tipo. Sabemos que los primos inferiores a 12 son: 2, 3, 5, 7 y 11. Cinco en total. Aprovechamos que en Cartesius los sumandos se pueden definir mediante conjuntos (valores separados por comas, sin espacios), lo que facilita las cosas:

Declaramos un rango de sumas del 1 al 5, explicitamos cuáles son los sumandos y exigimos que la suma sea igual a 12. Resultan 6 posibilidades:

En este caso conocemos los sumandos, pero en otros no merece la pena buscarlos. Por ejemplo, deseamos conocer las particiones del número 1001 en suma de primos comprendidos entre 300 y 350. No esperamos más ni menos de tres sumandos, luego el planteamiento adecuado sería:

Esto es ya algo más complicado: XTOTAL=3 obliga a que sean tres sumandos, XT=300..350 establece el rango de los sumandos, y XT=FILTRO(PRIMO) indica que se seleccionan los sumandos primos, que en este caso son los de la imagen:

Obtendríamos dos sumas posibles:

Este ejemplo justifica el uso de Cartesius. Disponemos de los filtros PRIMO, PAR, IMPAR, CUADRADO, FIBONACCI y TRIANGULAR. En próximas versiones se podrían añadir más. Consulta las Instrucciones de Cartesius para más detalles. Puedes obtenerla en

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

Otro ejemplo

Sabemos que todo número entero se descompone en suma de a lo sumo tres números triangulares, pero ¿de cuántas formas? Por ejemplo, el número 30. Planteamos:

Y se obtiene

Existe otro teorema similar que afirma que todo número se puede descomponer en a lo sumo cuatro cuadrados. Bastaría para comprobarlo cambiar XRANGO a 4 y efectuar un filtro de cuadrados. Lo probamos con el número 100:

Resultan cinco posibilidades (salvo el orden):

Es curioso que todos tienen sumandos repetidos.

Por hoy hemos desarrollado bastante. En la siguiente entrada expresaremos números en función de listas o de otros tipos, como factoriales, números de Fibonacci, impares y demás. Comprobaremos con estos últimos un teorema importante que ya tratamos en este blog.

Descomposiciones múltiples del tipo x^2+ky^2

Últimamente nos han surgido cuestiones sobre descomposiciones en suma de cuadrados. Recordamos dos:

http://hojaynumeros.blogspot.com.es/2016/09/expresion-cuadratica-x2ky2-n.html
http://hojaynumeros.blogspot.com.es/2017/01/numero-de-descomposiciones-en.html

Siguiendo esta línea, hoy recorreremos aquellos números que se pueden descomponer en una suma del tipo x^2+ky^2, con k>1, x>0, y>0 de varias formas distintas. Expresado así, es un problema bastante general, que se presta a muchos casos y subcasos, por lo que sólo se desarrollarán algunos, con el fin de aprender a tratarlos y sacar alguna posible propiedad.

Hay un hecho que vale para todos ellos, y es que si N admite una descomposición de un tipo dado x^2+ky^2, con k>1, si lo multiplicamos por un cuadrado admitirá el mismo número de descomposiciones al menos, luego muchas soluciones que encontremos engendrarán otras al multiplicarlas por un cuadrado.

Caso k=2

Si deseamos encontrar todas las expresiones de un número de la forma x^2+2y^2, nuestra mejor herramienta es la que hemos presentado hace pocas semanas bajo el nombre de Cartesius, hoja de cálculo especializada en productos cartesianos condicionados. Puedes descargarla en versión para Excel y LibreOffice Calc, así como las instrucciones en la dirección

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

En este caso bastará concretar: 2 sumandos, uno de ellos un cuadrado, el otro doble de un cuadrado, y que la suma de ambos sea igual al número propuesto. Por ejemplo, para saber  cuántas descomposiciones de este tipo permite el número 969, daríamos a Cartesius estas instrucciones:

xtotal=2
xt=1..33
x1=suc(n^2)
x2=suc(2*n^2)
suma=969

La primera exige que sean dos sumandos. La segunda fija un rango de búsqueda de 1 al 33, para que no se nos escape ningún cuadrado inferior a 969, y las siguientes determinan un sumando n^2 y otro 2*n^2. Así se recorrerán todas las posibilidades, que resultan ser cuatro. Si copias esas instrucciones en Cartesius (zona de condiciones) y pulsas el botón Iniciar obtendrás estos cuatro sumandos:

Traducidos a nuestra cuestión, equivalen a las igualdades

969=1^2+2*22^2=13^2+2*20^2=29^2+2*8^2=31^2+2*2^2

No seguiremos por ahí. Nos interesa buscar números con este tipo de propiedad, y podemos dejar Cartesius solo para comprobar. Nos pasamos al VisualBasic de las hojas de cálculo.

Es fácil diseñar una función que recorra todas las posibilidades de suma del tipo x^2+ky^2 para un número dado. El que tenga forma de función nos permite construir tablas para distintos valores, cosa imposible con Cartesius. Proponemos esta:

Public Function numsumacuad(n, k)  ‘Tiene dos parámetros, el número n y k
Dim x, p

p = 0 ‘Iniciamos el contador a cero
For x = 1 To Sqr(n - k) ‘Al estar x elevada al cuadrado, será inferior a una raíz cuadrada
If escuad((n - x ^ 2) / k) Then p = p + 1 ‘Si la diferencia dividida entre k es cuadrado, vale
Next x
numsumacuad = p ‘Contamos las veces
End Function

Esta función no se puede aplicar a 1, pero ya sabemos que no es suma de cuadrados no nulos.

Así podemos formar tablas como esta:

Vemos que entre 20 y 30 solo tienen solución 22, 24 y 27, y esta, doble. Todos los números que admiten al menos una de estas descomposiciones, se podrán representar como suma de tres cuadrados simétricos. Es sólo una curiosidad, pero atractiva. Así, 24=2^2+4^2+2^2

Este número de soluciones, asignando un 0 al 1, está publicada en http://oeis.org/A216278

Destacamos en negrita el intervalo entre 20 y 30.
0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 2, 0, 0, 0, 0, 0, 2, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 2…

Con la función numsumacuad podemos seleccionar aquellos números que admiten dos representaciones (al menos) distintas del tipo x^2+2y^2. Los primeros son estos:

27, 33, 51, 54, 57, 66, 81, 99, 102, 108, 114, 123, 129, 132, 153, 162, 171, 177, 187, 198, 201, 204, 209, 216, 219, 228, 243, 246, 249, 258, 264, 267, 291, 297, 306, 321, 323, 324, 339, 342, 354, 363, 369, 374, 387, 393, 396, 402, 408, 411, 417, 418, 432, 438, 451, 456, 459, 473, 486, 489, 492, 498,…

Todos los números de la sucesión son compuestos, pues Fermat, Euler y Gauss demostraron que los números primos sólo podían descomponerse como x^2+2y^2 de forma única, y no todos, porque deberían ser congruentes con 1 o 3 respecto al módulo 8.

En esta tabla figuran los primeros números primos que se pueden descomponer de la forma dada, y vemos que sus restos son 1 o 3 módulo 8. Un buen ejercicio es adivinar la descomposición en cuadrados mentalmente: 73=1^2+2*6^2, 89=9^2+2*2^2,…

En este tipo de búsquedas siempre recomendamos el lenguaje PARI como complemento o ampliación. En esta cuestión el código adecuado sería, por ejemplo:

for(n=3,500,p=0;for(x=1,sqrtint(n-2),if(issquare((n - x ^ 2) / 2),p+=1));if(p>1,print1(n,", ")))

Si cambiamos la condición p>1 por p==2 obtendremos los números que admiten exactamente dos descomposiciones del tipo que estamos estudiando:

27, 33, 51, 54, 57, 66, 81, 102, 108, 114, 123, 129, 132, 162, 177, 187, 201, 204, 209, 216, 219, 228, 246, 249, 258, 264, 267, 291, 321, 323, 324, 339, 354, 374, 393, 402, 408, 411, 417, 418, 432, 438, 451, 456, 473, 489, 492, 498,…

Vemos que faltan algunos, como el 99, que admiten más de una descomposición.
En todos estos números se dará la siguiente igualdad

N= a²+2b²=c²+2d²  que equivale a (a+c)(a-c)=2(d+b)(d-b)

De esa identidad se deduce que a y c han de tener la misma paridad, para que coincida con el múltiplo de 2 del segundo miembro, pero entonces (a+c)(a-c) será múltiplo de 4, lo que obliga a que también d y b tengan la misma paridad.

Lo puedes comprobar con los ejemplos.

Algunos de estos elementos son cuadrados

81, 324, 729, 1089, 1296, 2025, 2601, 2916, 3249, 3969, 4356, 5184, 6561, 8100, 9801,…

En ellos se cumple que n²=x²+2y², o bien (n²-x²)/2=y², es decir, que (n+x)(n-x)/2=y^2. Podemos interpretar que estos números generan triángulos de catetos enteros cuya área coincide con la de un cuadrado. Por ejemplo, tomamos 1089=33^2. Según nuestra hoja Cartesius admite cuatro descomposiciones del tipo deseado:

Si tomo la segunda, tendré: n=33, x=17, y=20, y se cumple 33²=17²+2*20², y aplicando los cálculos anteriores, se puede formar el triángulo de lados (33+17, 33-17), es decir 50 y 16, con área 50*16/2=400=20², que efectivamente, es un cuadrado.

Con el primero: (33+11,33-11) se convierte en los lados 44 y 22 de área 44*22/2=484=22^2.

Tipo x^2+3y^2

Este caso ofrece menor interés. Estos son los primeros números que admiten más de una descomposición de ese tipo:

Con más de un caso de sumas de cuadrados

28, 52, 76, 84, 91, 112, 124, 133, 148, 156, 172, 196, 208, 217, 228, 244, 247, 252, 259, 268, 273, 292, 301, 304, 316, 336, 343, 364, 372, 388, 399, 403, 412, 427, 436, 444, 448, 468, 469, …

Los puedes generar con este código PARI o con Cartesius o nuestra función en Visual Basic para Excel.

for(n=4,1000,p=0;for(x=1,sqrtint(n-3),if(issquare((n - x ^ 2) / 3),p+=1));if(p>1,write1("final.txt",n,", ")))

Por ejemplo, 469 se descompone como

469=13^2+3*10^2=19^2+3*6^2

Podemos seguir con otros números de casos. Por ejemplo, con tres o más descomposiciones están:

28, 52, 76, 84, 112, 124, 148, 156, 172, 196, 208, 228, 244, 252, 268, 292, 304, 316, 336, 364, 372, 388, 412, 436, 444, 448, 468, 496,…

Vemos que falta el 469, pero no el 468, que admite tres descomposiciones:
468=6²+3*12²=15²+3*9²=21²+3*3²

Puedes intentar descubrir casos llamativos. Un ejemplo: 2548 es el primero con nueve descomposiciones distintas. Insertamos el desarrollo con Cartesius. Las columnas X4 y X5 son los valores de x e y respectivamente:

Tipo x^2+4y^2

Su interés radica en que produce sumas simétricas de cinco cuadrados. No lo estudiaremos. Tan sólo un ejemplo:

464=10^2+10^2+8^2+10^2+10^2


Tipo 2x^2+3^y2

También este caso presenta el interés de obtener una suma de cinco cuadrados que sea simétrica y con bases alternantes. También damos un ejemplo:

365 =3^2+13^2+3^2+13^2+3^2

La reiteración mata el interés. Es mejor parar aquí y dejar abiertos otros caminos de investigación.