domingo, 25 de marzo de 2018

Cuadrados del tipo n(n+k) (2/3)


En la anterior entrada comenzamos a “dar vueltas” a la cuestión de qué números n cumplen que n(n+k) es un cuadrado para un número k dado. Ya presentamos la función escuadprod(n,k) para averiguar si un número n forma cuadrado mediante n(n+k). Después se tradujo a PARI y se desarrolló un procedimiento algebraico para encontrar las soluciones del problema planteado.

En esta segunda entrada comenzaremos por contar las soluciones que presenta cada valor de k, para pasar luego a algunos casos interesantes.

Función para contar soluciones

Mediante procedimientos similares a los desarrollados en la anterior entrada, podemos crear la función numcuadprod(k) que cuente las soluciones para un valor concreto de k. El siguiente código para VBA de Excel resuelve la cuestión.

Function numcuadprod(k)
Dim a, i, r, c

c = 0 ‘Contador de soluciones
r = k ^ 2 / 4 ‘Cota de búsqueda
For i = 1 To r
a = i * (i + k)
If a = Int(Sqr(a)) ^ 2 Then c = c + 1 ‘Si se cumple, se incrementa el contador
Next i
numcuadprod = c
End Function

Si prefieres la exactitud del lenguaje PARI, puedes usar este código:

numcp(k)={local(c=0, a=0,r=k^2/4,i=0);for(i=1,r,a=i*(i+k);if(issquare(a),c+=1)); c}
print(numcp(960))

Lo hemos particularizado para k=960

Aquí tienes el resultado en Excel


Y aquí en PARI



Con la función escuadprod(n,k) que estudiamos en la anterior entrada podemos buscar esas 40 soluciones. Son:

En Excel:



Y en PARI



Casos particulares

Estudiaremos a continuación algunos casos particulares en los que no es complicado contar soluciones.

Múltiplos de 3

Todos tienen al menos una solución. Si k=3m, una solución para n es m, ya que m(m+3m)=4m2=(2m)2

Un razonamiento similar valdría para múltiplos de 8, ya que m(m+8m)=(3m)2

Por tanto los múltiplos de un número anterior a un cuadrado presentarán la misma situación.

Números que no presentan soluciones

Los números 1, 2 y 4 no admiten soluciones, porque sus cuadrados no se pueden descomponer en dos factores A y B cuya diferencia sea múltiplo de 4.

Números primos mayores que 2

Si k es primo, A=k2 y B=1. Todos los cuadrados de primos mayores que 2 son de la forma 4m+1, ya que (2k+1)2=4(k2+k)+1, (2k+3)2=4(k2+3k+2)+1, y por tanto A-B será múltiplo de 4. En este caso tendremos que p=(k2+1)/2 y n=((k2+1)/2-k)/2=(k2-2k+1)/4=(k-1)2/4, o bien:


Así lo comunica @republicofmath



Aquí añadimos que esta solución también es válida para todos los impares, aunque sólo tiene que ser única para los primos (recuérdese el 21).

En el caso de 21, n=(21-1)2/4=400/4=100, pero existen otras.

Podemos listar las soluciones para los primeros primos y comprobar esa fórmula:



Potencias de 2 mayores que 4

Si k=2r, con r>2, el número de soluciones será r-2

En efecto, k2 en ese caso se podría descomponer de la forma A=2a, B=2b, con la condición de que a+b=2r a>b y que la diferencia A-B sea múltiplo de 4, para lo que b ha de ser mayor que 1, ya que

A-B=2a-2b=(2a-b-1)*2b

En esa diferencia el paréntesis es impar, luego sólo será múltiplo de 4 si lo es 2b, es decir, con b>1


Esto reduce los valores de b a 2, 3, 4,…r-1, ya que el valor r produciría la
igualdad A=B. Contamos casos, y, efectivamente, son r-2

Lo vemos para el 16:

Si k=16, r=4, 2r=8, y los valores posibles de b, 2 y 3

Si b=2, B=4, A=64, p=(A+B)/2=34, n=(34-16)/2=9, y se cumple

9(9+16)=225=152

