martes, 26 de noviembre de 2013

Primo, ¿qué tienes que ver con tu número de orden?

Esta entrada participa en la Edición 4.12310562 del Carnaval de Matemáticas cuyo blog anfitrión es ZTFNews.org.


En el mes de septiembre, en un diálogo a través de Twiter, Benjamin Vitale (http://benvitalenum3ers.wordpress.com/) me hizo notar que 3559 es el número primo de número de orden 499, y que ambos números tienen la misma suma de cifras, 22. Ya sabéis que en este blog respondemos, cuando es posible, a todas las ideas que nos llegan con una cuestión a resolver, y no es la primera vez que estas nos llegan de Ben Vitale. En este caso podría ser:

¿Qué detalles pueden tener en común un número primo y su número de orden en la lista de los mismos?

Coincidencia entre cifras

No sólo pueden coincidir en la suma de sus cifras. Será relativamente fácil que lo hagan en la última cifra. En efecto, los primos 17, 31, 83, 109, 157, 563, 587, 599, 661, 811, 823, 859, … Por ejemplo, el 17 es el primo número 7 y 31 el número 11. Puedes estudiarlos mejor en http://oeis.org/A085598

Es más difícil que ambos números coincidan en sus dos últimas cifras. Los primeros números que cumplen esto son (los presentamos por pares, número de orden y primo):

(243,1543), (519, 3719), (589, 4289), (703, 5303), (741, 5641), (823, 6323), (901, 7001), (959, 7559), (973, 7673), (1033, 8233), (1081, 8681), (1197, 9697), (1223, 9923), (1443, 12043), (1477, 12377), (1491, 12491),(1541, 12941), (1723, 14723) (1751, 14951)…

En todos ellos coinciden las dos últimas cifras del primo y de su número de orden. Para encontrarlos necesitamos dos funciones: CORTACIFRAS y PRIMONUM.

Cortar cifras

La primera no es difícil de programar en cualquier lenguaje. Su misión es seleccionar algunas cifras de la expresión decimal de un número. La versión más simple, sin control de errores, es esta
CORTACIFRAS(P,M,N)=(P MOD 10^N)\10^(M-1), en la que P es el número, M el inicio del corte y N el final, ambos incluidos (pueden ser iguales y entonces se corta una sola cifra). El significado de la fórmula es que calculas el módulo o residuo de P respecto a 10^N y el resultado lo divides de forma entera entre 10^(M-1)

Si del número 288762 deseas seleccionar las cifras que van de la segunda a la quinta deberás efectuar estos cálculos: 288763 MOD 10^5 = 88762 y ese número lo divides sin decimales entre 10^(2-1), es decir 8876.

En hoja de cálculo se expresaría así: =COCIENTE(RESIDUO(288762;10^5);10). Compruébalo.

En PARI es más sintético: (288762%10^5)\10

Encontrar el número primo dado su número de orden

Esta función PRIMONUM es más difícil de conseguir. En PARI está yá implementada: prime(k), pero no para números grandes. En el resto de la entrada usaremos esta notación prime(k) que resulta muy sintética. En hoja de cálculo no está disponible de entrada, aunque sí en algún complemento. Un código que resulta un poco lento podría ser este:

Public Function primonum(n)
Dim p, c, i

'encuentra el primo cuyo número de orden es n

c = 0: i = 2
While c < n
If esprimo(i) Then c = c + 1: p = i
i = i + 1
Wend
primonum = p
End Function

Para quienes siguen este blog no será muy difícil encontrar la función esprimo.

Con estas dos funciones y una estructura tipo FOR_NEXT puedes encontrar los primos deseados. Hemos usado también este programa en PARI:

cutdigit(a,p,q)=(a%10^q)\10^(p-1)
{for(n=5,5000,p=prime(n);if(cutdigit(p,1,2)==cutdigit(n,1,2),print(p)))}

En primer lugar hemos definido cutdigit para seleccionar cifras y después la hemos usado entre 1 y 2 para averiguar si coinciden las cifras en k y prime(k)

Hemos publicado la tabla para prime(k) en  https://oeis.org/A232102 y la de k ya estaba publicada en https://oeis.org/A067838

Modificando lo anterior podemos buscar la igualdad en las tres últimas cifras. Los resultados son estos:

(1491, 12491), (1723, 14723), (4119, 39119), (4437, 42437), (6347, 63347), (6931, 69931), (7817, 79817), (9551, 99551), (12083, 129083), (12637, 135637), (13647, 147647), (15103, 165103), (16637, 183637), (17181, 190181),…

Los números primos los hemos publicado en https://oeis.org/A232104 y sus números de orden los tienes en https://oeis.org/A067841. Intenta reproducirlos.

Con cuatro cifras tenemos que forzar la máquina, porque en Basic resulta lento y en PARI la función prime(k) sólo está definida hasta un tope, que en nuestro caso se supera después de obtener el primo número 24833. Hemos tenido que acudir a la función primenext (o nuestra primprox), pero no daremos detalles. El resultado es, para los números de orden:

9551, 15103, 18697, 23071, 24833, 48229, 53853, 58681, 83819, 91617, 93909, 107647, 115259, 120487, 126497, 156991, 160681, 162857, 177477, 181833, 189143, 194229, 208679, 213703, 221569,…

Y para los números primos:

99551, 165103, 208697, 263071, 284833, 588229, 663853, 728681, 1073819, 1181617,
1213909, 1407647, 1515259, 1590487, 1676497, 2116991, 2170681, 2202857, 2417477,
2481833, 2589143, 2664229, 2878679, 2953703, 3071569,…

Puedes compara uno a uno. Por ejemplo, el primo número 194229 es el 2664229.

Las hemos incorporado a https://oeis.org/A232189 y https://oeis.org/A232188 respectivamente.

No seguimos presentando sucesiones, por nuestro deseo de no cansar. Sólo destacaremos que los primos 1407647 y 1515259, de órdenes respectivos 107647 y 115259 son los primeros en presentar una coincidencia de cinco cifras, y prime(303027)=4303027, prime(440999)=6440999 son los primeros en coincidir en seis.

De los de coincidencia en siete cifras damos el primero: prime(5517973)=95517973, pero le siguen más. Hay que forzar el PARI y con las hojas de cálculo mejor lo olvidamos.

Coincidencia total

Existen primos cuyo número de orden constituye todo su final en cifras. Son los llamados primos automórficos, y están publicados en http://oeis.org/A046883. Por ejemplo, el primo número 9551 resulta ser 99551 y el 303027, 4303027, coincidencia en las últimas cifras.

Operaciones con cifras

Las coincidencias en la suma de cifras similares a las de 499 y 3559 están recogidas en http://oeis.org/A033548 y reciben el nombre de “primos de Honaker”. Puedes ver en la siguiente dirección un ejemplo notable de este tipo de primos:

http://primes.utm.edu/curios/page.php/37778931862957154241011.html

Hemos investigado las coincidencias en el producto de cifras, pero no presenta gran interés, ya que las cifras 0 aumentan las posibilidades de coincidencia. Te lo dejamos como propuesta. Los primeros son: 17, 181, 409, 443, 491, 601, 809, 1013, 1069,…

Concatenaciones

Están publicadas relaciones basadas en la concatenación de cifras:

Concatenar p y prime(p) y que resulte un primo:

http://oeis.org/A084667: La concatenaciones primeras son (separamos con un guión el número de orden y el primo) 2-3, 4-7, 6-13, 12-37, 17-59, 18-61, 23-83, 27-103, 30-113, 35-149, 36-151,…

Concatenación inversa

http://oeis.org/A084669: Si invertimos la concatenación también obtenemos ejemplos:

5-3, 23-9, 67-19, 73-21, 157-37, 307-63, 389-77, 419-81, 449-87, 587-107,…

Hemos investigado también las diferencias entre prime(k) y k, pero o están publicadas o carecen de interés. Ahí tienes un reto.




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


miércoles, 13 de noviembre de 2013

¿De dónde vengo? (2) – Sumamos divisores

Proseguimos nuestra búsqueda de esa especie de función inversa que hemos rotulado con MF en la anterior entrada. Ahora estudiaremos la suma de divisores.

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.

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. Esto nos lleva a que el mejor método entre los que propusimos en  la anterior entrada sea el de búsqueda acotada.

Así lo hemos intentado con hoja de cálculo, llegando a la misma conclusión que las dos sucesiones citadas de OEIS:

Tienen un valor determinado para MF_SIGMA(N) los números
1, 3, 4, 6, 7, 8, 12, 13, 14, 15, 18, 20…http://oeis.org/A002191

Puedes comprobarlo en esta tabla obtenida con hoja de cálculo:



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.

Hemos usado la función SIGMA definida por nosotros. Si no tienes acceso a ella puedes usar el siguiente código para obtener los mismos resultados. Como advertimos a menudo, estos códigos se trasladan fácilmente a otros lenguajes de programación. Este que ofrecemos devuelve un cero si MF_SIGMA no está definida para ese número. No es muy eficiente, pero sí fácil de entender:

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

vale = True
k = 1
a = 0
While vale And k <= n
s = 0
For j = 1 To k
If k / j = k \ j Then s = s + j ‘Este FOR-NEXT calcula la función sigma de k
Next j
If s = n Then a = k: vale = False ' comprueba si SIGMA coincide con el argumento n
k = k + 1
Wend
mfsigma = a
End Function

Con esta función puedes determinar si un número coincide con la función SIGMA de otro. Por ejemplo MF_SIGMA(2014)=0, luego no existe ningún otro número cuya suma de divisores sea 2014. Si embargo, MF_SIGMA(2012)=2011, porque este último es primo, y MF_SIGMA(2016)=660, porque

2016= 660+330+220+165+132+110+66+60+55+44+33+30+22+20+15+12+11+10+6+5+4+3+2+ 1

Puedes usar también la función definida en PARI

mfsigma1(n)={k=0;while(k<=n&&sumdiv(k, d, d)<>n, k=k+1);if(k>=n,k=0); return(k)}
{print(mfsigma1(20))}

Con él, cambiando el valor de 20 por otro cualquiera, puedes encontrar su MF_SIGMA

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?

Repetimos todo el trabajo. Basta sustituir la línea de código

If k / j = k \ j Then s = s + j

Por esta otra

If k / j = k \ j Then s = s + j^2

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

1, 5, 10, 21, 26, 50, 85, 91, 122, 130, 170, 210, 250, 260, 290, 341, 362, 455, 500, 530, 546, 610, 651, 820, 842, 850, 962, 1050, 1220, 1300, 1365, 1370, 1450, 1682, 1700, 1810, 1850, 1911, 2210, 2366, 2451, 2500, 2562…

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

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

Como complemento de ella, podemos encontrar los números cuyo valor de sigma_2 coincide con los valores de la anterior sucesión.

1, 2, 3, 4, 5, 6, 8, 9, 11, 10, 13, 12, 14, 15, 17, 16, 19, 18, 21, 23, 20, 22, 25, 27, 29, 24, 31, 28, 33, 30, 32, 37, 34, 41, 39, 38, 43, 36, 40, 45, 49, 42, 44, 46, 53, 51, 55, 50, 48, 59, 52, 57, 61, 54, 58, 56, 65, 67, 63, 62, 71, 69, 73, 60, 64, 68, 66, 79, 70, 75, 74, 83, 81, 85, 76, 72, 89, 82, 87, 78, 80, 86, 97, 95, 93…

Están casi todos los números. Los que faltan no son los mínimos con cada valor de la función. Por ejemplo, el 7 no está porque sigma_2(7)=50 y sigma_2(6)=50, luego ha de figurar el 6 y no el 7.

Para SIGMA_3

Estos son los valores que puede tomar sigma_3. Como se ve, con frecuencia muy baja.

1, 9, 28, 73, 126, 252, 344, 585, 757, 1134, 1332, 2044, 2198, 3096, 3528, 4681, 4914, 6813, 6860,…
http://oeis.org/A001158

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

Puedes encontrar casos similares en  http://oeis.org/A063972 para divisores unitarios y en  http://oeis.org/A070015 para las partes alícuotas.

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.