11
\$\begingroup\$

Relevant links here and here, but here is the short version:

You have an input of two integers \$a\$ and \$b\$ between negative infinity and infinity (though if necessary, I can restrict the range, but the function must still accept negative inputs).

Definition of the Kronecker symbol

You must return the Kronecker symbol \$(a|b)\$ for inputs \$a\$ and \$b\$ where

$$(a|b) = (a|p_1)^{e_1} \cdot (a|p_2)^{e_2} \cdots (a|p_n)^{e_n}$$

where \$b = p_1^{e_1} \cdot p_2^{e_2} \cdots p_n^{e_n}\$, and \$p_i\$ and \$e_i\$ are the primes and exponents in the prime factorization of \$b\$.

  • For an odd prime \$p\$, \$(a|p)=a^{\frac{p-1}2} \mod p\$ as defined here.

  • For \$b = 2\$,

$$ (n|2) = \begin{cases} 0 & \text{if } n \equiv 0 \mod 2 \\ 1 & \text{if } n \equiv \pm 1 \mod 8 \\ -1 & \text{if } n \equiv \mp 3 \mod 8 \end{cases} $$

  • For \$b = -1\$,

$$ (n|-1) = \begin{cases} -1 & \text{if } n < 0 \\ 1 & \text{if } n \ge 0 \end{cases} $$

  • If \$a \ge b\$, \$(a|b) = (z|b)\$ where \$z = a\mod b\$. By this property, and as explained here and here, \$a\$ is a quadratic residue of \$b\$ if \$z\$ is, even though \$a \ge b\$.

  • \$(-1|b) = 1\$ if \$b \equiv 0,1,2 \mod 4\$ and \$-1\$ if \$b = 3 \mod 4\$.

  • \$(0|b)\$ is \$0\$ except for \$(0|1)\$ which is \$1\$, because \$(a|1)\$ is always \$1\$ and for negative \$a\$, \$(-a|b) = (-1|b) \times (a|b)\$.

The output of the Kronecker symbol is always \$-1, 0 \text{ or } 1\$, where the output is \$0\$ if \$a\$ and \$b\$ have any common factors. If \$b\$ is an odd prime, \$(a|b) = 1\$ if \$a\$ is a quadratic residue \$\mod b\$, and \$-1\$ if is it is not a quadratic residue.

Rules

  • Your code must be a program or a function.

  • The inputs must be in the order a b.

  • The output must be either \$-1, 0 \text{ or } 1\$.

  • This is code golf, so your code does not have to be efficient, just short.

  • No built-ins that directly calculate the Kronecker or the related Jacobi and Legendre symbols. Other built-ins (for prime factorization, for example) are fair game.

Examples

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

This is a complicated function, so please let me know if anything is unclear.

\$\endgroup\$
11
  • \$\begingroup\$ Are you sure you don't want to disallow built-ins? reference.wolfram.com/language/ref/KroneckerSymbol.html \$\endgroup\$ Nov 30, 2015 at 18:54
  • \$\begingroup\$ @MartinBüttner I was editing in examples when I saw your comment. I will disallow built-ins that directly calculate the Kronecker, Jacobi or Legendre symbols, but anything else (including prime factorization functions) should be fair game. \$\endgroup\$
    – Sherlock9
    Nov 30, 2015 at 18:55
  • \$\begingroup\$ im not entirely sure why (31|5) gives 1. There shouldnt be a qudratic residue so why isnt it -1? \$\endgroup\$
    – Eumel
    Nov 30, 2015 at 19:51
  • \$\begingroup\$ also 7/19 should be 1 and 19/7 should be -1 according to the wiki you linked \$\endgroup\$
    – Eumel
    Nov 30, 2015 at 20:03
  • 3
    \$\begingroup\$ If solutions have to handle negative and zero inputs correctly, you should definitely add some test cases for that. \$\endgroup\$ Nov 30, 2015 at 20:12

6 Answers 6

