The Jacobi symbol is a multiplicative function that generalizes the Legendre symbol. Specifically, the Jacobi symbol (a | n) equals the product of the Legendre symbols (a | p_i)^(k_i), where n = p_1^(k_1)*p_2^(k_2)*...*p_i^(k_i) and the Legendre symbol (a | p) denotes the value of a ^ ((p-1)/2) (mod p)

 (a | p) ≡   1     if a is a square (mod p)
 (a | p) ≡ -1     if a is not a square (mod p)
 (a | p) ≡   0     if a ≡ 0 
If n is prime, then the Jacobi symbol (a | n) equals the Legendre symbol (a | n).

Task

Calculate the Jacobi symbol (a | n).

Reference

 Wikipedia article on Jacobi symbol.
template isOdd(n: int): bool = (n and 1) != 0
template isEven(n: int): bool = (n and 1) == 0
 
 
func jacobi(n, k: int): range[-1..1] =
  assert k > 0 and k.isOdd
  var n = n mod k
  var k = k
  result = 1
  while n != 0:
    while n.isEven:
      n = n shr 1
      if (k and 7) in [3, 5]:
        result = -result
    swap n, k
    if (n and 3) == 3 and (k and 3) == 3:
      result = -result
    n = n mod k
  if k != 1: result = 0
 
when isMainModule:
 
  import strutils
 
  stdout.write "n/k|"
  for n in 1..20:
    stdout.write align($n, 3)
  echo '\n' & repeat("—", 64)
 
  for k in countup(1, 21, 2):
    stdout.write align($k, 2), " |"
    for n in 1..20:
      stdout.write align($jacobi(n, k), 3)
    echo ""