Son interesantes las posibilidades de descomponer un número N mediante factores semiprimos. En primer lugar, hay que ponerse de acuerdo en cómo deseamos que se construya esa factorización. Veremos algunas variantes que se pueden plantear, y comenzaremos por la más natural.
Factorización completa con repetición
Un número, como el 100, se puede construir como
producto de dos factores semiprimos de dos formas: 100=10*10=4*25 (en la
primera existe repetición). Otros, como veremos a continuación, admiten hasta
cinco productos distintos. Así, 1764=22*32*72,
admite los divisores semiprimos 4, 6, 9, 14, 21 y 49. Si los multiplicamos
convenientemente para que su producto sea 1764, nos resultan cinco
posibilidades (salvo el orden).
1764=4*9*49=4*21*21=6*6*49=6*14*21=9*14*14
Sin embargo, el número 420, que tiene como
divisores semiprimos 4, 6, 10, 14, 15,
21 y 35, no admite factorizaciones de este tipo.
Se adivina fácilmente la razón, y es que 420
posee un número impar de factores primos, 2, 2, 3, 5 y 7, y así no hay forma de
crear conjuntos de semiprimos con factores disjuntos, cuyo producto sea 420,
pues siempre sobraría un primo.
Sin embargo, 1764 sí posee un número par de
factores primos: 2, 2, 3, 3, 7 y 7. Con estos dos ejemplos ya podemos construir
un criterio:
Poseerán factorizaciones semiprimas aquellos números con un número par de
factores primos (contados con repetición)
Esto excluye, por ejemplo a los números primos y
a las potencias impares de los mismos.
El número de factorizaciones de este tipo está
publicado en https://oeis.org/A320655.
Aquí disponemos de la herramienta Cartesius para
comprobar ese número (descargable
desde http://www.hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#cartesius y ya usada en esta serie sobre semiprimos)
Para encontrar las
factorizaciones comenzaremos por crear la lista de divisores semiprimos,
mediante nuestra función div_semi,
usada en anteriores cuestiones sobre divisores semiprimos. Tomaremos como ejemplo
el contenido en la página de OEIS citada, el 900:
DIV_SEMI(900)= 6
: 4 6 9 10 15 25
Posee seis
divisores de este tipo. Con esta lista planteamos en Cartesius lo siguiente:
XTOTAL=3 indica que
buscamos tríos de factores, la mitad de los seis factores primos que existen.
XT=4,5,9,10,15,25
crea la lista de factores semiprimos que vamos a usar (el formato es que estén
separados sólo por una coma)
PRODUCTO=900 el
producto que pretendemos crear.
CRECIENTE es la
condición para evitar duplicidades.
Pulsamos el botón Iniciar y obtenemos los cinco productos
posibles:
900 = (4*9*25)
900 = (4*15*15)
900 = (6*6*25)
900 = (6*10*15)
900 = (9*10*10)
Aunque el dato del 900 no está visible en la página
de OEIS, lo puedes consultar el la lista general (ver https://oeis.org/A320655/b320655.txt)
En ella está asignado el número 5 al 900. El
cálculo directo de ese número no es sencillo. En esa página se propone una
función recursiva en PARI, que adaptamos a nuestro lenguaje y ejemplo:
(n, m=n) = if(1==n, 1, my(s=0); fordiv(n, d,
if((2==bigomega(d)&&(d<=m)), s += A320655(n/d, d))); (s)); \\ Antti
Karttunen, Dec 06 2020
Nuestra versión
parti(n, m=n) = if(1==n, 1, my(s=0); fordiv(n, d,
if((2==bigomega(d)&&(d<=m)), s += parti(n/d, d))); (s));
print(parti(900))
Volcamos este código en la página de PARI y nos
queda:
La respuesta es 5, como era de esperar.
Otros ejemplos
Para N=100
Como 100 es 2*2*5*5 tomo XTOTAL=2. Sus divisores semiprimos son 4, 10, 25.
Resultado:
Otro ejemplo
N=210=2*3*5*7
Planteo en
Cartesius:
Resultado:
Por último
N=9048=2^3*3*13*29
Planteo:
Resultado:
Son cuatro resultados.
Fundamento combinatorio
Aunque no muy claramente, en la página de OEIS enlazada se afirma que el número de factorizaciones depende de las particiones de dos elementos en que podamos descomponer el conjunto de divisores primos. Se usa el ejemplo del 900:
The a(900) = 5 multiset partitions into pairs:
{{1,1},{2,2},{3,3}}
{{1,1},{2,3},{2,3}}
{{1,2},{1,2},{3,3}}
{{1,2},{1,3},{2,3}}
{{2,2},{1,3},{1,3}}
Explicado de otra forma, si dos números coinciden en su signatura prima (exponentes de sus factores primos), coincidirán en el número de factorizaciones semiprimas. Por ejemplo, vimos que 100=22*52 (signatura prima 2,2) posee dos factorizaciones. Si tomamos otro número con idéntica signatura, como 5929=72*112 y seguimos los pasos necesarios, obtenemos:
También resultan dos.
El autor ha intentado profundizar en la cuestión de particiones de un conjunto en subconjuntos de dos elementos, pero pronto se ha encontrado con planteamientos que usan números de Stirling o de Bell, lo que supera el nivel de este blog. Nos quedamos con la recursividad en PARI, que funciona bien.
Si un número posee un número impar de factores primos, no por eso debemos renunciar a la factorización semiprima. Basta descomponer el cociente del número entre cada primo y después completar con ese primo.
Es mejor estudiarlo con nuestro Cartesius. Por ejemplo, 2310=2*3*5*7*11, un número impar de factores, pero podemos plantear como si fueran pares y después añadir el factor primo que falta en una columna nueva. Sería así:
Fijamos los factores en 2, y rellenamos las dos primeras columnas con los divisores semiprimos. De esta forma nunca formaremos un producto igual a 2310. Para completar los productos añadimos una tercera columna con los factores primos 2, 3, 5, 7 y 11.
Con ello resultan todos los productos, pero debemos condicionarlos. Lo primero es exigir que el producto sea igual a 2310, y falta por explicar una condición, la de
ES (X1<X2)+(X1=X2)
La hemos añadido para evitar duplicidades. Significa que X1 es menor o igual que X2. La peculiar forma de escribirlo se debe a que CARTESIUS no usa las condiciones <= o <> y hay que acudir a un truco.
El resultado, obtenido sin más análisis, es:
Observamos 15 resultados con
un producto igual a 2310 y el uso, según conveniencia, de los primos aislados
de la tercera columna.
Si algunos factores primos están repetidos, funciona igual, pero en los productos también podrá haber semiprimos repetidos. Por ejemplo, 2925=22*32*13
El planteo sería similar:
Vemos que los primos repetidos
se toman sólo una vez cada uno. El resultado es:
En uno de los productos figura
el 15 repetido, como era de prever.
No hay comentarios:
Publicar un comentario