# Jacobi symbol

Jacobi symbol
You are encouraged to solve this task according to the task description, using any language you may know.

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

Calculate the Jacobi symbol (a | n).

Reference

## 11l

Translation of: Python
```F jacobi(=a, =n)
I n <= 0
X.throw ValueError(‘'n' must be a positive integer.’)
I n % 2 == 0
X.throw ValueError(‘'n' must be odd.’)
a %= n
V result = 1
L a != 0
L a % 2 == 0
a /= 2
V n_mod_8 = n % 8
I n_mod_8 C (3, 5)
result = -result
(a, n) = (n, a)
I a % 4 == 3 & n % 4 == 3
result = -result
a %= n
I n == 1
R result
E
R 0

print(‘n\k|’, end' ‘’)
V kmax = 20
L(k) 0..kmax
print(‘#3’.format(k), end' ‘’)
print("\n----", end' ‘’)
L(k) 0..kmax
print(end' ‘---’)
print()
L(n) (1..21).step(2)
print(‘#<2 |’.format(n), end' ‘’)
L(k) 0..kmax
print(‘#3’.format(jacobi(k, n)), end' ‘’)
print()```
Output:
```n\k|  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
-------------------------------------------------------------------
1  |  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
3  |  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1
5  |  0  1 -1 -1  1  0  1 -1 -1  1  0  1 -1 -1  1  0  1 -1 -1  1  0
7  |  0  1  1 -1  1 -1 -1  0  1  1 -1  1 -1 -1  0  1  1 -1  1 -1 -1
9  |  0  1  1  0  1  1  0  1  1  0  1  1  0  1  1  0  1  1  0  1  1
11 |  0  1 -1  1  1  1 -1 -1 -1  1 -1  0  1 -1  1  1  1 -1 -1 -1  1
13 |  0  1 -1  1  1 -1 -1 -1 -1  1  1 -1  1  0  1 -1  1  1 -1 -1 -1
15 |  0  1  1  0  1  0  0 -1  1  0  0 -1  0 -1 -1  0  1  1  0  1  0
17 |  0  1  1 -1  1 -1 -1 -1  1  1 -1 -1 -1  1 -1  1  1  0  1  1 -1
19 |  0  1 -1 -1  1  1  1  1 -1  1 -1  1 -1 -1 -1 -1  1  1 -1  0  1
21 |  0  1 -1  0  1  1  0  0 -1  0 -1 -1  0 -1  0  0  1  1  0 -1  1
```

## Action!

```INCLUDE "D2:PRINTF.ACT" ;from the Action! Tool Kit

INT FUNC Jacobi(INT a,n)
INT res,tmp

IF a>=n THEN
a=a MOD n
FI
res=1
WHILE a
DO
WHILE (a&1)=0
DO
a=a RSH 1
tmp=n&7
IF tmp=3 OR tmp=5 THEN
res=-res
FI
OD
tmp=a a=n n=tmp
IF (a%3)=3 AND (n%3)=3 THEN
res=-res
FI
a=a MOD n
OD

IF n=1 THEN
RETURN (res)
FI
RETURN (0)

PROC PrintTable(INT maxK,maxN)
INT res,n,k
CHAR ARRAY t(10)

Put('n) Put(7) Put('k) Put(124)
FOR k=0 TO maxK
DO
StrI(k,t) PrintF("%3S",t)
OD
PutE()

Put(18) Put(18) Put(18) Put(19)
FOR k=0 TO 3*maxK+2
DO
Put(18)
OD
PutE()

FOR n=1 TO maxN STEP 2
DO
StrI(n,t) PrintF("%3S",t)
Put(124)
FOR k=0 TO maxK
DO
res=Jacobi(k,n)
StrI(res,t) PrintF("%3S",t)
OD
PutE()
OD
RETURN

PROC Main()
Put(125) PutE() ;clear the screen
PrintTable(10,39)
RETURN```
Output:
```n\k│  0  1  2  3  4  5  6  7  8  9 10
───┼─────────────────────────────────
1│  1  1  1  1  1  1  1  1  1  1  1
3│  0 -1  1  0 -1  1  0 -1  1  0 -1
5│  0  1 -1  1  1  0  1 -1  1  1  0
7│  0  1  1 -1  1 -1 -1  0  1  1 -1
9│  0  1  1  0  1  1  0  1  1  0  1
11│  0  1 -1  1  1  1 -1  1 -1  1 -1
13│  0  1 -1 -1  1  1  1 -1 -1  1 -1
15│  0  1  1  0  1  0  0  1  1  0  0
17│  0  1  1  1  1 -1  1 -1  1  1 -1
19│  0  1 -1 -1  1  1  1 -1 -1  1 -1
21│  0  1 -1  0  1  1  0  0 -1  0 -1
23│  0  1  1  1  1  1  1  1  1  1  1
25│  0  1  1 -1  1  0 -1  1  1  1  0
27│  0  1 -1  0  1 -1  0 -1 -1  0  1
29│  0  1 -1  1  1  1 -1  1 -1  1 -1
31│  0  1  1 -1  1  1 -1 -1  1  1  1
33│  0  1  1  0  1  1  0 -1  1  0  1
35│  0  1 -1  1  1  0 -1  0 -1  1  0
37│  0  1 -1 -1  1 -1  1  1 -1  1  1
39│  0  1  1  0  1  1  0  1  1  0  1
```

## ALGOL 68

Translation of: Wren
```BEGIN # Jacobi symbol - translation of the Wren sample #

PROC jacobi = ( INT a in, n in )INT:
IF n in <= 0 OR NOT ODD n in THEN
print( ( "The 'n' parameter of jacobi must be an odd positive integer.", newline ) );
stop
ELSE
INT a      := a in MOD n in, n := n in;
INT result := 1;
WHILE a /= 0 DO
WHILE NOT ODD a DO
a OVERAB 2;
INT nm8 = n MOD 8;
IF nm8 = 3 OR nm8 = 5 THEN result := - result FI
OD;
INT t = a;
a    := n;
n    := t;
IF a MOD 4 = 3 AND n MOD 4 = 3 THEN result := - result FI;
a MODAB n
OD;
IF n = 1 THEN result ELSE 0 FI
FI # jacobi # ;

print( ( "Table of jacobi(a, n):", newline ) );
print( ( "n/a   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15", newline ) );
print( ( "---------------------------------------------------------------", newline ) );
FOR n BY 2 TO 29 DO
print( ( whole( n, -3 ) ) );
FOR a TO 15 DO print( ( whole( jacobi( a, n ), -4 ) ) ) OD;
print( ( newline ) )
OD

END```
Output:
```Table of jacobi(a, n):
n/a   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
---------------------------------------------------------------
1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
3   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0
5   1  -1  -1   1   0   1  -1  -1   1   0   1  -1  -1   1   0
7   1   1  -1   1  -1  -1   0   1   1  -1   1  -1  -1   0   1
9   1   1   0   1   1   0   1   1   0   1   1   0   1   1   0
11   1  -1   1   1   1  -1  -1  -1   1  -1   0   1  -1   1   1
13   1  -1   1   1  -1  -1  -1  -1   1   1  -1   1   0   1  -1
15   1   1   0   1   0   0  -1   1   0   0  -1   0  -1  -1   0
17   1   1  -1   1  -1  -1  -1   1   1  -1  -1  -1   1  -1   1
19   1  -1  -1   1   1   1   1  -1   1  -1   1  -1  -1  -1  -1
21   1  -1   0   1   1   0   0  -1   0  -1  -1   0  -1   0   0
23   1   1   1   1  -1   1  -1   1   1  -1  -1   1   1  -1  -1
25   1   1   1   1   0   1   1   1   1   0   1   1   1   1   0
27   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0
29   1  -1  -1   1   1   1   1  -1   1  -1  -1  -1   1  -1  -1
```

## ALGOL W

Translation of: Wren
```begin % Jacobi symbol %

integer procedure jacobi( integer value aIn, nIn ) ;
if nIn <= 0 or not odd( nIn ) then begin
write( "The 'n' parameter of jacobi must be an odd positive integer." );
0
end
else begin
integer a, n, js;
a := aIn rem nIn; n := nIn; js := 1;
while a not = 0 do begin
while a rem 2 = 0 do begin
integer nm8;
a := a div 2;
nm8 := n rem 8;
if nm8 = 3 or nm8 = 5 then js := - js;
end while_a_rem_2_eq_0 ;
begin integer t; t := a; a := n; n := t end;
if a rem 4 = 3 and n rem 4 = 3 then js := - js;
a := a rem n
end;
if n = 1 then js else 0
end jacobi ;

write( "Table of jacobi(a, n):" );;
write( "n/a   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15" );
write( "---------------------------------------------------------------" );
for n := 1 step 2 until 29 do begin
write( i_w := 3, s_w := 0, n );
for a := 1 until 15 do writeon( i_w := 4, s_w := 0, jacobi( a, n ) );
end

end.```
Output:
```Table of jacobi(a, n):
n/a   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
---------------------------------------------------------------
1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
3   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0
5   1  -1  -1   1   0   1  -1  -1   1   0   1  -1  -1   1   0
7   1   1  -1   1  -1  -1   0   1   1  -1   1  -1  -1   0   1
9   1   1   0   1   1   0   1   1   0   1   1   0   1   1   0
11   1  -1   1   1   1  -1  -1  -1   1  -1   0   1  -1   1   1
13   1  -1   1   1  -1  -1  -1  -1   1   1  -1   1   0   1  -1
15   1   1   0   1   0   0  -1   1   0   0  -1   0  -1  -1   0
17   1   1  -1   1  -1  -1  -1   1   1  -1  -1  -1   1  -1   1
19   1  -1  -1   1   1   1   1  -1   1  -1   1  -1  -1  -1  -1
21   1  -1   0   1   1   0   0  -1   0  -1  -1   0  -1   0   0
23   1   1   1   1  -1   1  -1   1   1  -1  -1   1   1  -1  -1
25   1   1   1   1   0   1   1   1   1   0   1   1   1   1   0
27   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0
29   1  -1  -1   1   1   1   1  -1   1  -1  -1  -1   1  -1  -1
```

## Arturo

Translation of: Nim
```jacobi: function [n,k][
N: n % k
K: k

result: 1
while [N <> 0][
while [even? N][
N: shr N 1
if contains? [3 5] and K 7 ->
result: neg result
]
[N,K]: @[K,N]
if and? 3=and N 3 3=and K 3 ->
result: neg result
N: N % K
]
if K <> 1 ->
result: 0

return result
]

print ["" "k/n" "|"] ++ map to [:string] 1..20 'item -> pad.left item 2
print repeat "=" 67
loop range.step:2 1 21 'k [
print [
"" pad to :string k 3 "|" join.with:" " map to [:string] map 1..20 'n -> jacobi n k
]
]
```
Output:
``` k/n |  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
===================================================================
1 |  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
3 |  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1
5 |  1 -1 -1  1  0  1 -1 -1  1  0  1 -1 -1  1  0  1 -1 -1  1  0
7 |  1  1 -1  1 -1 -1  0  1  1 -1  1 -1 -1  0  1  1 -1  1 -1 -1
9 |  1  1  0  1  1  0  1  1  0  1  1  0  1  1  0  1  1  0  1  1
11 |  1 -1  1  1  1 -1 -1 -1  1 -1  0  1 -1  1  1  1 -1 -1 -1  1
13 |  1 -1  1  1 -1 -1 -1 -1  1  1 -1  1  0  1 -1  1  1 -1 -1 -1
15 |  1  1  0  1  0  0 -1  1  0  0 -1  0 -1 -1  0  1  1  0  1  0
17 |  1  1 -1  1 -1 -1 -1  1  1 -1 -1 -1  1 -1  1  1  0  1  1 -1
19 |  1 -1 -1  1  1  1  1 -1  1 -1  1 -1 -1 -1 -1  1  1 -1  0  1
21 |  1 -1  0  1  1  0  0 -1  0 -1 -1  0 -1  0  0  1  1  0 -1  1
```

