Jacobi symbol: Difference between revisions

From Rosetta Code
Content added Content deleted
 
(18 intermediate revisions by 9 users not shown)
Line 16: Line 16:
{{trans|Python}}
{{trans|Python}}


<lang 11l>F jacobi(=a, =n)
<syntaxhighlight lang="11l">F jacobi(=a, =n)
I n <= 0
I n <= 0
X ValueError(‘'n' must be a positive integer.’)
X.throw ValueError(‘'n' must be a positive integer.’)
I n % 2 == 0
I n % 2 == 0
X ValueError(‘'n' must be odd.’)
X.throw ValueError(‘'n' must be odd.’)
a %= n
a %= n
V result = 1
V result = 1
Line 50: Line 50:
L(k) 0..kmax
L(k) 0..kmax
print(‘#3’.format(jacobi(k, n)), end' ‘’)
print(‘#3’.format(jacobi(k, n)), end' ‘’)
print()</lang>
print()</syntaxhighlight>


{{out}}
{{out}}
Line 71: Line 71:
=={{header|Action!}}==
=={{header|Action!}}==
{{libheader|Action! Tool Kit}}
{{libheader|Action! Tool Kit}}
<lang Action!>INCLUDE "D2:PRINTF.ACT" ;from the Action! Tool Kit
<syntaxhighlight lang="action!">INCLUDE "D2:PRINTF.ACT" ;from the Action! Tool Kit


INT FUNC Jacobi(INT a,n)
INT FUNC Jacobi(INT a,n)
Line 136: Line 136:
Put(125) PutE() ;clear the screen
Put(125) PutE() ;clear the screen
PrintTable(10,39)
PrintTable(10,39)
RETURN</lang>
RETURN</syntaxhighlight>
{{out}}
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Jacobi_symbol.png Screenshot from Atari 8-bit computer]
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Jacobi_symbol.png Screenshot from Atari 8-bit computer]
Line 162: Line 162:
37│ 0 1 -1 -1 1 -1 1 1 -1 1 1
37│ 0 1 -1 -1 1 -1 1 1 -1 1 1
39│ 0 1 1 0 1 1 0 1 1 0 1
39│ 0 1 1 0 1 1 0 1 1 0 1
</pre>

=={{header|ALGOL 68}}==
{{Trans|Wren}}
<syntaxhighlight lang="algol68">
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
</syntaxhighlight>
{{out}}
<pre>
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
</pre>

=={{header|ALGOL W}}==
{{Trans|Wren}}
<syntaxhighlight lang="algolw">
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.
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
</pre>


=={{header|Arturo}}==
=={{header|Arturo}}==
{{trans|Nim}}
{{trans|Nim}}
<lang rebol>jacobi: function [n,k][
<syntaxhighlight lang="rebol">jacobi: function [n,k][
N: n % k
N: n % k
K: k
K: k
Line 195: Line 314:
'item -> pad.left item 2
'item -> pad.left item 2
]
]
]</lang>
]</syntaxhighlight>


{{out}}
{{out}}
Line 211: Line 330:
17 | 1 1 -1 1 -1 -1 -1 1 1 -1 -1 -1 1 -1 1 1 0 1 1 -1
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
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</pre>
21 | 1 -1 0 1 1 0 0 -1 0 -1 -1 0 -1 0 0 1 1 0 -1 1
</pre>

=={{header|AutoHotkey}}==
<syntaxhighlight lang="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
}</syntaxhighlight>
{{out}}
<pre>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 </pre>


=={{header|AWK}}==
=={{header|AWK}}==
{{trans|Go}}
{{trans|Go}}
<syntaxhighlight lang="awk">
<lang AWK>
# syntax: GAWK -f JACOBI_SYMBOL.AWK
# syntax: GAWK -f JACOBI_SYMBOL.AWK
BEGIN {
BEGIN {
Line 262: Line 431:
return(0)
return(0)
}
}
</syntaxhighlight>
</lang>
{{out}}
{{out}}
<pre>
<pre>
Line 285: Line 454:


