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. 

 

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=2²*3²*7², 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=2²*5² (signatura prima 2,2) posee dos factorizaciones. Si tomamos otro número con idéntica signatura, como 5929=7²*11² 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=2²*3²*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.

 

Sigmas de divisores semiprimos

Al igual que con los divisores habituales y los unitarios, los divisores semiprimos pueden dar lugar a funciones SIGMA y TAU.

En la entrada anterior usamos la función div_semi para encontrar y contar los divisores semiprimos de un número. Esta sería la función TAU en este caso. Bastará cambiar ligeramente estas líneas de su código para sumar en lugar de contar o usar potencias:

If essemiprimo(k) And n / k = n \ k Then ‘Es divisor semiprimo
nn = n: e = 0 ‘Posibles exponentes
If repe Then ‘Caso de repetición
While nn / k = nn \ k: e = e + 1: nn = nn / k: Wend
End If
If repe Then m = m + e Else m = m + 1

La última línea cuenta divisores, pero si la sustituyéramos por m=m+e*k^t o m=m+k^t nos serviría para el cálculo de la familia de las SIGMAS, que suman divisores, o sus cuadrados, o también cualquier potencia. Incluso si el exponente es 0, la función seguiría contando en lugar de sumar, es decir, que sería TAU. Estos pequeños cambios en la función div_semi los daremos por supuestos en cada caso.

Funciones SIGMA

Tradicionalmente, estas funciones han sumado los divisores de un número o bien alguna potencia de ellos. En el caso de los semiprimos les añadiremos _S para distinguirlas. Así SIGMA3_S sumará los cubos de los divisores semiprimos. Por ahora no consideraremos las repeticiones.

La más sencilla será SIGMA_S, que sumará los divisores semiprimos sin contar repeticiones. En la función div_semi sustituiremos m=m+1 por m=m+k. De esta forma podemos calcular la suma sin repetición si usamos el parámetro repe=0. Por ejemplo, para 330 pediríamos DIV-SEMI(330;0). En la imagen podemos comparar la lista de divisores semiprimos con su suma:

Así que, en este caso, SIGMA_S(330)=141

El resultado, para los primeros números es:

Podemos comparar las dos últimas columnas para verificar las sumas.

Las sumas de la segunda columna están publicadas en  https://oeis.org/A076290

Tambien, si cambiamos ligeramente la versión en PARI, obtendremos los mismos resultados. Esta sería la nueva versión:

sigma_s(n)= sumdiv(n, d, (bigomega(d)==2)*d)
print(sigma_s(330))

Su resultado:

Y para los 20 primeros:

Observamos que coinciden con los publicados.

Hemos intentado buscar números s_perfectos, que coincidan con la suma de sus divisores semiprimos, pero no hemos encontrado ninguno para números inferiores a 2*10^6. Entre los 20 primeros son todos s_deficientes, y, según nuestras búsquedas, 30 es el único s_abundante, pues sus divisores primos suman 31: 6+10+15=31

Algunos tipos de sigma_s

Los resultados de la suma de divisores pueden presentar alguna curiosidad. Recorremos posibilidades:

Sigma_s semiprima

Si un número N es semiprimo, el valor de SIGMA_S(N) coincide con N, luego será otro semiprimo. Si no lo es, sí puede serlo SIGMA_S. Estos son los primeros ejemplos:

Observamos algo lógico, y es que las potencias de primos poseen una sigma_s semiprima, pues coincidiría con el cuadrado de ese primo. De paso hemos descubierto que existen infinitas sigmas cuadradas.

Sigma_s cuadrada

Dejamos aparte las sigmas de las potencias de primos, que son todas cuadradas, e investigamos si existen en otros casos. El resultado es

Aparecen tres números poderosos, como 225, 675 y 1125. Estos poseen todos los factores primos con exponentes superiores a la unidad, lo que explica que se esperen sigmas cuadradas.

Sigma_s prima

Por último, destacamos que aparecen bastantes sigmas primas en los primeros números, y que vuelven a aparecer números poderosos.

 

Las otras sigmas

Sumas de cuadrados

Podemos sumar los divisores semiprimos previamente elevados al cuadrado, con lo que lograríamos SIGMA2_S. Basta un pequeño ajuste en nuestras funciones, usando la operación m=m+k^2

Los primeros resultados serían

Por ejemplo, SIGMA2_S(2160)=458, porque esa es la suma de los cuadrados de sus divisores semiprimos:

4^2+6^2+9^2+10^2+15^2=458

El valor de SIGMA2_S(N) es mayor o igual al de SIGMA_S(N), lo que nos abre la posibilidad de que aquí sí existan números s2_perfectos. Y es así, porque en la tabla vemos que SIGMA2_S(16)=16. ¿Existirán más? Los buscamos, y los primeros son: 16, 81, 625 y 2401, es decir, potencias cuartas de primos, en los que su divisor semiprimo es un cuadrado de primo, y al elevarlo al cuadrado, resulta N, que así se convierte en un s2_perfecto.

