4 votos

¿Tamiz de Eratosthenes-como - infinitamente muchos unstruck?

Dado cualquier secuencia infinita $c_1,c_2...$ de los números naturales, si todos los números naturales $x$ tal de que no existe $n$ tal que $x\equiv c_n (\mod p_n)$ $x \geq 2p$ donde $p_n$ es el enésimo número primo, son eliminados de la lista, debe haber un número infinito de números naturales a la izquierda en la lista de después?

por ejemplo, $c_i=1 \ \forall i\\ 1,2,3,4,\not5,6,\not7,8,\not9,\not10,\not11,12,\not13,14,\not15,\not16,\not17,18,\not19,20...$

Hasta ahora lo único que sé sobre el caso trivial donde $c_i=0$, y que puede haber perdido obvio contraejemplos.

2voto

Peter Taylor Puntos 5221

Sí, hay una infinidad de números naturales a la izquierda después.

Cuando la realización de Eratóstenes' sin modificar el cribado de la operación, la huelga de los múltiplos de $2$ elimina $\frac12$ de los valores mayor que $2$; la huelga de los múltiplos de $3$ elimina $\frac13 (1 - \frac12) = \frac16$ de los valores mayor que $3$; la huelga de los múltiplos de $5$ elimina $\frac15 (1 - \frac12 - \frac16) = \frac1{15}$ de los valores mayor que $5$; etc.

Con el desplazamiento del tamiz, los números ponchó son diferentes, pero las proporciones son exactamente los mismos. La razón es simple: cada número primo es (por definición) coprime con todos los números primos. Por lo tanto, no hay ninguna correlación entre los números que se ponchó antes de llegar a ese primer y el número de los que son golpeados por que el primer, y a pesar de que el valor de $c_i$ huelga de $\frac1{p_i}$ de los no producido números de $\ge 2p_i$.

Un poco más de rigor: desde la $p_i$ son distintos de los números primos, el MCM de un conjunto de ellos es simplemente su producto, y, en particular, $p_i$ es coprime con $\prod_{j<i} p_j$. A continuación, considere el equivalente clases de $\mathbb{Z} / \prod_{j\le i} p_j \mathbb{Z}$: el teorema del resto Chino nos da un natural bijection con el producto Cartesiano $(\mathbb{Z} / \prod_{j\lt i} p_j \mathbb{Z}) \times (\mathbb{Z} / p_i \mathbb{Z})$. A continuación, todos los elementos que comparten una proyección en $\mathbb{Z} / \prod_{j\lt i} p_j \mathbb{Z}$ compartir un estado actual (tachado o no); y cuando nos la huelga de los elementos en los que la proyección en $\mathbb{Z} / p_i \mathbb{Z}$ $c_i$ vamos a la huelga, precisamente, $\frac1{p_i}$ de aquellos que no fueron ponchó (y volver a la huelga de la misma, la proporción de los que ya se ponchó).

Por lo tanto, para cualquier secuencia $c_i$, y para cualquier entero positivo $C$, después de golpear con los valores correspondientes a las $j$th prime el número de no producido los números menores que $C \prod_{k\le j}p_k$ será al menos tan numerosos como para que la secuencia de $c_i = 0$ (y no exceda ese número por más de $j$, donde el exceso es debido a los números en $(p, 2p]$ no ser golpeado).

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X