Mental De Pruebas De Primalidad

Question

En una noche de trivia, la siguiente pregunta que se planteó: "¿Cuál es la menor de 5 dígitos prime?"

Equipos (de 4) recibieron cerca de un minuto para escribir su respuesta a la pregunta. Obviamente, la respuesta es googleable, así que no estoy preguntando cuál es la respuesta a la pregunta de la trivia es, sino más bien: ¿cómo podría un equipo de encontrar rápidamente la respuesta sin necesidad de conocimientos previos de la misma? Si quería intentar resolver la pregunta de la trivia de uno mismo, no de seguir leyendo, ya que voy a empezar a discutir la respuesta y descartar otros números de ahora.

---

Mis pensamientos hasta el momento:

1. Si usted sabe que su regla de cálculo, se espera que el primer densidad es cercana a $ln(10,000)$ o 10%. Así, un enfoque razonable sería centrarse en los números de 10,000 a través de 10,010. Realmente, lo que importa es que (supongo) de empezar a 10.000, el factor de la cantidad de números en una fila como usted puede, y, a continuación, invitado en el primer número que no compremos.
2. Podemos descartar un montón, con fácil pruebas de divisibilidad, dejando 10001, 10003, 10007, y 10009.
3. Suponiendo que uno de su gente, es rápido, con la división o conoce mejor las reglas de divisibilidad, 10003 también es eliminado debido a que tiene un pequeño divisor (7). Esto no requiere de una técnica especial.
4. Ahora estamos a la izquierda con 3 números que razonable pruebas de divisibilidad no manejar. Resulta 10,001 es compuesto, mientras que 10,007 y 10,009 ambos son primos. Pero el más pequeño factor de 10,001 es de 73, que es el 21 de prime. Si el equipo pudiera hacer los pasos de arriba y luego descartar 10,001 dividiendo por el primero de los 21 números primos (también suponiendo que se sabe de los primeros 21 de los números primos), que es de suponer que adivinar 10,007 lo que es el correcto (aunque no necesariamente confianza en su respuesta).
5. Pero, supongamos que el 21 divisiones no son posibles. Es allí una manera más rápida? Vamos a decir que sea una prueba de que rápidamente se determina que 10,001 es probable que el compuesto o una prueba que determina que 10,007 es probable que el primer es suficiente, ya que podría ser a algunos de los trabajo de la conjetura en este punto, pero los puntos de bonificación si podemos saber con certeza 10,001 es compuesto o saber con certeza 10,007 es primo, y puntos de bonificación extra si lo hacemos los dos!
6. Potencialmente hay enfoques que no se basan en el descarte de 10,001. Por ejemplo, yo tenía la idea de que, dado que 10,001, 10,007, y 10,009 son cada duro para dividir, tal vez, es bastante probable que 10,007 y 10,009 son dos números primos, y por lo tanto es más probable que 10,007 es una de las principales de 10,001 y supongo que de todos modos. Mientras 10,007 y 10,009 hacer llegar a dos primos, yo en realidad no creo que la afirmación se sostiene, y esto parece más a la suerte.

Answer 1

Para lo que vale, acabo de temporizado a mí mismo haciendo prueba de la división:

$10001=100^2+1$, por lo que sólo necesita comprobar los números primos que son de 1 mod 4

$10001=10010-9$, por lo que no $7$, $11$, $13$

$10001=10030-29$, por lo que no $17$ o $29$

$10001 = 9990+11$ no $37$

$41*61 = 2501 = 10001-7500$ no $41$ o $61$

$10600-10001 = 599$ no $53$

$10001 +219 = 10220 = 20*511 = 20*7*73$

Por lo $73$ es un factor!

Tiempo: 3 minutos 40 segundos. (No se incluyen volver a formatear las ecuaciones.) Yo podría haber sido capaz de obtener menos de 3 minutos cuando yo estaba haciendo matemáticas concursos de veinte años. Dudo que haya más de diez personas en el país que podría hacer la prueba de la división en menos de un minuto, excepto por suerte adivinando que prime a tratar. Sasha Schwartz fue de miedo rápido en mi día, tal vez él podría tener.

