martes, 11 de junio de 2024

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=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:

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. 

 

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.

 

lunes, 20 de mayo de 2024

Regresos 9 – Como una función inversa

Hace tiempo publicamos unas entradas dedicadas a investigar si un número es el resultado de aplicar una función aritmética a otro. No llamamos función inversa a este proceso porque normalmente cada número puede provenir de varios orígenes distintos.

Dado un número natural N cualquiera se intenta encontrar otro número M natural tal que al aplicarle una cierta función aritmética, nos resulte el primero, es decir F(M)=N.

Como en teoría de números suelen existir varias soluciones, elegiremos siempre la menor de ellas. La representaremos con el prefijo MF seguido del nombre de la función.

En este regreso al tema prescindiremos de algunos detalles, e intentaremos generalizar los procesos. Lo efectuaremos mediante una función que nos devuelva el menor número M tal que F(M)=N. Nos basaremos en un esquema mínimo, tanto en VBasic como en PARI, dejando bien destacadas dos líneas en las que modificaremos la función y la cota de búsqueda.

Es muy difícil acotar la búsqueda en general. Una estrategia es la de fijar una cota, por ejemplo 10^4, para números pequeños y tratar luego aparte las excepciones. Si con una cota no aparece el resultado, habrá que ampliarla, y si se sigue obteniendo un resultado negativo, buscar otros métodos teóricos para resolver la cuestión o dejarla como conjetura.

La función que proponemos devuelve un cero si no encuentra resultado, y en caso positivo, devuelve el menor valor que cumpla los requisitos.

En los ejemplos se usan las funciones TAU, SIGMA, PHI, que hemos usado en este blog en algún momento. Puedes buscar ahí sus códigos o definiciones.

Esquema de función

Function mfun(n)
Dim k, a, f, cota
Dim vale As Boolean

'En esta línea concretamos la cota

cota = 10 ^ 4 ‘Para rellenar previamente

k = 1’Inicio de la búsqueda
a = 0 ‘Variable del resultado
vale = False ‘No hay todavía solución
While Not vale And k < cota

'En esta línea concretamos la función
f = tau(k) ‘Para rellenar previamente

If f = n Then vale = True: a = k ‘Se encontró la solución
k = k + 1
Wend
mfun = a
End Function

Hemos rellenado como ejemplo la función TAU, o número de divisores. Aplicada a los primeros números nos devuelve las primeras soluciones de MF_TAU, es decir, los menores números cuya función TAU devuelve el número dado.

Es ilustrativo observar los valores que son potencias de 2, los que son libres de cuadrados, y los que dan un cero. En los primeros se puede comprobar contando, como 64=MF_TAU(7), ya que los divisores de 64 son siete: 1, 2, 4, 8, 16, 32, 64.  Los libres de cuadrados, como el 6, se corresponden con soluciones pares, y los que contienen cuadrados, salvo casos particulares, provienen de impares, como 144=MF_TAU(15). El caso del 17 y el 19 es especial, porque lo que ha ocurrido es que la cota se ha quedado corta. La subimos y queda:

Estos dos ejemplos ilustran el problema con el que nos encontraremos, y es que, a veces, la cota que fijemos se queda pequeña.

Estos valores de MF_TAU están publicados en

http://oeis.org/A005179

1, 2, 4, 6, 16, 12, 64, 24, 36, 48, 1024, 60, 4096, 192, 144, 120, 65536, 180, 262144, 240, 576, 3072, 4194304, 360, 1296, 12288, 900, 960, 268435456

En esta página puedes consultar algunos valores concretos de esta función. Por ejemplo, para N=p primo, el resultado es 2^(p-1). Para un semiprimo de tipo N=pq con p<=q obtendríamos 3^(p-1)*2^(q-1). Son resultados fáciles de razonar, pero no es nuestro objetivo seguir con ellos.

Observamos que los resultados aparecen de forma irregular y que algunos, como el último, requieren cotas grandes. Esto justifica que pensemos en una versión en PARI, que aporta más velocidad y un rango mayor de valores. Podemos usar este código:

ff(n)=numdiv(n) \\Aquí definimos la función

mfun(n)={my(cota=10^8,k=1,a=0,vale=0,f);while(vale==0&&k<cota,f=ff(k);if(f==n,vale=1;a=k);k+=1);a}\\El mismo algoritmo
for(i=1,20,print1(mfun(i),", ")) \\Pedimos resultados en un rango

El código está adaptado a nuestro ejemplo, la función TAU. En la primera línea escribimos la función (aquí numdiv). Dentro del código, podemos alterar la cota, si vemos que es excesiva (10^8).

Lo hemos comprobado en la página oficial de PARI

(https://pari.math.u-bordeaux.fr/gp.html)

 


Función SIGMA

Recuerda que la función SIGMA suma todos los divisores de un número. Generalizaciones de la misma son las funciones SIGMA_K, que suman los divisores elevados al exponente K

(Ver http://hojaynumeros.blogspot.com.es/2011/02/la-familia-de-las-sigmas-1.html y la entrada siguiente).

Cualquier valor elegido al azar no tiene por qué ser el resultado de este tipo de sumas. De hecho, se sabe ya qué valores puede tomar SIGMA(N) y cuáles no.

En nuestro caso deberíamos cambiar la línea que define la función en VBasic:

'En esta línea concretamos la función

f = sigma(k) ‘Para rellenar previamente

La cota la dejamos en 10^3. Pedimos resultados y nos queda:

Observamos la abundancia de ceros, lo que significa que para esos números no hay solución. Podemos aumentar la cota, pero ya sabemos, por estar publicados, en qué casos ocurre esto. No tienen solución los incluidos en http://oeis.org/A007369: 2, 5, 9, 10, 11, 16, 17, 19, 21, 22, 23… La función SIGMA no puede tener nunca estos valores. No existe ningún número cuya suma de divisores sea 17, 19 o 21.

Sí la tienen estos otros (http://oeis.org/A002191): 1, 3, 4, 6, 7, 8, 12, 13, 14, 15, 18, 20…Por ejemplo, el valor 13 se corresponde con la suma de divisores de 9: 9+3+1=13.

Para reproducir esta situación podemos acudir a la siguiente consideración: Para un N dado, SIGMA(N)³1+N, porque ese sería el valor más desfavorable, que se da cuando N es primo. En cualquier otra situación, aparecerán otros divisores, superando así el valor 1+N. así que, N£SIGMA(N)-1. Por tanto, si nos dan un valor fijo K=SIGMA(N),  bastará buscar N en el rango 1…K-1.

Así que, en este caso, la mejor cota es N

Comprobamos las dos soluciones:

Números que siempre tienen solución:

Coinciden con los publicados:

1, 3, 4, 6, 7, 8, 12, 13, 14, 15, 18, 20…http://oeis.org/A002191

Observa que cuando la diferencia entre N y MF_SIGMA(N) es 1, el número de la segunda columna es primo.

En la tabla se intuye que los dobles de los perfectos, como el 12, coinciden con la suma de divisores de su mitad, el 6.

Si imponemos la condición de que MF_SIGMA(N) sea nula, obtendremos el conjunto complementario, de los que no presentan solución:

También hay coincidencia con lo publicado (https://oeis.org/A007369)

Podemos usar una versión en PARI:

ff(n)=sigma(n)
mfun(n)={my(cota=200,k=1,a=0,vale=0,f);while(vale==0&&k<cota,f=ff(k);if(f==n,vale=1;a=k);k+=1);a}
for(i=1,50,if(mfun(i)==0,print1(i,", ")))


Las otras sigmas

Si sumamos los cuadrados de los divisores de un número nos resulta la función SIGMA_2, con los cubos SIGMA_3 y, en general, podemos definir toda la familia para exponentes mayores.

¿Qué números coinciden con la suma de los cuadrados de los divisores de otros?

En este caso bastará usar las funciones predefinidas que ya hemos usado en otra ocasión

(Ver https://hojaynumeros.blogspot.com/2011/03/la-familia-de-las-sigmas-2.html)

Obtenemos así la lista de números cuya MF_SIGMA_2 está definida:


Entre ellos están los de la forma 1+p
2 con p primo.

Figuran en http://oeis.org/A001157, pero con algunos repetidos respecto a nuestra sucesión.

En PARI

Como este lenguaje no tiene implementadas las SIGMAS_K, deberemos introducirlas en la línea de ff:

ff(n)=sumdiv(n, d, d^2)
mfun(n)={my(cota=200,k=1,a=0,vale=0,f);while(vale==0&&k<cota,f=ff(k);if(f==n,vale=1;a=k);k+=1);a}
for(i=1,300,if(mfun(i)<>0,print1(i,", ")))

El uso de sumdiv es muy potente. Recorremos con él los divisores d y sumamos d^2 (en este caso).

Invitamos a los lectores a ampliar la cuestión, modificando la primera línea, a SIGMA_3, SIGMA_4, y demás. Deben obtener:

Para SIGMA_3: 1, 9, 28, 73, 126, 252, 344, 585, 757,…(tarda un poco) (https://oeis.org/A001158)

Para SIGMA_4: 1, 17, 82, 273, 626,…( https://oeis.org/A001159)

En PARI

mfsigma3(n)={k=0;while(k<=n&&sumdiv(k, d, d^3)<>n, k=k+1);if(k>=n,k=0); return(k)}

Un caso atractivo es el de USIGMA, que suma sólo los divisores unitarios, que son aquellos d primos con N/d. En este caso, la línea de ff(n) en PARI quedaría así:

ff(n)=sumdiv(n, d, d*(gcd(d,n/d)==1))

Podemos traducir como “sumar todos los divisores d que sean primos con N/d”

Los primeros valores de MF_USIGMA, a partir del 2, son: 2, 3, 4, 5, 0, 7, 8, 9, 0, 6, 0, 13, 0, 0, 16, 10, 0, 12, 0, 0, 0, 14, 0, 25, 0, 27, 0, 18, 0, 21, 32, 0, 0, 22, 0, 37, 0, 28 (Ver  http://oeis.org/A063972)

 

Sumamos y contamos factores primos

Vamos a fijarnos en los divisores primos, y en las funciones que los cuentan y suman.

Función Omega

Esta función cuenta los factores primos distintos de un número natural. No se cuentan las repeticiones, sino el número de primos distintos. Así, w(6)= w(12)= w(18)= w(24)=2, porque todos comparten dos primos distintos, 2 y 3.

Para encontrar MF_OMEGA(N) de un número bastará encontrar el primorial

(http://hojaynumeros.blogspot.com.es/2012/02/el-primorial.html), que contiene tantos factores primos como indique N. Esto es así porque los primoriales tienen como expresión  2*3*5*…*k , y es fácil entender que son los números mínimos que tienen k factores primos distintos.

Para comprobarlo, volvemos a nuestro esquema de búsqueda, usando OMEGA en la línea adecuada:

'En esta línea concretamos la función

f = omega(k) ‘Para rellenar previamente

El resultado es:


Efectivamente, son primoriales. Los últimos los hemos rellenado manualmente.

Con bigomega

Bigomega cuenta los factores primos con repetición. Esto cambia totalmente el planteamiento, porque es fácil ver que MF_BIGOMEGA(N)=2^N

Es fácil de entender: si con factores primos distintos el mínimo vendrá de productos tipo 2*3*5*7…, si se admite repetición, se convertirán en 2*2*2*2…como candidatos a MF_BIGOMEGA

Por cambiar de procedimiento, lo comprobamos con PARI:


Sólo hemos cambiado OMEGA por BIGOMEGA.

Función SOPF

Esta función suma los factores primos de un número sin contar repeticiones. Por ejemplo, sopf(84)=3+2+7=12, porque aunque el factor 2 figura al cuadrado en la descomposición factorial, sólo se cuenta una vez.

Podemos definir MF_SOPF(N) como el mínimo número cuyo resultado en la función SOPF es N. En el ejemplo anterior no sería 84 el valor de MF_SOPF(12). Habría que profundizar más

¿Cómo encontramos el valor de MF_SOPF(N)?

Es fácil encontrar una cota para un número con un valor de SOPF dado, sea, por ejemplo N. Todos los sumandos primos en los que pueda descomponerse N serán menores o iguales que N y como todos son mayores o iguales a 2, su número no sobrepasará N/2. Así que el número buscado tendrá como cota N^(N/2). Es muy amplia, y en la mayoría de los casos se encontrará la solución mucho antes, pero lo importante es que existe y nos permite acotar la búsqueda. La función SOPF la tenemos implementada, por ejemplo en https://hojaynumeros.blogspot.com/2019/11/unidos-por-el-sopf.html

Así que en la línea de definición de la función escribiremos f=sopf(k), dentro de nuestra función básica, y como cota n^(n/2). Resultará en la búsqueda:


Parece que solo los números 1, 4 y 6 no son SOPF(K) para ningún valor de K. En el caso de PARI hay que definir
sopf previamente:


Con este código podemos reproducir las soluciones contenidas en
http://oeis.org/A064502

Con SOPFR

La función logaritmo entero o sopfr es similar a la anterior, pero contando los primos con repetición. Casi todas las consideraciones estudiadas hasta ahora siguen siendo válidas salvo algún detalle:

Ahora el 4 y el 6 poseen valores para la función buscada: MF_SOPFR(4)=4=2*2 y MF_SOPFR(6)=8=2*2*2. El 1 sigue sin presentar solución.

La función sopfr se obtiene con un código similar al de sopf, pero los divisores primos se suman cada vez que aparecen. Están publicados en http://oeis.org/A056240

Función PHI de Euler

Otro caso interesante es el de aquellos números tales que existe un X tal que PHI(X)=N. Recordamos que PHI cuenta los números menores que X y que son primos con él, incluido el 1. Es evidente que X no será menor que N, lo que puede complicarnos la cota de búsqueda. En estos casos elegiremos cotas altas y estudiaremos los casos particulares. En la línea de definición escribiremos:

F=EULER(k)

La tenemos implementada en https://hojaynumeros.blogspot.com/search?q=euler%28

Obtendremos:


Observamos que, a partir del 2, sólo los números pares poseen valores en MF_EULER. Están publicados en
https://oeis.org/A002202

Como en PARI está implementada esta función como eulerphi, es fácil adaptar nuestro código a ella:

Observamos que, salvo el 1, ningún impar es valor de PHI.