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.
function jacobi(a, n)
    a %= n
    result = 1
    while a != 0
        while iseven(a)
            a ÷= 2
            ((n % 8) in [3, 5]) && (result *= -1)
        end
        a, n = n, a
        (a % 4 == n % 4 == 3) && (result *= -1)
        a %= n
    end
    return n == 1 ? result : 0
end
 
print(" Table of jacobi(a, n) for a 1 to 12, n 1 to 31\n   1   2   3   4   5   6   7   8", 
    "   9  10  11  12\nn\n_____________________________________________________")
for n in 1:2:31
    print("\n", rpad(n, 3))
    for a in 1:11
        print(lpad(jacobi(a, n), 4))
    end
end
 