## AutoHotkey

```result := "n/k|"
loop 20
result .= SubStr(" " A_Index, -1) " "
l := StrLen(result)
result .= "`n"
loop % l
result .= "-"
result .= "`n"

loop 21
{
if !Mod(n := A_Index, 2)
continue
result .= SubStr(" " n, -1) " |"
loop 20
result .= SubStr(" " jacobi(a := A_Index, n), -1) " "
result .= "`n"
}
MsgBox, 262144, , % result
return

jacobi(a, n) {
a := Mod(a, n), t := 1
while (a != 0) {
while !Mod(a, 2)
a := a >> 1, r := Mod(n, 8), t := (r=3 || r=5) ? -t : t
r := n, n := a, a := r
if (Mod(a, 4)=3 && Mod(n, 4)=3)
t := -t
a := Mod(a, n)
}
return (n=1) ? t : 0
}
```
Output:
```n/k| 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
----------------------------------------------------------------
1 | 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
3 | 1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1
5 | 1 -1 -1  1  0  1 -1 -1  1  0  1 -1 -1  1  0  1 -1 -1  1  0
7 | 1  1 -1  1 -1 -1  0  1  1 -1  1 -1 -1  0  1  1 -1  1 -1 -1
9 | 1  1  0  1  1  0  1  1  0  1  1  0  1  1  0  1  1  0  1  1
11 | 1 -1  1  1  1 -1 -1 -1  1 -1  0  1 -1  1  1  1 -1 -1 -1  1
13 | 1 -1  1  1 -1 -1 -1 -1  1  1 -1  1  0  1 -1  1  1 -1 -1 -1
15 | 1  1  0  1  0  0 -1  1  0  0 -1  0 -1 -1  0  1  1  0  1  0
17 | 1  1 -1  1 -1 -1 -1  1  1 -1 -1 -1  1 -1  1  1  0  1  1 -1
19 | 1 -1 -1  1  1  1  1 -1  1 -1  1 -1 -1 -1 -1  1  1 -1  0  1
21 | 1 -1  0  1  1  0  0 -1  0 -1 -1  0 -1  0  0  1  1  0 -1  1 ```

## AWK

Translation of: Go
```# syntax: GAWK -f JACOBI_SYMBOL.AWK
BEGIN {
max_n = 29
max_a = max_n + 1
printf("n\\a")
for (i=1; i<=max_a; i++) {
printf("%3d",i)
underline = underline " --"
}
printf("\n---%s\n",underline)
for (n=1; n<=max_n; n+=2) {
printf("%3d",n)
for (a=1; a<=max_a; a++) {
printf("%3d",jacobi(a,n))
}
printf("\n")
}
exit(0)
}
function jacobi(a,n,  result,tmp) {
if (n%2 == 0) {
print("error: 'n' must be a positive odd integer")
exit
}
a %= n
result = 1
while (a != 0) {
while (a%2 == 0) {
a /= 2
if (n%8 == 3 || n%8 == 5) {
result = -result
}
}
tmp = a
a = n
n = tmp
if (a%4 == 3 && n%4 == 3) {
result = -result
}
a %= n
}
if (n == 1) {
return(result)
}
return(0)
}
```
Output:
```n\a  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
--- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
3  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0
5  1 -1 -1  1  0  1 -1 -1  1  0  1 -1 -1  1  0  1 -1 -1  1  0  1 -1 -1  1  0  1 -1 -1  1  0
7  1  1 -1  1 -1 -1  0  1  1 -1  1 -1 -1  0  1  1 -1  1 -1 -1  0  1  1 -1  1 -1 -1  0  1  1
9  1  1  0  1  1  0  1  1  0  1  1  0  1  1  0  1  1  0  1  1  0  1  1  0  1  1  0  1  1  0
11  1 -1  1  1  1 -1 -1 -1  1 -1  0  1 -1  1  1  1 -1 -1 -1  1 -1  0  1 -1  1  1  1 -1 -1 -1
13  1 -1  1  1 -1 -1 -1 -1  1  1 -1  1  0  1 -1  1  1 -1 -1 -1 -1  1  1 -1  1  0  1 -1  1  1
15  1  1  0  1  0  0 -1  1  0  0 -1  0 -1 -1  0  1  1  0  1  0  0 -1  1  0  0 -1  0 -1 -1  0
17  1  1 -1  1 -1 -1 -1  1  1 -1 -1 -1  1 -1  1  1  0  1  1 -1  1 -1 -1 -1  1  1 -1 -1 -1  1
19  1 -1 -1  1  1  1  1 -1  1 -1  1 -1 -1 -1 -1  1  1 -1  0  1 -1 -1  1  1  1  1 -1  1 -1  1
21  1 -1  0  1  1  0  0 -1  0 -1 -1  0 -1  0  0  1  1  0 -1  1  0  1 -1  0  1  1  0  0 -1  0
23  1  1  1  1 -1  1 -1  1  1 -1 -1  1  1 -1 -1  1 -1  1 -1 -1 -1 -1  0  1  1  1  1 -1  1 -1
25  1  1  1  1  0  1  1  1  1  0  1  1  1  1  0  1  1  1  1  0  1  1  1  1  0  1  1  1  1  0
27  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0
29  1 -1 -1  1  1  1  1 -1  1 -1 -1 -1  1 -1 -1  1 -1 -1 -1  1 -1  1  1  1  1 -1 -1  1  0  1
```

## C

```#include <stdlib.h>
#include <stdio.h>

#define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))

int jacobi(unsigned long a, unsigned long n) {
if (a >= n) a %= n;
int result = 1;
while (a) {
while ((a & 1) == 0) {
a >>= 1;
if ((n & 7) == 3 || (n & 7) == 5) result = -result;
}
SWAP(a, n);
if ((a & 3) == 3 && (n & 3) == 3) result = -result;
a %= n;
}
if (n == 1) return result;
return 0;
}

void print_table(unsigned kmax, unsigned nmax) {
printf("n\\k|");
for (int k = 0; k <= kmax; ++k) printf("%'3u", k);
printf("\n----");
for (int k = 0; k <= kmax; ++k) printf("---");
putchar('\n');
for (int n = 1; n <= nmax; n += 2) {
printf("%-2u |", n);
for (int k = 0; k <= kmax; ++k)
printf("%'3d", jacobi(k, n));
putchar('\n');
}
}

int main() {
print_table(20, 21);
return 0;
}
```
Output:
```n\k|  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
---+---------------------------------------------------------------
1  |  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
3  |  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1
5  |  0  1 -1 -1  1  0  1 -1 -1  1  0  1 -1 -1  1  0  1 -1 -1  1  0
7  |  0  1  1 -1  1 -1 -1  0  1  1 -1  1 -1 -1  0  1  1 -1  1 -1 -1
9  |  0  1  1  0  1  1  0  1  1  0  1  1  0  1  1  0  1  1  0  1  1
11 |  0  1 -1  1  1  1 -1 -1 -1  1 -1  0  1 -1  1  1  1 -1 -1 -1  1
13 |  0  1 -1  1  1 -1 -1 -1 -1  1  1 -1  1  0  1 -1  1  1 -1 -1 -1
15 |  0  1  1  0  1  0  0 -1  1  0  0 -1  0 -1 -1  0  1  1  0  1  0
17 |  0  1  1 -1  1 -1 -1 -1  1  1 -1 -1 -1  1 -1  1  1  0  1  1 -1
19 |  0  1 -1 -1  1  1  1  1 -1  1 -1  1 -1 -1 -1 -1  1  1 -1  0  1
21 |  0  1 -1  0  1  1  0  0 -1  0 -1 -1  0 -1  0  0  1  1  0 -1  1
```

## C++

```#include <algorithm>
#include <cassert>
#include <iomanip>
#include <iostream>

int jacobi(int n, int k) {
assert(k > 0 && k % 2 == 1);
n %= k;
int t = 1;
while (n != 0) {
while (n % 2 == 0) {
n /= 2;
int r = k % 8;
if (r == 3 || r == 5)
t = -t;
}
std::swap(n, k);
if (n % 4 == 3 && k % 4 == 3)
t = -t;
n %= k;
}
return k == 1 ? t : 0;
}

void print_table(std::ostream& out, int kmax, int nmax) {
out << "n\\k|";
for (int k = 0; k <= kmax; ++k)
out << ' ' << std::setw(2) << k;
out << "\n----";
for (int k = 0; k <= kmax; ++k)
out << "---";
out << '\n';
for (int n = 1; n <= nmax; n += 2) {
out << std::setw(2) << n << " |";
for (int k = 0; k <= kmax; ++k)
out << ' ' << std::setw(2) << jacobi(k, n);
out << '\n';
}
}

int main() {
print_table(std::cout, 20, 21);
return 0;
}
```
Output:
```n\k|  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
-------------------------------------------------------------------
1 |  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
3 |  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1
5 |  0  1 -1 -1  1  0  1 -1 -1  1  0  1 -1 -1  1  0  1 -1 -1  1  0
7 |  0  1  1 -1  1 -1 -1  0  1  1 -1  1 -1 -1  0  1  1 -1  1 -1 -1
9 |  0  1  1  0  1  1  0  1  1  0  1  1  0  1  1  0  1  1  0  1  1
11 |  0  1 -1  1  1  1 -1 -1 -1  1 -1  0  1 -1  1  1  1 -1 -1 -1  1
13 |  0  1 -1  1  1 -1 -1 -1 -1  1  1 -1  1  0  1 -1  1  1 -1 -1 -1
15 |  0  1  1  0  1  0  0 -1  1  0  0 -1  0 -1 -1  0  1  1  0  1  0
17 |  0  1  1 -1  1 -1 -1 -1  1  1 -1 -1 -1  1 -1  1  1  0  1  1 -1
19 |  0  1 -1 -1  1  1  1  1 -1  1 -1  1 -1 -1 -1 -1  1  1 -1  0  1
21 |  0  1 -1  0  1  1  0  0 -1  0 -1 -1  0 -1  0  0  1  1  0 -1  1
```

## Crystal

Translation of: Swift
```def jacobi(a, n)
raise ArgumentError.new "n must b positive and odd" if n < 1 || n.even?
res = 1
until (a %= n) == 0
while a.even?
a >>= 1
res = -res if [3, 5].includes? n % 8
end
a, n = n, a
res = -res if a % 4 == n % 4 == 3
end
n == 1 ? res : 0
end

