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
Examples
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
Links
- T. D. Noe, Rows n = 1..100, flattened
- Eric Weisstein's World of Mathematics, Quadratic Residue.
Crossrefs
Programs
-
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 -
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 *) -
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 -
SageMath
for n in range(2, 16): print(quadratic_residues(n)[1:]) # Peter Luschny, Jun 02 2024
Extensions
Edited by Franklin T. Adams-Watters, Nov 07 2006
Comments