Finalizamos las descomposiciones en factores semiprimos (ver entrada anterior) planteando aquellas que no usen factores repetidos. Es una exigencia que puede resultar fuerte, porque muchos números no admiten estas descomposiciones aunque posean un número par de factores. Están publicados:
A320892 Numbers with an even number of
prime factors (counted with multiplicity) that cannot be factored into distinct
semiprimes.
16, 64, 81, 96, 144,
160, 224, 256, 324, 352, 384, 400, 416, 486, 544, 576, 608, 625, 640, 729, 736,
784, 864, 896, 928, 960, 992, 1024, 1184, 1215, 1296, 1312, 1344, 1376, 1408,
1440, 1504, 1536, 1600, 1664, 1696, 1701, 1888, 1936, 1944, 1952, 2016, 2025
Por ejemplo, 160=25*5, y en cualquier factorización hay que repetir el factor 4.
Con Cartesius basta añadir la condición NO REPITE, para obtener las factorizaciones requeridas. Elegimos un ejemplo, el 693=32*7*11:
Son condiciones similares a
las anteriores, pero añadiendo NO REPITE. Así conseguimos las factorizaciones
sin repetición:
Si tomamos nuestro ejemplo del 900, que poseía cinco factorizaciones, al evitar repeticiones se pierden tres:
Quedaría:
Versión VBasic
Lo que sigue es un ejercicio de programación, prescindible, pero usa un truco que puede ser interesante. Quien no tenga interés en ello, puede interrumpir aquí la lectura.
Para encontrar todas las combinaciones de factores semiprimos sin repetir, expresamos en sistema de numeración binario todos los números desde el 1 hasta el cardinal del conjunto de factores menos una unidad. Así representaremos cada elección de factores con un binario, desde 000000…, que equivale a no elegir ninguno, hasta 111111…, en el que se elegirían todos. El 010110, por ejemplo, representaría el producto del segundo factor con el cuarto y el quinto (donde figuran los unos). El que se elija o no cada factor lo reflejamos en el vector e(). Explicado de esta forma parece lento y complicado, pero el algoritmo resulta rápido en recorrer todos los productos posibles. El listado es el siguiente, en forma de función:
Function descompsemi$(n)
Dim i, j, contador, tope, m,
p, k, fp
Dim producto As Long
Dim seguir As Boolean
Dim su(1000), e(1000) ‘Vectores para acoger factores
Dim st$ ‘String para acoger resultados
If esprimo(n) Then descompsemi
= "0": Exit Function ‘No hay descomposición
If essemiprimo(n) Then
descompsemi = "1 : " + factores(n): Exit Function ‘Solo una descomposición.
'En primer lugar se rellena el
vector su, con semiprimos divisores
tope = 0: i = 0: st$ =
""
For j = 1 To n
If essemiprimo(j) And n / j =
n \ j Then i = i + 1: su(i) = j: tope = tope + 1
Next j ‘Si es divisor semiprimo se incorpora al
vector
For j = 1 To 2 ^ tope – 1 ‘Se generan los productos
m = j: p = 0: producto = 1
While m > 0: p = p + 1:
e(p) = m Mod 2: m = Int(m / 2): Wend ‘Códigos en binario para los productos
For k = 1 To p
If e(k) > 0 Then producto =
producto * su(k):
Next k ‘Se crean los productos
fp = n / producto
If fp = 1 Then ‘El producto termina con éxito.
Se incrementa el contador y se
escribe la solución.
contador = contador + 1
st = st + " "
For k = 1 To p
If e(k) > 0 Then st = st +
Str$(su(k)) + "*"
Next k
If Right$(st, 1) =
"*" Then st = Left(st, Len(st) - 1)
If fp > 1 Then st = st +
"*" + Str$(fp)
End If
Next j
El resultado se presenta con
el contador seguido de la solución.
st = ajusta(contador) + "
## " + st
If Right$(st, 1) =
"*" Then st = Left(st, Len(st) - 1)
descompsemi = st
End Function
Los resultados de esta función coinciden con los obtenidos mediante Cartesius:
Descompsemi(900)= 2 ## 6* 10* 15 4* 9* 25
Descompsemi(693)= 2 ## 21*
33 9* 77
Descompsemi(160)= 0 ## (No hay
solución)
En la página https://oeis.org/A322353 se recogen los números de factorizaciones en distintos semiprimos, así como los record que se producen. Por ejemplo, 1260 es el primer número con cinco factorizaciones. Lo comprobamos:
Descompsemi(1260)= 5 ## 9* 10* 14 6* 14* 15
6* 10* 21 4* 15* 21 4* 9* 35
Con esta función podemos encontrar aquellos números que sólo admiten una descomposición sin ser semiprimos:
Otra
factorización
El autor Gus Wiseman, de la Universidad de California, ha estudiado casi todas las factorizaciones que hemos desarrollado, y algunas otras suyas usan indistintamente los primos y los semiprimos como factores. Anteriormente hemos usado aquí los dos tipos, pero con un solo número primo para completar. Ahora los usaremos como un solo conjunto. Basta cambiar ligeramente nuestra última función para que los vectores su() y e() admitan también divisores primos.
Este ha sido el resultado para los veinte
primeros números:
Puede que se echen de menos algunas factorizaciones, pero es que no admiten repetición, si no, sería 8=2*2*2, y no ha resultado así.
Gus Wiseman las ha publicado en
A339839 Number of
factorizations of n into distinct primes or semiprimes.
1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 2, 0, 1, 2, 1, 2, 2, 2, 1, 2, 1,
2, 1, 2, 1, 4, 1,
Reproducimos aquí algunas factorizaciones
logradas con nuestra función:
30: 4
## 2* 3* 5 5*
6 3* 10 2* 15
60: 5
## 3* 4* 5 2* 5* 6
2* 3* 10 6* 10 4* 15
180: 6 ##
2* 3* 5* 6 4* 5* 9 3* 6* 10
2* 9* 10 3* 4* 15 2* 6* 15
210: 10 ##
2* 3* 5* 7 5* 6* 7 3* 7* 10
3* 5* 14 2* 7* 15 14* 15
2* 5* 21 10* 21
2* 3* 35 6* 35
Con estos ejemplos damos por finalizado el repaso que hemos emprendido sobre las factorizaciones con semiprimos. Queda algún tipo, pero aquí paramos el desarrollo.