Si b=3, B=8, A=32, p=(A+B)/2=20, n=(20-16)/2=2, y tenemos 2(2+16)=36=62

Con la función numcuadprod(n) podemos comprobar estos resultados:


Se observa la coincidencia de valores en los resultados de la función numcuadprod y la expresión r-2

Semiprimos pares mayores que 4

Estos números presentan una sola solución, ya que si k=2h, k2=4h2, con h primo impar y la única forma de descomponer k en dos factores adecuados es A=2h2, B=2, con lo que su diferencia será 2*(h2-1). El paréntesis será múltiplo de 4, ya que h2 es de la forma 4m+1. Así que las soluciones se formarán así:

p=(2h2+2)/2=h2+1 y de ahí, n=(p-k)/2=(h2+1-2h)/2=
(h-1)2/2=(k-2)2/8

En resumen

Lo puedes comprobar con la tabla de los primeros semiprimos pares:


Estos razonamientos confirman lo visto en la anterior entrada, cuando se afirmaba que 2018 (semiprimo par) sólo presentaba una solución, 508032.

Números de la forma k=2m*p, con m>1 y p primo mayor que 2

En este caso k2=22m*p2

Al descomponer k2 en factores, el primo p puede pertenecer a ambos, o bien p2 pertenecerá a uno de ellos y al otro no.

Primer caso

Si el primo figura en ambos factores, sean A=2rp y B=2sp, aparecerán tantos factores como indique 2m, ya que p no añadirá ninguno más. Como vimos en el apartado de potencias de 2, se producirán m-2 soluciones válidas.

Segundo caso

Si p2 figura en un factor y en otro no, ambos factores han de ser múltiplos de 4, luego de todas las potencias de 2 que dividen a 2m, sean 21, 22, 23,… 22m-2, 22m-1,22m, habrá que eliminar la primera, que no es múltiplo de 4, y las dos últimas, que impedirían que fuera múltiplo de 4 el otro factor, luego sólo nos quedan 2m-3 posibilidades.

Sumamos y resultan 3m-5 el número de soluciones que admite k=2m*p.

Lo comprobamos con un ejemplo. Sea k=80=24*5. Según la fórmula, deben aparecer 2*4-5=7 soluciones. Lo desarrollamos:

K22=6400

Descomponemos en productos válidos.

Primer caso

Debe entrar el 5 en ambos factores. Las posibilidades son: 320*20 y 160*40, en total 4-2 soluciones, que serían:

A=320, B=20, p=(320+20)/2=170, n=(170-80)/2=45. Compruebo: 45(45+80)=752
A=160 B=40, p=(160+40)/2=100, n=(100-80)/2=10. Se cumple: 10(10+80)=900=302

Segundo caso

El primo 5 sólo figura en un factor. Nos quedarían los productos válidos 1600*4, 800*8, 400*16, 200*32, 100*64, que darían lugar (omitimos los cálculos) a las soluciones 361, 162, 64, 18 y 1. Serían 5 soluciones, es decir 2*4-3, según la fórmula.

Resumimos ambos casos y resultan las siete soluciones (3*4-5) que podemos obtener con la función escuadprod:


Números impares

En el caso de los impares el cálculo se simplifica. Sólo necesitamos conocer su descomposición factorial, en la que todos los números primos serán impares. Todos ellos serán del tipo 4k+1 o 4k+3, pero sus cuadrados, cuartas o sextas potencias serán todos del tipo 4k+1 y sus diferencias múltiplos de 4. Si en el emparejamiento un primo del tipo 4k+3 se toma una vez, el otro factor también lo contendrá, y se compensa el 3 al restar, resultando también un múltiplo de 4.
En este caso k2 tendrá la forma k2=p2tq2ur2vs2w…, con p, q, r, s primos y t, u, v y w sus exponentes primitivos. Se sabe que entonces su número de divisores será (1+2t)(1+2u)(1+2v)…Este producto es la función TAU, la que cuenta divisores.

Todos esos factores se deberán emparejar, ya que sus diferencias siempre serán múltiplos de 4. Un par tendrá dos factores iguales, y se deberá eliminar, con lo que nos quedan (TAU(k2)-1)/2 productos posibles, y soluciones para k.

