Dado un número entero no negativo N
, genera el número entero impar impar más pequeño que es un pseudoprimo fuerte para todas las primeras N
bases primas.
Esta es la secuencia OEIS A014233 .
Casos de prueba (un índice)
1 2047
2 1373653
3 25326001
4 3215031751
5 2152302898747
6 3474749660383
7 341550071728321
8 341550071728321
9 3825123056546413051
10 3825123056546413051
11 3825123056546413051
12 318665857834031151167461
13 3317044064679887385961981
Los casos de prueba para N > 13
no están disponibles porque esos valores aún no se han encontrado. Si logra encontrar los siguientes términos en la secuencia, ¡asegúrese de enviarlos a OEIS!
Reglas
- Puede optar por tomar
N
un valor indexado a cero o uno indexado. - Es aceptable que su solución solo funcione para los valores representables dentro del rango de enteros de su idioma (hasta los
N = 12
enteros de 64 bits sin signo), pero su solución debe funcionar teóricamente para cualquier entrada con la suposición de que su idioma admite enteros de longitud arbitraria.
Antecedentes
Cualquier entero par positivo x
puede escribirse en la forma x = d*2^s
donde d
sea impar. d
y s
se puede calcular dividiendo repetidamente entre n
2 hasta que el cociente ya no sea divisible entre 2. d
es ese cociente final y s
es el número de veces que 2 se divide n
.
Si un número entero positivo n
es primo, entonces el pequeño teorema de Fermat dice:
En cualquier campo finito Z/pZ
(donde p
es primo), las únicas raíces cuadradas de 1
son 1
y -1
(o, equivalentemente, 1
y p-1
).
Podemos usar estos tres hechos para demostrar que una de las siguientes dos afirmaciones debe ser verdadera para un primo n
(donde d*2^s = n-1
y r
es algún número entero [0, s)
):
La prueba de primalidad de Miller-Rabin funciona probando el contrapositivo de la afirmación anterior: si existe una base a
tal que ambas condiciones anteriores son falsas, entonces n
no es primo. Esa base a
se llama testigo .
Ahora, probar cada base [1, n)
sería prohibitivamente costoso en tiempo de cálculo para grandes n
. Existe una variante probabilística de la prueba de Miller-Rabin que solo prueba algunas bases elegidas al azar en el campo finito. Sin embargo, se descubrió que probar solo las a
bases primarias es suficiente y, por lo tanto, la prueba se puede realizar de manera eficiente y determinista. De hecho, no todas las bases primas necesitan ser probadas, solo se requiere un cierto número, y ese número depende del tamaño del valor que se está probando para la primalidad.
Si se prueba un número insuficiente de bases primas, la prueba puede producir falsos positivos, enteros compuestos impares donde la prueba no puede demostrar su composición. Específicamente, si una base a
no puede demostrar la composición de un número compuesto impar, ese número se llama un pseudoprimo fuerte a la base a
. Este desafío consiste en encontrar los números compuestos impares que son fuertes psuedoprimos para todas las bases menores o iguales que el N
número primo th (lo que equivale a decir que son pseudoprimos fuertes para todas las bases primas menores o iguales que el N
número primo th) .
Respuestas:
C,
349295277267255 bytesToma una entrada basada en 1 en stdin, por ejemplo:
Ciertamente no va a descubrir nuevos valores en la secuencia en el corto plazo, pero hace el trabajo. ACTUALIZACIÓN: ¡ahora incluso más lento!
a^(d*2^r) == (a^d)^(2^r)
)__int128
, que es más corto queunsigned long long
mientras trabaja con números más grandes! También en máquinas little endian, el printf con%llu
todavía funciona bien.Menos minificado
(Anticuado) Desglose
Como se mencionó, esto utiliza una entrada basada en 1.
Pero para n = 0 produce 9, que sigue la secuencia relacionada https://oeis.org/A006945 .Ya no; ahora se cuelga en 0.Debería funcionar para todos los n (al menos hasta que la salida alcance 2 ^ 64) pero es increíblemente lento. Lo he verificado en n = 0, n = 1 y (después de mucha espera), n = 2.
fuente
Python 2,
633465435292282275256247 bytes0 indexado
La conversión de una función a un programa ahorra algunos bytes de alguna manera ...
Si Python 2 me da una forma más corta de hacer lo mismo, voy a usar Python 2. La división es un entero por defecto, por lo que es una forma más fácil de dividir por 2 y
print
no necesita paréntesis.Pruébalo en línea!
Python es notoriamente lento en comparación con otros lenguajes.
Define una prueba de división de prueba para la corrección absoluta, luego aplica repetidamente la prueba de Miller-Rabin hasta que se encuentra una pseudoprima.
Pruébalo en línea!
EDITAR : finalmente golfed la respuesta
EDITAR : Utilizado
min
para la prueba de primalidad de división de prueba y lo cambió a alambda
. Menos eficiente, pero más corto. Tampoco pude evitarlo y usé un par de operadores bit a bit (sin diferencia de longitud). En teoría debería funcionar (ligeramente) más rápido.EDITAR : Gracias @Dave. Mi editor me trolleó. Pensé que estaba usando pestañas, pero se estaba convirtiendo en 4 espacios. También revisé casi todos los consejos de Python y lo apliqué.
EDITAR : Cambiado a indexación 0, me permite guardar un par de bytes con la generación de los números primos. También repensé un par de comparaciones
EDITAR : se utiliza una variable para almacenar el resultado de las pruebas en lugar de las
for/else
declaraciones.EDITAR : movió el
lambda
interior de la función para eliminar la necesidad de un parámetro.EDITAR : convertido a un programa para guardar bytes
EDITAR : ¡Python 2 me ahorra bytes! Además, no tengo que convertir la entrada a
int
fuente
a^(d*2^r) mod n
!Perl + Math :: Prime :: Util, 81 + 27 = 108 bytes
Corre con
-lpMMath::Prime::Util=:all
(penalización de 27 bytes, ¡ay!).Explicación
No es solo Mathematica el que tiene una función integrada para prácticamente cualquier cosa. Perl tiene CPAN, uno de los primeros repositorios de bibliotecas grandes, y que tiene una gran colección de soluciones listas para tareas como esta. Desafortunadamente, no se importan (ni siquiera se instalan) de forma predeterminada, lo que significa que, básicamente, nunca es una buena opción usarlos en el código de golf , pero cuando uno de ellos encaja perfectamente con el problema ...
Recorremos números enteros consecutivos hasta encontrar uno que no sea primo y, sin embargo, un pseudoprimo fuerte para todas las bases enteras, desde 2 hasta n º primo. La opción de línea de comandos importa la biblioteca que contiene el builtin en cuestión, y también establece la entrada implícita (line-at-a-time;
Math::Prime::Util
tiene su propia biblioteca bignum incorporada que no le gustan las nuevas líneas en sus enteros). Esto utiliza el truco estándar de Perl de usar$\
(separador de línea de salida) como una variable para reducir los análisis incómodos y permitir que la salida se genere implícitamente.Tenga en cuenta que tenemos que usar
is_provable_prime
aquí para solicitar una prueba principal determinista, en lugar de probabilística. (Especialmente dado que una prueba de prueba probabilística probablemente esté usando Miller-Rabin en primer lugar, ¡lo cual no podemos esperar para dar resultados confiables en este caso!)Perl + Math :: Prime :: Util, 71 + 17 = 88 bytes, en colaboración con @Dada
Corre con
-lpMntheory=:all
(17 bytes de penalización).Esto usa algunos trucos de golf de Perl que tampoco conocía (¡aparentemente Math :: Prime :: Util tiene una abreviatura!), Sabía pero no pensé en usar (
}{
para generar$\
implícitamente una vez, en lugar de"$_$\"
implícitamente cada línea) , o lo sabía, pero de alguna manera logró aplicar mal (eliminando paréntesis de las llamadas a funciones). Gracias a @Dada por señalarme esto. Aparte de eso, es idéntico.fuente
ntheory
lugar deMath::Prime::Util
. Además, en}{
lugar de;$_=""
debería estar bien. Y puede omitir el espacio después1
y el paréntesis de algunas llamadas a funciones. Además,&
funciona en lugar de&&
. Eso debería dar 88 bytes:perl -Mntheory=:all -lpe '1until!is_provable_prime(++$\)&is_strong_pseudoprime$\,2..nth_prime$_}{'
}{
. (Curiosamente, recordé el paréntesis, pero ha pasado un tiempo desde que jugué al golf en Perl y no podía recordar las reglas para dejarlo fuera). Sin embargo, no sabía nada de lantheory
abreviatura.