4
\$\begingroup\$

Python 3, 747 369 335 bytes

As an example answer, only slightly golfed, and to give you an idea of what an answer will look like.

And yes, the prime factorization and run-length-encoding bits are cribbed from Pyth with apologies to 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
\$\endgroup\$
1
  • 6
    \$\begingroup\$ Apology accepted - I'm glad someone reads Pyth source code. \$\endgroup\$
    – isaacg
    Nov 30, 2015 at 20:19
3
\$\begingroup\$

CJam (70 bytes)

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

Online demo (test cases generated with Mathematica).

Dissection

{               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
}

I found several ways of evaluating (a|2) for the same character count, and have chosen to use the one with the clearest presentation.

integer array <W= is IMO a quite elegant way of doing fallbacks: if the integer is greater than the length of the array, we select the last element.

Other comments

It's disappointing that for odd prime p the direct Fermat-style (a|p) is so short, because there's a very golfy way of finding (a|n) for positive odd n which I wanted to use. The basis is Zolotarev's lemma:

If p is an odd prime and a is an integer coprime to p then the Legendre symbol (a|p) is the sign of the permutation x -> ax (mod p)

This was strengthened by Frobenius to

If a and b are coprime positive odd integers then the Jacobi symbol (a|b) is the sign of the permutation x -> ax (mod b)

and by Lerch to

If b is a positive odd integer and a is an integer coprime to b then the Jacobi symbol (a|b) is the sign of the permutation x -> ax (mod b)

See Brunyate and Clark, Extending the Zolotarev-Frobenius approach to quadratic reciprocity, The Ramanujan Journal 37.1 (2014): 25-50 for references.

And it can easily be strengthened one step further (although I haven't seen this in the literature) to

If b is a positive odd integer and a is an integer then the Jacobi symbol (a|b) is the Levi-Civita symbol of the map x -> ax (mod b).

Proof: if a is coprime to b then we use Zolotarev-Frobenius-Lerch; otherwise the map is not a permutation, and the Levi-Civita symbol is 0 as desired.

This gives the Jacobi symbol calculation

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

But the special treatment required for (a|-1) and (a|2) mean that I haven't found a way of calculating the Kronecker symbol which is shorter with this approach: it's shorter to factorise and treat the primes individually.

\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

LabVIEW, 44 Bytes LabVIEW Primitives

Since its symetrical i swapped the inputs if a was bigger than b.

Represents the real formula now

counting like always according to

for true case

\$\endgroup\$
12
  • \$\begingroup\$ Unfortunately, (a|b) != (b|a) in all cases. In most cases, yes, but not in all of them. Though it would work if you reduced a mod b instead of swapping them. \$\endgroup\$
    – Sherlock9
    Nov 30, 2015 at 20:15
  • \$\begingroup\$ since i have the explantion now i can edit it, give me a min \$\endgroup\$
    – Eumel
    Nov 30, 2015 at 20:16
  • 1
    \$\begingroup\$ Is there any way I can test this? I don't really understand how LabView works. \$\endgroup\$
    – Sherlock9
    Nov 30, 2015 at 20:45
  • \$\begingroup\$ that is a good question, i can think of 2 ways. First i can build an .exe and send it to you, second you can get a labview test version and i can send you the vi or you can rebuild it from the pic. \$\endgroup\$
    – Eumel
    Nov 30, 2015 at 21:49
  • 7
    \$\begingroup\$ This is not 44 bytes. If you define a scoring system that is not based on the size of the file, you should call it something other than bytes. \$\endgroup\$
    – feersum
    Nov 30, 2015 at 21:57
1
\$\begingroup\$

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)))

This is a recursive function k that accepts two integers and returns an integer.

Ungolfed:

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
\$\endgroup\$
1
\$\begingroup\$

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)

Probably not completely optimized, but a valiant effort. The Kronecker symbol is defined as the infix function a#b, i.e.

*Main>323#455265 
1
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.