Es esta propuesta de método de búsqueda de números primos válido? Si es así, sería eficaz?

Question

(Vea la pregunta hacia el final)

Supongamos que tomamos los cuatro primeros números primos consecutivos, $$2, 3, 5, 7$$ Ya que estos son números primos, máximo común divisor es 1. En otras palabras, ellos serán co-prime. Sabiendo esto, esto también significa que su mínimo común múltiplo será el producto de los números primos se multiplican. $2*3*5*7$ resultará en $210$.

$210$ obviamente no va a ser el primer como es divisible por $2, 3, 5,$ e $7$, pero esto debe significar $210$'s sólo son factores de $2, 3, 5,$ e $7$ debido a que cada número sólo tiene una factorización en primos que también es único (ignorar compuesto de factores, que no importa en mi método).

Siguiendo esta lógica, $23$, igual a la expresión $(2*3*5) - 7$, no puede ser divisible por $2, 3, 5,$ o $7$.

$23$'s no divisible por $7$ porque sabemos que el primer término de la expresión, $(2*3*5)$, no era un múltiplo de 7 (ya que no tienen 7 en su descomposición en factores primos), por lo que restando 7 de que no va a cambiar eso. También, desde la $7$ es co-prime con los otros tres primos, restando $7$ de $(2*3*5)$ hace $23$ no divisible por $2, 3,$ o $5$ así.

$23$ entonces no es divisible por $2, 3, 5,$ o $7$. Debido a cómo los factores de trabajo, para comprobar si cualquier entero positivo, c, es el primer, usted puede tomar la raíz cuadrada de c y encontrar los números primos por debajo de ese valor. Si no se prepara a menos que la raíz cuadrada de c divide uniformemente en c, c es primo.

Si aplicamos esto a $23$, obtenemos $\lfloor{\sqrt23}\rfloor = 4$. Hemos demostrado anteriormente $23$ no es divisible por los números primos hasta $7$, por lo que no es divisible por los números primos hasta $4$ bien. Por lo tanto, $23$ es primo.

La generalización de esta manera, podemos tomar los primeros n números primos consecutivos ( $p_1, p_2, p_3, ... , p_{n-1}, p_n$) y la organización de estos números primos en dos grupos, sin embargo, te gustaría. A continuación, tomar los productos de los números primos dentro de cada grupo. Pongamos nombre a la más grande del producto, una, y la más pequeña del producto, b.

Tomar la diferencia de $a - b$. Esta diferencia entre una y b siempre será primero las declaraciones: $$\sqrt{a - b} \leq p_n$$ and $${a - b} >1$$

es cierto en lo que a $p_n$ es el n-ésimo primo.

Por ejemplo, $227$ es un prime que me encontré con este método. Tomamos los 8 primeros números primos consecutivos, $$2, 3, 5, 7, 11, 13, 17, 19$$y dividir en cualquiera de los dos grupos que nos gustaría, en este caso:

1. $2, 5, 17, 19$

2. $3, 7, 11, 13$

De tomar los productos de cada grupo, se obtiene:

$2*5*17*19 = 3,230$

$3*7*11*13 = 3,003$

Tiene el mayor producto de ser una y la menor producto b. Después, tomar la diferencia de $a - b$ : $$3,230 - 3,003 = 227$$

$\lfloor{\sqrt227}\rfloor = 15$.

$15 < 19$ e $227 > 1$, lo $227$ es primo.

---

Mi Pregunta:

Es este método para encontrar los números primos válido? Si es así, sería eficaz para utilizar cuando se trata de encontrar grandes números primos?

(Esta pregunta realmente difícil de articular, y soy consciente de que probablemente yo no hice un buen trabajo. Modificaciones, sugerencias, y la aclaración es bienvenida!)

Answer 1

Sí, este método es válido (en particular, su razonamiento de que los números que te salen son los principales es correcto), pero no parece que vaya a ser particularmente eficaz.

Voy a asumir que la familiaridad con los grandes - y pequeños-O notación; si usted no está familiarizado con este, la Wikipedia es un buen recurso.

La cuestión clave que hace que este no es muy efectivo es el $\sqrt{a-b}\leq p_n$ condición. Esto significa que, si usted quiere encontrar un alojamiento que se trata de $X$, usted necesita saber todos los números primos menos de $\sqrt X$. Esto significa esencialmente que el juicio de división de trabajo fino (ya que esto es todo lo que necesita para la prueba de la división), como sería algo así como la Criba de Eratóstenes.

La otra cosa es que, como $n$ se agranda, la condición de que $\sqrt{a-b}\leq p_n$ se vuelve muy difícil de satisfacer. Considere que el producto $$P_x=p_1p_2\cdots p_n$$ de todos los números primos menos de un cierto número $x$. Es conocido que este producto es $e^{x(1+o(1))}$. Estás buscando un divisor $a$ de este producto para que $$0\leq a-\frac{P_x}{a}\leq x^2.$$ La solución para $a$, esto se convierte en $$0\leq a^2-P_x\leq ax^2\Leftrightarrow \sqrt{P_x}\leq a\leq \frac{x^2+\sqrt{x^2+4P_x}}{2}=\frac{x^2}2+\sqrt{P_x+\frac{x^2}4}.$$ El problema es que, como $x$ es grande, $P_x$ es mucho más grande de lo $x^2$, y así $$\sqrt{P_x+\frac{x^2}4}\leq \sqrt{P_x}+1.$$ Básicamente, esto significa que cualquier producto $a$ tiene que estar en un rango de alrededor de $\sqrt{P_x}$ de que el tamaño del $x^2$. Porque hay $2^n\ll P_x$ divisores de $P_x$, parece poco probable que muchos de ellos estarán tan cerca de $\sqrt{P_x}$, por lo que para muchos de los grandes números primos de esta técnica puede no dar números a todos.

Answer 2

El método propuesto trabaja para encontrar un primer estrictamente entre $p_n$ e $p_n^2$, siempre se puede encontrar la clasificación de los valores de $a,b$ tal que $1 < |a-b| < p_n^2$.

La idea es interesante, pero tan lejos como valor práctico, hay dos problemas principales . . .

1. Una búsqueda exhaustiva requeriría pruebas en el orden de $2^{n-1}$ potencial de pares $(a,b)$, por lo menos $n$ es pequeña, decir $n < 50$, tal búsqueda no sería viable.$\\[4pt]$
2. Que es peor, parece probable que para casi todos los $n > 9$ (posiblemente todos), no habrá clasificación de los valores de $a,b$ tal que $1 < |a-b| < p_n^2$. En particular, no existen valores de $a,b$ para $10\le n\le 20$.