Ejemplo

Si k=165=3*5*11, según la función numcuadprod, se deberán esperar 13 soluciones, número que coincide con la fórmula que acabamos de obtener: =(TAU(1652)-1)/2=(33-1)/2=26/2=13. En efecto, al sacar los divisores de 1652 podemos obtener trece pares válidos. Reproducimos los cálculos habituales para sacar todas las soluciones para k=165:



El último par se desecha por tener los factores idénticos, y nos quedan 13 soluciones en la última columna. Coinciden con las obtenidas mediante búsqueda ordenada con la función escuadprod ya vista anteriormente:



Un ejemplo con k conteniendo potencias:

Sea k=33*52*7=4725. Su cuadrado tendrá de exponentes 6, 4 y 2. Calculamos TAU=(1+6)(1+4)(1+2)=7*5*3=105

El número de soluciones será (TAU-1)/2=(105-1)/2=52, que coincide con el que nos devuelve numcuadprod:



En la siguiente entrada discutiremos el caso general y el problema inverso.

jueves, 15 de marzo de 2018

Cuadrados del tipo n(n+k) (1/3)


En enero de 2018 se publicaron en Twitter varios resultados sobre una propuesta de Republic of Math @republicofmath, uno de los cuales insertamos a continuación:



En este blog acudimos con frecuencia a la técnica de “dar vueltas” a una cuestión de la que tengamos noticia. En este caso concreto estudiaremos de forma algebraica y algorítmica la cuestión de qué números n cumplen que n(n+k) es un cuadrado para un número k dado. Por ejemplo, si k=16, existen dos números, 2 y 9, que producen un cuadrado mediante dicha expresión. En efecto:

2(2+16)=2*18=36=62; 9(9+16)=9*25=225=152

Para encontrar soluciones correspondientes a un valor de k acudiremos a búsqueda en hoja de cálculo y PARI para después abordar un estudio teórico. Es una metodología muy frecuente en este blog: comenzar con una búsqueda sin apoyo teórico y después ir buscando regularidades o fundamentaciones algebraicas.

Estudio con hoja de cálculo

Es fácil programar una función que nos indique si un número n produce un cuadrado en la expresión n(n+k) para un k dado. La que insertamos a continuación nos servirá para valores de k pequeños. En otros casos los errores de truncamiento de los cálculos nos pueden llevar a conclusiones falsas. Por eso es interesante acudir a un lenguaje de más exactitud como PARI y dar una vuelta de Álgebra a esta cuestión.

La función más simple que podemos proponer es esta:

Function escuadprod(n, k) As Boolean
‘Depende de dos variables y devuelve VERDADERO o FALSO
Dim a
a = n * (n + k) ‘Construimos el producto pedido
If a = Int(Sqr(a)) ^ 2 Then escuadprod = True Else escuadprod = False
‘Si a equivale al cuadrado de la parte entera de su raíz cuadrada, vale
End Function

Con ella y un bucle de búsqueda se pueden encontrar las soluciones para un valor de k dado. En la imagen figuran las correspondientes a k=21, que son 4, 7, 27 y 100.



Las comprobamos:

4(4+21)=4*25=100=102
7(7+21)=7*28=196=142
27(27+21)=27*48=1296=362
100(100+21)=100*121=12100=1102

¿Se podrán encontrar más? Lo veremos en el estudio algebraico.

Para mayor velocidad y exactitud trasladamos vuestra función a PARI (lo puedes realizar fácilmente con otro lenguaje). Este sería el listado para k=21.

escp(n,k)=issquare(n*(n+k))
k=21;for(i=1,10000,if(escp(i,k),print(i)))

Hemos acotado la búsqueda en 10000, pero para valores de k superiores deberíamos ampliar la búsqueda. Ya trataremos esto más adelante.

El resultado es:



Coinciden las soluciones 4, 7, 27 y 100.

Estudio algebraico

Llamemos m2 al cuadrado que debe producir el producto n(n+k).
En ese caso se cumplirá: n(n+k)=m2

Resolviendo la ecuación de segundo grado resultante:



El radicando ha de ser un cuadrado perfecto, llamémosle p2, lo que nos lleva a que