Como se puede ver, la parte de la forma en que hago la prueba de la división es que me he aprendido de memoria un montón de nonprimes cerca de múltiplos de 100: $7 \times 11 \times 13 = 1001$, $17 \times 59 = 1003$, $19 \times 53=1007$, $3 \times 23 \times 29 = 2001$, $31 \times 71 = 2201$, $3^3 \times 37=999$, $41 \times 61 = 2501$, $43 \times 7 = 301$. Que cubre todos los números primos hasta el 43, además de unos cuantos más. (Hmm, después de haber escrito esto, me siento como que debo memorizar un múltiplo de $47$, ya que ya tengo $53$, $59$, $61$, $71$ y $201 = 3 \times 67$. Tal vez voy a tratar de recordar $799=47 \times 17$.)

Esto me sugiere que algunas personas que están más obsesionados que me podría haber memorizado nonprimes cerca de múltiplos de 1000, y por lo tanto podría saber 10001 = 73*137 por el corazón.

Aparte de eso, sin embargo, creo que tienes que tener suerte para responder a este en un minuto.

Answer 2

Tal vez alguien tuvo la suerte de leer la Lista de números Primos y recordar (como yo) hay sólo dos conocidos "Generalizada de los números primos de Fermat base 10", así que 10001 no es primo. ¿Que cuentan?

P. S. también Se puede utilizar esta Un teorema sobre el primer divisores generalizada de los números de Fermat? para encontrar "sólo" necesidad de dividir 10001 por los números primos de la forma$8k+1$$k=1,\ldots,12$, y los que se $17,41,73,89,97$

Así que si la cuestión es "¿Cuál es el más pequeño de n dígitos prime?" para algunos relativamente pequeña n, usted podría descuidadamente omitt $10\ldots01$ de factoring, ahorrar un poco de tiempo, ya que la gente sin duda marcada por los "Generalizada de los números primos de Fermat base 10", o que al menos podría acelerar su factorización.

Lo siento, no puedo comentar.

Answer 3

Cuando usted está haciendo algo como esto, las ventajas de un cerebro de más de un equipo son mínimos. Es mejor admitir que y seleccionar el algoritmo que se puede llevar a cabo más rápido. La creatividad juega un papel mínimo en intuitivamente reconocer nada, pero el más pequeño de los números primos, y cualquiera de los "trucos" que casi seguramente corresponden a conocidos pruebas de primalidad y por lo tanto caen bajo el enfoque propuesto de todos modos.

Así que, mira esto como un problema computacional. Hay dos enfoques básicos para encontrar los números primos de cómputo. Usted puede probar solo números o puede encontrar todos los números primos en un intervalo usando una técnica llamada "tamizado".

La manera más rápida para que un equipo de prueba de un solo pequeño número de primalidad es el uso de Miller-Rabin pruebas con un potencial testigo conjunto que se conoce de antemano a ser determinista. Echa un vistazo a la wiki el artículo de Miller-Rabin de pruebas, si usted no está familiarizado con ella. sin embargo, de manera determinista de Miller-Rabin pruebas de un 10000ish número requeriría un par de docenas de modular multiplicaciones con una base de la cantidad que está siendo probado. Esto no es muy práctico para una persona a hacer en un minuto ni un solo número. Otros determinista único número de métodos de ensayo son al menos comparables a lo complejo, por lo que este enfoque es, probablemente, no va a funcionar.

Para un pequeño intervalo, un equipo que sería probable que el uso de una combinación de cribado y las pruebas de primalidad. Realmente no hay mucho más disponible. Desde las pruebas de primalidad, usted sólo tiene tamizado.

De forma determinista el tamiz de un intervalo, el "tamiz" de los composites. Hay un pequeño incremento del costo de aumentar el tamaño del intervalo, entonces usted probablemente querrá ir con algo como [10000,10030] para asegurarse de que usted no pierda su primo.

El más eficiente de tamiz para pequeños intervalos es la Criba de Eratóstenes (el Tamiz de Atkin es más eficiente para grandes intervalos, pero los intervalos deben ser grande). La Criba de Eratóstenes, básicamente, requiere para tachar los múltiplos de los números primos menos de $\sqrt{1030}$, por lo que usted está interesado en los números primos menores que 100. Esto es porque cada número compuesto en el intervalo de prueba tiene un factor primo de menos de 100.