puts "Jacobian symbols for jacobi(a, n)"
puts "n\\a  0  1  2  3  4  5  6  7  8  9 10"
puts "------------------------------------"
1.step(to: 17, by: 2) do |n|
printf("%2d ", n)
(0..10).each { |a| printf(" % 2d", jacobi(a, n)) }
puts
end
```
Output:
```Jacobian symbols for jacobi(a, n)
n\a  0  1  2  3  4  5  6  7  8  9 10
------------------------------------
1   1  1  1  1  1  1  1  1  1  1  1
3   0  1 -1  0  1 -1  0  1 -1  0  1
5   0  1 -1 -1  1  0  1 -1 -1  1  0
7   0  1  1 -1  1 -1 -1  0  1  1 -1
9   0  1  1  0  1  1  0  1  1  0  1
11   0  1 -1  1  1  1 -1 -1 -1  1 -1
13   0  1 -1  1  1 -1 -1 -1 -1  1  1
15   0  1  1  0  1  0  0 -1  1  0  0
17   0  1  1 -1  1 -1 -1 -1  1  1 -1
```

## Erlang

```jacobi(_, N) when N =< 0 -> jacobi_domain_error;
jacobi(_, N) when (N band 1) =:= 0 -> jacobi_domain_error;
jacobi(A, N) when A < 0 ->
J2 = ja(-A, N),
case N band 3 of
1 -> J2;
3 -> -J2
end;
jacobi(A, N) -> ja(A, N).

ja(0, _) -> 0;
ja(1, _) -> 1;
ja(A, N) when A >= N -> ja(A rem N, N);
ja(A, N) when (A band 1) =:= 0 -> % A is even
J2 = ja(A bsr 1, N),
case N band 7 of
1 -> J2;
3 -> -J2;
5 -> -J2;
7 -> J2
end;
ja(A, N) ->    % if we get here, A is odd, so we can flip it.
J2 = ja(N, A),
case (A band 3 =:= 3) and (N band 3 =:= 3) of
true  -> -J2;
false -> J2
end.
```

## F#

```//Jacobi Symbol. Nigel Galloway: July 14th., 2020
let J n m=let rec J n m g=match n with
0->if m=1 then g else 0
|n when n%2=0->J(n/2) m (if m%8=3 || m%8=5 then -g else g)
|n->J (m%n) n (if m%4=3 && n%4=3 then -g else g)
J (n%m) m 1
printfn "n\m   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30\n     ----------------------------------------------------------------------------------------------------------------------"
[1..2..29]|>List.iter(fun m->printf "%3d" m; [1..30]|>List.iter(fun n->printf "%4d" (J n m)); printfn "")
```
Output:
```n\m   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30
----------------------------------------------------------------------------------------------------------------------
1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
3   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0
5   1  -1  -1   1   0   1  -1  -1   1   0   1  -1  -1   1   0   1  -1  -1   1   0   1  -1  -1   1   0   1  -1  -1   1   0
7   1   1  -1   1  -1  -1   0   1   1  -1   1  -1  -1   0   1   1  -1   1  -1  -1   0   1   1  -1   1  -1  -1   0   1   1
9   1   1   0   1   1   0   1   1   0   1   1   0   1   1   0   1   1   0   1   1   0   1   1   0   1   1   0   1   1   0
11   1  -1   1   1   1  -1  -1  -1   1  -1   0   1  -1   1   1   1  -1  -1  -1   1  -1   0   1  -1   1   1   1  -1  -1  -1
13   1  -1   1   1  -1  -1  -1  -1   1   1  -1   1   0   1  -1   1   1  -1  -1  -1  -1   1   1  -1   1   0   1  -1   1   1
15   1   1   0   1   0   0  -1   1   0   0  -1   0  -1  -1   0   1   1   0   1   0   0  -1   1   0   0  -1   0  -1  -1   0
17   1   1  -1   1  -1  -1  -1   1   1  -1  -1  -1   1  -1   1   1   0   1   1  -1   1  -1  -1  -1   1   1  -1  -1  -1   1
19   1  -1  -1   1   1   1   1  -1   1  -1   1  -1  -1  -1  -1   1   1  -1   0   1  -1  -1   1   1   1   1  -1   1  -1   1
21   1  -1   0   1   1   0   0  -1   0  -1  -1   0  -1   0   0   1   1   0  -1   1   0   1  -1   0   1   1   0   0  -1   0
23   1   1   1   1  -1   1  -1   1   1  -1  -1   1   1  -1  -1   1  -1   1  -1  -1  -1  -1   0   1   1   1   1  -1   1  -1
25   1   1   1   1   0   1   1   1   1   0   1   1   1   1   0   1   1   1   1   0   1   1   1   1   0   1   1   1   1   0
27   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0
29   1  -1  -1   1   1   1   1  -1   1  -1  -1  -1   1  -1  -1   1  -1  -1  -1   1  -1   1   1   1   1  -1  -1   1   0   1
```

## Factor

The `jacobi` word already exists in the `math.extras` vocabulary. See the implementation here.

## FreeBASIC

```function gcdp( a as uinteger, b as uinteger ) as uinteger
if b = 0 then return a
return gcdp( b, a mod b )
end function

function gcd(a as integer, b as integer) as uinteger
return gcdp( abs(a), abs(b) )
end function

function jacobi( a as uinteger, n as uinteger ) as integer
if gcd(a, n)<>1 then return 0
if a = 1 then return 1
if a>n then return jacobi( a mod n, n )
if a mod 2 = 0 then
if n mod 8 = 1 or n mod 8 = 7 then
return jacobi(a/2, n)
else
return -jacobi(a/2, n)
end if
end if
dim as integer q = (-1)^((a-1)/2 * (n-1)/2)
return q/jacobi(n, a)
end function

'print a table

function padto( i as ubyte, j as integer ) as string
return wspace(i-len(str(j)))+str(j)
end function

dim as uinteger pn, k, prime(0 to 16) = {3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61}
dim as string outstr = "  k       "

for k = 1 to 36
outstr = outstr + padto(2, k)+"  "
next k
print outstr
print " n"
for pn=0 to 16
outstr= " "+padto( 2, prime(pn) )+"       "
for k = 1 to 36
outstr = outstr + padto(2, jacobi(k, prime(pn))) + "  "
next k
print outstr
next pn```
Output:
```  k        1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36
n
3        1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0
5        1  -1  -1   1   0   1  -1  -1   1   0   1  -1  -1   1   0   1  -1  -1   1   0   1  -1  -1   1   0   1  -1  -1   1   0   1  -1  -1   1   0   1
7        1   1  -1   1  -1  -1   0   1   1  -1   1  -1  -1   0   1   1  -1   1  -1  -1   0   1   1  -1   1  -1  -1   0   1   1  -1   1  -1  -1   0   1
11        1  -1   1   1   1  -1  -1  -1   1  -1   0   1  -1   1   1   1  -1  -1  -1   1  -1   0   1  -1   1   1   1  -1  -1  -1   1  -1   0   1  -1   1
13        1  -1   1   1  -1  -1  -1  -1   1   1  -1   1   0   1  -1   1   1  -1  -1  -1  -1   1   1  -1   1   0   1  -1   1   1  -1  -1  -1  -1   1   1
17        1   1  -1   1  -1  -1  -1   1   1  -1  -1  -1   1  -1   1   1   0   1   1  -1   1  -1  -1  -1   1   1  -1  -1  -1   1  -1   1   1   0   1   1
19        1  -1  -1   1   1   1   1  -1   1  -1   1  -1  -1  -1  -1   1   1  -1   0   1  -1  -1   1   1   1   1  -1   1  -1   1  -1  -1  -1  -1   1   1
23        1   1   1   1  -1   1  -1   1   1  -1  -1   1   1  -1  -1   1  -1   1  -1  -1  -1  -1   0   1   1   1   1  -1   1  -1   1   1  -1  -1   1   1
29        1  -1  -1   1   1   1   1  -1   1  -1  -1  -1   1  -1  -1   1  -1  -1  -1   1  -1   1   1   1   1  -1  -1   1   0   1  -1  -1   1   1   1   1
31        1   1  -1   1   1  -1   1   1   1   1  -1  -1  -1   1  -1   1  -1   1   1   1  -1  -1  -1  -1   1  -1  -1   1  -1  -1   0   1   1  -1   1   1
37        1  -1   1   1  -1  -1   1  -1   1   1   1   1  -1  -1  -1   1  -1  -1  -1  -1   1  -1  -1  -1   1   1   1   1  -1   1  -1  -1   1   1  -1   1
41        1   1  -1   1   1  -1  -1   1   1   1  -1  -1  -1  -1  -1   1  -1   1  -1   1   1  -1   1  -1   1  -1  -1  -1  -1  -1   1   1   1  -1  -1   1
43        1  -1  -1   1  -1   1  -1  -1   1   1   1  -1   1   1   1   1   1  -1  -1  -1   1  -1   1   1   1  -1  -1  -1  -1  -1   1  -1  -1  -1   1   1
47        1   1   1   1  -1   1   1   1   1  -1  -1   1  -1   1  -1   1   1   1  -1  -1   1  -1  -1   1   1  -1   1   1  -1  -1  -1   1  -1   1  -1   1
53        1  -1  -1   1  -1   1   1  -1   1   1   1  -1   1  -1   1   1   1  -1  -1  -1  -1  -1  -1   1   1  -1  -1   1   1  -1  -1  -1  -1  -1  -1   1
59        1  -1   1   1   1  -1   1  -1   1  -1  -1   1  -1  -1   1   1   1  -1   1   1   1   1  -1  -1   1   1   1   1   1  -1  -1  -1  -1  -1   1   1
61        1  -1   1   1   1  -1  -1  -1   1  -1  -1   1   1   1   1   1  -1  -1   1   1  -1   1  -1  -1   1  -1   1  -1  -1  -1  -1  -1  -1   1  -1   1```

## Go

The big.Jacobi function in the standard library (for 'big integers') returns the Jacobi symbol for given values of 'a' and 'n'.

This translates the Lua code in the above referenced Wikipedia article to Go (for 8 byte integers) and checks that it gives the same answers for a small table of values - which it does.

```package main

import (
"fmt"
"log"
"math/big"
)

func jacobi(a, n uint64) int {
if n%2 == 0 {
log.Fatal("'n' must be a positive odd integer")
}
a %= n
result := 1
for a != 0 {
for a%2 == 0 {
a /= 2
nn := n % 8
if nn == 3 || nn == 5 {
result = -result
}
}
a, n = n, a
if a%4 == 3 && n%4 == 3 {
result = -result
}
a %= n
}
if n == 1 {
return result
}
return 0
}

func main() {
fmt.Println("Using hand-coded version:")
fmt.Println("n/a  0  1  2  3  4  5  6  7  8  9")
fmt.Println("---------------------------------")
for n := uint64(1); n <= 17; n += 2 {
fmt.Printf("%2d ", n)
for a := uint64(0); a <= 9; a++ {
fmt.Printf(" % d", jacobi(a, n))
}
fmt.Println()
}

ba, bn := new(big.Int), new(big.Int)
fmt.Println("\nUsing standard library function:")
fmt.Println("n/a  0  1  2  3  4  5  6  7  8  9")
fmt.Println("---------------------------------")
for n := uint64(1); n <= 17; n += 2 {
fmt.Printf("%2d ", n)
for a := uint64(0); a <= 9; a++ {
ba.SetUint64(a)
bn.SetUint64(n)
fmt.Printf(" % d", big.Jacobi(ba, bn))
}
fmt.Println()
}
}
```
Output:
```Using hand-coded version:
n/a  0  1  2  3  4  5  6  7  8  9
---------------------------------
1   1  1  1  1  1  1  1  1  1  1
3   0  1 -1  0  1 -1  0  1 -1  0
5   0  1 -1 -1  1  0  1 -1 -1  1
7   0  1  1 -1  1 -1 -1  0  1  1
9   0  1  1  0  1  1  0  1  1  0
11   0  1 -1  1  1  1 -1 -1 -1  1
13   0  1 -1  1  1 -1 -1 -1 -1  1
15   0  1  1  0  1  0  0 -1  1  0
17   0  1  1 -1  1 -1 -1 -1  1  1

Using standard library function:
n/a  0  1  2  3  4  5  6  7  8  9
---------------------------------
1   1  1  1  1  1  1  1  1  1  1
3   0  1 -1  0  1 -1  0  1 -1  0
5   0  1 -1 -1  1  0  1 -1 -1  1
7   0  1  1 -1  1 -1 -1  0  1  1
9   0  1  1  0  1  1  0  1  1  0
11   0  1 -1  1  1  1 -1 -1 -1  1
13   0  1 -1  1  1 -1 -1 -1 -1  1
15   0  1  1  0  1  0  0 -1  1  0
17   0  1  1 -1  1 -1 -1 -1  1  1
```

Translation of: Scheme
```jacobi :: Integer -> Integer -> Integer
jacobi 0 1 = 1
jacobi 0 _ = 0
jacobi a n =
let a_mod_n = rem a n
in if even a_mod_n
then case rem n 8 of
1 -> jacobi (div a_mod_n 2) n
3 -> negate \$ jacobi (div a_mod_n 2) n
5 -> negate \$ jacobi (div a_mod_n 2) n
7 -> jacobi (div a_mod_n 2) n
else if rem a_mod_n 4 == 3 && rem n 4 == 3
then negate \$ jacobi n a_mod_n
else jacobi n a_mod_n
```

Or, expressing it slightly differently, and adding a tabulation:

```import Data.Bool (bool)
import Data.List (replicate, transpose)
import Data.List.Split (chunksOf)

---------------------- JACOBI SYMBOL ---------------------

jacobi :: Int -> Int -> Int
jacobi = go
where
go 0 1 = 1
go 0 _ = 0
go x y
| even r =
plusMinus
(rem y 8 `elem` [3, 5])
(go (div r 2) y)
| otherwise = plusMinus (p r && p y) (go y r)
where
plusMinus = bool id negate
p = (3 ==) . flip rem 4
r = rem x y

--------------------------- TEST -------------------------
main :: IO ()
main = putStrLn \$ jacobiTable 11 9

------------------------- DISPLAY ------------------------
jacobiTable :: Int -> Int -> String
jacobiTable nCols nRows =
let rowLabels = [1, 3 .. (2 * nRows)]
colLabels = [0 .. pred nCols]
in withColumnLabels ("" : fmap show colLabels) \$
labelledRows (fmap show rowLabels) \$
chunksOf nRows \$
uncurry jacobi
<\$> ((,) <\$> colLabels <*> rowLabels)

------------------- TABULATION FUNCTIONS -----------------
Show a =>
[[a]] ->
[[String]]
let scols = fmap show <\$> cols
w = maximum \$ length <\$> concat scols
in map (justifyRight w ' ') <\$> scols

labelledRows :: [String] -> [[String]] -> [[String]]
labelledRows labels cols =
let w = maximum \$ map length labels
in zipWith
(:)
((<> " ->") . justifyRight w ' ' <\$> labels)
(transpose cols)

withColumnLabels :: [String] -> [[String]] -> String
withColumnLabels _ [] = ""
withColumnLabels labels rows@(x : _) =
let labelRow =
unwords \$
zipWith
(`justifyRight` ' ')
(length <\$> x)
labels
in unlines \$
labelRow :
replicate (length labelRow) '-' : fmap unwords rows

justifyRight :: Int -> a -> [a] -> [a]
justifyRight n c = (drop . length) <*> (replicate n c <>)
```
Output:
```       0  1  2  3  4  5  6  7  8  9 10
--------------------------------------
1 ->  1  1  1  1  1  1  1  1  1  1  1
3 ->  0  1 -1  0  1 -1  0  1 -1  0  1
5 ->  0  1 -1 -1  1  0  1 -1 -1  1  0
7 ->  0  1  1 -1  1 -1 -1  0  1  1 -1
9 ->  0  1  1  0  1  1  0  1  1  0  1
11 ->  0  1 -1  1  1  1 -1 -1 -1  1 -1
13 ->  0  1 -1  1  1 -1 -1 -1 -1  1  1
15 ->  0  1  1  0  1  0  0 -1  1  0  0
17 ->  0  1  1 -1  1 -1 -1 -1  1  1 -1```

## J

```NB. functionally equivalent translation of the Lua program found
NB. at https://en.wikipedia.org/wiki/Jacobi_symbol
jacobi=: {{
assert. (0<x) * 1=2|x
y=. x|y
t=. 1
while. y do.
e=. (|.#:y) i.1
y=. <.y%2^e
t=. t*_1^(*/3 = 4|x,y)+(2|e)*(8|x) e.3 5
'x y'=. y, y|x
end.
t*x=1
}}"0
```

```   k=: 1 2 p. i. 30
n=: #\ k

k jacobi table n
+------+--------------------------------------------------------------------------------------+
|jacobi|1  2  3 4  5  6  7  8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30|
+------+--------------------------------------------------------------------------------------+
| 1    |1  1  1 1  1  1  1  1 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1|
| 3    |1 _1  0 1 _1  0  1 _1 0  1 _1  0  1 _1  0  1 _1  0  1 _1  0  1 _1  0  1 _1  0  1 _1  0|
| 5    |1 _1 _1 1  0  1 _1 _1 1  0  1 _1 _1  1  0  1 _1 _1  1  0  1 _1 _1  1  0  1 _1 _1  1  0|
| 7    |1  1 _1 1 _1 _1  0  1 1 _1  1 _1 _1  0  1  1 _1  1 _1 _1  0  1  1 _1  1 _1 _1  0  1  1|
| 9    |1  1  0 1  1  0  1  1 0  1  1  0  1  1  0  1  1  0  1  1  0  1  1  0  1  1  0  1  1  0|
|11    |1 _1  1 1  1 _1 _1 _1 1 _1  0  1 _1  1  1  1 _1 _1 _1  1 _1  0  1 _1  1  1  1 _1 _1 _1|
|13    |1 _1  1 1 _1 _1 _1 _1 1  1 _1  1  0  1 _1  1  1 _1 _1 _1 _1  1  1 _1  1  0  1 _1  1  1|
|15    |1  1  0 1  0  0 _1  1 0  0 _1  0 _1 _1  0  1  1  0  1  0  0 _1  1  0  0 _1  0 _1 _1  0|
|17    |1  1 _1 1 _1 _1 _1  1 1 _1 _1 _1  1 _1  1  1  0  1  1 _1  1 _1 _1 _1  1  1 _1 _1 _1  1|
|19    |1 _1 _1 1  1  1  1 _1 1 _1  1 _1 _1 _1 _1  1  1 _1  0  1 _1 _1  1  1  1  1 _1  1 _1  1|
|21    |1 _1  0 1  1  0  0 _1 0 _1 _1  0 _1  0  0  1  1  0 _1  1  0  1 _1  0  1  1  0  0 _1  0|
|23    |1  1  1 1 _1  1 _1  1 1 _1 _1  1  1 _1 _1  1 _1  1 _1 _1 _1 _1  0  1  1  1  1 _1  1 _1|
|25    |1  1  1 1  0  1  1  1 1  0  1  1  1  1  0  1  1  1  1  0  1  1  1  1  0  1  1  1  1  0|
|27    |1 _1  0 1 _1  0  1 _1 0  1 _1  0  1 _1  0  1 _1  0  1 _1  0  1 _1  0  1 _1  0  1 _1  0|
|29    |1 _1 _1 1  1  1  1 _1 1 _1 _1 _1  1 _1 _1  1 _1 _1 _1  1 _1  1  1  1  1 _1 _1  1  0  1|
|31    |1  1 _1 1  1 _1  1  1 1  1 _1 _1 _1  1 _1  1 _1  1  1  1 _1 _1 _1 _1  1 _1 _1  1 _1 _1|
|33    |1  1  0 1 _1  0 _1  1 0 _1  0  0 _1 _1  0  1  1  0 _1 _1  0  0 _1  0  1 _1  0 _1  1  0|
|35    |1 _1  1 1  0 _1  0 _1 1  0  1  1  1  0  0  1  1 _1 _1  0  0 _1 _1 _1  0 _1  1  0  1  0|
|37    |1 _1  1 1 _1 _1  1 _1 1  1  1  1 _1 _1 _1  1 _1 _1 _1 _1  1 _1 _1 _1  1  1  1  1 _1  1|
|39    |1  1  0 1  1  0 _1  1 0  1  1  0  0 _1  0  1 _1  0 _1  1  0  1 _1  0  1  0  0 _1 _1  0|
|41    |1  1 _1 1  1 _1 _1  1 1  1 _1 _1 _1 _1 _1  1 _1  1 _1  1  1 _1  1 _1  1 _1 _1 _1 _1 _1|
|43    |1 _1 _1 1 _1  1 _1 _1 1  1  1 _1  1  1  1  1  1 _1 _1 _1  1 _1  1  1  1 _1 _1 _1 _1 _1|
|45    |1 _1  0 1  0  0 _1 _1 0  0  1  0 _1  1  0  1 _1  0  1  0  0 _1 _1  0  0  1  0 _1  1  0|
|47    |1  1  1 1 _1  1  1  1 1 _1 _1  1 _1  1 _1  1  1  1 _1 _1  1 _1 _1  1  1 _1  1  1 _1 _1|
|49    |1  1  1 1  1  1  0  1 1  1  1  1  1  0  1  1  1  1  1  1  0  1  1  1  1  1  1  0  1  1|
|51    |1 _1  0 1  1  0 _1 _1 0 _1  1  0  1  1  0  1  0  0  1  1  0 _1  1  0  1 _1  0 _1  1  0|
|53    |1 _1 _1 1 _1  1  1 _1 1  1  1 _1  1 _1  1  1  1 _1 _1 _1 _1 _1 _1  1  1 _1 _1  1  1 _1|
|55    |1  1 _1 1  0 _1  1  1 1  0  0 _1  1  1  0  1  1  1 _1  0 _1  0 _1 _1  0  1 _1  1 _1  0|
|57    |1  1  0 1 _1  0  1  1 0 _1 _1  0 _1  1  0  1 _1  0  0 _1  0 _1 _1  0  1 _1  0  1  1  0|
|59    |1 _1  1 1  1 _1  1 _1 1 _1 _1  1 _1 _1  1  1  1 _1  1  1  1  1 _1 _1  1  1  1  1  1 _1|
+------+--------------------------------------------------------------------------------------+
```

## Java

```public class JacobiSymbol {

public static void main(String[] args) {
int max = 30;
System.out.printf("n\\k ");
for ( int k = 1 ; k <= max ; k++ ) {
System.out.printf("%2d  ", k);
}
System.out.printf("%n");
for ( int n = 1 ; n <= max ; n += 2 ) {
System.out.printf("%2d  ", n);
for ( int k = 1 ; k <= max ; k++ ) {
System.out.printf("%2d  ", jacobiSymbol(k, n));
}
System.out.printf("%n");
}
}

//  Compute (k n), where k is numerator
private static int jacobiSymbol(int k, int n) {
if ( k < 0 || n % 2 == 0 ) {
throw new IllegalArgumentException("Invalid value. k = " + k + ", n = " + n);
}
k %= n;
int jacobi = 1;
while ( k > 0 ) {
while ( k % 2 == 0 ) {
k /= 2;
int r = n % 8;
if ( r == 3 || r == 5 ) {
jacobi = -jacobi;
}
}
int temp = n;
n = k;
k = temp;
if ( k % 4 == 3 && n % 4 == 3 ) {
jacobi = -jacobi;
}
k %= n;
}
if ( n == 1 ) {
return jacobi;
}
return 0;
}

}
```
Output:
```n\k  1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30
1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
3   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0
5   1  -1  -1   1   0   1  -1  -1   1   0   1  -1  -1   1   0   1  -1  -1   1   0   1  -1  -1   1   0   1  -1  -1   1   0
7   1   1  -1   1  -1  -1   0   1   1  -1   1  -1  -1   0   1   1  -1   1  -1  -1   0   1   1  -1   1  -1  -1   0   1   1
9   1   1   0   1   1   0   1   1   0   1   1   0   1   1   0   1   1   0   1   1   0   1   1   0   1   1   0   1   1   0
11   1  -1   1   1   1  -1  -1  -1   1  -1   0   1  -1   1   1   1  -1  -1  -1   1  -1   0   1  -1   1   1   1  -1  -1  -1
13   1  -1   1   1  -1  -1  -1  -1   1   1  -1   1   0   1  -1   1   1  -1  -1  -1  -1   1   1  -1   1   0   1  -1   1   1
15   1   1   0   1   0   0  -1   1   0   0  -1   0  -1  -1   0   1   1   0   1   0   0  -1   1   0   0  -1   0  -1  -1   0
17   1   1  -1   1  -1  -1  -1   1   1  -1  -1  -1   1  -1   1   1   0   1   1  -1   1  -1  -1  -1   1   1  -1  -1  -1   1
19   1  -1  -1   1   1   1   1  -1   1  -1   1  -1  -1  -1  -1   1   1  -1   0   1  -1  -1   1   1   1   1  -1   1  -1   1
21   1  -1   0   1   1   0   0  -1   0  -1  -1   0  -1   0   0   1   1   0  -1   1   0   1  -1   0   1   1   0   0  -1   0
23   1   1   1   1  -1   1  -1   1   1  -1  -1   1   1  -1  -1   1  -1   1  -1  -1  -1  -1   0   1   1   1   1  -1   1  -1
25   1   1   1   1   0   1   1   1   1   0   1   1   1   1   0   1   1   1   1   0   1   1   1   1   0   1   1   1   1   0
27   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0
29   1  -1  -1   1   1   1   1  -1   1  -1  -1  -1   1  -1  -1   1  -1  -1  -1   1  -1   1   1   1   1  -1  -1   1   0   1
```

## jq

Translation of: Julia
```def lpad(\$len): tostring | (\$len - length) as \$l | (" " * \$l)[:\$l] + .;
def rpad(\$len): tostring | (\$len - length) as \$l | . + (" " * \$l)[:\$l];

def jacobi(a; n):
{a: (a % n), n: n, result: 1}
| until(.a == 0;
until( .a % 2 != 0;
.a /= 2
| if (.n % 8) | IN(3, 5) then .result *= -1 else . end )
| {a: .n, n: .a, result}   # swap .a and .n
| (.n % 4) as \$nmod4
| if (.a % 4) == \$nmod4 and \$nmod4 == 3 then .result *= -1 else . end
| .a = .a % .n )
| if .n == 1 then .result else 0 end ;

"                Table of jacobi(a; n)",
"n\\k   1   2   3   4   5   6   7   8   9  10  11  12",
"_____________________________________________________",
(range( 1; 32; 2) as \$n
| "\(\$n|rpad(3))" + reduce range(1; 13) as \$a (""; . + (jacobi(\$a; \$n) | lpad(4) ))
)```
Output:
```                Table of jacobi(a, n)
n\k   1   2   3   4   5   6   7   8   9  10  11  12
_____________________________________________________
1     1   1   1   1   1   1   1   1   1   1   1   1
3     1  -1   0   1  -1   0   1  -1   0   1  -1   0
5     1  -1  -1   1   0   1  -1  -1   1   0   1  -1
7     1   1  -1   1  -1  -1   0   1   1  -1   1  -1
9     1   1   0   1   1   0   1   1   0   1   1   0
11    1  -1   1   1   1  -1  -1  -1   1  -1   0   1
13    1  -1   1   1  -1  -1  -1  -1   1   1  -1   1
15    1   1   0   1   0   0  -1   1   0   0  -1   0
17    1   1  -1   1  -1  -1  -1   1   1  -1  -1  -1
19    1  -1  -1   1   1   1   1  -1   1  -1   1  -1
21    1  -1   0   1   1   0   0  -1   0  -1  -1   0
23    1   1   1   1  -1   1  -1   1   1  -1  -1   1
25    1   1   1   1   0   1   1   1   1   0   1   1
27    1  -1   0   1  -1   0   1  -1   0   1  -1   0
29    1  -1  -1   1   1   1   1  -1   1  -1  -1  -1
31    1   1  -1   1   1  -1   1   1   1   1  -1  -1```

## Julia

Translation of: Python
```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
for a in 1:11
end
end
```
Output:
``` Table of jacobi(a, n) for a 1 to 12, n 1 to 31
1   2   3   4   5   6   7   8   9  10  11  12
n
_____________________________________________________
1     1   1   1   1   1   1   1   1   1   1   1
3     1  -1   0   1  -1   0   1  -1   0   1  -1
5     1  -1  -1   1   0   1  -1  -1   1   0   1
7     1   1  -1   1  -1  -1   0   1   1  -1   1
9     1   1   0   1   1   0   1   1   0   1   1
11    1  -1   1   1   1  -1  -1  -1   1  -1   0
13    1  -1   1   1  -1  -1  -1  -1   1   1  -1
15    1   1   0   1   0   0  -1   1   0   0  -1
17    1   1  -1   1  -1  -1  -1   1   1  -1  -1
19    1  -1  -1   1   1   1   1  -1   1  -1   1
21    1  -1   0   1   1   0   0  -1   0  -1  -1
23    1   1   1   1  -1   1  -1   1   1  -1  -1
25    1   1   1   1   0   1   1   1   1   0   1
27    1  -1   0   1  -1   0   1  -1   0   1  -1
29    1  -1  -1   1   1   1   1  -1   1  -1  -1
31    1   1  -1   1   1  -1   1   1   1   1  -1
```

## Kotlin

```fun jacobi(A: Int, N: Int): Int {
assert(N > 0 && N and 1 == 1)
var a = A % N
var n = N
var result = 1
while (a != 0) {
var aMod4 = a and 3
while (aMod4 == 0) {    // remove factors of four
a = a shr 2
aMod4 = a and 3
}
if (aMod4 == 2) {       // if even
a = a shr 1         // remove factor 2 and possibly change sign
if ((n and 7).let { it == 3 || it == 5 })
result = -result
aMod4 = a and 3
}
if (aMod4 == 3 && n and 3 == 3)
result = -result
a = (n % a).also { n = a }
}
return if (n == 1) result else 0
}
```

## Lua

Translation of: ALGOL 68
```do -- Jacobi symbol - translation of the Algol 68 sample

local function jacobi( aIn, nIn )
if nIn <= 0 or nIn % 2 == 0 then
print( "The 'n' parameter of jacobi must be an odd positive integer." )
return 0
else
local a, n, result = aIn % nIn, nIn, 1
while a ~= 0 do
while a % 2 == 0 do
a = math.floor( a / 2 )
local nm8 = n % 8
if nm8 == 3 or nm8 == 5 then result = - result end
end
a, n = n, a;
if a % 4 == 3 and n % 4 == 3 then result = - result end
a = a % n
end
return n == 1 and result or 0
end
end

print( "Table of jacobi(a, n):" );
print( "n/a   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15" )
print( "---------------------------------------------------------------" )
for n = 1, 29, 2 do
io.write( string.format( "%3d", n ) )
for a = 1, 15 do io.write( string.format( "%4d", jacobi( a, n ) ) ) end
io.write( "\n" )
end

end
```
Output:
```Table of jacobi(a, n):
n/a   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
---------------------------------------------------------------
1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
3   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0
5   1  -1  -1   1   0   1  -1  -1   1   0   1  -1  -1   1   0
7   1   1  -1   1  -1  -1   0   1   1  -1   1  -1  -1   0   1
9   1   1   0   1   1   0   1   1   0   1   1   0   1   1   0
11   1  -1   1   1   1  -1  -1  -1   1  -1   0   1  -1   1   1
13   1  -1   1   1  -1  -1  -1  -1   1   1  -1   1   0   1  -1
15   1   1   0   1   0   0  -1   1   0   0  -1   0  -1  -1   0
17   1   1  -1   1  -1  -1  -1   1   1  -1  -1  -1   1  -1   1
19   1  -1  -1   1   1   1   1  -1   1  -1   1  -1  -1  -1  -1
21   1  -1   0   1   1   0   0  -1   0  -1  -1   0  -1   0   0
23   1   1   1   1  -1   1  -1   1   1  -1  -1   1   1  -1  -1
25   1   1   1   1   0   1   1   1   1   0   1   1   1   1   0
27   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0
29   1  -1  -1   1   1   1   1  -1   1  -1  -1  -1   1  -1  -1
```

## Mathematica / Wolfram Language

```TableForm[Table[JacobiSymbol[n, k], {n, 1, 17, 2}, {k, 16}],
TableHeadings -> {ReplacePart[Range[1, 17, 2], 1 -> "n=1"],
ReplacePart[Range[16], 1 -> "k=1"]}]
```
Output:

Produces a nicely typeset table.

## Nim

```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 ""
```
Output:
```n/k|  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
————————————————————————————————————————————————————————————————
1 |  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
3 |  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1
5 |  1 -1 -1  1  0  1 -1 -1  1  0  1 -1 -1  1  0  1 -1 -1  1  0
7 |  1  1 -1  1 -1 -1  0  1  1 -1  1 -1 -1  0  1  1 -1  1 -1 -1
9 |  1  1  0  1  1  0  1  1  0  1  1  0  1  1  0  1  1  0  1  1
11 |  1 -1  1  1  1 -1 -1 -1  1 -1  0  1 -1  1  1  1 -1 -1 -1  1
13 |  1 -1  1  1 -1 -1 -1 -1  1  1 -1  1  0  1 -1  1  1 -1 -1 -1
15 |  1  1  0  1  0  0 -1  1  0  0 -1  0 -1 -1  0  1  1  0  1  0
17 |  1  1 -1  1 -1 -1 -1  1  1 -1 -1 -1  1 -1  1  1  0  1  1 -1
19 |  1 -1 -1  1  1  1  1 -1  1 -1  1 -1 -1 -1 -1  1  1 -1  0  1
21 |  1 -1  0  1  1  0  0 -1  0 -1 -1  0 -1  0  0  1  1  0 -1  1```

## Perl

Translation of: Raku
```use strict;
use warnings;

sub J {
my(\$k,\$n) = @_;

\$k %= \$n;
my \$jacobi = 1;
while (\$k) {
while (0 == \$k % 2) {
\$k = int \$k / 2;
\$jacobi *= -1 if \$n%8 == 3 or \$n%8 == 5;
}
(\$k, \$n) = (\$n, \$k);
\$jacobi *= -1 if \$n%4 == 3 and \$k%4 == 3;
\$k %= \$n;
}
\$n == 1 ? \$jacobi : 0
}

my \$maxa = 1 + (my \$maxn = 29);

print 'n\k';
printf '%4d', \$_ for 1..\$maxa;
print "\n";
print '   ' . '-' x (4 * \$maxa) . "\n";

for my \$n (1..\$maxn) {
next if 0 == \$n % 2;
printf '%3d', \$n;
printf '%4d', J(\$_, \$n) for 1..\$maxa;
print "\n"
}
```
Output:
```n\k   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30
------------------------------------------------------------------------------------------------------------------------
1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
3   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0
5   1  -1  -1   1   0   1  -1  -1   1   0   1  -1  -1   1   0   1  -1  -1   1   0   1  -1  -1   1   0   1  -1  -1   1   0
7   1   1  -1   1  -1  -1   0   1   1  -1   1  -1  -1   0   1   1  -1   1  -1  -1   0   1   1  -1   1  -1  -1   0   1   1
9   1   1   0   1   1   0   1   1   0   1   1   0   1   1   0   1   1   0   1   1   0   1   1   0   1   1   0   1   1   0
11   1  -1   1   1   1  -1  -1  -1   1  -1   0   1  -1   1   1   1  -1  -1  -1   1  -1   0   1  -1   1   1   1  -1  -1  -1
13   1  -1   1   1  -1  -1  -1  -1   1   1  -1   1   0   1  -1   1   1  -1  -1  -1  -1   1   1  -1   1   0   1  -1   1   1
15   1   1   0   1   0   0  -1   1   0   0  -1   0  -1  -1   0   1   1   0   1   0   0  -1   1   0   0  -1   0  -1  -1   0
17   1   1  -1   1  -1  -1  -1   1   1  -1  -1  -1   1  -1   1   1   0   1   1  -1   1  -1  -1  -1   1   1  -1  -1  -1   1
19   1  -1  -1   1   1   1   1  -1   1  -1   1  -1  -1  -1  -1   1   1  -1   0   1  -1  -1   1   1   1   1  -1   1  -1   1
21   1  -1   0   1   1   0   0  -1   0  -1  -1   0  -1   0   0   1   1   0  -1   1   0   1  -1   0   1   1   0   0  -1   0
23   1   1   1   1  -1   1  -1   1   1  -1  -1   1   1  -1  -1   1  -1   1  -1  -1  -1  -1   0   1   1   1   1  -1   1  -1
25   1   1   1   1   0   1   1   1   1   0   1   1   1   1   0   1   1   1   1   0   1   1   1   1   0   1   1   1   1   0
27   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0
29   1  -1  -1   1   1   1   1  -1   1  -1  -1  -1   1  -1  -1   1  -1  -1  -1   1  -1   1   1   1   1  -1  -1   1   0   1```

## Phix

```with javascript_semantics
function jacobi(integer a, n)
atom result = 1
a = remainder(a,n)
while a!=0 do
while remainder(a,2)==0 do
a /= 2
if find(remainder(n,8),{3,5}) then result *= -1 end if
end while
{a, n} = {n, a}
if remainder(a,4)==3 and remainder(n,4)==3 then result *= -1 end if
a = remainder(a,n)
end while
return iff(n==1 ? result : 0)
end function

printf(1,"n\\a   0   1   2   3   4   5   6   7   8   9  10  11\n")
printf(1,"   ________________________________________________\n")
for n=1 to 31 by 2 do
printf(1,"%3d", n)
for a=0 to 11 do
printf(1,"%4d",jacobi(a, n))
end for
printf(1,"\n")
end for
```
Output:
```n\a   0   1   2   3   4   5   6   7   8   9  10  11
________________________________________________
1   1   1   1   1   1   1   1   1   1   1   1   1
3   0   1  -1   0   1  -1   0   1  -1   0   1  -1
5   0   1  -1  -1   1   0   1  -1  -1   1   0   1
7   0   1   1  -1   1  -1  -1   0   1   1  -1   1
9   0   1   1   0   1   1   0   1   1   0   1   1
11   0   1  -1   1   1   1  -1  -1  -1   1  -1   0
13   0   1  -1   1   1  -1  -1  -1  -1   1   1  -1
15   0   1   1   0   1   0   0  -1   1   0   0  -1
17   0   1   1  -1   1  -1  -1  -1   1   1  -1  -1
19   0   1  -1  -1   1   1   1   1  -1   1  -1   1
21   0   1  -1   0   1   1   0   0  -1   0  -1  -1
23   0   1   1   1   1  -1   1  -1   1   1  -1  -1
25   0   1   1   1   1   0   1   1   1   1   0   1
27   0   1  -1   0   1  -1   0   1  -1   0   1  -1
29   0   1  -1  -1   1   1   1   1  -1   1  -1  -1
31   0   1   1  -1   1   1  -1   1   1   1   1  -1
```

## PL/M

Translation of: Wren

...via Algol W.

Works with: 8080 PL/M Compiler

... under CP/M (or an emulator)

Note that although the 8080 PL/M compiler only supports unsigned integers, the unary minus operator produces a correct two's complement result, so for byte values, -1 = 255 and -255 = 1.

```100H: /* JACOBI SYMBOL                                                       */

/* CP/M BDOS SYSTEM CALLS AND I/O ROUTINES                                */
BDOS:   PROCEDURE( FN, ARG ); DECLARE FN BYTE, ARG ADDRESS; GOTO 5; END;
PR\$CHAR:   PROCEDURE( C ); DECLARE C BYTE;    CALL BDOS( 2, C );    END;
PR\$STRING: PROCEDURE( S ); DECLARE S ADDRESS; CALL BDOS( 9, S );    END;
PR\$NL:     PROCEDURE; CALL PR\$STRING( .( 0DH, 0AH, '\$' ) );         END;
PR\$NUMBER: PROCEDURE( N ); /* PRINTS A NUMBER IN THE MINIMUN FIELD WIDTH  */
DECLARE V ADDRESS, N\$STR ( 6 )BYTE, W BYTE;
V = N;
W = LAST( N\$STR );
N\$STR( W ) = '\$';
N\$STR( W := W - 1 ) = '0' + ( V MOD 10 );
DO WHILE( ( V := V / 10 ) > 0 );
N\$STR( W := W - 1 ) = '0' + ( V MOD 10 );
END;
CALL PR\$STRING( .N\$STR( W ) );
END PR\$NUMBER;

JACOBI: PROCEDURE( A\$IN, N\$IN )BYTE;
DECLARE ( A\$IN, N\$IN ) ADDRESS;
IF N\$IN MOD 2 <> 1 THEN DO;
CALL PR\$STRING( .'JACOBI PARAMETER NOT ODD\$' );
RETURN 0;
END;
ELSE DO;
DECLARE ( A, N, NM8, T ) ADDRESS;
DECLARE JS BYTE;
A = A\$IN MOD N\$IN; N = N\$IN; JS = 1;
DO WHILE A <> 0;
DO WHILE A MOD 2 = 0;
A = A / 2;
NM8 = N MOD 8;
IF NM8 = 3 OR NM8 = 5 THEN JS = - JS;
END;
T = A; A = N; N = T;
IF A MOD 4 = 3 AND N MOD 4 = 3 THEN JS = - JS;
A = A MOD N;
END;
IF N = 1 THEN RETURN JS;
ELSE RETURN 0;
END;
END JACOBI ;

DECLARE JS BYTE;

CALL PR\$STRING( .'TABLE OF JACOBI(A, N):\$' );CALL PR\$NL;
CALL PR\$STRING( .'N/A   1   2   3   4   5   6   7\$' );
CALL PR\$STRING( .'   8   9  10  11  12  13  14  15\$' );CALL PR\$NL;
CALL PR\$STRING( .'-------------------------------\$' );
CALL PR\$STRING( .'--------------------------------\$' );CALL PR\$NL;
DO N = 1 TO 29 BY 2;
CALL PR\$CHAR( ' ' );
IF N < 10 THEN CALL PR\$CHAR( ' ' );
CALL PR\$NUMBER( N );
DO A = 1 TO 15;
JS = JACOBI( A, N );
IF      JS = 0 THEN CALL PR\$STRING( .'   0\$' );
ELSE IF JS = 1 THEN CALL PR\$STRING( .'   1\$' );
ELSE                CALL PR\$STRING( .'  -1\$' );
END;
CALL PR\$NL;
END;

EOF```
Output:
```TABLE OF JACOBI(A, N):
N/A   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
---------------------------------------------------------------
1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
3   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0
5   1  -1  -1   1   0   1  -1  -1   1   0   1  -1  -1   1   0
7   1   1  -1   1  -1  -1   0   1   1  -1   1  -1  -1   0   1
9   1   1   0   1   1   0   1   1   0   1   1   0   1   1   0
11   1  -1   1   1   1  -1  -1  -1   1  -1   0   1  -1   1   1
13   1  -1   1   1  -1  -1  -1  -1   1   1  -1   1   0   1  -1
15   1   1   0   1   0   0  -1   1   0   0  -1   0  -1  -1   0
17   1   1  -1   1  -1  -1  -1   1   1  -1  -1  -1   1  -1   1
19   1  -1  -1   1   1   1   1  -1   1  -1   1  -1  -1  -1  -1
21   1  -1   0   1   1   0   0  -1   0  -1  -1   0  -1   0   0
23   1   1   1   1  -1   1  -1   1   1  -1  -1   1   1  -1  -1
25   1   1   1   1   0   1   1   1   1   0   1   1   1   1   0
27   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0
29   1  -1  -1   1   1   1   1  -1   1  -1  -1  -1   1  -1  -1
```

## Python

```def jacobi(a, n):
if n <= 0:
raise ValueError("'n' must be a positive integer.")
if n % 2 == 0:
raise ValueError("'n' must be odd.")
a %= n
result = 1
while a != 0:
while a % 2 == 0:
a /= 2
n_mod_8 = n % 8
if n_mod_8 in (3, 5):
result = -result
a, n = n, a
if a % 4 == 3 and n % 4 == 3:
result = -result
a %= n
if n == 1:
return result
else:
return 0
```

## Raku

(formerly Perl 6)

Works with: Rakudo version 2019.11
```# Jacobi function
sub infix:<J> (Int \$k is copy, Int \$n is copy where * % 2) {
\$k %= \$n;
my \$jacobi = 1;
while \$k {
while \$k %% 2 {
\$k div= 2;
\$jacobi *= -1 if \$n % 8 == 3 | 5;
}
(\$k, \$n) = \$n, \$k;
\$jacobi *= -1 if 3 == \$n%4 & \$k%4;
\$k %= \$n;
}
\$n == 1 ?? \$jacobi !! 0
}

# Testing

my \$maxa = 30;
my \$maxn = 29;

say 'n\k ', (1..\$maxa).fmt: '%3d';
say '   ', '-' x 4 * \$maxa;
for 1,*+2 … \$maxn -> \$n {
print \$n.fmt: '%3d';
for 1..\$maxa -> \$k {
print (\$k J \$n).fmt: '%4d';
}
print "\n";
}
```
Output:
```n\k   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30
------------------------------------------------------------------------------------------------------------------------
1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
3   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0
5   1  -1  -1   1   0   1  -1  -1   1   0   1  -1  -1   1   0   1  -1  -1   1   0   1  -1  -1   1   0   1  -1  -1   1   0
7   1   1  -1   1  -1  -1   0   1   1  -1   1  -1  -1   0   1   1  -1   1  -1  -1   0   1   1  -1   1  -1  -1   0   1   1
9   1   1   0   1   1   0   1   1   0   1   1   0   1   1   0   1   1   0   1   1   0   1   1   0   1   1   0   1   1   0
11   1  -1   1   1   1  -1  -1  -1   1  -1   0   1  -1   1   1   1  -1  -1  -1   1  -1   0   1  -1   1   1   1  -1  -1  -1
13   1  -1   1   1  -1  -1  -1  -1   1   1  -1   1   0   1  -1   1   1  -1  -1  -1  -1   1   1  -1   1   0   1  -1   1   1
15   1   1   0   1   0   0  -1   1   0   0  -1   0  -1  -1   0   1   1   0   1   0   0  -1   1   0   0  -1   0  -1  -1   0
17   1   1  -1   1  -1  -1  -1   1   1  -1  -1  -1   1  -1   1   1   0   1   1  -1   1  -1  -1  -1   1   1  -1  -1  -1   1
19   1  -1  -1   1   1   1   1  -1   1  -1   1  -1  -1  -1  -1   1   1  -1   0   1  -1  -1   1   1   1   1  -1   1  -1   1
21   1  -1   0   1   1   0   0  -1   0  -1  -1   0  -1   0   0   1   1   0  -1   1   0   1  -1   0   1   1   0   0  -1   0
23   1   1   1   1  -1   1  -1   1   1  -1  -1   1   1  -1  -1   1  -1   1  -1  -1  -1  -1   0   1   1   1   1  -1   1  -1
25   1   1   1   1   0   1   1   1   1   0   1   1   1   1   0   1   1   1   1   0   1   1   1   1   0   1   1   1   1   0
27   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0
29   1  -1  -1   1   1   1   1  -1   1  -1  -1  -1   1  -1  -1   1  -1  -1  -1   1  -1   1   1   1   1  -1  -1   1   0   1```

## REXX

Translation of: Go

A little extra code was added to make a prettier grid.

```/*REXX pgm computes/displays the Jacobi symbol, the # of rows & columns can be specified*/
parse arg rows cols .                            /*obtain optional arguments from the CL*/
if rows='' | rows==","  then rows= 17            /*Not specified?  Then use the default.*/
if cols='' | cols==","  then cols= 16            /* "      "         "   "   "      "   */
call hdrs                                        /*display the (two) headers to the term*/
do r=1  by 2  to rows;     _= right(r, 3)  /*build odd (numbered) rows of a table.*/
do c=0  to cols         /* [↓]  build a column for a table row.*/
_= _ ! right(jacobi(c, r), 2);   != '│'  /*reset grid end char.*/
end   /*c*/
say _ '║';  != '║'                         /*display a table row; reset grid glyph*/
end   /*r*/
say translate(@.2, '╩╧╝', "╬╤╗")                 /*display the bottom of the grid border*/
exit                                             /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
hdrs: @.1= 'n/a ║';      do c=0  to cols;    @.1= @.1 || right(c, 3)"  ";   end
L= length(@.1);                        @.1= left(@.1,   L - 1)    ;          say @.1
@.2= '════╬';      do c=0  to cols;    @.2= @.2 || "════╤"        ;   end
L= length(@.2);                        @.2= left(@.2,   L - 1)"╗" ;          say @.2
!= '║'        ;    return                  /*define an external grid border glyph.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
jacobi: procedure; parse arg a,n;  er= '***error***';        \$ = 1      /*define result.*/
if n//2==0  then do;   say er    n   " must be a positive odd integer.";   exit 13
end
a= a // n                                      /*obtain  A  modulus  N          */
do while a\==0                               /*perform while  A  isn't zero.  */
do while a//2==0;  a= a % 2   /*divide  A  (as a integer) by 2 */
if n//8==3 | n//8==5  then \$= -\$               /*use  N mod  8 */
end   /*while a//2==0*/
parse value  a  n     with     n  a          /*swap values of variables:  A N */
if a//4==3 & n//4==3  then \$= -\$             /* A mod 4, N mod 4.   Both ≡ 3 ?*/
a= a // n                                    /*obtain  A  modulus  N          */
end   /*while a\==0*/
if n==1  then return \$
return 0
```
output   when using the default inputs:
```n/a ║  0    1    2    3    4    5    6    7    8    9   10   11   12   13   14   15   16
════╬════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╗
1 ║  1 │  1 │  1 │  1 │  1 │  1 │  1 │  1 │  1 │  1 │  1 │  1 │  1 │  1 │  1 │  1 │  1 ║
3 ║  0 │  1 │ -1 │  0 │  1 │ -1 │  0 │  1 │ -1 │  0 │  1 │ -1 │  0 │  1 │ -1 │  0 │  1 ║
5 ║  0 │  1 │ -1 │ -1 │  1 │  0 │  1 │ -1 │ -1 │  1 │  0 │  1 │ -1 │ -1 │  1 │  0 │  1 ║
7 ║  0 │  1 │  1 │ -1 │  1 │ -1 │ -1 │  0 │  1 │  1 │ -1 │  1 │ -1 │ -1 │  0 │  1 │  1 ║
9 ║  0 │  1 │  1 │  0 │  1 │  1 │  0 │  1 │  1 │  0 │  1 │  1 │  0 │  1 │  1 │  0 │  1 ║
11 ║  0 │  1 │ -1 │  1 │  1 │  1 │ -1 │ -1 │ -1 │  1 │ -1 │  0 │  1 │ -1 │  1 │  1 │  1 ║
13 ║  0 │  1 │ -1 │  1 │  1 │ -1 │ -1 │ -1 │ -1 │  1 │  1 │ -1 │  1 │  0 │  1 │ -1 │  1 ║
15 ║  0 │  1 │  1 │  0 │  1 │  0 │  0 │ -1 │  1 │  0 │  0 │ -1 │  0 │ -1 │ -1 │  0 │  1 ║
17 ║  0 │  1 │  1 │ -1 │  1 │ -1 │ -1 │ -1 │  1 │  1 │ -1 │ -1 │ -1 │  1 │ -1 │  1 │  1 ║
════╩════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╝
```

## Ruby

Translation of: Crystal
```def jacobi(a, n)
raise ArgumentError.new "n must b positive and odd" if n < 1 || n.even?
res = 1
until (a %= n) == 0
while a.even?
a >>= 1
res = -res if [3, 5].include? n % 8
end
a, n = n, a
res = -res if [a % 4, n % 4] == [3, 3]
end
n == 1 ? res : 0
end

puts "Jacobian symbols for jacobi(a, n)"
puts "n\\a  0  1  2  3  4  5  6  7  8  9 10"
puts "------------------------------------"
1.step(to: 17, by: 2) do |n|
printf("%2d ", n)
(0..10).each { |a| printf(" % 2d", jacobi(a, n)) }
puts
end
```
Output:
```Jacobian symbols for jacobi(a, n)
n\a  0  1  2  3  4  5  6  7  8  9 10
------------------------------------
1   1  1  1  1  1  1  1  1  1  1  1
3   0  1 -1  0  1 -1  0  1 -1  0  1
5   0  1 -1 -1  1  0  1 -1 -1  1  0
7   0  1  1 -1  1 -1 -1  0  1  1 -1
9   0  1  1  0  1  1  0  1  1  0  1
11   0  1 -1  1  1  1 -1 -1 -1  1 -1
13   0  1 -1  1  1 -1 -1 -1 -1  1  1
15   0  1  1  0  1  0  0 -1  1  0  0
17   0  1  1 -1  1 -1 -1 -1  1  1 -1```

## Rust

Translation of: C++
```fn jacobi(mut n: i32, mut k: i32) -> i32 {
assert!(k > 0 && k % 2 == 1);
n %= k;
let mut t = 1;
while n != 0 {
while n % 2 == 0 {
n /= 2;
let r = k % 8;
if r == 3 || r == 5 {
t = -t;
}
}
std::mem::swap(&mut n, &mut k);
if n % 4 == 3 && k % 4 == 3 {
t = -t;
}
n %= k;
}
if k == 1 {
t
} else {
0
}
}

fn print_table(kmax: i32, nmax: i32) {
print!("n\\k|");
for k in 0..=kmax {
print!(" {:2}", k);
}
print!("\n----");
for _ in 0..=kmax {
print!("---");
}
println!();
for n in (1..=nmax).step_by(2) {
print!("{:2} |", n);
for k in 0..=kmax {
print!(" {:2}", jacobi(k, n));
}
println!();
}
}

fn main() {
print_table(20, 21);
}
```
Output:
```n\k|  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
-------------------------------------------------------------------
1 |  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
3 |  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1
5 |  0  1 -1 -1  1  0  1 -1 -1  1  0  1 -1 -1  1  0  1 -1 -1  1  0
7 |  0  1  1 -1  1 -1 -1  0  1  1 -1  1 -1 -1  0  1  1 -1  1 -1 -1
9 |  0  1  1  0  1  1  0  1  1  0  1  1  0  1  1  0  1  1  0  1  1
11 |  0  1 -1  1  1  1 -1 -1 -1  1 -1  0  1 -1  1  1  1 -1 -1 -1  1
13 |  0  1 -1  1  1 -1 -1 -1 -1  1  1 -1  1  0  1 -1  1  1 -1 -1 -1
15 |  0  1  1  0  1  0  0 -1  1  0  0 -1  0 -1 -1  0  1  1  0  1  0
17 |  0  1  1 -1  1 -1 -1 -1  1  1 -1 -1 -1  1 -1  1  1  0  1  1 -1
19 |  0  1 -1 -1  1  1  1  1 -1  1 -1  1 -1 -1 -1 -1  1  1 -1  0  1
21 |  0  1 -1  0  1  1  0  0 -1  0 -1 -1  0 -1  0  0  1  1  0 -1  1
```

## Scala

```def jacobi(a_p: Int, n_p: Int): Int =
{
var a = a_p
var n = n_p
if (n <= 0) return -1
if (n % 2 == 0) return -1

a %= n
var result = 1
while (a != 0) {
while (a % 2 == 0) {
a /= 2
if (n % 8 == 3 || n % 8 == 5) result = -result
}
val t = a
a = n
n = t
if (a % 4 == 3 && n % 4 == 3) result = -result
a %= n
}
if (n != 1) result = 0

result
}

def main(args: Array[String]): Unit =
{
for {
a <- 0 until 11
n <- 1 until 31 by 2
} yield println("n = " + n + ", a = " + a + ": " + jacobi(a, n))
}
```
output:
```n = 1, a = 0: 1

n = 3, a = 0: 0

n = 5, a = 0: 0

n = 7, a = 0: 0

n = 9, a = 0: 0

n = 1, a = 1: 1

n = 3, a = 1: 1

n = 5, a = 1: 1

n = 7, a = 1: 1

n = 9, a = 1: 1

n = 1, a = 2: 1

n = 3, a = 2: -1

n = 5, a = 2: -1

n = 7, a = 2: 1

n = 9, a = 2: 1

n = 1, a = 3: 1

n = 3, a = 3: 0

n = 5, a = 3: -1

n = 7, a = 3: -1

n = 9, a = 3: 0

n = 1, a = 4: 1

n = 3, a = 4: 1

n = 5, a = 4: 1

n = 7, a = 4: 1

n = 9, a = 4: 1

n = 1, a = 5: 1

n = 3, a = 5: -1

n = 5, a = 5: 0

n = 7, a = 5: -1

n = 9, a = 5: 1

n = 1, a = 6: 1

n = 3, a = 6: 0

n = 5, a = 6: 1

n = 7, a = 6: -1

n = 9, a = 6: 0

n = 1, a = 7: 1

n = 3, a = 7: 1

n = 5, a = 7: -1

n = 7, a = 7: 0

n = 9, a = 7: 1

n = 1, a = 8: 1

n = 3, a = 8: -1

n = 5, a = 8: -1

n = 7, a = 8: 1

n = 9, a = 8: 1

n = 1, a = 9: 1

n = 3, a = 9: 0

n = 5, a = 9: 1

n = 7, a = 9: 1

n = 9, a = 9: 0

n = 1, a = 10: 1

n = 3, a = 10: 1

n = 5, a = 10: 0

n = 7, a = 10: -1

n = 9, a = 10: 1
```

## Scheme

```(define jacobi (lambda (a n)
(let ((a-mod-n (modulo a n)))
(if (zero? a-mod-n)
(if (= n 1)
1
0)
(if (even? a-mod-n)
(case (modulo n 8)
((3 5) (- (jacobi (/ a-mod-n 2) n)))
((1 7) (jacobi (/ a-mod-n 2) n)))
(if (and (= (modulo a-mod-n 4) 3) (= (modulo n 4) 3))
(- (jacobi n a-mod-n))
(jacobi n a-mod-n)))))))
```

## Sidef

Also built-in as kronecker(n,k).

```func jacobi(a, n) {

assert(n > 0,    "#{n} must be positive")
assert(n.is_odd, "#{n} must be odd")

var t = 1
while (a %= n) {
if (a.is_even) {
var v = a.valuation(2)
t *= (-1)**v if (n%8 ~~ [3,5])
a >>= v
}
(a,n) = (n,a)
t = -t if ([a%4, n%4] == [3,3])
}

n==1 ? t : 0
}

for a in (0..50), n in (0..50) {
assert_eq(jacobi(a, 2*n + 1), kronecker(a, 2*n + 1))
}
```

## Swift

```import Foundation

func jacobi(a: Int, n: Int) -> Int {
var a = a % n
var n = n
var res = 1

while a != 0 {
while a & 1 == 0 {
a >>= 1

if n % 8 == 3 || n % 8 == 5 {
res = -res
}
}

(a, n) = (n, a)

if a % 4 == 3 && n % 4 == 3 {
res = -res
}

a %= n
}

return n == 1 ? res : 0
}

print("n/a  0  1  2  3  4  5  6  7  8  9")
print("---------------------------------")

for n in stride(from: 1, through: 17, by: 2) {
print(String(format: "%2d", n), terminator: "")

for a in 0..<10 {
print(String(format: " % d", jacobi(a: a, n: n)), terminator: "")
}

print()
}
```
Output:
```n/a  0  1  2  3  4  5  6  7  8  9
---------------------------------
1  1  1  1  1  1  1  1  1  1  1
3  0  1 -1  0  1 -1  0  1 -1  0
5  0  1 -1 -1  1  0  1 -1 -1  1
7  0  1  1 -1  1 -1 -1  0  1  1
9  0  1  1  0  1  1  0  1  1  0
11  0  1 -1  1  1  1 -1 -1 -1  1
13  0  1 -1  1  1 -1 -1 -1 -1  1
15  0  1  1  0  1  0  0 -1  1  0
17  0  1  1 -1  1 -1 -1 -1  1  1```

## V (Vlang)

Translation of: Go
```fn jacobi(aa u64, na u64) ?int {
mut a := aa
mut n := na
if n%2 == 0 {
return error("'n' must be a positive odd integer")
}
a %= n
mut result := 1
for a != 0 {
for a%2 == 0 {
a /= 2
nn := n % 8
if nn == 3 || nn == 5 {
result = -result
}
}
a, n = n, a
if a%4 == 3 && n%4 == 3 {
result = -result
}
a %= n
}
if n == 1 {
return result
}
return 0
}

fn main() {
println("Using hand-coded version:")
println("n/a  0  1  2  3  4  5  6  7  8  9")
println("---------------------------------")
for n := u64(1); n <= 17; n += 2 {
print("\${n:2} ")
for a := u64(0); a <= 9; a++ {
t := jacobi(a, n)?
print(" \${t:2}")
}
println('')
}
}```
Output:
```n/a  0  1  2  3  4  5  6  7  8  9
---------------------------------
1   1  1  1  1  1  1  1  1  1  1
3   0  1 -1  0  1 -1  0  1 -1  0
5   0  1 -1 -1  1  0  1 -1 -1  1
7   0  1  1 -1  1 -1 -1  0  1  1
9   0  1  1  0  1  1  0  1  1  0
11   0  1 -1  1  1  1 -1 -1 -1  1
13   0  1 -1  1  1 -1 -1 -1 -1  1
15   0  1  1  0  1  0  0 -1  1  0
17   0  1  1 -1  1 -1 -1 -1  1  1
```

## Wren

Translation of: Python
Library: Wren-fmt
```import "./fmt" for Fmt

var jacobi = Fn.new { |a, n|
if (!n.isInteger || n <= 0 || n%2 == 0) {
Fiber.abort("The 'n' parameter must be an odd positive integer.")
}
a = a % n
var result = 1
while (a != 0) {
while (a%2  == 0) {
a = a / 2
var nm8 = n % 8
if ([3, 5].contains(nm8)) result = -result
}
var t = a
a = n
n = t
if (a%4 == 3 && n%4 == 3) result = -result
a = a % n
}
return (n == 1) ? result : 0
}

System.print("Table of jacobi(a, n):")
System.print("n/a   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15")
System.print("---------------------------------------------------------------")
var n = 1
while (n < 31) {
Fmt.write("\$3d", n)
for (a in 1..15) Fmt.write("\$4d", jacobi.call(a, n))
System.print()
n = n + 2
}
```
Output:
```Table of jacobi(a, n):
n/a   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
---------------------------------------------------------------
1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
3   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0
5   1  -1  -1   1   0   1  -1  -1   1   0   1  -1  -1   1   0
7   1   1  -1   1  -1  -1   0   1   1  -1   1  -1  -1   0   1
9   1   1   0   1   1   0   1   1   0   1   1   0   1   1   0
11   1  -1   1   1   1  -1  -1  -1   1  -1   0   1  -1   1   1
13   1  -1   1   1  -1  -1  -1  -1   1   1  -1   1   0   1  -1
15   1   1   0   1   0   0  -1   1   0   0  -1   0  -1  -1   0
17   1   1  -1   1  -1  -1  -1   1   1  -1  -1  -1   1  -1   1
19   1  -1  -1   1   1   1   1  -1   1  -1   1  -1  -1  -1  -1
21   1  -1   0   1   1   0   0  -1   0  -1  -1   0  -1   0   0
23   1   1   1   1  -1   1  -1   1   1  -1  -1   1   1  -1  -1
25   1   1   1   1   0   1   1   1   1   0   1   1   1   1   0
27   1  -1   0   1  -1   0   1  -1   0   1  -1   0   1  -1   0
29   1  -1  -1   1   1   1   1  -1   1  -1  -1  -1   1  -1  -1
```

## XPL0

Translation of: C
```func Jacobi(A, N);
int A, N, Result, T;
[if A >= N then A:= rem(A/N);
Result:= 1;
while A do
[while (A&1) = 0 do
[A:= A >> 1;
if (N&7) = 3 or (N&7) = 5 then Result:= -Result;
];
T:= A;  A:= N;  N:= T;
if (A&3) = 3 and (N&3) = 3 then Result:= -Result;
A:= rem(A/N);
];
if N = 1 then return Result;
return 0;
];

proc PrintTable(KMax, NMax);
int  KMax, NMax, K, N;
[Text(0, "N\K|");
Format(3, 0);
for K:= 0 to KMax do RlOut(0, float(K));
CrLf(0);
Text(0, "----");
for K:= 0 to KMax do Text(0, "---");
CrLf(0);
for N:= 1 to NMax do
[Format(2, 0);
RlOut(0, float(N));
Text(0, " |");
Format(3, 0);
for K:= 0 to KMax do
RlOut(0, float(Jacobi(K, N)));
CrLf(0);
N:= N+1;
];
];

PrintTable(20, 21);```
Output:
```N\K|  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
-------------------------------------------------------------------
1 |  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
3 |  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1  0  1 -1
5 |  0  1 -1 -1  1  0  1 -1 -1  1  0  1 -1 -1  1  0  1 -1 -1  1  0
7 |  0  1  1 -1  1 -1 -1  0  1  1 -1  1 -1 -1  0  1  1 -1  1 -1 -1
9 |  0  1  1  0  1  1  0  1  1  0  1  1  0  1  1  0  1  1  0  1  1
11 |  0  1 -1  1  1  1 -1 -1 -1  1 -1  0  1 -1  1  1  1 -1 -1 -1  1
13 |  0  1 -1  1  1 -1 -1 -1 -1  1  1 -1  1  0  1 -1  1  1 -1 -1 -1
15 |  0  1  1  0  1  0  0 -1  1  0  0 -1  0 -1 -1  0  1  1  0  1  0
17 |  0  1  1 -1  1 -1 -1 -1  1  1 -1 -1 -1  1 -1  1  1  0  1  1 -1
19 |  0  1 -1 -1  1  1  1  1 -1  1 -1  1 -1 -1 -1 -1  1  1 -1  0  1
21 |  0  1 -1  0  1  1  0  0 -1  0 -1 -1  0 -1  0  0  1  1  0 -1  1
```

## zkl

```fcn jacobi(a,n){
if(n.isEven or n<1)
throw(Exception.ValueError("'n' must be a positive odd integer"));
a=a%n;   result,t := 1,0;
while(a!=0){
while(a.isEven){
a/=2;   n_mod_8:=n%8;
if(n_mod_8==3 or n_mod_8==5) result=-result;
}
t,a,n = a,n,t;
if(a%4==3 and n%4==3) result=-result;
a=a%n;
}
if(n==1) result else 0
}```
```println("Using hand-coded version:");
println("n/a  0  1  2  3  4  5  6  7  8  9");
println("---------------------------------");
foreach n in ([1..17,2]){
print("%2d ".fmt(n));
foreach a in (10){ print(" % d".fmt(jacobi(a,n))) }
println();
}```
Library: GMP

GNU Multiple Precision Arithmetic Library

```var [const] BI=Import.lib("zklBigNum");  // libGMP
println("\nUsing BigInt library function:");
println("n/a  0  1  2  3  4  5  6  7  8  9");
println("---------------------------------");
foreach n in ([1..17,2]){
print("%2d ".fmt(n));
foreach a in (10){ print(" % d".fmt(BI(a).jacobi(n))) }
println();
}```
Output:
```Using hand-coded version:
n/a  0  1  2  3  4  5  6  7  8  9
---------------------------------
1   1  1  1  1  1  1  1  1  1  1
3   0  1 -1  0  1 -1  0  1 -1  0
5   0  1 -1 -1  1  0  1 -1 -1  1
7   0  1  1 -1  1 -1 -1  0  1  1
9   0  1  1  0  1  1  0  1  1  0
11   0  1 -1  1  1  1 -1 -1 -1  1
13   0  1 -1  1  1 -1 -1 -1 -1  1
15   0  1  1  0  1  0  0 -1  1  0
17   0  1  1 -1  1 -1 -1 -1  1  1

Using BigInt library function:
n/a  0  1  2  3  4  5  6  7  8  9
---------------------------------
1   1  1  1  1  1  1  1  1  1  1
3   0  1 -1  0  1 -1  0  1 -1  0
5   0  1 -1 -1  1  0  1 -1 -1  1
7   0  1  1 -1  1 -1 -1  0  1  1
9   0  1  1  0  1  1  0  1  1  0
11   0  1 -1  1  1  1 -1 -1 -1  1
13   0  1 -1  1  1 -1 -1 -1 -1  1
15   0  1  1  0  1  0  0 -1  1  0
17   0  1  1 -1  1 -1 -1 -1  1  1
```