Calcule el símbolo de Kronecker

9

Enlaces relevantes aquí y aquí , pero aquí está la versión corta:

Tiene una entrada de dos enteros ay bentre 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 ay bdó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_iy e_ison 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í , aes un residuo cuadrático de bif zis, aunque a >= b.

(-1|b)= 1si b == 0,1,2 (mod 4)y -1si b == 3 (mod 4). (0|b)es 0a excepción de (0|1)lo que es 1, porque (a|1)está siempre 1y 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 0si ay btiene factores comunes. Si bes un primo impar, (a|b) == 1si aes un mod de residuo cuadráticob , y -1si 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, 0o 1.

  • 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.

Sherlock9
fuente
¿Estás seguro de que no quieres rechazar las incorporaciones? reference.wolfram.com/language/ref/KroneckerSymbol.html
Martin Ender
@ MartinBüttner Estaba editando ejemplos cuando vi tu comentario. No permitiré las incorporaciones que calculen directamente los símbolos de Kronecker, Jacobi o Legendre, pero cualquier otra cosa (incluidas las funciones de factorización principal) debería ser un juego justo.
Sherlock9
No estoy completamente seguro de por qué (31 | 5) da 1. No debería haber un residuo qudratico, entonces ¿por qué no es -1?
Eumel
también el 19/7 debería ser 1 y el 19/7 debería ser -1 según el wiki que vinculó
Eumel
3
Si las soluciones tienen que manejar correctamente las entradas negativas y cero, definitivamente debe agregar algunos casos de prueba para eso.
Martin Ender

Respuestas:

2

CJam (70 bytes)

{_g\zmf+f{:P2+"W>2*(
z1=
;1
7&4-z[0W0X0]=
P%P+P(2/#P%_1>P*-"N/<W=~}:*}

Demostración en línea (casos de prueba generados con Mathematica).

Disección

{               e# Anonymous function. Stack: a b
  _g\zmf+       e# Factorise b, with special treatment for negatives
                e# CJam also gives special treatment to 0 and 1
                e# Stack: e.g. a [-1 2 2 5]; or a [-1 1]; or a [0 0]; or a [1 2 2 5]
  f{            e# For each "prime" factor P, find (a|P)
    :P2+        e# Extract code for P from an array formed by splitting a string
    "W>2*(      e#   a -> (a|-1)
z1=             e#   a -> (a|0)
;1              e#   a -> (a|1)
7&4-z[0W0X0]=   e#   a -> (a|2)
P%P+P(2/#P%_1>P*-" e# a -> (a|P) for odd prime P
    N/<W=~      e# Split string and select appropriate element
  }
  :*            e# Multiply the components together
}

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, pel estilo directo de Fermat (a|p)sea ​​tan corto, porque hay una forma muy golfística de encontrar (a|n)un extraño positivo nque quería usar. La base es el lema de Zolotarev:

Si pes un primo impar y aes un coprimo entero para pentonces, el símbolo de Legendre (a|p)es el signo de la permutaciónx -> ax (mod p)

Esto fue fortalecido por Frobenius para

Si ay bson enteros impares positivos coprimos, entonces el símbolo de Jacobi (a|b)es el signo de la permutaciónx -> ax (mod b)

y por Lerch a

Si bes un entero impar positivo y aes un coprimo entero para bentonces, el símbolo de Jacobi (a|b)es el signo de la permutaciónx -> ax (mod b)

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

Si bes un entero impar positivo y aes un entero, entonces el símbolo de Jacobi (a|b)es el símbolo de Levi-Civita del mapa x -> ax (mod b).

Prueba: si aes coprime, bentonces usamos Zolotarev-Frobenius-Lerch; de lo contrario, el mapa no es una permutación, y el símbolo de Levi-Civita es el 0deseado.

Esto da el cálculo del símbolo de Jacobi

{_2m*{~>},@ff*\ff%::-:*g}

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.

Peter Taylor
fuente
4

Python 3, 747 369 335 bytes

Como 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 .

from itertools import*
def k(d,r):
 if d<0:a=-d;m=1
 else:a=d;m=0
 if r==1:return 1
 p=1;w=r;n=2;f=[]
 while n*n<=w:
  while w%n<1:w//=n;f+=n,
  n+=1
 if w>1:f+=w,
 z=[[k,len(list(g))]for k,g in groupby(f)]
 for i,j in z:
  if i==2:p*=pow(-1,(a*a-1)//8)
  x=pow(a,(i-1)//2,i)
  if x>1:x-=i
  p*=x**j
 if m:p*=pow(-1,(r-1)//2)
 return p
Sherlock9
fuente
44
Disculpa aceptada: me alegra que alguien lea el código fuente de Pyth.
isaacg
2

Mathematica, 169 175 165 bytes

(1|-1)~k~0=_~k~1=1
_~k~0=0
a_~k~-1=If[a<0,-1,1]
a_~k~2=DirichletCharacter[8,2,a]
a_~k~p_/;PrimeQ@p=Mod[a^((p-1)/2),p,-1]
a_~k~b_:=1##&@@(a~k~#^#2&@@@FactorInteger@b)
alephalpha
fuente
2

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

Eumel
fuente
Lamentablemente, (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 en a mod blugar de intercambiarlos.
Sherlock9
ya que tengo la explicación ahora puedo editarla, dame un minuto
Eumel
1
¿Hay alguna forma de probar esto? Realmente no entiendo cómo funciona LabView.
Sherlock9
Esa es una buena pregunta, puedo pensar en 2 formas. Primero puedo construir un .exe y enviártelo, luego puedes obtener una versión de prueba de Labview y puedo enviarte el vi o puedes reconstruirlo a partir de la imagen.
Eumel
77
Esto no es 44 bytes. Si define un sistema de puntuación que no se basa en el tamaño del archivo, debe llamarlo de otra manera que no sean bytes.
feersum
1

Julia, 195 bytes

k(a,b)=b==0?a∈[1,-1]?1:0:b==1?1:b==2?iseven(a)?0:a%8∈[1,-1]?1:-1:b==-1?a<1?-1:1:isprime(b)&&b>2?a%b==0?0:a∈[i^2%b for i=0:b-1]?1:-1:k(a,sign(b))*prod(i->k(a,i)^factor(b)[i],keys(factor(b)))

Esta es una función recursiva kque acepta dos enteros y devuelve un entero.

Sin golf:

function k(a::Integer, b::Integer)
    if b == 0
        return a  [1, -1] ? 1 : 0
    elseif b == 1
        return 1
    elseif b == 2
        return iseven(a) ? 0 : a % 8  [1, -1] ? 1 : -1
    elseif b == -1
        return a < 1 ? -1 : 1
    elseif isprime(b) && b > 2
        return a % b == 0 ? 0 : a  [i^2 % b for i = 1:b-1] ? 1 : -1
    else
        p = factor(b)
        return k(a, sign(b)) * prod(i -> k(a, i)^p[i], keys(p))
    end
end
Alex A.
fuente
1

Haskell, 286 bytes

a#0|abs a==1=1|1<2=0
a#1=1
a#2|even a=0|mod a 8`elem`[1,7]=1|1<2=(-1)
a#b|b<0=a`div`abs a*a#(-b)|all((/=0).mod b)[2..b-1]=if elem n[0,1] then n else(-1)|1<2=product$map(a#)$f b where n=a^(div(b-1)2)`mod`b
f 1=[]
f n|n<0=(-1):f(-n)|1<2=let p=head$filter((==0).mod n)[2..n]in p:f(div n p)

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

*Main>323#455265 
1
killmous
fuente