=={{header|C}}==
=={{header|C}}==
<lang c>#include <stdlib.h>
<syntaxhighlight lang="c">#include <stdlib.h>
#include <stdio.h>
#include <stdio.h>


Line 323: Line 492:
print_table(20, 21);
print_table(20, 21);
return 0;
return 0;
}</lang>
}</syntaxhighlight>


{{out}}
{{out}}
Line 344: Line 513:


=={{header|C++}}==
=={{header|C++}}==
<lang cpp>#include <algorithm>
<syntaxhighlight lang="cpp">#include <algorithm>
#include <cassert>
#include <cassert>
#include <iomanip>
#include <iomanip>
Line 387: Line 556:
print_table(std::cout, 20, 21);
print_table(std::cout, 20, 21);
return 0;
return 0;
}</lang>
}</syntaxhighlight>


{{out}}
{{out}}
Line 408: Line 577:
=={{header|Crystal}}==
=={{header|Crystal}}==
{{trans|Swift}}
{{trans|Swift}}
<lang ruby>def jacobi(a, n)
<syntaxhighlight lang="ruby">def jacobi(a, n)
raise ArgumentError.new "n must b positive and odd" if n < 1 || n.even?
raise ArgumentError.new "n must b positive and odd" if n < 1 || n.even?
res = 1
res = 1
Line 429: Line 598:
(0..10).each { |a| printf(" % 2d", jacobi(a, n)) }
(0..10).each { |a| printf(" % 2d", jacobi(a, n)) }
puts
puts
end</lang>
end</syntaxhighlight>


{{out}}
{{out}}
Line 448: Line 617:


=={{header|Erlang}}==
=={{header|Erlang}}==
<syntaxhighlight lang="erlang">
<lang Erlang>
jacobi(_, N) when N =< 0 -> jacobi_domain_error;
jacobi(_, N) when N =< 0 -> jacobi_domain_error;
jacobi(_, N) when (N band 1) =:= 0 -> jacobi_domain_error;
jacobi(_, N) when (N band 1) =:= 0 -> jacobi_domain_error;
Line 476: Line 645:
false -> J2
false -> J2
end.
end.
</syntaxhighlight>
</lang>


