viernes, 27 de abril de 2018

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.

No hay comentarios: