Voozh

A046071

Triangle of nonzero quadratic residues mod n.

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

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

OFFSET

2,5

COMMENTS

Rows start with 1's.

LINKS

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

Eric Weisstein's World of Mathematics, Quadratic Residue.

EXAMPLE

1, 4,

1, 3, 4,

1, 2, 4,

1, 4,

1, 4, 7,

1, 4, 5, 6, 9,

1, 3, 4, 5, 9,

1, 4, 9,

1, 3, 4, 9, 10, 12,

1, 2, 4, 7, 8, 9, 11

1, 4, 6, 9, 10,

- Geoffrey Critzer, Apr 03 2015

MAPLE

seq(op(select(numtheory:-quadres=1, [$1..n-1], n)), n=2..30); # Robert Israel, Apr 03 2015

MATHEMATICA

residueQ[n_, k_] := Length[ Select[ Range[ Floor[k/2]]^2, Mod[#, k] == n & , 1]] == 1; row[n_] := Select[ Range[n-1], residueQ[#, n]& ]; Table[row[n], {n, 2, 22}] // Flatten (* Jean-François Alcover, Oct 23 2012 *)

row[n_] := Table[PowerMod[k, 2, n], {k, 0, n-1}] // Union // Rest; Table[row[n], {n, 2, 22}] // Flatten (* Jean-François Alcover, Jul 07 2019 *)

PROG

(PARI) residue(n, m)={local(r); r=0; for(i=0, floor(m/2), if(i^2%m==n, r=1)); r} \\ Michael B. Porter, May 03 2010

(Haskell)

import Data.List (sort, nub, genericIndex)

a046071 n k = genericIndex a046071_tabf (n-2) !! (k-1)

a046071_row n = genericIndex a046071_tabf (n-2)

a046071_tabf = f [1] 2 3 where

f qs@(q:_) i j = ys : f ((q + j) : qs) (i + 1) (j + 2) where

ys = nub $ sort $ filter (> 0) $ map (flip mod i) qs

-- Reinhard Zumkeller, May 10 2015

(SageMath)