p2 - 4m2 = k2
(p+2m)(p-2m)=k2

Si encontramos dos valores enteros para p y m, sustituyendo en la resolución de la ecuación:

Bastará entonces descomponer k2 en dos factores, sean A y B, e igualar:

Resultará p+2m=A, p-2m=B, p=(A+B)/2, m=(A-B)/4

Deberemos buscar entonces A y B de forma que su diferencia sea múltiplo de 4 y distinto de cero, para evitar la solución cero.

Veamos el caso de 21. Su cuadrado 441 admite estas descomposiciones en productos:

441*1=147*3=63*7=49*9=21*21

Los cuatro primeros se diferencian en un múltiplo de 4, y nos queda:

441*1: m=(441-1)/4=110; p=(441+1)/2=221; n=(p-k)/2=(221-21)/2=100
147*3: m=(147-3)/4=36; p=(147+3)/2=75; n=(75-21)/2=27
63*7: m=(63-7)/4=14; p=(63+7)/2=35; n=(35-21)/2=7
49*9: m=(49-9)/4=10; p=(49+9)/2=29; n=(29-21)/2=4

Obtenemos las soluciones sabidas 100, 27, 7 y 4. Hemos desechado la solución cero, que se obtendría de 21*21.

Hemos deducido que el valor de p equivale a p=(A+B)/2, siendo A y B factores de k2, luego p<=k2/2, y, por tanto, el valor buscado n=(p-k)/2, tendrá como amplia cota k2/4:



Podíamos ajustar más, pero no es necesario. Por ejemplo, para el caso k=2018, PARI nos da la solución (por cierto, única) de n=508032, ya publicada en Twitter



Esta solución cumple 508032<20182/4=1018081

Por tanto, en PARI deberíamos buscar hasta esa cantidad:

escp(n,k)=issquare(n*(n+k))
k=2018;for(i=1,1018081,if(escp(i,k),print(i)))

Obtendríamos la misma solución única:



¿Por qué es única?

Seguimos el proceso algebraico:

20182=4072324=4072324*1=2036162*2=1018081*4=4036*1009=2018*2018

El único par válido es 2036162*2, luego p=(2036162+2)/2=1018082 y n=(1018082-2018)/2=508032

Es única la solución 508032

Terminamos esta entrada con una consideración:

Si n convierte n(n+k) en un cuadrado, es decir, es solución para un k dado, el número rn será solución para rk.

Es una propiedad muy importante, que se justifica en estas simples igualdades:
Si n(n+k)=m2, entonces rn(rn+rk)=(rm)2

En la siguiente entrada estudiaremos casos particulares y usaremos esta propiedad.

lunes, 5 de marzo de 2018

Otros números piramidales de cuatro dimensiones

Esta es nuestra tercera entrada sobre números piramidales de cuatro dimensiones.

Puedes leer las anteriores en

http://hojaynumeros.blogspot.com.es/2017/11/numeros-piramidales-de-cuatro.html

y

http://hojaynumeros.blogspot.com.es/2018/01/piramides-cuadrangulares-en-cuatro.html

Hoy nos dedicaremos a los pentagonales y hexagonales. Seguiremos los mismos procedimientos para descubrirlos, ya que se desprenden directamente de la definición.

Generación directa

Partimos de los piramidales pentagonales de tres dimensiones:

1, 6, 18, 40, 75, 126, 196, 288, 405, 550, 726, 936, 1183, 1470, 1800, 2176, 2601, 3078, 3610, 4200, 4851, 5566, 6348, 7200, 8125,…

http://hojaynumeros.blogspot.com.es/2017/06/numeros-piramidales-4-pentagonos.html

Como en casos anteriores, construimos las sumas parciales: 1, 1+6=7, 1+6+18=25, 1+6+18+40=65,…y obtenemos:

1, 7, 25, 65, 140, 266, 462, 750, 1155, 1705, 2431, 3367, 4550, 6020, 7820, 9996, 12597, 15675, 19285, 23485, 28336, 33902,…

Estos serán, pues los piramidales pentagonales de cuatro dimensiones. Los puedes estudiar en

http://oeis.org/A001296

Expresión algebraica

