Si tienes un primo, y una afirmación de que es el enésimo primo, ¿hay una forma rápida de comprobarlo?

Question

Sé que hay formas rápidas de descartarlo para casos especiales, pero suponiendo que sea realmente cierto, ¿con qué rapidez se puede verificar?

También me pregunto sobre las secuencias de las que los primos son un subconjunto, como las OEIS A050376 y A000961, si verificar un índice es más fácil en ellas.

Answer 1

Supongo que tu pregunta es que sabes que el número dado es primo y sólo quieres saber si es el $n$ -a primo o no. Aquí hay una aproximación.

Como punto de partida se pueden utilizar límites explícitos en el $n$ -a primo como el de Dusart

$$ n\log n + n\log\log n - n < p_n < n\log n + n\log\log n $$

que es válida para $n \ge 6$ o utilizar nuevos y recientes límites más estrechos de Christian Axler . Esto reducirá su rango de búsqueda a menos de $n$ enteros que luego pueden ser manejados por una búsqueda informática de fuerza bruta.