miércoles, 18 de abril de 2018

Cancelaciones anómalas (2/2)


Cancelaciones de tres cifras

Continuamos con las cancelaciones anómalas, estudio que iniciamos en la entrada anterior para números de dos cifras. Pasamos ahora al caso en el que tengan tres, siempre en base 10. Distinguimos algunos casos:

(1) Cancelación de la primera del numerador con la tercera del denominador.

Una vez hemos resuelto el problema con dos cifras mediante la función cancela (ver entrada anterior), bastará cambiar algunas líneas de código para poder cancelar la primera del numerador con la tercera del denominador. Como existen tres cifras, en la identidad de productos cruzados, en lugar de usar la función CIFRA usaremos TROZOCIFRAS, para abarcar las dos cifras restantes después de cancelar. Tendríamos que cambiar estas líneas:

p = numcifras(i)
If p = 3 And m = 3 Then ‘Ahora exigimos que ambos sean de tres cifras
x = cifra(i, 1) ‘Del numerador elegimos la primera cifra
y = cifra(n, 3) ‘Del denominador, la tercera
If x = y And n * trozocifras(i, 2, 3) = i * trozocifras(n, 1, 2) Then s$ = Str(n) + ", " + Str$(i)
‘Los productos cruzados serán de una cifra en un factor y de dos cifras en el otro
End If


Con estos cambios encontramos varios ejemplos. Reproducimos el resultado de nuestra operación de búsqueda. La primera columna son los denominadores y la segunda los numeradores.

Den. Num.
664 166
665 266
775 217
995 199
996 249
998 499

Son fáciles de comprobar. Lo vemos en la siguiente tabla:


En las dos primeras columnas figuran las soluciones obtenidas y el valor decimal de sus fracciones (en rojo). En las siguientes las resultantes de cancelar primera con tercera cifra, y al final, los valores coincidentes con los primeros.

Hemos destacado en color azul y negrita las fracciones ya “simplificadas” que coinciden con las soluciones obtenidas con dos cifras. La explicación de que figuren ahí es la igualdad de cifras que existente en cuatro de las seis soluciones. Ha sido un resultado no buscado.


(2) Cancelación de la segunda del numerador con la tercera del denominador.

Con un método similar podemos encontrar las cancelaciones anómalas en las que se “simplifica” la primera cifra del numerador con la tercera del denominador.
Las soluciones son estas:

Den.Num.
220 121
325 130
330 231
335 134
340 238
345 138
440 341
550 451
640 160
644 161
648 162
650 260
652 163
655 262
656 164
660 561
664 166
665 266
668 167
670 469
672 168
676 169
756 270
770 671
880 781
950 190
955 191
960 192
965 193
970 291
975 390
980 490
982 491
984 492
985 591
986 493
988 494
990 891
992 496
994 497
995 796
996 498
998 499

Los cambios en el código han sido

If p = 3 And m = 3 Then
x = cifra(i, 2)
y = cifra(n, 3)
If x = y And x <> 0 And n * (cifra(i, 3) * 10 + cifra(i, 1)) = i * trozocifras(n, 1, 2) Then s$ = Str(n) + ", " + Str$(i)

Vemos que al eliminar la segunda cifra del numerador hemos tenido que combinar la tercera con la primera, porque TROZOCIFRAS no nos servía en este caso.

Aparecen muchas más soluciones que en el caso anterior.

(3) Cancelación de la primera con la segunda

Sólo se publican las soluciones, dejando el desarrollo como ejercicio:

Den.Num.
265 106
298 149
365 146
398 199
464 116
465 186
498 249
532 133
565 226
595 119
596 149
597 199
598 299
664 166
665 266
695 139
698 349
732 183
765 306
775 217
795 159
796 199
798 399
854 305
864 216
865 346
894 149
895 179
897 299
898 449
931 133
932 233
965 386
976 427
995 199
996 249
998 499



(4) Otras cancelaciones

Sólo desarrollaremos la de dos cifras en el numerador y tres en el denominador.

(4.1) Si cancelamos la primera cifra del numerador con la segunda del denominador se producen muchos casos triviales. Hemos eliminado aquellos en los que el numerador es múltiplo de 11 y los que se producen cuando el denominador termina en 0. Nos hemos quedado con estos:




(4.2) La cancelación de primera cifra con tercera produce estos tres resultados (eliminando también los triviales):



