Demostrar el siguiente hecho: dada cualquier secuencia de dígitos en cualquier base, por ejemplo, 314159265358979323 base 10, hay infinitamente muchos primos que comienzan con estos dígitos, por ejemplo, cuando se expresa en decimal comienzan con 314159265358979323. Creo que usar un teorema de números primos será útil. Pero todavía no estoy consiguiendo un punto de cómo empezar la prueba.
Respuestas
¿Demasiados anuncios?
Oli
Puntos
89
Usamos el Teorema de los Números Primos, nada más, y hacemos todos los detalles para un caso particular. El método utilizado puede trasladarse fácilmente al caso general.
Sea $\pi(x)$ sea el número de primos menores o iguales que $x$ . Para cualquier número real $x>1$ , dejemos que $F(x)=\dfrac{x}{\ln x}$ . El teorema de los números primos dice que $$\lim_{x\to \infty}\frac{\pi(x)}{F(x)}=1.$$ Por el definición de límite, dado cualquier $\epsilon$ tenemos $$1-\epsilon <\frac{\pi(x)}{F(x)} <1+\epsilon\qquad\text{(Inequality $ 1 $)}$$ si $x$ es lo suficientemente grande. (El significado de "suficientemente grande" depende del valor de $\epsilon$ .)
Demostraremos que existen infinitos primos cuya representación hexadecimal comienza por $324$ . Por qué $324$ ? En hexadecimal representación de $\pi$ comienza con $3.24$ . El OP utilizó una cadena de dígitos mucho más larga, también conectada a $\pi$ . Pero algo de esa longitud, tanto en hexadecimal como en decimal, sería un engorro de teclear. Parece apropiado utilizar "dígitos" iniciales de $\pi$ ya que trabajaremos con $\pi(x)$ . ¿Por qué hexadecimal? Para demostrar que la base no importa. Además, ¡la pregunta procedía originalmente de un sitio de programación! ¿Por qué no utilizar un principio general y una base general? Porque hacerlo podría ocultar la simplicidad básica del argumento.
Nota importante : En lo que sigue, los números $324$ y $325$ aparecen a menudo. Son siempre para ser leídos como números a la base $16$ . (Así, por ejemplo, $324$ se refiere al número que en base diez se escribiría como $804$ .) La base $16$ ocurre con bastante frecuencia. Por supuesto, debe leerse en base diez. Los otros pocos números que aparecen, a menos que se especifique lo contrario, deben leerse en base $16$ números. Ocasionalmente, para enfatizar, se menciona explícitamente la base.
Queremos demostrar que hay enteros arbitrariamente grandes $n$ para el que existe un primo $p$ con $$324_{16}\times 16^n <p < 325_{16}\times 16^n.$$ (La desigualdad anterior equivale a decir que los tres primeros "dígitos" hexadecimales de $p$ son $3$ , $2$ y $4$ .)
Por desigualdad $1$ el número de primos menores que $325\times 16^n$ est $>(1-\epsilon)F(325\times 16^n)$ . De nuevo por la desigualdad $1$ el número de primos menores que $324\times 16^n$ est $<(1+\epsilon)F(324\times 16^n)$ . Por tanto, el número de primos en el intervalo ( $324_{16}\times 16^n, 325_{16}\times 16^n)$ es mayor que $(1-\epsilon)F(325\times 16^n) -(1+\epsilon)F(324\times 16^n)$ . Así, si
$$(1-\epsilon)F(325\times 16^n) -(1+\epsilon)F(324\times 16^n)>0,$$ debe haber al menos un primo entre nuestros dos límites. (Recordemos que somos Contando primos. Si una desigualdad nos dice que la cuenta es mayor que $0$ ese recuento es al menos $1$ .)
Así que queremos elegir $n$ lo suficientemente grande como para que la desigualdad $1$ y tal que $$(1-\epsilon)\frac{325\times 16^n}{\ln(325\times 16^n)}>(1+\epsilon)\frac{324\times 16^n}{\ln(324\times 16^n)}.$$ Las "leyes de los logaritmos", junto con algunos reordenamientos, muestran que la desigualdad anterior es equivalente a $$n(\ln 16)(1-649\epsilon)>(1+\epsilon)(324)(\ln 325)-(1-\epsilon)(325)(\ln 324)\qquad\text{(Inequality $ 2 $)}$$ Tenga en cuenta que $649$ debe leerse en base $16$ . Ahora estamos listos para el empujón final.
En primer lugar $\epsilon$ sea el recíproco de $1000_{16}$ (este recíproco es seguramente menor que el recíproco de $649_{16}$ ).
Entonces a la izquierda de Desigualdad $2$ tenemos $n$ veces una constante positiva, y a la derecha tenemos una constante. A continuación $n$ sea lo suficientemente grande como para garantizar que la desigualdad $1$ se cumple para el valor de $\epsilon$ y $x >324\times 16^n$ .
Por último $n$ sea también lo suficientemente grande como para garantizar que la Desigualdad $2$ se cumple para el valor de $\epsilon$ . Entonces siempre hay un primo entre $324_{16}\times 16^n$ y $325_{16}\times 16^n$ es decir, un primo cuyos "dígitos" hexadecimales iniciales son $3$ , $2$ y $4$ .
Sólo se necesitan pequeños cambios de edición para que el argumento funcione para cualquier secuencia inicial de "dígitos", y cualquier base.
tomash
Puntos
4364
A simple consecuencia de la PNT es el hecho de que para cualquier número real $k>1$ existe un $n_0$ tal que existe un primo entre $n$ y $kn$ para todos $n > n_0$ . Ahora supongamos que tu base de partida deseada $b$ secuencia es $d$ dígitos largos; set $k = 1 + b^{-d}$ y aplicar el hecho anterior.
dave
Puntos
224
Este es un caso especial del siguiente hecho, cuya sencilla y breve demostración aparece en la p. 4 de Secuencias disyuntivas: Una visión general de Calude, Priese y Staiger (1997):
- Si $a_1, a_2, a_3, \dots$ es una creciente de enteros positivos tal que $\lim_{n \rightarrow \infty} (a_{n+1}/a_{n}) = 1$ para cualquier entero positivo $m$ y cualquier base entera $b ≥ 2$ existe alguna (y por tanto infinitas) $a_n$ cuya expresión en base $b$ comienza con la expresión de $m$ en base $b$ .
El resultado deseado se obtiene tomando $a_n$ ser el $n$ th prime $p_n$ señalando que el teorema del número primo implica $p_n \sim n \ln n$ y, por tanto, que $\lim_{n \rightarrow \infty} (p_{n+1}/p_{n}) = 1$ .
sewo
Puntos
58
Utiliza el teorema de los números primos para demostrar que existe un N tal que para cada M>N existe al menos un número primo que se escribe como 314159265358979323 seguido de otros M dígitos.
(Heurísticamente: Hay $10^M$ números posibles de esta forma, y la probabilidad de que cada uno de ellos sea primo es asintóticamente proporcional a 1/M -- por tanto la esperado número de primos en cada intervalo de este tipo crece hacia el infinito. Idear un argumento riguroso a partir de este esbozo y una de las versiones exactas del teorema de los números primos queda como ejercicio :-)
