jueves, 7 de noviembre de 2013

¿De dónde vengo? (1) Generalidades


Nota previa: la serie de entradas que iniciamos hoy no tiene pretensiones de tipo teórico ni de descubrimiento de hechos nuevos. Gran parte de lo que trataremos está ya estudiado, pero con los procesos que desarrollaremos quienes nos lean podrán repasar conceptos y ejercitarse en buscar soluciones y justificarlas.

Trataremos en esta entrada y en las siguientes un problema similar al de la función inversa:

Dado un número natural N cualquiera intentaremos 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. Lo vemos con algún ejemplo:

Si tomamos el número 31, ¿qué otro número tendrá ese resultado al sumar sus divisores (función sigma)? Si calculamos un poco, veremos que el más pequeño que cumple esto es el 16, ya que 16+8+4+2+1=31. Lo expresaremos como 16=MF_SIGMA(31)

¿Cuál es el primer número que tiene exactamente 8 divisores (función tau)? Se trata del 24, que posee como divisores  24, 12, 8, 6, 4, 3, 2 y 1, luego MF_TAU(8)=24

No es fácil esta búsqueda, porque no siempre tenemos una acotación para encontrar aquellos números cuyo resultado en una función es el número dado. Por eso, tendremos que encontrar distintas estrategias. Avanzamos tres de ellas:

Reflexión teórica

Esta es la más valiosa, pero no siempre posible. Intentaremos en ella llegar al resultado por razonamiento. En el caso del ejemplo anterior MF_TAU(8)=24 era fácil. La función TAU viene dada por la fórmula

En ella a1, a2, … son los exponentes de los números primos en la descomposición factorial de N. Es claro que para que se tengan 8 divisores D(N) ha de tener como factores 2*2*2, 4*2 o 8, o lo que es igual, signatura prima (conjunto de los exponentes de los primos) igual a (1,1,1), (3,1) o (7). Para encontrar el mínimo N imagina qué primos se pueden corresponder con esos exponentes. Lo vemos:

2*2*2: la combinación de primos mínima en este caso sería 21*31*51 =30

2*4: Exponentes 1 y 3. El número mínimo sería 23*3= 24

8: El único exponente sería 7, y el mínimo posible N=27 = 128

De las tres posibilidades el resultado más pequeño es 24, luego es la solución.

Se comprende que no siempre será posible este tipo de razonamiento

Búsqueda acotada

Es muy difícil acotar la búsqueda del número mínimo que estamos intentando encontrar. Una estrategia sería la de fijar una cota, por ejemplo 1000, para números pequeños y tratar luego aparte las excepciones. Algo parecido hicimos en la entrada de este blog

http://hojaynumeros.blogspot.com.es/2011/01/alguien-sabe-algo-de-esto-1.html

En ella resolvíamos el problema propuesto, pero fracasando en números como 223 al intentar usar una hoja de cálculo.

Probemos con la indicatriz de Euler. Recuerda que esta función cuenta los números menores que N y coprimos con él, incluyendo el 1. Escribimos la lista de posibles resultados, 1, 2, 3, 4, … y buscamos hasta 10^4 qué números poseen como función de Euler ese valor. Podríamos usar un código parecido a este:

For i = j To l
k = i
vale = True
While vale And k < 10 ^ 4
If euler(k) = i Then vale = False: a = k
k = k + 1
Wend
If Not vale Then
Msgbox(i)
Msgbox(a)
Next  i


Si existe algún fallo se aumenta el tope o se estudia teóricamente.

Por ejemplo, en esta tabla figuran los resultados para la función de Euler en los primeros números. Cuando la imagen es 0 significa que se ha llegado a 10^4 sin encontrar resultados. Como son muchos, habría que aumentar el tope de 10^4 o bien cambiar de técnica.



Rellenado de resultados

Podemos plantear la búsqueda con el punto de vista contrario. Recorremos los números naturales y para cada uno de ellos evaluamos la función deseada. Preparamos unas memorias (pueden ser celdas de hojas de cálculo) y las vamos rellenando ordenadamente con los resultados. Las memorias que queden vacías necesitarán un estudio aparte.

Se puede intentar este método con la función TAU, o DIVISOR o SIGMA0, que estudiamos en anteriores párrafos. Este caso ya está publicado en OEIS 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...

Se ve que este método resultaría lento y necesitaría topes muy grandes, por la existencia del valor 268435456 que supera cualquier planteamiento.

En la imagen puedes ver un barrido efectuado entre 1 y 100



En ella falta el 1, porque todo número tiene al menos dos divisores, y el 11, que según http://oeis.org/A005179 su imagen sería 4096, fuera del rango de búsqueda.

Cuando ocurra que queden ceros en las memorias, se deberá ampliar la búsqueda, cambiar de método o demostrar la imposibilidad.

En las dos siguientes entradas estudiaremos algunos ejemplos concretos que presentan cierto interés. Puede que usemos los tres métodos de búsqueda, según la naturaleza de la función que tratemos.


No hay comentarios: