Enlaces relevantes aquí y aquí , pero aquí está la versión corta:
Tiene una entrada de dos enteros a
y b
entre infinito negativo e infinito (aunque si es necesario, puedo restringir el rango, pero la función aún debe aceptar entradas negativas).
Definición del símbolo de Kronecker
Debe devolver el símbolo de Kronecker (a|b)
para las entradas a
y b
dónde
(a|b) = (a|p_1)^e_1 * (a|p_2)^e_2 * ... * (a|p_n)^e_n
donde b = p_1^e_1 * p_2^e_2 * ... * p_n^e_n
, y p_i
y e_i
son los primos y exponentes en la factorización prima de b
.
Para una prima impar p
, (a|p)=a^((p-1)/2) (mod p)
como se define aquí .
para b == 2
,(n|2)={0 for n even; 1 for n odd, n=+/-1 (mod 8); -1 for n odd, n=+/-3 (mod 8)
para b == -1
,(n|-1)={-1 for n<0; 1 for n>0
Si a >= b
, (a|b) == (z|b)
donde z == a % b
. Por esta propiedad, y como se explica aquí y aquí , a
es un residuo cuadrático de b
if z
is, aunque a >= b
.
(-1|b)
= 1
si b == 0,1,2 (mod 4)
y -1
si b == 3 (mod 4)
. (0|b)
es 0
a excepción de (0|1)
lo que es 1
, porque (a|1)
está siempre 1
y para el negativo a
, (-a|b) == (-1|b) * (a|b)
.
La salida del símbolo de Kronecker es siempre -1, 0 or 1
, donde la salida es 0
si a
y b
tiene factores comunes. Si b
es un primo impar, (a|b) == 1
si a
es un mod de residuo cuadráticob
, y -1
si lo es, no es un residuo cuadrático.
Reglas
Su código debe ser un programa o una función.
Las entradas deben estar en el orden
a b
.La salida debe ser
-1
,0
o1
.Este es el código de golf, por lo que su código no tiene que ser eficiente, solo corto.
No hay elementos integrados que calculen directamente el Kronecker o los símbolos relacionados de Jacobi y Legendre. Otros elementos integrados (para la factorización prima, por ejemplo) son juegos justos.
Ejemplos
>>> kronecker(1, 5)
1
>>> kronecker(3, 8)
-1
>>> kronecker(15, 22)
1
>>> kronecker(21, 7)
0
>>> kronecker(5, 31)
1
>>> kronecker(31, 5)
1
>>> kronecker(7, 19)
1
>>> kronecker(19, 7)
-1
>>> kronecker(323, 455625)
1
>>> kronecker(0, 12)
0
>>> kronecker(0, 1)
1
>>> kronecker(12, 0)
0
>>> kronecker(1, 0)
1
>>> kronecker(-1, 5)
1
>>> kronecker(1, -5)
1
>>> kronecker(-1, -5)
-1
>>> kronecker(6, 7)
-1
>>> kronecker(-1, -7)
1
>>> kronecker(-6, -7)
-1
Esta es una función complicada, así que avíseme si algo no está claro.
fuente
Respuestas:
CJam (70 bytes)
Demostración en línea (casos de prueba generados con Mathematica).
Disección
Encontré varias formas de evaluar
(a|2)
el mismo recuento de caracteres, y he elegido usar el que tenga la presentación más clara.integer array <W=
IMO es una forma bastante elegante de hacer retrocesos: si el entero es mayor que la longitud de la matriz, seleccionamos el último elemento.Otros comentarios
Es decepcionante que, por extraño que sea,
p
el estilo directo de Fermat(a|p)
sea tan corto, porque hay una forma muy golfística de encontrar(a|n)
un extraño positivon
que quería usar. La base es el lema de Zolotarev:Esto fue fortalecido por Frobenius para
y por Lerch a
Ver Brunyate y Clark, Extendiendo el enfoque de Zolotarev-Frobenius a la reciprocidad cuadrática , The Ramanujan Journal 37.1 (2014): 25-50 para referencias.
Y puede fortalecerse fácilmente un paso más (aunque no he visto esto en la literatura) para
Prueba: si
a
es coprime,b
entonces usamos Zolotarev-Frobenius-Lerch; de lo contrario, el mapa no es una permutación, y el símbolo de Levi-Civita es el0
deseado.Esto da el cálculo del símbolo de Jacobi
Pero el tratamiento especial requerido
(a|-1)
y(a|2)
significa que no he encontrado una manera de calcular el símbolo de Kronecker que es más corto con este enfoque: es más corto factorizar y tratar los números primos individualmente.fuente
Python 3,
747369335 bytesComo respuesta de ejemplo, solo un poco de golf, y para darle una idea de cómo se verá una respuesta.
Y sí, los factores primos de factorización y codificación de longitud de ejecución se cifran desde Pyth con disculpas a isaacg .
fuente
Mathematica,
169175165 bytesfuente
LabVIEW, 44 Bytes Primitivas de LabVIEW
Como es simétrico, cambié las entradas si a era mayor que b.Representa la fórmula real ahora
contando como siempre según
para el caso verdadero
fuente
(a|b) != (b|a)
en todos los casos. En la mayoría de los casos, sí, pero no en todos. Aunque funcionaría si los redujes ena mod b
lugar de intercambiarlos.Julia, 195 bytes
Esta es una función recursiva
k
que acepta dos enteros y devuelve un entero.Sin golf:
fuente
Haskell, 286 bytes
Probablemente no esté completamente optimizado, pero es un esfuerzo valiente. El símbolo de Kronecker se define como la función infija a # b, es decir
fuente