Nos gustaría que factorizar un semiprimo . El objetivo de este reto es encontrar dos enteros pequeños y tal que puede ser trivialmente factorized con el método de Fermat, lo que permite deducir fácilmente los factores de .u v u v N N
La tarea
Dado un semiprime y un entero positivo , definimos e como:k x y
y=x2-kN
Paso # 1 - Encuentra
Primero debe encontrar el valor más pequeño posible de modo que sea un número cuadrado ( también conocido como cuadrado perfecto).y
Esto permite factorizar con una sola iteración del método de factorización de Fermat . Más concretamente, esto lleva inmediatamente a:
(Actualización: esta secuencia ahora se publica como A316780 )
Paso # 2 - Factoriza
Luego debe encontrar los dos enteros positivos y manera que:v
c u = x + √
donde y son los factores primos de .d N
Resumen
Su tarea es escribir un programa o función que tome como entrada e imprima o salga y en cualquier orden y en cualquier formato razonable.u v
Ejemplo
Consideremos
Paso 1
El valor más pequeño posible de es , lo que da:40
y=28232-40×199163=7969329-7966520=2809=532kN=(2823+53)×(2823-53)kN=2876×2770
Paso 2
La factorización correcta de es , porque:k = 4 × 10
k N = ( 719 × 4 ) × ( 277 × 10 ) N = 719 × 277
Reglas
- La entrada está garantizada como semiprime.
- Este es el código de golf, por lo que gana la respuesta más corta en bytes.
- Las lagunas estándar están prohibidas.
Casos de prueba
N | k | Output
-----------+------+------------
143 | 1 | [ 1, 1 ]
2519 | 19 | [ 1, 19 ]
199163 | 40 | [ 4, 10 ]
660713 | 1 | [ 1, 1 ]
4690243 | 45 | [ 9, 5 ]
11755703 | 80 | [ 40, 2 ]
35021027 | 287 | [ 7, 41 ]
75450611 | 429 | [ 143, 3 ]
806373439 | 176 | [ 8, 22 ]
1355814601 | 561 | [ 17, 33 ]
3626291857 | 77 | [ 7, 11 ]
6149223463 | 255 | [ 17, 15 ]
6330897721 | 3256 | [ 74, 44 ]
Implementación de ejemplo
fuente
N
será de hecho un semiprime?Respuestas:
Mathematica,
8179 bytes¡Gracias a Martin Ender por guardar 2 bytes!
Función pura que toma un semiprime como entrada y devuelve un par ordenado de enteros positivos. El
For
bucle implementa el procedimiento exacto descrito en la pregunta (usando#
para la entrada en lugar den
),x
tal como se define allí, aunque almacenamos enj = k*n
lugar dek
sí mismo y enz=Sqrt[y]
lugar dey
sí mismo. También calculamosp={x+z,x-z}
dentro delFor
ciclo, que termina guardando un byte (como en el séptimo intento). Entonces los dos factores deseados son(x+z)/GCD[#,x+z]
y(x-z)/GCD[#,x-z]
, que la expresión concisap/#~GCD~p
calcula directamente como un par ordenado.Curiosidades: queremos hacer un bucle hasta que
z
sea un número entero; pero como lo vamos a usarCeiling
en el código, guarda dos bytes!IntegerQ@z
para definirc=Ceiling
(lo que cuesta cuatro bytes, como saben los golfistas de Mathematica) y luego prueba sic@z>z
. Tenemos que inicializarz
a algo, y es mejor que algo no sea un número entero para que el ciclo pueda comenzar; Afortunadamente,E
es una elección concisa.fuente
JavaScript (ES7),
8681 bytesEditar: Guardado 4 bytes gracias a @Arnauld.
fuente
Python 2,
12712111711110710410199 bytes-1 byte gracias a Neil y -3 bytes gracias a ovs
Pruébalo en línea!
Curiosidades:
p
se inicializa para.5
que la condición del bucle sea verdadera en la primera iteración. Tenga en cuenta que es más corto almacenarp
(comox
+sqrt(y)
) que almacenar cada uno de ellosx
y pory
separado.fuente
x*x
en lugar dex**2
?Axioma,
131115bytesLa función que resolvería la pregunta es r (n) arriba. ungolf y prueba
fuente