viernes, 14 de marzo de 2014

Restos en la función PRIMO(n)


Seguimos con nuestra tendencia a jugar y experimentar con los conceptos matemáticos. Ahora lo haremos con la enumeración de los números primos, por la que asignamos a cada número natural N el número primo que ocupa el lugar N en su orden natural. Esta función así construida la podemos llamar PRIMO(N), prime(n) en inglés, o, como hemos usado este año en el blog, PRIMNUM(N).  Para simplificar la escritura usaremos P(N).

Esta función, como es de esperar, está bien estudiada. En http://oeis.org/A000040 tienes muchos detalles. Si la representamos (de forma falsamente continua) notamos que es casi lineal, con concavidad hacia arriba.


En la página de OEIS citada se incluye la propiedad de que P(n) es siempre mayor que nln(n). En efecto, si representamos ambas funciones en un mismo gráfico, observamos que son muy similares. Ambas tienden “suavemente” a infinito conjuntamente con n.



Relaciones lineales

Esto nos va a servir para lo siguiente: Para cualquier valor de N, podemos encontrar el cociente entero P(N)\N y el resto correspondiente. Por ejemplo, P(22)=79, porque este es el primo que ocupa el lugar 22. Podemos expresarlo así: 79=3*22+13. Esto siempre es posible, y el cociente entero será igual o mayor que 1, porque P(N)>N. Aquí nos interesará el resto 13.

Todo número primo se puede expresar mediante el cociente entero entre su número de orden y el resto correspondiente.

En la gráfica esto equivaldría a dibujar una línea recta que corta exactamente a la gráfica de los primos en el punto (N,P(N)).

Restos posibles

El resto de la división entera entre un primo y su número de orden puede presentar muchos valores distintos. Vemos algunos de los primos publicados:

2, 3, 11, 13, 37, 43, 1087, 64591, 64601, 64661,… se caracterizan porque su resto respecto a su número de orden es 1. Por ejemplo, 64661 es el primo número 6466 y se cumple que 64661=6466*10+1. Estos números primos los tienes en http://oeis.org/A048891

También aparecen restos 2 (ver http://oeis.org/A156152). Por ejemplo, P(73)=367=73*5+2. Y también 3 (A171430) o resto -1 (A052013)

¿Aparecerán todos los restos si recorremos los números primos y los dividimos entre sus números de orden? En http://oeis.org/A004648 tienes su enumeración ordenada:

0, 1, 2, 3, 1, 1, 3, 3, 5, 9, 9, 1, 2, 1, 2, 5, 8, 7, 10, 11, 10, 13, 14, 17, 22, 23…

Al recorrer los primeros 1000 primos echamos de menos algún resto, como el 18 o el 20 ¿acabarán apareciendo? Para averiguar esto usaremos una técnica similar a otras que han aparecido en este blog: fijamos un número grande, como el 10^6, y para cada valor de resto que elijamos, por ejemplo ese 18 que no aparece, recorremos todos los primos menores que el tope y les calculamos su resto respecto al número de orden. Si aparece  el que queremos, ya lo hemos encontrado; si no, aumentamos el tope. Lo podemos construir en el Basic de las hojas de cálculo:

Public Function primoresto(n)
Dim a, i, p, r
a = 2: i = 1: r = -1: p = -2  Iniciamos la lista de primos y la variable r a -1
While p <> n And i <= 10 ^ 6  Bucle hasta la solución o hasta el tope
p = a - i * Int(a / i)  Buscamos el resto entre el primo a y su orden i
If p = n Then r = a Si el resto coincide con el número propuesto, ya tenemos solución
i = i + 1  Si no, avanzamos en la lista de primos
a = primprox(a)
Wend
primoresto = r
End Function

Si la función devuelve el valor -1, es que no se ha encontrado solución y hay que subir el tope. Con esta función y con Excel, que es una hoja rápida, hemos encontrado estos valores:



Llama la atención el mínimo primo que presenta resto 18. Efectivamente, 176557 es el primo número 16049 y el cociente entre ellos es 11 y el resto 18, como cabía esperar. Más impresionante es el correspondiente a 44, nada menos que 1304867. Para avanzar más hemos traducido el algoritmo a PARI

resprime(n)={local(a,i,r,p);a=2;i=1;r=-1;p=-2;while(p<>n&&i<=10^6,p=a%i;if(p==n,r=a);i+=1;a=nextprime(a+1));return(r)}
{for(i=1,50,print(resprime(i)))}

Con él, subiendo el tope a 10^8, hemos descubierto que el resto 110 no aparece hasta el primo 514279133

¿Existirá siempre un número primo que produzca un resto igual a un número que elijamos? No lo sabemos. Lo dejamos como conjetura:

Conjetura: Para cada número natural n>1 existe un número primo P(k) que produce un resto respecto a k igual a n.

Si alguien sabe algo más lo publicaremos como extensión.