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

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,
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,
- 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)
for n in range(2, 16): print(quadratic_residues(n)[1:]) # Peter Luschny, Jun 02 2024

Crossrefs

Cf. A105612 (row lengths), A165909 (row sums), A372651 (row products).

Cf. A096008 (including zeros), A063987.

Sequence in context: A309603 A328611 A084118 * A376353 A078147 A376312

Adjacent sequences: A046068 A046069 A046070 * A046072 A046073 A046074

Keyword

easy,nonn,tabf

Author

Eric W. Weisstein

Extensions

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

Status

approved