A046071 - OEIS

%I #37 Jun 02 2024 06:30:00

%S 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,

%T 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,

%U 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

%N Triangle of nonzero quadratic residues mod n.

%C Rows start with 1's.

%H T. D. Noe, <a href="/A046071/b046071.txt">Rows n = 1..100, flattened</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/QuadraticResidue.html">Quadratic Residue</a>.

%e 1,

%e 1,

%e 1,

%e 1, 4,

%e 1, 3, 4,

%e 1, 2, 4,

%e 1, 4,

%e 1, 4, 7,

%e 1, 4, 5, 6, 9,

%e 1, 3, 4, 5, 9,

%e 1, 4, 9,

%e 1, 3, 4, 9, 10, 12,

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

%e 1, 4, 6, 9, 10,

%e - _Geoffrey Critzer_, Apr 03 2015

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

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

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

%o (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

%o (Haskell)

%o import Data.List (sort, nub, genericIndex)

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

%o a046071_row n = genericIndex a046071_tabf (n-2)

%o a046071_tabf = f [1] 2 3 where

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

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

%o -- _Reinhard Zumkeller_, May 10 2015

%o (SageMath)

%o for n in range(2, 16): print(quadratic_residues(n)[1:]) # _Peter Luschny_, Jun 02 2024

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

%Y Cf. A096008 (including zeros), A063987.

%K easy,nonn,tabf

%O 2,5

%A _Eric W. Weisstein_

%E Edited by _Franklin T. Adams-Watters_, Nov 07 2006