Lo que sigue lo hemos aplicado en bastantes números figurados, por lo que simplificaremos las explicaciones. En primer lugar, abrimos nuestro interpolador para números naturales

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

Escribimos en él los primeros términos de la sucesión que hemos formado.


Leemos los coeficientes de (x-1), (x-1)(x-2), (x-1)(x-2)(x-3),…y formamos el polinomio interpolador, que según la anulación de diferencias quintas, será de cuarto grado:

1+6*(x-1)+6*(x-1)*(x-2)+10/6*(x-1)*(x-2)*(x-3)+3/24*(x-1)*(x-2)*(x-3)*(x-4)

Lo simplificamos en la página de WolframAlpha y obtenemos



Expresión que coincide con una de las contenidas en https://oeis.org/A001296

Son números de Stirling

Los pentagonales que estamos estudiando son un caso particular de los números de Stirling de segunda clase para los índices (n+2,n), como puedes ver en los elementos subrayados de nuestra tabla



(La tienes alojada en http://www.hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#nume)

Si deseas conocer mejor estos números puedes acudir a

https://es.wikipedia.org/wiki/N%C3%BAmeros_de_Stirling_de_segunda_especie

Relación con números triangulares

En https://oeis.org/A001296 figura una propiedad interesante, debida a Jon Perry, y es que cada número piramidal pentagonal de cuatro dimensiones es suma de números triangulares multiplicado cada uno por su número de orden, es decir:



Esto se cumple para los primeros términos. Si tomamos los triangulares 1, 3, 6, 10, 15,…y formamos las sumas 1*1=1, 1*1+2*3=7, 1*1+2*3+3*6=25, 1*1+2*3+3*6+4*10=65,…y comprobamos que se cumple para los primeros términos. Acudimos a la inducción completa.

Bastará demostrar que PIR5_4(n+1)-PIR5_4(n) = (n+1)*T(n+1). En efecto, es cuestión de Álgebra:

PIR5_4(n+1)-PIR5_4(n)=((n+1)(n+2)(n+3)(3(n+1)+1)-n(n+1)(n+2)(3n+1))/24

Simplificamos y queda:

PIR5_4(n+1)-PIR5_4(n)=(n+1)(n+2)(12n+12)/24=(n+1)(n+1)(n+2)/2=(n+1)T(n+1)

Luego la propiedad es extensible a todos los términos.

En la misma página de OEIS, J. M. Bergot interpreta esta propiedad como la suma de todos los productos de dos elementos del conjunto {1, 2, …, n} tomados de todas las formas posibles, sin tener en cuenta el orden). Por ejemplo, 1*1 + 1*2 + 1*3 + 2*2 + 2*3 + 3*3 = 25.

Es sencillo de comprender, ya que si desarrollamos la suma de cada triangular por su número de orden, basta recordar que cada triangular es suma de números consecutivos, luego la suma queda:

1*T(1)+2*T(2)+3*T(3)+4*T(4) = 1*1+2(1+2)+3*(1+2+3)+4*(1+2+3+4)+…
Se ve que en la suma están contenidos todos los productos de cada número natural por sus precedentes, tal como afirma J. M. Bergot.

Es un buen ejercicio de hoja de cálculo construir una tabla que refleje este resultado. Hay que manejar bien las referencias absolutas y relativas. Un buen ejercicio de aprendizaje.

En la tabla que hemos construido se destaca el conjunto de sumandos que forman el piramidal pentagonal 140:




Piramidales hexagonales

Según nuestra política de no cansar con los temas, a los piramidales hexagonales les dedicaremos menos espacio y con ellos terminaremos el recorrido por los que tienen cuatro dimensiones.

Las operaciones que hay que realizar son:

(1) Acumulación de piramidales hexagonales de tres dimensiones

Partimos de los piramidales hexagonales de tres dimensiones:

1, 7, 22, 50, 95, 161, 252, 372, 525, 715, 946, 1222, 1547, 1925, 2360, 2856, 3417, 4047, 4750, 5530, 6391, 7337, 8372,…