El truco es llevar esto a cabo rápidamente. Para ello, reducir 10000 modulo de cada primer, y el uso de esta reducción de encontrar a la próxima múltiples. Posterior múltiplos seguir fácilmente mediante la adición de la cantidad a la de su primera múltiples.

Como he explicado antes, yo realmente no creo que nada más rápido disponible. Si lo fuera, sería utilizado en los algoritmos de computadora, en lugar de los métodos mencionados. Así que, haciendo esto en un minuto sería duro, pero una rápida equipo de varias personas, probablemente, podría tirar de él si se inicia en este algoritmo de inmediato. Tenga en cuenta que el 25 números primos menores que 100 (23 otro de los casos simples de 2 y 5) permitir la fácil paralelization de este algoritmo, y es razonable hacer esto con cada persona que se toma sólo 5-6 números primos.

Voy a dar el caso, de 29 de como un ejemplo. Tenga en cuenta que el sistema modular de reducciones se podría hacer de forma rápida en cada caso por la reducción de 100 y, a continuación, ajustarlo. Así,

$$100 = 13 \;\text{mod}\; 29; \;\;\; 10000 = 13^2 \;\text{mod}\; 29 = 169 \;\text{mod}\; 29 = 24 \;\text{mod}\; 29$$

Que es realmente muy rápido, y ciertamente beats dividiendo nada muy grande por 29. 23 de estas operaciones realmente son bastante razonables. Simplemente añadir -24 mod 29 a 10000 para obtener el primer múltiplo de 29. Que es 10005. La próxima está fuera de rango. Para marcar 10005, o simplemente pasar a la siguiente el primer reconociendo que este número ya estaba marcado 5 cuando fue procesado y sus múltiplos fueron marcadas.

Después de 25 (23 no trivial) dichas operaciones, tendría todos los números primos en el intervalo. Nada significativamente más rápido que este, probablemente requieran fundamentalmente de nuevos conocimientos en el área de primer computación.

Por último, me sugirió un amplio intervalo, que en realidad no contiene los números primos más allá de un intervalo de 10 o así. Eso es porque estoy asumiendo ningún conocimiento especial de prime distribución en el intervalo en cuestión, y un intervalo más amplio es en general mejor para este tipo de cosas, ya que tiene muy poco costo adicional y a veces sería necesario para evitar el fracaso.

EDIT: en cuanto a mi comentario sobre los cerebros que poco tienen ventajas sobre los equipos en los que este tipo de cosas, me explico. Cerebros puede soplar las computadoras fuera del agua, en muchas circunstancias. Por ejemplo, un equipo que lleva tanto tiempo para encontrar una prueba de que nunca va a suceder sin la guía en todos, pero el más sencillo de los casos, mientras que un cerebro puede encontrar increíbles y complejas pruebas. Sin embargo, este problema es inherentemente computacional. Han sido muchos años-hombre de la puesta de investigación en lo que se puede hacer para identificar números primos. El cerebro funciona para este tipo de cosas realmente ha sido elaborado. Usted puede ser la próxima brillante persona que hace un avance, pero no lo hará en un minuto. Así, se basan en el trabajo intelectual que ya se ha hecho, y seleccionar el mejor algoritmo que se ha encontrado.

Con respecto a la diferencia de coste en las operaciones entre un cerebro y un ordenador, que se considera. He presentado el algoritmo más simple basado en la relación tiempo de cálculo de las operaciones de un cerebro. A lo que me refería no era a hacer lo que un programa de ordenador (que posiblemente sería simplemente hacer de Miller-Rabin pruebas sobre todo en el rango de evitar las asignaciones de memoria y/o caché de instrucciones se pierde). Me refería a tratar su cerebro como una computadora, seleccionar el algoritmo más rápido que pudo llevarse a cabo debido a la relativa de los costes de las operaciones para el cerebro. Así, por ejemplo, el proceso que dio puede ser mejorado para el caso de 3 reconociendo que cualquier potencia de 10 es 1 mod 3, y así 1002 es el primer múltiplo de la misma. También se podría reconocer que el 97*103 es de bajo rango, mientras que la de 97*105 está sobre el rango y no molestar con 97. Pero el algoritmo como me lo dio no puede ser drásticamente más rápido, teniendo en cuenta lo que los cerebros de hacer de la mejor manera, sin conocimiento nuevo sobre el primer cálculos.