jueves, 30 de mayo de 2024

Descomposición en factores semiprimos (1)

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:

Lo explicamos:

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:

Observamos que coinciden con los publicados en OEIS:

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:

Obtenemos dos factorizaciones, como se indicó anteriormente.

Otro ejemplo

N=210=2*3*5*7

Planteo en Cartesius:

 


Resultado:

Aquí serían 3 los resultados.

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.

 Uso de un primo para completar semiprimos

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: