A096008 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,10

LINKS

T. D. Noe, Rows n = 1..100, flattened

Eric Weisstein's World of Mathematics, Quadratic Residue.

EXAMPLE

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]

...

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

PROG

(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}

(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

(SageMath)

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

CROSSREFS

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

Last elements of rows give A047210.

Row sums give A165909.

Sequence in context: A298063 A298712 A127538 * A122873 A221275 A176803