=={{header|F_Sharp|F#}}==
=={{header|F_Sharp|F#}}==
<lang fsharp>
<syntaxhighlight lang="fsharp">
//Jacobi Symbol. Nigel Galloway: July 14th., 2020
//Jacobi Symbol. Nigel Galloway: July 14th., 2020
let J n m=let rec J n m g=match n with
let J n m=let rec J n m g=match n with
Line 488: Line 657:
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 ----------------------------------------------------------------------------------------------------------------------"
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 "")
[1..2..29]|>List.iter(fun m->printf "%3d" m; [1..30]|>List.iter(fun n->printf "%4d" (J n m)); printfn "")
</syntaxhighlight>
</lang>
{{out}}
{{out}}
<pre style="font-size: 12px">
<pre>
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\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
----------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------
Line 514: Line 683:


=={{header|FreeBASIC}}==
=={{header|FreeBASIC}}==
<lang freebasic>function gcdp( a as uinteger, b as uinteger ) as uinteger
<syntaxhighlight lang="freebasic">function gcdp( a as uinteger, b as uinteger ) as uinteger
if b = 0 then return a
if b = 0 then return a
return gcdp( b, a mod b )
return gcdp( b, a mod b )
Line 558: Line 727:
next k
next k
print outstr
print outstr
next pn</lang>
next pn</syntaxhighlight>
{{out}}
{{out}}
<pre> 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
<pre style="font-size: 11px"> 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
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
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
Line 584: Line 753:


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.
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.
<lang go>package main
<syntaxhighlight lang="go">package main


import (
import (
Line 643: Line 812:
fmt.Println()
fmt.Println()
}
}
}</lang>
}</syntaxhighlight>


{{out}}
{{out}}
Line 676: Line 845:
=={{header|Haskell}}==
=={{header|Haskell}}==
{{trans|Scheme}}
{{trans|Scheme}}
<lang haskell>jacobi :: Integer -> Integer -> Integer
<syntaxhighlight lang="haskell">jacobi :: Integer -> Integer -> Integer
jacobi 0 1 = 1
jacobi 0 1 = 1
jacobi 0 _ = 0
jacobi 0 _ = 0
Line 689: Line 858:
else if rem a_mod_n 4 == 3 && rem n 4 == 3
else if rem a_mod_n 4 == 3 && rem n 4 == 3
then negate $ jacobi n a_mod_n
then negate $ jacobi n a_mod_n
else jacobi n a_mod_n</lang>
else jacobi n a_mod_n</syntaxhighlight>




Or, expressing it slightly differently, and adding a tabulation:
Or, expressing it slightly differently, and adding a tabulation:
<lang haskell>import Data.Bool (bool)
<syntaxhighlight lang="haskell">import Data.Bool (bool)
import Data.List (replicate, transpose)
import Data.List (replicate, transpose)
import Data.List.Split (chunksOf)
import Data.List.Split (chunksOf)
Line 764: Line 933:


justifyRight :: Int -> a -> [a] -> [a]
justifyRight :: Int -> a -> [a] -> [a]
justifyRight n c = (drop . length) <*> (replicate n c <>)</lang>
justifyRight n c = (drop . length) <*> (replicate n c <>)</syntaxhighlight>
{{Out}}
{{Out}}
<pre> 0 1 2 3 4 5 6 7 8 9 10
<pre> 0 1 2 3 4 5 6 7 8 9 10
Line 779: Line 948:


=={{header|J}}==
=={{header|J}}==
<syntaxhighlight lang="j">
<lang J>
NB. direct translation of the Lua program found
NB. functionally equivalent translation of the Lua program found
NB. at https://en.wikipedia.org/wiki/Jacobi_symbol
NB. at the wikipedia entry incorporated here in comments.
jacobi=: {{

NB.function jacobi(n, k)
jacobi=: dyad define every

k=. x NB. k is the left argument
n=. y NB. n is the right hand argument

NB.assert(k > 0 and k % 2 == 1)
assert. (k > 0) *. 1 = 2 | k

NB.n = n % k
n =. k | n

NB.t = 1
t =. 1

NB.while n ~= 0 do
while. n do.

NB. while n % 2 == 0 do
while. -. 2 | n do.

NB. n = n / 2
n =. <. n % 2
NB. r = k % 8
r =. 8 | k

NB. if r == 3 or r == 5 then
if. r e. 3 5 do.

NB. t = -t
t =. -t

NB. end
end.

NB. end
end.

NB. n, k = k, n
'n k' =. k , n

NB. if n % 4 == 3 and k % 4 == 3 then
if. (3 = 4 | n) *. (3 = 4 | k) do.

NB. t = -t
t =. -t

NB. end
end.

NB. n = n % k
n =. k | n

NB.end
end.

NB.if k == 1 then
if. k = 1 do.

NB. return t
t

NB.else
else.

NB. return 0
0

NB.end
end.

NB.end
)
</lang>

Here's a more compact (but functionally equivalent) translation of that lua implementation:

<lang J>jacobi=: {{
assert. (0<x) * 1=2|x
assert. (0<x) * 1=2|x
y=. x|y
y=. x|y
Line 868: Line 958:
e=. (|.#:y) i.1
e=. (|.#:y) i.1
y=. <.y%2^e
y=. <.y%2^e
t=. t*_1^(2|e)*(8|x) e.3 5
t=. t*_1^(*/3 = 4|x,y)+(2|e)*(8|x) e.3 5
t=. t*_1^*/3 = 4|x,y
'x y'=. y, y|x
'x y'=. y, y|x
end.
end.
t*x=1
t*x=1
}}&></lang>
}}"0</syntaxhighlight>




Line 918: Line 1,007:


=={{header|Java}}==
=={{header|Java}}==
<lang java>
<syntaxhighlight lang="java">


public class JacobiSymbol {
public class JacobiSymbol {
Line 969: Line 1,058:


}
}
</syntaxhighlight>
</lang>
{{out}}
{{out}}
<pre style="font-size: 13px">
<pre>
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
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
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
Line 992: Line 1,081:
=={{header|jq}}==
=={{header|jq}}==
{{trans|Julia}}
{{trans|Julia}}
<syntaxhighlight lang="jq">
<lang jq>
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
def rpad($len): tostring | ($len - length) as $l | . + (" " * $l)[:$l];
def rpad($len): tostring | ($len - length) as $l | . + (" " * $l)[:$l];
Line 1,013: Line 1,102:
(range( 1; 32; 2) as $n
(range( 1; 32; 2) as $n
| "\($n|rpad(3))" + reduce range(1; 13) as $a (""; . + (jacobi($a; $n) | lpad(4) ))
| "\($n|rpad(3))" + reduce range(1; 13) as $a (""; . + (jacobi($a; $n) | lpad(4) ))
)</lang>
)</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>
Line 1,038: Line 1,127:
=={{header|Julia}}==
=={{header|Julia}}==
{{trans|Python}}
{{trans|Python}}
<lang julia>function jacobi(a, n)
<syntaxhighlight lang="julia">function jacobi(a, n)
a %= n
a %= n
result = 1
result = 1
Line 1,061: Line 1,150:
end
end
end
end
</lang>{{out}}
</syntaxhighlight>{{out}}
<pre>
<pre>
Table of jacobi(a, n) for a 1 to 12, n 1 to 31
Table of jacobi(a, n) for a 1 to 12, n 1 to 31
Line 1,086: Line 1,175:


=={{header|Kotlin}}==
=={{header|Kotlin}}==
<lang scala>fun jacobi(A: Int, N: Int): Int {
<syntaxhighlight lang="scala">fun jacobi(A: Int, N: Int): Int {
assert(N > 0 && N and 1 == 1)
assert(N > 0 && N and 1 == 1)
var a = A % N
var a = A % N
Line 1,108: Line 1,197:
}
}
return if (n == 1) result else 0
return if (n == 1) result else 0
}</lang>
}</syntaxhighlight>