Hemos acudido a la velocidad de PARI, y al menos, para números inferiores a 10^6, todos los s2_perfectos son potencias cuartas de primos:

 

Otras sigmas de potencias

Las sumas con cubos son:

 

 Igual se encontrarían para otras potencias. Lo dejamos aquí.

 

Conjunto de divisores semiprimos

(Ver entradas anteriores sobre números semiprimos)

La búsqueda de los divisores semiprimos de un número N es similar a la de los divisores primos. Aquí deberemos buscar entre todos los números menores o iguales a N, pues existen semiprimos consecutivos y no nos podemos saltar ninguno.

Una forma sencilla de identificar si un número k es divisor de N es exigir que N/k=N\k, porque entonces la división normal “/” coincidirá con la entera “\”, lo que supone que el resto de la división es cero. Si le añadimos la condición essemiprimo(k), ya los tendremos identificados.

La siguiente función construye el conjunto de divisores primos y los cuenta:

Function div_semi$(n, repe As Boolean)
Dim k, m, nn, e
Dim s$

‘La función posee el parámetro repe para detectar si un divisor puede estar elevado a una potencia

 If esprimo(n) Then div_semi = "0": Exit Function
If essemiprimo(n) Then m = m + 1: div_semi = "1 : " + Str$(n): Exit Function ‘Casos primo y semiprimo
m = 0 ‘Contendrá el número de divisores
s = ""’Será la lista de divisores
k = 4 ’Comenzamos a ensayar semiprimos
While k <= n
If essemiprimo(k) And n / k = n \ k Then ‘Es divisor semiprimo
nn = n: e = 0 ‘Posibles exponentes
If repe Then ‘Caso de repetición
While nn / k = nn \ k: e = e + 1: nn = nn / k: Wend
End If
If repe Then m = m + e Else m = m + 1
s = s + Str$(k) ‘Recoge una nueva solución
If e > 1 Then s = s + "^" + ajusta(e )’Exponente
End If
k = k + 1
Wend
s = ajusta(m) + " : " + s ‘ajusta es como Str$ sin espacio en blanco
div_semi = s
End Function

Para el caso de no contar repetidos, estos son los primeros valores. Los resultados se componen del número de divisores seguido de la lista de semiprimos:

El número de divisores está publicado en  https://oeis.org/A086971

En esa dirección figura un `programa en PARI sumamente sintético:

a(n) = sumdiv(n, d, bigomega(d)==2)

También en ella se usa otra definición de estos divisores, como aquellos semiprimos que dividen a N, pero a su cuadrado no.

La última igualdad vale 1 si es verdadera, por lo que la suma se convierte en un conteo.

Para cualquier número elegido al azar disponemos de la misma respuesta. Por ejemplo, el número 2160 posee este conjunto de divisores semiprimos: 5 :  4 6 9 10 15, es decir, 5 divisores, 4, 6, 9, 10, 15.

Podemos encontrar también la lista de divisores semiprimos contando repeticiones, si en la función anterior usamos el parámetro 1. En la siguiente tabla la hemos aplicado en números de cuatro cifras:

Los repetidos figuran con su exponente.

Versión numérica

En la función que usamos podemos concretar la salida como el número de divisores nada más. De esa forma podemos catalogar bien el objeto de la búsqueda. Por ejemplo, ¿Cuál es el primer número de cinco cifras con seis divisores semiprimos sin repetir?

Las primeras soluciones son

 

El primer número con seis divisores es el 210, y sus divisores son 6, 10, 14, 15, 21 y 35. En la dirección https://oeis.org/A220264 figuran los primeros de cada número de divisores.

Todos estos recuentos se pueden realizar a partir de la descomposición factorial del número, como un ejercicio de combinatoria elemental.

Por ejemplo, 210=2*3*5*7, y basta agruparlos por pares: 2*3=6, 2*5=10, 2*7=14, 3*5=15, 3*7=21, 5*7=35.

Si existen factores repetidos, hay que combinar con cuidado, para no repetir soluciones, En 540=2^2*3^3*5 iríamos construyendo 2*2=4, 2*3=6, 3*3=9, 2*5=10, 3*5=15.

Con la función div_semi y parámetro 0: div_semi(540;0)= 5 :  4 6 9 10 15

Nota

En el conjunto de divisores semiprimos no se puede definir un orden parcial múltiplo-divisor, ya que ningún semiprimo es múltiplo de otro. Por eso, al contrario de los divisores generales, este conjunto no forma retículo.

Puedes consultar

https://hojaynumeros.blogspot.com/2013/05/reticulos-en-el-conjunto-de-divisores-1.html y siguiente.