Descomposición en factores semiprimos (2)

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=2⁵*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=3²*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:

Es fácil descubrir por qué son estos y no otros.

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

https://oeis.org/A339839

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.