=={{header|Lua}}==
{{Trans|ALGOL 68}}
<syntaxhighlight lang="lua">
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
</syntaxhighlight>
{{out}}
<pre>
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
</pre>


=={{header|Mathematica}} / {{header|Wolfram Language}}==
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<lang Mathematica>TableForm[Table[JacobiSymbol[n, k], {n, 1, 17, 2}, {k, 16}],
<syntaxhighlight lang="mathematica">TableForm[Table[JacobiSymbol[n, k], {n, 1, 17, 2}, {k, 16}],
TableHeadings -> {ReplacePart[Range[1, 17, 2], 1 -> "n=1"],
TableHeadings -> {ReplacePart[Range[1, 17, 2], 1 -> "n=1"],
ReplacePart[Range[16], 1 -> "k=1"]}]</lang>
ReplacePart[Range[16], 1 -> "k=1"]}]</syntaxhighlight>
{{out}}
{{out}}
Produces a nicely typeset table.
Produces a nicely typeset table.
Line 1,119: Line 1,267:
=={{header|Nim}}==
=={{header|Nim}}==
Translation of the Lua program from Wikipedia page.
Translation of the Lua program from Wikipedia page.
<lang Nim>template isOdd(n: int): bool = (n and 1) != 0
<syntaxhighlight lang="nim">template isOdd(n: int): bool = (n and 1) != 0
template isEven(n: int): bool = (n and 1) == 0
template isEven(n: int): bool = (n and 1) == 0


Line 1,152: Line 1,300:
for n in 1..20:
for n in 1..20:
stdout.write align($jacobi(n, k), 3)
stdout.write align($jacobi(n, k), 3)
echo ""</lang>
echo ""</syntaxhighlight>


{{out}}
{{out}}
Line 1,171: Line 1,319:
=={{header|Perl}}==
=={{header|Perl}}==
{{trans|Raku}}
{{trans|Raku}}
<lang perl>use strict;
<syntaxhighlight lang="perl">use strict;
use warnings;
use warnings;


