cp's OEIS Frontend

A046071 Triangle of nonzero quadratic residues mod n.

%I A046071 #38 Feb 16 2025 08:32:38
%S A046071 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 A046071 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 A046071 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 A046071 Triangle of nonzero quadratic residues mod n.
%C A046071 Rows start with 1's.
%H A046071 T. D. Noe, <a href="/A046071/b046071.txt">Rows n = 1..100, flattened</a>
%H A046071 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/QuadraticResidue.html">Quadratic Residue</a>.
%e A046071 1,
%e A046071 1,
%e A046071 1,
%e A046071 1, 4,
%e A046071 1, 3, 4,
%e A046071 1, 2, 4,
%e A046071 1, 4,
%e A046071 1, 4, 7,
%e A046071 1, 4, 5, 6, 9,
%e A046071 1, 3, 4, 5, 9,
%e A046071 1, 4, 9,
%e A046071 1, 3, 4, 9, 10, 12,
%e A046071 1, 2, 4, 7, 8, 9, 11
%e A046071 1, 4, 6, 9, 10,
%e A046071 - _Geoffrey Critzer_, Apr 03 2015
%p A046071 seq(op(select(numtheory:-quadres=1,[$1..n-1],n)),n=2..30); # _Robert Israel_, Apr 03 2015
%t A046071 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 A046071 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 A046071 (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 A046071 (Haskell)
%o A046071 import Data.List (sort, nub, genericIndex)
%o A046071 a046071 n k = genericIndex a046071_tabf (n-2) !! (k-1)
%o A046071 a046071_row n = genericIndex a046071_tabf (n-2)
%o A046071 a046071_tabf = f [1] 2 3 where
%o A046071    f qs@(q:_) i j = ys : f ((q + j) : qs) (i + 1) (j + 2) where
%o A046071                     ys = nub $ sort $ filter (> 0) $ map (flip mod i) qs
%o A046071 -- _Reinhard Zumkeller_, May 10 2015
%o A046071 (SageMath)
%o A046071 for n in range(2, 16): print(quadratic_residues(n)[1:]) # _Peter Luschny_, Jun 02 2024
%Y A046071 Cf. A105612 (row lengths), A165909 (row sums), A372651 (row products).
%Y A046071 Cf. A096008 (including zeros), A063987.
%K A046071 easy,nonn,tabf
%O A046071 2,5
%A A046071 _Eric W. Weisstein_
%E A046071 Edited by _Franklin T. Adams-Watters_, Nov 07 2006