cp's OEIS Frontend

A096008 Irregular triangle read by rows where n-th row contains all quadratic residues (including zero) mod n.

%I A096008 #43 Feb 16 2025 08:32:53
%S A096008 0,0,1,0,1,0,1,0,1,4,0,1,3,4,0,1,2,4,0,1,4,0,1,4,7,0,1,4,5,6,9,0,1,3,
%T A096008 4,5,9,0,1,4,9,0,1,3,4,9,10,12,0,1,2,4,7,8,9,11,0,1,4,6,9,10,0,1,4,9,
%U A096008 0,1,2,4,8,9,13,15,16,0,1,4,7,9,10,13,16,0,1,4,5,6,7,9,11,16,17,0,1,4,5,9,16
%N A096008 Irregular triangle read by rows where n-th row contains all quadratic residues (including zero) mod n.
%H A096008 T. D. Noe, <a href="/A096008/b096008.txt">Rows n = 1..100, flattened</a>
%H A096008 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/QuadraticResidue.html">Quadratic Residue</a>.
%e A096008 The table starts:
%e A096008   [1]  [0]
%e A096008   [2]  [0, 1]
%e A096008   [3]  [0, 1]
%e A096008   [4]  [0, 1]
%e A096008   [5]  [0, 1, 4]
%e A096008   [6]  [0, 1, 3, 4]
%e A096008   [7]  [0, 1, 2, 4]
%e A096008   [8]  [0, 1, 4]
%e A096008   [9]  [0, 1, 4, 7]
%e A096008   [10] [0, 1, 4, 5, 6, 9]
%e A096008   ...
%p A096008 q := n -> sort(convert({seq(i^2 mod n, i=0..n-1)}, list));
%p A096008 # _N. J. A. Sloane_, Feb 09 2011
%p A096008 # Alternative:
%p A096008 QR := (a, n) -> NumberTheory:-QuadraticResidue(a, n):
%p A096008 for n from 1 to 10 do print(select(a -> 1 = QR(a, n), [seq(0..n-1)])) od:
%p A096008 # _Peter Luschny_, Jun 02 2024
%t A096008 row[n_] := Table[PowerMod[k, 2, n], {k, 0, n-1}] // Union; Table[row[n], {n, 1, 20}] // Flatten (* _Jean-François Alcover_, Sep 09 2013 *)
%t A096008 ResourceFunction["QuadraticResidues"] /@ Range[20] // Flatten  (* _Peter Luschny_, May 23 2024 *)
%o A096008 (PARI) T(n) = {local(v,r,i,j,k); v=vector(n,i,0); for(i=0,floor(n/2),v[i^2%n+1]=1); k=sum(i=1,n,v[i]); j=0; r=vector(k); for(i=1,n, if(v[i], j++; r[j]=i-1)); r}
%o A096008 (Haskell)
%o A096008 a096008 n k = a096008_tabf !! (n-1) !! (k-1)
%o A096008 a096008_row n = a096008_tabf !! (n-1)
%o A096008 a096008_tabf = [0] : map (0 :) a046071_tabf
%o A096008 -- _Reinhard Zumkeller_, May 10 2015
%o A096008 (SageMath)
%o A096008 for n in range(1, 11): print(quadratic_residues(n)) # _Peter Luschny_, Jun 02 2024
%Y A096008 Cf. A046071 (without zeros), A000224 (row lengths), A063987.
%Y A096008 Last elements of rows give A047210.
%Y A096008 Row sums give A165909.
%K A096008 easy,tabf,nonn
%O A096008 1,10
%A A096008 _Cino Hilliard_, Jul 20 2004
%E A096008 Edited by _Franklin T. Adams-Watters_, Nov 07 2006