jueves, 19 de octubre de 2017

Suma de cuadrado y capicúa


Hoy comenzamos con una cuestión sencilla que nos va a permitir algún desarrollo:

¿De cuantas formas se le puede restar a N un cuadrado y que la diferencia sea capicúa?

Operaremos con capicúas de al menos dos cifras, pues el conjunto de 0 a 9, aunque se consideran capicúas, produce resultados sin interés. Con nuestra herramienta Cartesius (http://www.hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#cartesius) el estudio es muy simple. Basta usar las condiciones siguientes, que hemos particularizado para el número 892:

xtotal=2
xt=1..1000
X1=filtro(cuadrado)
x2=filtro(capicua)
suma=892

En ellas se suman dos números del 1 al 1000 filtrando el primero como cuadrado y el segundo como capicúa. El resultado es

Como vemos, se obtienen cinco soluciones.

Número de descomposiciones

Con Cartesius se presenta el proceso de forma clara, pero para contar soluciones es preferible otra herramienta. Comenzaremos con el BASIC de las hojas de cálculo. Se puede definir fácilmente una función que cuente las sumas que se producen. Necesitaremos la función ESCAPICUA y con ella organizar un bucle de búsqueda. Dispones de su código al final de la entrada. La función requerida para encontrar esas sumas puede ser la siguiente:

Public Function numcuadcapi(n)
Dim x, p

p = 0 ‘ Contador de soluciones
For x = 1 To Sqr(n) ‘Llegamos hasta la raíz cuadrada de N
If escapicua(n - x ^ 2) Then p = p + 1 ‘Si es capicúa la diferencia, se incrementa el contador
Next x
numcuadcapi = p
End Function

Hay que tener en cuenta que ESCAPICUA no considera números de una cifra.

La probamos con el 892 y resultan cinco soluciones.

Si deseáramos leer esas soluciones, convertiríamos la función en una variable tipo texto para que las recogiera. Usaríamos esta variante:

Public Function numcuadcapi2$(n)
Dim x, a, b
Dim nc$

nc$ = ""
For x = 1 To Sqr(n)
a = x ^ 2
b = n - a
If escapicua(b) Then nc$ = nc$ + " CUAD " + Str$(a) + " CAP " + Str$(b)
Next x
numcuadcapi2 = nc$
End Function

Vemos en la imagen los dos tipos de resultados:

El segundo coincide con el obtenido en Cartesius.

La primera función nos permite obtener un listado de los números que admiten al menos una descomposición de este tipo:

12, 15, 20, 23, 26, 27, 31, 34, 36, 37, 38, 42, 45, 47, 48, 49, 53, 56, 58, 59, 60, 64, 67, 69, 70, 71, 75, 78, 80, 81, 82, 86, 89, 91, 92, 93, 97, 100, 102, 103, 104, 105, 108, 110, 111, 112, 113, 114, 115, 117, 119, 120,…

Con el lenguaje PARI se consigue la misma lista:

ispal(n)={n==eval(concat(Vecrev(Str(n))))&&n>=10}
numsumsqpal(n)={p=0;for(i=1,sqrt(n),if(ispal(n-i^2),p+=1));p}
for(x=1,100,q=numsumsqpal(x);if(q>=1,print1(x,", ")))

12, 15, 20, 23, 26, 27, 31, 34, 36, 37, 38, 42, 45, 47, 48, 49, 53, 56, 58, 59, 60, 64, 67, 69, 70, 71, 75, 78, 80, 81, 82, 86, 89, 91, 92, 93, 97, 100, 102, 103, 104, 105, 108, 110, 111, 112, 113, 114, 115, 117, 119, 120, 122, 124, 125, 126, 127, 130, 132, 133, 135, …

Entre los menores de 1000 el record lo tiene 817, con siete descomposiciones




Cuadrados con base capicúa

Podemos repetir el estudio pero exigiendo que la base del cuadrado sea también capicúa. Modificaremos los códigos para exigirlo. Con Cartesius habrá que modificar las condiciones:

xtotal=2
x1=1..32
x2=10..1000
xt=filtro(capicua)
es x1*x1+x2=892

Recorremos con X1 hasta la raíz de 892, con X2 hasta 1000, y exigimos que x1*x1+x2=892

Como era de esperar, no se obtiene ninguna solución, pero sí la tienen números cercanos a 892: 898 presenta dos soluciones, 11^2+777 y 22^2+414. Igual ocurre con 908, que es igual 11^2+787 y a 22^2+424. El resto de número próximos no presenta esta propiedad.

Con BASIC y PARI, añadiendo la condición de que la base sea capicúa mayor que 10, obtenemos un listado de los números que equivalen a este tipo de suma al menos de una forma:

132, 143, 154, 165, 176, 187, 198, 209, 220, 222, 232, 242, 252, 262, 272, 282, 292, 302, 312, 323, 333, 343, 353, 363, 373, 383, 393, 403, 413, 424, 434, 444, 454, 464, 474,…

El código PARI adecuado sería:

ispal(n)={n==eval(concat(Vecrev(Str(n))))&&n>=10}
numsumsqpal(n)={p=0;for(i=1,sqrt(n),if(ispal(i),if(ispal(n-i^2),p+=1)));p}
for(x=10,1000,q=numsumsqpal(x);if(q>=1,print1(x,", ")))

Devuelve el listado

132, 143, 154, 165, 176, 187, 198, 209, 220, 222, 232, 242, 252, 262, 272, 282, 292, 302, 312, 323, 333, 343, 353, 363, 373, 383, 393, 403, 413, 424, 434, 444, 454, 464, 474, 484, 494, 495, 504, 506, 514, 517, 525, 528, 535, 539, 545, 550, 555, 561, 565, 572, 575, 583, …

Se distinguen en la lista muchos números que son capicúas. Los extraemos:

ispal(n)={n==eval(concat(Vecrev(Str(n))))&&n>=10}
numsumsqpal(n)={p=0;if(ispal(n),for(i=1,sqrt(n),if(ispal(i),if(ispal(n-i^2),p+=1))));p}
for(x=10,1000,q=numsumsqpal(x);if(q>=1,write1("final.txt",x,", ")))

222, 232, 242, 252, 262, 272, 282, 292, 323, 333, 343, 353, 363, 373, 383, 393, 424, 434, 444, 454, 464, 474, 484, 494, 525, 535, 545, 555, 565, 575, 585, 595, 626, 636, 646, 656, 666, 676, 686, 696, 727, 737, 747, 757, 767, 777, 787, 797, 828, 838, 848, 858, 868, 878, 888, 898, 929, 939, 949, 959, 969, 979, 989, 999,…

Están todos los capicúas de tres cifras salvo los que tienen las decenas con valor 0 o 1. Es porque los capicúas al cuadrado solo pueden ser 11^2=121 y 22^2=484. Todo capicúa con la segunda cifra mayor que 1 y las otras no nulas produce al restarle 121 otro capicúa, pero en caso contrario, si las decenas son 0 o 1, la cifra de arrastre impide un resultado capicúa. Igual ocurre con el 484, que exige un 8 o 8n 9 en las decenas.

Hemos experimentado con sumas de triangular y capicúa, o con primos, pero aparecen muchos resultados que trivializan la cuestión. La dejamos abierta.

Anexo

Código de la función ESCAPICUA

Public Function escapicua(n) As Boolean
Dim l, i, k
Dim c As Boolean
Dim auxi$,nn$

nn$ =Str$(n)
auxi= Right(nn$, Len(nn$) - 1)
l = Len(auxi)
If l < 2 Then
escapicua = False
Else
c = True
i = 1
k = Int(l / 2)
While i <= k And c
  If Mid(auxi, i, 1) <> Mid(auxi, l - i + 1, 1) Then c = False
  i = i + 1
  Wend
End If
escapicua = c
End Function

lunes, 9 de octubre de 2017

Cartesius(7) - Particiones especiales


Esta entrada desarrolla varias descomposiciones clásicas de un número en sumandos de cierto tipo, como en tres números triangulares, cuatro cuadrados o dos o tres primos. En otra entrada añadiremos otras que hemos usado en las redes sociales, como capicúas, cuadrados simétricos o productos cíclicos.

Teorema de Javier Cilleruelo

El matemático español recientemente fallecido Javier Cilleruelo demostró que todo número natural es suma de tres capicúas en cualquier base de numeración mayor o igual que 5.

Para el cumplimiento del teorema consideraremos (y así se suele hacer) como capicúas los números de una sola cifra. Podemos también incluir el cero o no, porque lo que deseamos es efectuar comprobaciones a nuestro criterio. Si deseas excluir los de una cifra en tus descomposiciones (aunque no se cumpla el teorema) puedes definir XT=11..200, por ejemplo, en los rangos de sumandos. Aquí no lo haremos así.

Un ejemplo: descomposición del número 167

Como ignoramos la cota de cada sumando, deberemos definir XT=1..167. Para que los sumandos sean capicúas filtraremos usando filtro(capicua). Definimos tres columnas de sumandos y el resto es sencillo de entender. Quedaría así:

Como hemos admitido capicúas de una cifra obtenemos bastantes resultados:



Si definimos el rango como XT=11..167 reduciremos los casos a dos o más cifras.


Observamos que entre ellos hay una descomposición simétrica: 33+101+33. En Twitter (@connumeros) publicamos casos simétricos de este tipo. Podemos obligar a que los dos primeros sumandos sean iguales, añadiendo ES X1=X2 a las condiciones. Así lo hemos efectuado con el número 231 obteniendo tres resultados:


Hemos supuesto algo que no nos consta, y es que los sumandos iguales son los dos primeros, pero podían ser los últimos (recuerda que al ser creciente no se dará la igualdad de primero y último salvo que los tres sean iguales)

Podemos tenerlo previsto si cambiamos ES X1=X2 por ES (X1=X2)+(X2=X3)
Funciona esta condición porque en Cartesius la suma en este caso equivale a la conectiva O lógica. Lo hemos aplicado al 111 admitiendo capicúas de una cifra y se perciben muy bien los dos casos:



Los filtros en Cartesius pueden resultar lentos, porque se selecciona elemento a elemento. Hay que ejercitar la paciencia en casos más complejos. El siguiente listado, correspondiente a sumandos de tres cifras para generar el número 636, ha tardado algunos minutos.



Teorema de Lagrange

Todo entero positivo es suma de cuatro cuadrados.

Es evidente que pueden ser menos de 4, por lo que usaremos XRANGO=4 en lugar de XTOTAL=4.

Este caso resulta más rápido que el anterior. Hay dos razones para ello. Por una parte, no es necesario usar filtros, porque los cuadrados se pueden definir mediante la condición XT=SUC(n^2), lo que nos lleva a la segunda ventaja, y es que el rango se reduce a la raíz cuadrada del número dado.

Comenzamos este caso con el número 874 (elegido al azar). El planteo podría ser:



Se toma xrango=4 para que también aparezcan sumas de dos o tres cuadrados. El intervalo se toma de 1 a 30, que es la raíz cuadrada de 874 por exceso. La condición suc(n^2) exige que los sumandos sean cuadrados. Después sigue que la suma sea la pedida, 874, y que los sumandos estén ordenados de forma creciente.

Con ese planteamiento resultan 40 casos, de los que insertamos algunos:


Todos esos cuadrados suman 874. En el mismo desarrollo, mediante la función RAIZ puedes adjuntar las bases de esos cuadrados. Aquí tienes un recorte:


Lagrange demostró que bastan tres cuadrados, salvo en unos casos poco  numerosos, que son aquellos números que se pueden escribir como 4^k*(8m+7).

Para comprobar esta variante del problema basta definir XTOTAL=3. Hemos preparado así un listado de números del 600 al 610 con una descomposición en tres cuadrados para cada uno (hay más)



Vemos que faltan el 604 y el 607, y es que pertenecen a las excepciones, ya que 604=4^1*(8*18+7) y 607=4^0*(8*75+7)

Teorema de Gauss

Todo entero positivo es suma de tres números triangulares.

Este es el más popular de este tipo de teoremas. En esta imagen tan conocida expresó con ¡Eureka! su alegría por haber encontrado esta propiedad.



Con la condición SUC de Cartesius basta para engendrar los triangulares. Escribiremos XT=SUC(n*(n+1)/2)

Quedaría así en el caso de N=107:



Usamos XRANGO por si basta con un triángulo o dos. La cota 22 es la suficiente para llegar a 107. Después se definen los triangulares mediante xt=suc(n*(n+1)/2), y finalmente se ajusta la suma. Si se añade la condición CRECIENTE para eliminar repeticiones, resultarían cuatro descomposiciones:


Con Cartesius es fácil descubrir los sumandos triangulares. En una entrada ya antigua de este blog proponemos otro algoritmo para encontrarlos:
http://hojaynumeros.blogspot.com.es/2009/12/suma-de-tres-numeros-triangulares.html

Teorema de los poligonales

Fermat extendió las propiedades anteriores a sumas de cinco pentagonales, seis hexagonales y así con cualquier número de lados. Lo intentamos con pentagonales:

Los números pentagonales 1, 5, 12, 22, 35, 51, 70, 92,… se engendran con la expresión n(3n-1)/2

Así que basta adaptar lo expuesto anteriormente al caso de cinco sumandos del tipo pentagonal. Incluimos el planteamiento para el número 68:



Y el resultado:


Conjetura de Goldbach para impares

Todo número impar mayor que cinco se escribe como la suma de tres números primos.

Para comprobar esta conjetura volveremos a los filtros. Si los sumandos han de ser primos, usaremos FILTRO(PRIMO). En el siguiente ejemplo lo usamos para descomponer el número 67



Definimos tres columnas con rango 1..67 y filtro primo. Después obligamos a que la suma sea 67. Resultan 20 soluciones:



En la siguiente entrada desvelaremos algún secreto de nuestra publicaciones diarias sobre fechas en Twitter @connumeros.



viernes, 29 de septiembre de 2017

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 a1, a2,, a3,,…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=23*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=24*32; 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.





lunes, 18 de septiembre de 2017

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.

miércoles, 6 de septiembre de 2017

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 a0 es el primer término, d1 la primera diferencia, d2 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.