Line 1,203: Line 1,351:
printf '%4d', J($_, $n) for 1..$maxa;
printf '%4d', J($_, $n) for 1..$maxa;
print "\n"
print "\n"
}</lang>
}</syntaxhighlight>
{{out}}
{{out}}
<pre>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
<pre style="font-size: 13px">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
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
Line 1,224: Line 1,372:


=={{header|Phix}}==
=={{header|Phix}}==
<!--<lang Phix>(phixonline)-->
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">jacobi</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">jacobi</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
Line 1,250: Line 1,398:
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</lang>-->
<!--</syntaxhighlight>-->
{{out}}
{{out}}
<pre>
<pre>
Line 1,271: Line 1,419:
29 0 1 -1 -1 1 1 1 1 -1 1 -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
31 0 1 1 -1 1 1 -1 1 1 1 1 -1
</pre>

=={{header|PL/M}}==
{{Trans|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.
<syntaxhighlight lang="plm">
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 N ADDRESS;
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;

/* TASK */

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 ( A, N )ADDRESS;
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
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
</pre>


=={{header|Python}}==
=={{header|Python}}==
<lang python>def jacobi(a, n):
<syntaxhighlight lang="python">def jacobi(a, n):
if n <= 0:
if n <= 0:
raise ValueError("'n' must be a positive integer.")
raise ValueError("'n' must be a positive integer.")
Line 1,294: Line 1,539:
return result
return result
else:
else:
return 0</lang>
return 0</syntaxhighlight>


=={{header|Raku}}==
=={{header|Raku}}==
Line 1,300: Line 1,545:
{{works with|Rakudo|2019.11}}
{{works with|Rakudo|2019.11}}


<lang perl6># Jacobi function
<syntaxhighlight lang="raku" line># Jacobi function
sub infix:<J> (Int $k is copy, Int $n is copy where * % 2) {
sub infix:<J> (Int $k is copy, Int $n is copy where * % 2) {
$k %= $n;
$k %= $n;
Line 1,329: Line 1,574:
}
}
print "\n";
print "\n";
}</lang>
}</syntaxhighlight>
{{out}}
{{out}}
<pre>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
<pre style="font-size: 13px">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
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
Line 1,353: Line 1,598:


<br>A little extra code was added to make a prettier grid.
<br>A little extra code was added to make a prettier grid.
<lang rexx>/*REXX pgm computes/displays the Jacobi symbol, the # of rows & columns can be specified*/
<syntaxhighlight lang="rexx">/*REXX pgm computes/displays the Jacobi symbol, the # of rows & columns can be specified*/
parse arg rows cols . /*obtain optional arguments from the CL*/
parse arg rows cols . /*obtain optional arguments from the CL*/
if rows='' | rows=="," then rows= 17 /*Not specified? Then use the default.*/
if rows='' | rows=="," then rows= 17 /*Not specified? Then use the default.*/
Line 1,386: Line 1,631:
end /*while a\==0*/
end /*while a\==0*/
if n==1 then return $
if n==1 then return $
return 0</lang>
return 0</syntaxhighlight>
{{out|output|text=&nbsp; when using the default inputs:}}
{{out|output|text=&nbsp; when using the default inputs:}}
<pre>
<pre>
Line 1,405: Line 1,650:
=={{header|Ruby}}==
=={{header|Ruby}}==
{{trans|Crystal}}
{{trans|Crystal}}
<lang ruby>def jacobi(a, n)
<syntaxhighlight lang="ruby">def jacobi(a, n)
raise ArgumentError.new "n must b positive and odd" if n < 1 || n.even?
raise ArgumentError.new "n must b positive and odd" if n < 1 || n.even?
res = 1
res = 1
Line 1,426: Line 1,671:
(0..10).each { |a| printf(" % 2d", jacobi(a, n)) }
(0..10).each { |a| printf(" % 2d", jacobi(a, n)) }
puts
puts
end</lang>
end</syntaxhighlight>


