martes, 19 de noviembre de 2013

¿De dónde vengo? (3) – Sumamos y contamos factores primos


En la anterior entrada vimos todos los divisores de un número en la búsqueda de una función inversa tal como la definimos previamente. Vamos a fijarnos en los primos, en las funciones que cuentan y suman primos.

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.

Como ya conocemos la solución, podemos plantear la estrategia 2 de búsqueda acotada y obtendremos las soluciones:2, 6, 30, 210, 2310…

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

Se entiende que 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

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)?

Si es un número relativamente pequeño bastará con descomponerlo en suma de números primos diferentes de todas las formas posibles y después elegir aquellos cuyo producto sea mínimo. Así, como todos estarán elevados a la unidad, nos garantizamos que el resultado es el MF_SOPF buscado.

Si el número N es primo, MF_SOPF(N)=N, porque N sería el mínimo valor de la suma de factores primos distintos que den N. Esto es trivial en el caso de 2, 3 y 5. Para primos mayores es así porque si descomponemos N primo en una suma de primos, el valor más pequeño posible, además de N, sería 2(N-2) (en el caso de que N y N-2 fueran primos gemelos y esto ocurre a partir de 7, luego N>=7, con lo que 2(N-2)=N+N-4>N. Lo mismo ocurriría con 3(N-3), 5(N-5), que cada vez producirían un resultado mayor. Esto es así porque la función x(N-x) presenta un máximo en x=N/2.

Si se descompone en más de dos sumandos, por un razonamiento similar vemos que el valor mínimo posible es N, luego

Si N es primo, MF_SOPF(N)=N

Si N es compuesto, lo descomponemos en sumandos primos diferentes, como se indicó en párrafos anteriores. En el caso de 12 lo podemos descomponer como 12=7+5=7+3+2. Los productos resultantes son 7*5=35 y 7*3*2=42, luego la solución es 35: MF_SOPF(12)=35

Según la conjetura de Golbach todo número par mayor o igual que 4 puede descomponerse en la suma de dos primos y según una variante débil, todo impar se puede descomponer en suma de tres primos. En ninguna de las dos se afirma que los sumandos sean distintos, por lo que no tenemos la absoluta certeza de que todos los números a partir de 7 posean un valor para la función. Existe una conjetura similar que afirma que todo número par mayor que 8 es suma de dos primos distintos. Podemos seguir con el tema con una cierta seguridad de que salvo 1, 4 y 6, todos los números naturales poseen un valor para MF_SOPF, salvo que se demuestre algún día que estas conjeturas son falsas.

Para números mayores tendríamos que automatizar el proceso: buscaríamos todas las descomposiciones de N en suma de primos distintos y evaluaríamos los productos para descubrir el mínimo.

Búsqueda acotada

Usaremos la Búsqueda acotada que explicamos en la primera entrada de esta serie. 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. Con esta idea podemos construir la función. Se supone que tenemos implementada la función SOPF, que no es difícil de programar.

Public Function sopf(n)
Dim f, a, s
Dim vale as boolean

If n=1 then sopf=0:exit function
If <4 then sopf=n:exit function
a = n
f = 2: s=0
While f * f <= a
vale=false
While a / f = Int(a / f)
Vale=true
a = a / f
Wend
If vale then s=s+f
If f = 2 Then f = 3 Else f = f + 2
Wend
sopf = s
End Function

Sobre esta función definimos MF_SOPF

Public Function mfsopf(n)
Dim vale As Boolean
Dim k, a, s, j

vale = True
k = 1
a = 0
While vale And k <= n ^ (n / 2)
If sopf(k) = n Then a = k: vale = False
k = k + 1
Wend
mfsop = a
End Function

Está diseñada para que en caso de que no se obtenga solución devuelva un 0. Esto sólo ocurre en 1, 4 y 6. Estudia la razón.

La cota es tan alta que, a partir de 255 aproximadamente, los registros de Excel se sobrepasan en muchos números. En estos casos se puede intentar la búsqueda con cotas más pequeñas, o bien usar un lenguaje más potente, como PARI

Código PARI

sopf(n)={local(f,s=0);f=factor(n);for(i=1,matsize(f)[1],s+=f[i,1]);return(s)}
mfsopf(n)={k=1;m=0;t=n^(n/2);while(m==0&&k<t,k=k+1;p=sopf(k);if(p==n,m=k));return(m)}
{for(i=7;200,print(mfsopf(i))

Con este código podemos reproducir las soluciones contenidas en http://oeis.org/A064502
Después de muchas búsquedas, parece que sí, que sólo 1, 4 y 6 carecen de función.

En esta tabla puedes ver los valores mayores que alcanza MF_SOPF para números menores que 1000:


Como se puede observar, muchos números requieren búsquedas que casi duplican su número de cifras, lo que obstaculiza el proceso.

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, pero los divisores primos se suman cada vez que aparecen (línea con el añadido de ‘**)

Public Function sopfr(n)
Dim f, a, s


If n=1 then sopfr=0:exit function
If <4 then sopfr=n:exit function
a = n
f = 2: s=0
While f * f <= a
While a / f = Int(a / f)
a = a / f
s=s+f ‘**
Wend
If f = 2 Then f = 3 Else f = f + 2
Wend
sopfr = s
End Function

La función MF_SOPFR también se obtiene con un código similar al de MF_SOPF sustituyendo las referencias a sopf por sopfr

Con estos cambios puedes obtener fácilmente los valores de MF_SOPFR, que están contenidos en http://oeis.org/A056240


No hay comentarios: