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+p2 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.