{{out}}
{{out}}
Line 1,445: Line 1,690:
=={{header|Rust}}==
=={{header|Rust}}==
{{trans|C++}}
{{trans|C++}}
<lang rust>fn jacobi(mut n: i32, mut k: i32) -> i32 {
<syntaxhighlight lang="rust">fn jacobi(mut n: i32, mut k: i32) -> i32 {
assert!(k > 0 && k % 2 == 1);
assert!(k > 0 && k % 2 == 1);
n %= k;
n %= k;
Line 1,491: Line 1,736:
fn main() {
fn main() {
print_table(20, 21);
print_table(20, 21);
}</lang>
}</syntaxhighlight>


{{out}}
{{out}}
Line 1,511: Line 1,756:


=={{header|Scala}}==
=={{header|Scala}}==
<lang scala>
<syntaxhighlight lang="scala">
def jacobi(a_p: Int, n_p: Int): Int =
def jacobi(a_p: Int, n_p: Int): Int =
{
{
Line 1,544: Line 1,789:
} yield println("n = " + n + ", a = " + a + ": " + jacobi(a, n))
} yield println("n = " + n + ", a = " + a + ": " + jacobi(a, n))
}
}
</syntaxhighlight>
</lang>


{{out|output}}
{{out|output}}
Line 1,660: Line 1,905:


=={{header|Scheme}}==
=={{header|Scheme}}==
<lang scheme>(define jacobi (lambda (a n)
<syntaxhighlight lang="scheme">(define jacobi (lambda (a n)
(let ((a-mod-n (modulo a n)))
(let ((a-mod-n (modulo a n)))
(if (zero? a-mod-n)
(if (zero? a-mod-n)
Line 1,672: Line 1,917:
(if (and (= (modulo a-mod-n 4) 3) (= (modulo n 4) 3))
(if (and (= (modulo a-mod-n 4) 3) (= (modulo n 4) 3))
(- (jacobi n a-mod-n))
(- (jacobi n a-mod-n))
(jacobi n a-mod-n)))))))</lang>
(jacobi n a-mod-n)))))))</syntaxhighlight>


=={{header|Sidef}}==
=={{header|Sidef}}==
Line 1,678: Line 1,923:
Also built-in as '''kronecker(n,k)'''.
Also built-in as '''kronecker(n,k)'''.


<lang ruby>func jacobi(n, k) {
<syntaxhighlight lang="ruby">func jacobi(a, n) {


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


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


k==1 ? t : 0
n==1 ? t : 0
}
}


for n in (0..50), k in (0..50) {
for a in (0..50), n in (0..50) {
assert_eq(jacobi(n, 2*k + 1), kronecker(n, 2*k + 1))
assert_eq(jacobi(a, 2*n + 1), kronecker(a, 2*n + 1))
}</lang>
}</syntaxhighlight>


=={{header|Swift}}==
=={{header|Swift}}==


<lang swift>import Foundation
<syntaxhighlight lang="swift">import Foundation


func jacobi(a: Int, n: Int) -> Int {
func jacobi(a: Int, n: Int) -> Int {
Line 1,740: Line 1,987:


print()
print()
}</lang>
}</syntaxhighlight>


{{out}}
{{out}}
Line 1,756: Line 2,003:
17 0 1 1 -1 1 -1 -1 -1 1 1</pre>
17 0 1 1 -1 1 -1 -1 -1 1 1</pre>


=={{header|Vlang}}==
=={{header|V (Vlang)}}==
{{trans|Go}}
{{trans|Go}}
<lang vlang>fn jacobi(aa u64, na u64) ?int {
<syntaxhighlight lang="v (vlang)">fn jacobi(aa u64, na u64) ?int {
mut a := aa
mut a := aa
mut n := na
mut n := na
Line 1,799: Line 2,046:
}
}
}
}
</syntaxhighlight>
</lang>
{{out}}
{{out}}
<pre>
<pre>
Line 1,818: Line 2,065:
{{trans|Python}}
{{trans|Python}}
{{libheader|Wren-fmt}}
{{libheader|Wren-fmt}}
<lang ecmascript>import "/fmt" for Fmt
<syntaxhighlight lang="wren">import "./fmt" for Fmt


