Jacobi symbol

From Rosetta Code
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[edit]

Translation of: Python
F jacobi(=a, =n)
   I n <= 0
      X ValueError(‘'n' must be a positive integer.’)
   I n % 2 == 0
      X 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![edit]

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

Arturo[edit]

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[edit]

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[edit]

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[edit]

#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++[edit]

#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[edit]

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[edit]

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#[edit]

//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[edit]

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

FreeBASIC[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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
}

Mathematica / Wolfram Language[edit]

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[edit]

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[edit]

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[edit]

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

Python[edit]

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[edit]

(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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

(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[edit]

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

func jacobi(n, k) {

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

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

    k==1 ? t : 0
}

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

Swift[edit]

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

Vlang[edit]

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[edit]

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) {
    System.write(Fmt.d(3, n))
    for (a in 1..15) System.write(Fmt.d(4, 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

zkl[edit]

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