¿Cómo se pueden generar eficientemente n números enteros pequeños relativamente primos?

Question

La definición de pequeño es que tienen bits O(lg n). Una forma es simplemente probar los números enteros 2,3,... para la primalidad y mantener los primeros n primos, pero esto toma por lo menos O(n log n) tiempo (multiplicado por el costo de la prueba de primalidad) usando un algoritmo ingenuo. ¿Es posible hacerlo en tiempo lineal?

Answer 1

Mira el capítulo 1 del libro de Paul Pollack " No siempre enterrado profundamente ". Enumera varias pruebas elementales de la infinidad de primos, algunas de las cuales pueden ser adaptadas para formar simples algoritmos iterativos.

(Lo siento, no puedo hacer que el látex funcione aquí. ¿No es como MathOverflow? De todas formas )

Sea S = {p1...pk} el conjunto de números enteros de coprimo generados previamente.

Y toma M = producto de números enteros en S

Ahora haz cualquiera de las siguientes cosas para conseguir un nuevo coprimo entero en el set S.

1. (Euclides) : M + 1
2. (Stieltjes) : Factor M como A.B de alguna manera, y toma A + B
3. (Euler) Totient(M)
4. (Braun y Metrod) : N = M/p1 + ... + M/p_k
5. (Goldbach) : N = 2 + M

También hay una prueba de Saidak del mismo libro:

• Toma N1=n; N2 = N1(N1+1); N3 = N2(N2+1)... Nk=Nk(Nk+1) y así sucesivamente. Esta es una secuencia primaria relativa.

Probablemente me faltan un par de pruebas más. De todos modos, ¡revisa el libro!

EDIT1 : **Voy a mantener la respuesta a pesar de los votos negativos, con la esperanza de que pueda incitar a alguien más a inventar un algoritmo mejor! *

Answer 2

Puedes encontrar el primer n primos en el tiempo $n \log n/ \log\log n$ con el tamiz de Atkin-Bernstein. Esto es mejor que tu ingenuo $n \log ^5n$ o un algoritmo así (o reducir el exponente en 1 usando pruebas preliminares con M-R), pero aún así es superlinear.

Answer 3

Mira esto. Generando todos los pares de co-prime ".

El método afirma ser completo y no se repite. Cada resultado genera TRES nuevos hijos; sólo detenga la generación si alguno de los miembros del par (m, n) excede su definición de "pequeño".

Como esta es una generación declarativa, eso cumple con tu criterio de "tiempo lineal", ¿verdad?

Para mis ojos (no matemáticos), esta relación se parece mucho a la generación de triples pitagóricos.

Answer 4

Asumo que S no tiene que ser primo (sólo relativamente primo)

Para S= {2, 15}

Método de Goldbach : N = 2 + M

                = 2 + 30

                = 32 (not relatively prime with 2)