Productos de tres divisores (1/3)

En el año 2009, dentro de este blog Números y hoja de cálculo, proponía como investigación en el aula la descomposición de un número natural en producto de tres factores también naturales de todas las formas posibles. No daba pistas para conseguirlo, pues deseaba que el alumnado discutiera posibles métodos empíricos para resolver la cuestión.

Incluyo el enlace a esa entrada:

http://hojaynumeros.blogspot.com.es/2009/07/descomponer-un-numero-en-tres-factores.html

En la siguiente entrada proponía una herramienta más general para comprobaciones, pero ya totalmente diseñada, y sugería su funcionamiento:

http://hojaynumeros.blogspot.com.es/2009/07/descomponer-un-numero-en-tres-factores_05.html

Por otra parte, el día 4/2/18 propuse una propiedad del número 4218 sobre descomposiciones similares, en tres factores.

4218 se puede descomponer en dos productos de tres factores con la misma suma de dos formas diferentes:

4218=1×57×74=2×19×111, con 1+57+74=2+19+111=132
4218=2×37×57=3×19×74, con 2+37+57=3+19+74=96

Esto me ha animado para profundizar en el tema de la descomposición en tres factores, pero desde el punto de vista algorítmico, y como ya viene siendo costumbre en este blog, abordando primero la cuestión usando algoritmos de “fuerza bruta”, sin análisis previos, para después ir profundizando en el tema hasta el límite que seamos capaces de alcanzar.

Fuerza bruta

Supondremos que todos los productos que buscamos poseerán sus factores ordenados en orden creciente. Esto no restringe el problema y nos permite simplificar los procesos.

Siempre que se tengan que combinar tres variables, aquí i*j*k=N, la primera idea que surge es el empleo de tres bucles anidados FOR-NEXT. Es un método lento, porque ha de recorrer muchos valores inútiles, aparte de la multiplicación de casos que se producen al combinar unas variables con otras.

En este caso, si dado un número N, admitimos como seguro el producto 1*1*N, podemos acotar las variables i, j y k mediante N/2, que sería el máximo divisor propio posible de N (evidentemente sería menor si N es impar). Así lo haremos con la primera variable, que recorrerá los valores desde 1 hasta N/2, sabiendo que después habrá que añadir el caso 1*1*N, que no se producirá.

La segunda variable j puede recorrer el intervalo entre el valor de la primera y N/2. Así conseguimos que sólo aparezcan productos en orden creciente.

Igualmente efectuaremos con la tercera variable k.

Hemos diseñado una función, trifactor(n), que nos devuelve la lista de los productos posibles, precedida del número de ellos. Es de tipo string, ya que alojará texto.

Function trifactor$(n) ‘La definimos como string o  texto
Dim i, j, k, v, t
Dim s$

s$ = "" ‘El resultado se inicia en un texto vacío
t = 0 ‘Contador de productos
v = n / 2 ‘Cota para los factores
For i = 1 To v
If n / i = n \ i Then ‘Comprueba que el valor de i es divisor de n
For j = i To v
If n / j = n \ j Then ‘El segundo valor también es divisor
For k = j To v
If n / k = n \ k Then ‘Tercer valor como divisor
If i * j * k = n Then s = s + Str$(i) + "*" + Str$(j) + "*" + Str$(k) + " , ": t = t + 1
‘Si el producto es N, incorporamos el resultado e incrementamos el contador
End If
Next k
End If
Next j
End If
Next i
s = Str$(t) + " resultados: " + s
trifactor = s
End Function


Por ejemplo, trifactor(546)=”13 resultados:  1* 2* 273 ,  1* 3* 182 ,  1* 6* 91 ,  1* 7* 78 ,  1* 13* 42 ,  1* 14* 39 ,  1* 21* 26 ,  2* 3* 91 ,  2* 7* 39 ,  2* 13* 21 ,  3* 7* 26 ,  3* 13* 14 ,  6* 7* 13,”

De esta forma disponemos de todas las soluciones en modo texto. Hay que acordarse de añadir 1*1*546. Si no nos convence esta opción, bastará cambiar la instrucción  v=n/2 por v=n. De esa forma la función será más lenta de cálculo, pero evitaremos que se nos olvide un producto.

La herramienta que propuse hace nueve años, alojada en

http://www.hojamat.es/sindecimales/divisibilidad/herramientas/hojas/enfactores.ods
http://www.hojamat.es/sindecimales/divisibilidad/herramientas/hojas/enfactores.xls

daba las soluciones sin tener en cuenta el factor 1. Puedes usarla para comprobaciones.

Fuerza “menos bruta”

En este algoritmo estamos usando tres bucles FOR-NEXT, pero, en realidad, basta con dos, ya que si conocemos los valores de i y de j, el de k puede obtenerse mediante una simple división: k=N/i/j. Pero esto tiene un coste en condiciones, ya que i*j puede que no sea divisor de N, por lo que hay que exigir que k sea entero y divisor de N. Además, deseamos que k sea igual o mayor que las otras variables. A pesar de estas condiciones, el algoritmo ganará en velocidad. Puede quedar así:

Function trifactor$(n)
Dim i, j, k, v, t
Dim s$

s$ = ""
t = 0
v = n / 2
For i = 1 To v
If n / i = n \ i Then
For j = i To v
If n / j = n \ j Then
k = n / i / j ‘Sustituimos el tercer bucle por un cociente
If k = Int(k + 0.0001) Then ‘Exigimos que sea entero, divisor de N y mayor o igual que j
If n / k = n \ k And k >= j Then s = s + Str$(i) + "*" + Str$(j) + "*" + Str$(k) + " , ": t = t + 1
End If  ‘El resto del algoritmo queda igual
End If
Next j
End If
Next i
s = Str$(t) + " resultados: " + s
trifactor = s
End Function

Da un resultado más en el ejemplo, el 1*1*546

“14 resultados:  1* 1* 546 ,  1* 2* 273 ,  1* 3* 182 ,  1* 6* 91 ,  1* 7* 78 ,  1* 13* 42 ,  1* 14* 39 ,  1* 21* 26 ,  2* 3* 91 ,  2* 7* 39 ,  2* 13* 21 ,  3* 7* 26 ,  3* 13* 14 ,  6* 7* 13,”

Como esta versión mejora bastante la anterior, la hemos traducido a PARI. Sólo tienes que escribir el valor de N, en este caso 546, al principio del código: n=546

n=546;v=truncate(n/2);for(i=1,v,if(n%i==0,for(j=i,v, if(n%j==0, k=n/(i*j);if(k==truncate(k)&&n%k==0&&k>=j,print(i,"*",j,"*",k))))))

Como era de esperar, nos produce el mismo resultado, pero con productos separados, no en forma de string.

En las dos entradas siguientes desarrollaremos más herramientas y cuestiones sobre este tema.

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.

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

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, 2^m, y parte impar. Entonces:

k²=2^2m*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(k² 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 2^m (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=2⁴*3*7. En este caso m=4 y la parte impar  de k² es 441=3²*7², 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 21² 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=1001². 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(2019²)=(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=2²*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 2020² 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(2310²)=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=r²*s, lo que nos lleva a la situación de que r²*s*(r²*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 r² en (r+1)². 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 r²*s*(r²*s+(2r+1)*s)= r²*s*(r+1)²*s= r²*s²*(r+1)², luego hemos conseguido el cuadrado.

Lo vemos con algún ejemplo:

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

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

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.