(Ver http://hojaynumeros.blogspot.com.es/2017/07/numeros-piramidales-5-hexagonos.html)

Los acumulamos en sumas parciales:

1, 1+7=8, 1+7+22=30, 1+7+22+50=80,…

Nos resultarán así los números piramidales hexagonales de cuatro dimensiones:
1, 8, 30, 80, 175, 336, 588, 960, 1485, 2200, 3146, 4368, 5915, 7840, 10200, 13056, 16473, 20520, 25270, 30800,…

Los tienes publicados en http://oeis.org/A002417

(2) Obtención de la fórmula algebraica

También para estos números usamos nuestro interpolador

http://www.hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#newton
Como ya lo hemos desarrollado para otros tipos de números, sólo insertaremos el volcado de pantalla:



Como en otras ocasiones, observamos la anulación de las diferencias quintas y copiamos los coeficientes del polinomio en la parte inferior.

1+7*(x-1)+15/2*(x-1)*(x-2)+13/6*(x-1)*(x-2)*(x-3)+4/24*(x-1)*(x-2)*(x-3)*(x-4)

Simplificamos la expresión en la página de WolframAlpha y nos devuelve cuatro variantes:



Aunque la cuarta es la más sintética a efectos de cálculo, nos quedamos con la primera, porque se puede interpretar en términos de número combinatorio:



Una curiosa propiedad

Según un comentario de Floor van Lamoen  en la página OEIS donde vienen publicados, se cumple que PIR6_4(n) es la suma de todos los números que no pueden expresarse de la forma t*(n+1) + u*(n+2) con t, u enteros no negativos. Desconocemos la demostración de este hecho, pero nos va a servir para repasar unos conceptos que desarrollamos en una entrada de este blog

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

Según el vocabulario introducido en esa entrada, lo que afirma Floor van Lamoen  es que los números que estamos estudiando son suma de aquellos que no son representables respecto al conjunto {n+1,n+2}. En la entrada citada llamábamos número de Frobenius al máximo número no representable para un conjunto. En el caso de dos números coprimos a y b, ese número equivale a a*b-a-b. Esto nos garantiza que la suma de no representables es finita, y que, por tanto, puede coincidir con un número de nuestra lista.

En este caso particular, el número de Frobenius para {n+1,n+2} será
(n+1)*(n+2)-(n+1)-(n+2)=n^2+n-1

En el caso de n=7, ese número será igual a 7^2+7-1=55. Quiere decir que los números no representables respecto al conjunto {8,9} serán no mayores que 55. En efecto, los hemos buscado con hoja de cálculo y resultan ser

1, 2, 3, 4, 5, 6, 7, 10, 11, 12, 13, 14, 15, 19, 20, 21, 22, 23, 28, 29, 30, 31, 37, 38, 39, 46, 47, 55

Su suma es 588, que coincide con PIR6_4(7), como puedes comprobar en la lista de arriba.

Podemos repetir esta comprobación para cualquier otro valor. Para ello necesitamos una función que nos devuelva VERDADERO si un número n es representable respecto al conjunto {a,b}. Puede ser esta:

Function sumamult(n, a, b) As Boolean ‘Investiga si n=t*a+u*t
Dim i, p, q
Dim es As Boolean

es = False
i = 0 ‘Recorrerá los posibles múltiplos de a
While i <= n And Not es
p = i / a: q = (n - i) / b ‘Encuentra los posibles valores de t y u
If p = Int(p) And q = Int(q) Then ‘Si ambos t y u son enteros, es representable
es = True
End If
i = i + 1
Wend
sumamult = es
End Function

Con esta función no es difícil sumar los no representables para un número dado:

Function suma_no_repr(n)
Dim i, s
s = 0
For i = 1 To n * n + n – 1 ‘Busca hasta el número de Frobenius
If Not sumamult(i, n + 1, n + 2) Then s = s + i ‘Si no es representable, lo suma
Next i
suma_no_repr = s
End Function

Efectivamente, con ella se reproduce la lista de los piramidales hexagonales de cuatro dimensiones:



Esto ocurre a menudo en las pequeñas investigaciones matemáticas, que aparecen conexiones inesperadas, como nos ha ocurrido aquí. Era difícil imaginar una conexión de números piramidales con el número de Frobenius.