Siguiendo nuestra norma de no cansar en los temas, remitimos a los casos publicados en OEIS (http://oeis.org/?language=spanish) Bastar plantear la búsqueda de "anomalous cancellation" y obtendrás dos páginas de resultados diversos. No están clasificados por el número de cifras, pero sirven de ayuda por si intentas otras búsquedas con las técnicas que hemos desarrollado.



martes, 10 de abril de 2018

Cancelaciones anómalas (1/2)


Cancelaciones con dos cifras

En este blog partimos a menudo de publicaciones en Twitter que nos llamen la atención.  El día 29/3/18, Fermat’s Library publicó las cancelaciones incorrectas en cuatro fracciones, pero que sus resultados sí son válidos. Ya conocíamos esta curiosidad, pero ante la invitación del texto del tweet, procedemos a pequeños desarrollos sobre el tema.


Siguiendo una metodología frecuente en este blog, comenzaremos por reproducir esta lista mediante VisualBasic para Excel o Calc, para después seguir con reflexiones teóricas y extensión a más cifras.

Función CANCELA

Comenzamos con la simple reproducción de estas cuatro fracciones mediante una búsqueda ordenada, restringiendo el estudio a números de dos cifras. En este caso, es claro que la solución es única para cada denominador, pero en nuestro planteamiento no lo tendremos en cuenta.

Nos basamos en las funciones CIFRA, NUMCIFRA y TROZOCIFRA ya diseñadas en este blog, y cuyo código se reproduce en el Apéndice.

CIFRA: extrae una cifra determinada de un número natural
NUMCIFRA: Cuenta las cifras de un número natural
TROZOCIFRA: Extrae del número unas cifras consecutivas determinadas.

Las condiciones de falsa cancelación son, por una parte, que la primera cifra de uno de los números sea idéntica a la segunda del otro, y que las cifras restantes representen fracciones equivalentes, lo que representaremos mediante la igualdad de productos cruzados. Quedará así, en forma de función:

Public Function cancela$(n) ‘Tiene forma de string para albergar varios números.
Dim i, m, p, q, x, y
Dim s$

m = numcifras(n) ‘Cuenta las cifras, y en esta fase sólo serán dos.
s$ = "" ‘La función comienza con una cadena vacía, por si no hay soluciones.
For i = 10 To n – 1 ‘Compara el número con todos sus anteriores.
p = numcifras(i)
If p = 2 And m = 2 Then ‘Restringe a números de dos cifras
x = cifra(i, 1)
y = cifra(n, 2)
If x = y And n * cifra(i, 2) = i * cifra(n, 1) Then s$ = s$ + Str(n) + ", " + Str$(i)
‘Unas cifras han de ser iguales, y las otras dar productos cruzados equivalentes.
End If
Next i
cancela = s ‘El resultado es el conjunto de soluciones para ese número
End Function

Con esta función y una búsqueda ordenada hemos obtenido las cuatro soluciones de dos cifras:


Estudio algebraico para dos cifras

Tienes un desarrollo similar en

https://en.wikipedia.org/wiki/Anomalous_cancellation y la presentación del problema en http://mathworld.wolfram.com/AnomalousCancellation.html

Aquí nos limitaremos a la base de numeración 10.

Si dos cifras han de ser iguales para poderse cancelar, los números se podrán representar en base 10 como ab(10 y ca(10, o lo que es igual, p=10a+b y q=10c+a. Si las cancelaciones han de funcionar como verdaderas, serán equivalentes los productos cruzados: p*c=q*b, o bien

(10a+b)*c=(10c+a)*b
10ac+bc=10bc+ab

 De esta igualdad básica podemos extraer otras. En Wikipedia se llega, para cualquier base p, a esta:



Particularizada a base 10 quedaría como

10c(a-b)=b(a-c)

También podemos despejar a, la cifra que se cancela:



Ya que este blog va de hojas de cálculo, nos podemos ahorrar más razonamientos y formar una tabla de doble entrada para c y b, destacando después los resultados enteros de ese cociente. Hemos situado la variable c en columnas, la b en filas y el posible valor de a en el interior de la tabla.




Salvo los casos triviales en los que b=c, obtenemos (destacados en rojo) las cuatro posibilidades válidas:

a=6, b=4, c=1
a=6, b=5, c=2
a=9, b=5, c=1
a=9, b=8, c=4

Coinciden con las cuatro soluciones obtenidas



Podemos prescindir de la hoja de cálculo con otro tipo de razonamiento, observando los valores que hacen enteras las fracciones.

10c(a-b)=b(a-c)

10 divide a b(a-c), lo que obliga a que b sea par y a-c=5, o bien, que b=5 y a-c par (son cifras, por lo que todos son iguales o menores que 9)

(1) Si b=5 queda a=45c/(10c-5)=9c/(2c-1)

Para que sea entero, 2c-1 ha de ser 1 o divisor de 9.

Si es 1, queda a=9 y la solución {95,19}. Si 2c-1 fuera divisor de 9, podría ser c igual a 2 o a 5.

Si c=2, a=(9*2)/3=6, lo que nos da la solución {65, 26}

Si c=5, a=(9*5)/(9)=5, lo que llevaría a una trivialidad: 55/55

(2) Si b es par y a-c=5 nos queda

10c(c+5-b)=5b
b=10c(c+5)/(10c+5)

Los valores que hacen entera esta fracción son:

c=1, b=60/15=4 y a=9*1*4/(10*1-4)=36/6=6, lo que nos lleva a la solución {64,16}

c=4, b=10*4*9/(10*4+5)=360/45=8, a=9*4*8/(10*4-8)=9, que conduce a {98, 49}

Ningún otro valor de c hace entera la fracción, luego se han agotado las posibilidades.

Hasta aquí el caso en el que numerador y denominador son ambos de dos cifras en base 10. Existen otros casos de más cifras, de los que algunos se presentan en el enlace a la página de Mathworld de más arriba, de la que ofrecemos un recorte


Dejamos el estudio de esos casos y otros nuestros inéditos para la próxima entrada.

Apéndice

Public Function cifra(m, n)

'Extrae la cifra n del número m si es natural.En caso contrario devuelve -1. También devuelve -1 si excede del número de cifras

Dim a, b

If m>0 and m=Int(m) Then
If n > numcifras(m) Then
  cifra = -1
  Else
  a = 10 ^ (n - 1)
  b = Int(m / a) - 10 * Int(m / a / 10)
  cifra = b
  End If
Else
cifra = -1
End If
End Function


Public Function numcifras(n)
Dim nn, a
'Calcula el número de cifras enteras de un número natural. Si no lo es, devuelve un cero

If n>0 and n=Int(n) Then
a = 1: nn = 0
While a <= n
a = a * 10: nn = nn + 1
Wend
numcifras = nn
Else
numcifras = 0
End If
End Function

Public Function trozocifras(m, n, p)

'Extrae un trozo desde la cifra n hasta la p

Dim a, b, c, d

If m>0 and m=Int(m) Then
c = numcifras(m)
If n > c Or p > c Then
  trozocifras = -1
  Else
  a = 10 ^ p
  d = 10 ^ (n - 1)
  b = m - Int(m / a) * a
  b = Int(b / d)
  trozocifras = b
  End If
Else
trozocifras = -1
End If
End Function

martes, 3 de abril de 2018

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

Caso general

Continuamos en esta entrada el estudio de las posibilidades de encontrar un número n que convierta la expresión n(n+k) en un cuadrado. Ya descubrimos cómo encontrar soluciones y cómo contarlas según varios tipos concretos de números.

Ya hemos acumulado experiencia para abordar el caso general, que resume en cierto modo lo descubierto hasta ahora. Mediante búsqueda empírica y razonamiento posterior, creemos que podemos acudir a este procedimiento:

(1) Encontramos la valuación del número k respecto a 2, es decir, el exponente máximo del 2 contenido en el número dado, llamémosle m. Esto quiere decir que el número k se descompone en parte par, 2m, y parte impar. Entonces:

k2=22m*v, siendo v la parte impar.

(2) Hallamos la función TAU de la parte impar v, y aplicamos la fórmula vista en párrafos anteriores (TAU(k2 2)-1)/2 , y al resultado le llamaremos t.

(3) En ese caso, el número de soluciones para nuestra condición de que sea cuadrado n(n+k) vendrá dada por

N=t*(2m-3)+m-2 si m>2. Si no, lo tratamos como impar.

El primer sumando proviene de combinar todas las soluciones de la parte impar (la TAU t) con todas las de 2m (vimos que con un solo primo resultaban 2m-3) y el segundo de la partición que se desechó en la parte impar por tener dos factores iguales (k*k).

Esto hay que tomarlo como una explicación, no como demostración, que requeriría un conteo más sistemático de todos los casos. Lo vemos, por ejemplo, con 336=24*3*7. En este caso m=4 y la parte impar  de k2 es 441=32*72, cuya TAU vale (1+2)(1+2)=9 y t=(9-1)/2=4. Por tanto, según la expresión que hemos presentado, n=4*(2*4-3)+4-2=4*5+2=22

En efecto, la función numcuadprod nos devuelve 22:



Según el razonamiento de más arriba, el segundo sumando, 4-2=2 proviene de tomar en la parte impar de 212 el par 21*21. Y así es en este ejemplo, ya que se corresponderían a los productos 1344*84=21*64*21*4=336*336 y a 672*168=21*32*21*8=336*336

Los restantes 20 productos válidos se corresponderán con todas las combinaciones válidas de los productos de la parte par con los de la parte par.

Por curiosidad, los copiamos aquí. Ninguno de ellos presenta el factor común 21 en ambos factores:

28224*4, 14112*8, 9408*12, 7056*16, 4704*24, 4032*28, 3528*32, 3136*36, 2352*48, 2016*56, 1764*64, 1568*72, 1344*84, 1176*96, 1008*112, 784*144, 672*168, 576*196, 504*224 y  448*252.

Las 22 soluciones para n respecto al valor de k=336 las podemos obtener, ordenadas de menor a mayor, con la función escuadprod:



Tomemos una al azar, como 847: 847*(847+336)=1002001=10012. Resulta un cuadrado, luego es una solución válida.

Hemos construido la función numcuadprod2 recogiendo el algoritmo propuesto.

Con ella se puede verificar la coincidencia de los dos métodos que podemos utilizar, el de la búsqueda simple (numcuadprod) y el basado en las consideraciones desarrolladas en este apartado (numcuadprod2)

En esta tabla de datos tomados al azar se observa la equivalencia:



Casos publicados

Analizamos ahora los casos que se publicaron en Twitter en enero de 2018:


Según nuestro procedimiento, como es impar, buscamos la función TAU de su cuadrado:

2019=3*673, luego TAU(20192)=(1+2)(1+2)=9, y el número de soluciones será (9-1)/2=4

Estas cuatro soluciones provendrán de los productos válidos del cuadrado de 2019:


Hemos seguido lo sugerido en esta serie de entradas:

 - Buscar productos cuya diferencia sea múltiplo de 4
– Llamar A y B  a los factores
– Encontrar su promedio p
– Aplicar la fórmula n=(p-k)/2.

Podemos observar la coincidencia entre nuestro cálculo y el publicado.



Aquí 2020=22*5*101. Es el caso en el que el exponente de 2 es 2, luego el número de casos será 4, pues la parte impar sólo presenta dos factores y el cuadrado de 2 no incrementa ese número.

Los productos válidos de 20202 son:




Para 2310=2*3*5*7*11 bastará calcular el número de casos de la parte impar de su cuadrado. Es fácil ver que TAU(23102)=3*3*3*3=81, luego el número de casos será (81-1)/2=40, tal como se afirma en la publicación que analizamos.

Reproducir los cuarenta casos es muy pesado. Deberíamos factorizar el cuadrado de 2310, 5336100 y buscarle todos los divisores:

5336100 2668050 1778700 1334025 …  10 9 7 6 5 4 3 2 1

Después formaríamos pares con ellos y nos quedaríamos con los que presentan una diferencia múltiplo de 4. No lo haremos con todos, sólo con los primeros:



Si siguiéramos el procedimiento con todos los pares de factores coincidiríamos con lo publicado de forma total.

Problema inverso

En las tres entradas referidas a este tema hemos buscado el valor de n que consigue que n(n+k) sea un cuadrado. Si planteamos el problema inverso, si dado un n ver si existe un k que cumpla la misma condición, con lo visto en párrafos anteriores tenemos la respuesta, pues vimos que n(n+3n) es un cuadrado, luego existe solución para todo n.

También vimos más arriba que 8n, 15n, 24n,…son todas soluciones para k, luego existen infinitas. La más pequeña suele ser 3n, pero con muchas excepciones, como puedes ver en la siguiente tabla, en la que las hemos marcado en rojo:



Esos casos se producen en los números que contienen cuadrados. Analizamos la situación:

(a) Si n es libre de cuadrados, será producto de varios primos, todos elevados a exponente 1. Por tanto, el cuadrado resultante de n(n+k) ha de ser múltiplo de los cuadrados de esos primos, luego el paréntesis también lo será, lo que obliga a que k sea múltiplo de n. De ahí que la solución mínima sea 3n.

(b) Si n contiene un cuadrado mayor que 1, será, por ejemplo, n=r2*s, lo que nos lleva a la situación de que r2*s*(r2*s+k) sea un cuadrado. Esto se consigue dando un valor a k que convierta el paréntesis en otro cuadrado. Para ello se puede convertir r2 en (r+1)2. Sabemos que la diferencia entre esos dos cuadrados es 2r+1, luego el valor de k que nos conviene es (2r+1)*s, ya que r2*s*(r2*s+(2r+1)*s)= r2*s*(r+1)2*s= r2*s2*(r+1)2, luego hemos conseguido el cuadrado.

Lo vemos con algún ejemplo:

N=20=22*5. Hacemos k=(2*2+1)*5=25 y queda 20(20+25)=20*45=900=302

N=24=22*6. Si k=(2*2+1)*6=30, tenemos 24(24+30)=1296=362

No hemos analizado si existe en el caso de números que contienen cuadrados alguna solución menor que la presentada. Lo importante es que todos los valores de n admiten infinitas soluciones para k.

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.