A096008 Irregular triangle read by rows where n-th row contains all quadratic residues (including zero) mod n.

0, 0, 1, 0, 1, 0, 1, 0, 1, 4, 0, 1, 3, 4, 0, 1, 2, 4, 0, 1, 4, 0, 1, 4, 7, 0, 1, 4, 5, 6, 9, 0, 1, 3, 4, 5, 9, 0, 1, 4, 9, 0, 1, 3, 4, 9, 10, 12, 0, 1, 2, 4, 7, 8, 9, 11, 0, 1, 4, 6, 9, 10, 0, 1, 4, 9, 0, 1, 2, 4, 8, 9, 13, 15, 16, 0, 1, 4, 7, 9, 10, 13, 16, 0, 1, 4, 5, 6, 7, 9, 11, 16, 17, 0, 1, 4, 5, 9, 16

Offset: 1

Author

Cino Hilliard, Jul 20 2004

Keywords

• easy
• tabf
• nonn

Examples

			The table starts:
  [1]  [0]
  [2]  [0, 1]
  [3]  [0, 1]
  [4]  [0, 1]
  [5]  [0, 1, 4]
  [6]  [0, 1, 3, 4]
  [7]  [0, 1, 2, 4]
  [8]  [0, 1, 4]
  [9]  [0, 1, 4, 7]
  [10] [0, 1, 4, 5, 6, 9]
  ...
		

Links

• T. D. Noe, Rows n = 1..100, flattened
• Eric Weisstein's World of Mathematics, Quadratic Residue.

Crossrefs

Cf. A046071 (without zeros), A000224 (row lengths), A063987.

Last elements of rows give A047210.

Row sums give A165909.

Programs

Haskell

a096008 n k = a096008_tabf !! (n-1) !! (k-1)
a096008_row n = a096008_tabf !! (n-1)
a096008_tabf = [0] : map (0 :) a046071_tabf
-- Reinhard Zumkeller, May 10 2015

Maple

q := n -> sort(convert({seq(i^2 mod n, i=0..n-1)}, list));
# N. J. A. Sloane, Feb 09 2011
# Alternative:
QR := (a, n) -> NumberTheory:-QuadraticResidue(a, n):
for n from 1 to 10 do print(select(a -> 1 = QR(a, n), [seq(0..n-1)])) od:
# Peter Luschny, Jun 02 2024

Mathematica

row[n_] := Table[PowerMod[k, 2, n], {k, 0, n-1}] // Union; Table[row[n], {n, 1, 20}] // Flatten (* Jean-François Alcover, Sep 09 2013 *)
ResourceFunction["QuadraticResidues"] /@ Range[20] // Flatten  (* Peter Luschny, May 23 2024 *)

PARI

T(n) = {local(v,r,i,j,k); v=vector(n,i,0); for(i=0,floor(n/2),v[i^2%n+1]=1); k=sum(i=1,n,v[i]); j=0; r=vector(k); for(i=1,n, if(v[i], j++; r[j]=i-1)); r}

SageMath

for n in range(1, 11): print(quadratic_residues(n)) # Peter Luschny, Jun 02 2024

Extensions

Edited by Franklin T. Adams-Watters, Nov 07 2006