var jacobi = Fn.new { |a, n|
var jacobi = Fn.new { |a, n|
Line 1,846: Line 2,093:
var n = 1
var n = 1
while (n < 31) {
while (n < 31) {
System.write(Fmt.d(3, n))
Fmt.write("$3d", n)
for (a in 1..15) System.write(Fmt.d(4, jacobi.call(a, n)))
for (a in 1..15) Fmt.write("$4d", jacobi.call(a, n))
System.print()
System.print()
n = n + 2
n = n + 2
}</lang>
}</syntaxhighlight>


{{out}}
{{out}}
Line 1,872: Line 2,119:
27 1 -1 0 1 -1 0 1 -1 0 1 -1 0 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
29 1 -1 -1 1 1 1 1 -1 1 -1 -1 -1 1 -1 -1
</pre>

=={{header|XPL0}}==
{{trans|C}}
<syntaxhighlight lang "XPL0">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);
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
</pre>


=={{header|zkl}}==
=={{header|zkl}}==
<lang zkl>fcn jacobi(a,n){
<syntaxhighlight lang="zkl">fcn jacobi(a,n){
if(n.isEven or n<1)
if(n.isEven or n<1)
throw(Exception.ValueError("'n' must be a positive odd integer"));
throw(Exception.ValueError("'n' must be a positive odd integer"));
Line 1,889: Line 2,195:
}
}
if(n==1) result else 0
if(n==1) result else 0
}</lang>
}</syntaxhighlight>
<lang zkl>println("Using hand-coded version:");
<syntaxhighlight lang="zkl">println("Using hand-coded version:");
println("n/a 0 1 2 3 4 5 6 7 8 9");
println("n/a 0 1 2 3 4 5 6 7 8 9");
println("---------------------------------");
println("---------------------------------");
Line 1,897: Line 2,203:
foreach a in (10){ print(" % d".fmt(jacobi(a,n))) }
foreach a in (10){ print(" % d".fmt(jacobi(a,n))) }
println();
println();
}</lang>
}</syntaxhighlight>
{{libheader|GMP}} GNU Multiple Precision Arithmetic Library
{{libheader|GMP}} GNU Multiple Precision Arithmetic Library
<lang zkl>var [const] BI=Import.lib("zklBigNum"); // libGMP
<syntaxhighlight lang="zkl">var [const] BI=Import.lib("zklBigNum"); // libGMP
println("\nUsing BigInt library function:");
println("\nUsing BigInt library function:");
println("n/a 0 1 2 3 4 5 6 7 8 9");
println("n/a 0 1 2 3 4 5 6 7 8 9");
Line 1,907: Line 2,213:
foreach a in (10){ print(" % d".fmt(BI(a).jacobi(n))) }
foreach a in (10){ print(" % d".fmt(BI(a).jacobi(n))) }
println();
println();
}</lang>
}</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>

Latest revision as of 08:56, 7 April 2024

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

Task

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!

Library: Action! Tool Kit
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:

Screenshot from Atari 8-bit computer 

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
                                                                        'item -> pad.left item 2
    ]
]
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

Haskell

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) $
          paddedCols $
            chunksOf nRows $
              uncurry jacobi
                <$> ((,) <$> colLabels <*> rowLabels)

------------------- TABULATION FUNCTIONS -----------------
paddedCols ::
  Show a =>
  [[a]] ->
  [[String]]
paddedCols cols =
  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
    print("\n", rpad(n, 3))
    for a in 1:11
        print(lpad(jacobi(a, n), 4))
    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

Translation of the Lua program from Wikipedia page. 

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 N ADDRESS;
      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;

   /* TASK                                                                   */

   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 ( A, N )ADDRESS;
   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
Retrieved from "https://rosettacode.org/wiki/Jacobi_symbol?oldid=363357"