A046071 -id:A046071 - cp's OEIS frontend

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

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

Offset: 1

Cino Hilliard, Jul 20 2004

			The table starts:
  [1]  [0]
  [2]  [0, 1]
  [3]  [0, 1]
  [4]  [0, 1]
  [5]  [0, 1, 4]
  [6]  [0, 1, 3, 4]
  [7]  [0, 1, 2, 4]
  [8]  [0, 1, 4]
  [9]  [0, 1, 4, 7]
  [10] [0, 1, 4, 5, 6, 9]
  ...

T. D. Noe, Rows n = 1..100, flattened
Eric Weisstein's World of Mathematics, Quadratic Residue.

Cf. A046071 (without zeros), A000224 (row lengths), A063987.
Last elements of rows give A047210.
Row sums give A165909.

a096008 n k = a096008_tabf !! (n-1) !! (k-1)
a096008_row n = a096008_tabf !! (n-1)
a096008_tabf = [0] : map (0 :) a046071_tabf
-- Reinhard Zumkeller, May 10 2015

q := n -> sort(convert({seq(i^2 mod n, i=0..n-1)}, list));
# N. J. A. Sloane, Feb 09 2011
# Alternative:
QR := (a, n) -> NumberTheory:-QuadraticResidue(a, n):
for n from 1 to 10 do print(select(a -> 1 = QR(a, n), [seq(0..n-1)])) od:
# Peter Luschny, Jun 02 2024

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 *)
ResourceFunction["QuadraticResidues"] /@ Range[20] // Flatten  (* Peter Luschny, May 23 2024 *)

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}

for n in range(1, 11): print(quadratic_residues(n)) # Peter Luschny, Jun 02 2024

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

A063987 Irregular triangle in which n-th row gives quadratic residues modulo the n-th prime.

Original entry on oeis.org

1, 1, 1, 4, 1, 2, 4, 1, 3, 4, 5, 9, 1, 3, 4, 9, 10, 12, 1, 2, 4, 8, 9, 13, 15, 16, 1, 4, 5, 6, 7, 9, 11, 16, 17, 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18, 1, 4, 5, 6, 7, 9, 13, 16, 20, 22, 23, 24, 25, 28, 1, 2, 4, 5, 7, 8, 9, 10, 14, 16, 18, 19, 20, 25, 28, 1, 3, 4, 7, 9, 10, 11, 12, 16, 21, 25

Offset: 1

Suggested by Gary W. Adamson, Sep 18 2001

For n >= 2, row lengths are (prime(n) - 1)/2. For example, since 17 is the 7th prime number, the length of row 7 is (17 - 1)/2 = 8. - Geoffrey Critzer, Apr 04 2015

			Modulo the 5th prime, 11, the (11 - 1)/2 = 5 quadratic residues are 1,3,4,5,9 and the 5 non-residues are 2, 6, 7, 8, 10.
The irregular triangle T(n, k) begins (p is prime(n)):
   n    p  \k 1 2 3 4  5  6  7  8  9 10 11 12 13 14
   1,   2:    1
   2,   3:    1
   3,   5:    1 4
   4,   7:    1 2 4
   5,  11:    1 3 4 5  9
   6:  13:    1 3 4 9 10 12
   7,  17:    1 2 4 8  9 13 15 16
   8,  19:    1 4 5 6  7  9 11 16 17
   9,  23:    1 2 3 4  6  8  9 12 13 16 18
  10,  29:    1 4 5 6  7  9 13 16 20 22 23 24 25 28
  ...  reformatted by _Wolfdieter Lang_, Mar 06 2016

Albert H. Beiler, Recreations in the theory of numbers, New York, Dover, (2nd ed.) 1966. See Table 82 at p. 202.

T. D. Noe, Rows n = 1..100 of triangle, flattened
C. F. Gauss, Vierter Abschnitt. Von den Congruenzen zweiten Grades. Quadratische Reste und Nichtreste. Art. 97, in "Untersuchungen über die höhere Arithmetik", Hrsg. H. Maser, Verlag von Julius Springer, Berlin, 1889.

Cf. A063988, A010379 (6th row), A010381 (7th row), A010385 (8th row), A010391 (9th row), A010392 (10th row), A278580 (row 23), A230077.
Cf. A076409 (row sums).
Cf. A046071 (for all n), A048152 (for all n, with 0's).

with(numtheory): for n from 1 to 20 do for j from 1 to ithprime(n)-1 do if legendre(j, ithprime(n)) = 1 then printf(`%d,`,j) fi; od: od:
# Alternative:
QR := (a, n) -> NumberTheory:-QuadraticResidue(a, n):
for n from 1 to 10 do p := ithprime(n):
print(select(a -> 1 = QR(a, p), [seq(1..p-1)])) od:  # Peter Luschny, Jun 02 2024

row[n_] := (p = Prime[n]; Select[ Range[p - 1], JacobiSymbol[#, p] == 1 &]); Flatten[ Table[ row[n], {n, 1, 12}]] (* Jean-François Alcover, Dec 21 2011 *)

residue(n,m)=local(r);r=0;for(i=0,floor(m/2),if(i^2%m==n,r=1));r
isA063987(n,m)=residue(n,prime(m)) /* Michael B. Porter, May 07 2010 */

row(n) = my(p=prime(n)); select(x->issquare(Mod(x,p)), [1..p-1]); \\ Michel Marcus, Nov 07 2020

from sympy import jacobi_symbol as J, prime
def a(n):
    p = prime(n)
    return [1] if n==1 else [i for i in range(1, p) if J(i, p)==1]
for n in range(1, 11): print(a(n)) # Indranil Ghosh, May 27 2017

for p in prime_range(30): print(quadratic_residues(p)[1:])
# Peter Luschny, Jun 02 2024

Edited by Wolfdieter Lang, Mar 06 2016

A048152 Triangular array T read by rows: T(n,k) = k^2 mod n, for 1 <= k <= n, n >= 1.

Original entry on oeis.org

0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 4, 4, 1, 0, 1, 4, 3, 4, 1, 0, 1, 4, 2, 2, 4, 1, 0, 1, 4, 1, 0, 1, 4, 1, 0, 1, 4, 0, 7, 7, 0, 4, 1, 0, 1, 4, 9, 6, 5, 6, 9, 4, 1, 0, 1, 4, 9, 5, 3, 3, 5, 9, 4, 1, 0, 1, 4, 9, 4, 1, 0, 1, 4, 9, 4, 1, 0, 1, 4, 9, 3, 12, 10, 10, 12, 3, 9, 4, 1, 0

Offset: 1

Clark Kimberling

			Rows:
  0;
  1, 0;
  1, 1, 0;
  1, 0, 1, 0;
  1, 4, 4, 1, 0;
  1, 4, 3, 4, 1, 0;

T. D. Noe, Rows n = 1..100 of triangle, flattened
Eric Weisstein's World of Mathematics, Quadratic Residue

Cf. A060036.
Cf. A225126 (central terms).
Cf. A070430 (row 5), A070431 (row 6), A053879 (row 7), A070432 (row 8), A008959 (row 10), A070435 (row 12), A070438 (row 15), A070422 (row 20).
Cf. A046071 (in ascending order, without zeros and duplicates).
Cf. A063987 (for primes, in ascending order, without zeros and duplicates).

a048152 n k = a048152_tabl !! (n-1) !! (k-1)
a048152_row n = a048152_tabl !! (n-1)
a048152_tabl = zipWith (map . flip mod) [1..] a133819_tabl
-- Reinhard Zumkeller, Apr 29 2013

Flatten[Table[PowerMod[k,2,n],{n,15},{k,n}]] (* Harvey P. Dale, Jun 20 2011 *)

T(n,k) = A133819(n,k) mod n, k = 1..n. - Reinhard Zumkeller, Apr 29 2013

T(n,k) = (T(n,k-1) + (2k+1)) mod n. - Andrés Ventas, Apr 06 2021

A034794 a(n) is the least prime p > a(n-1) such that a(n-1) is a quadratic residue mod p.

Original entry on oeis.org

2, 7, 19, 31, 41, 43, 53, 59, 67, 73, 79, 89, 97, 101, 107, 127, 139, 151, 163, 173, 179, 193, 197, 223, 241, 251, 283, 293, 307, 313, 317, 353, 383, 389, 409, 419, 443, 457, 461, 467, 487, 499, 521, 523, 571, 577, 593, 601, 607, 619, 631, 641, 643, 653, 659

Offset: 1

David W. Wilson

a(n-1) is a term in row a(n) of A046071. - Reinhard Zumkeller, May 10 2015

T. D. Noe, Table of n, a(n) for n=1..1000

Cf. A092581.

Cf. A046071, A000040.

a034794 n = a034794_list !! (n-1)
a034794_list = 2 : f 2 (tail  a000040_list) where
   f x (p:ps) = if elem x $ a046071_row p then p : f p ps else f x ps
-- Reinhard Zumkeller, May 10 2015

f:= proc(t) local i,p;
  p:= t;
  do
    p:= nextprime(p);
    if numtheory:-jacobi(t,p) = 1 then return p fi
  od
end proc:
A[1]:= 2:
for n from 2 to 100 do A[n]:= f(A[n-1]) od:
seq(A[i],i=1..100); # Robert Israel, Sep 04 2016

f[n_] := Block[{k = PrimePi[n] + 1}, While[ JacobiSymbol[n, Prime[k]] == -1, k++ ]; Prime[k]]; NestList[f, 2, 54] (* Robert G. Wilson v, Mar 16 2004 *)

Mathematica updated by Jean-François Alcover, Jul 04 2013

Name corrected by Robert Israel, Sep 04 2016

A165909 a(n) is the sum of the quadratic residues of n.

Original entry on oeis.org

0, 1, 1, 1, 5, 8, 7, 5, 12, 25, 22, 14, 39, 42, 30, 14, 68, 60, 76, 35, 70, 110, 92, 42, 125, 169, 126, 84, 203, 150, 186, 72, 165, 289, 175, 96, 333, 342, 208, 135, 410, 308, 430, 198, 225, 460, 423, 124, 490, 525, 408, 299, 689, 549, 385, 252, 532, 841, 767, 270

Offset: 1

Christopher Hunt Gribble, Sep 30 2009

nonn

The table below shows n, the number of nonzero quadratic residues (QRs) of n (A105612), the sum of the QRs of n and the nonzero QRs of n (A046071) for n = 1..10.
..n..num QNRs..sum QNRs.........QNRs
..1.........0.........0
..2.........1.........1.........1
..3.........1.........1.........1
..4.........1.........1.........1
..5.........2.........5.........1..4
..6.........3.........8.........1..3..4
..7.........3.........7.........1..2..4
..8.........2.........5.........1..4
..9.........3........12.........1..4..7
.10.........5........25.........1..4..5..6..9
When p is prime >= 5, a(p) is a multiple of p by a variant of Wolstenholme's theorem (see A076409 and A076410). Robert Israel remarks that we don't need Wolstenholme, just the fact that Sum_{x=1..p-1} x^2 = p*(2*p-1)*(p-1)/6. - Bernard Schott, Mar 13 2019

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 4th ed., Oxford Univ. Press, 1960, pp. 88-90.

Alois P. Heinz, Table of n, a(n) for n = 1..10000 (first 1000 terms from C. H. Gribble)

Row sums of A046071 and of A096008.

Cf. A000290, A076409, A076410.

import Data.List (nub)
a165909 n = sum $ nub $ map (`mod` n) $
                        take (fromInteger n) $ tail a000290_list
-- Reinhard Zumkeller, Aug 01 2012

residueQ[n_, k_] := Length[Select[Range[Floor[k/2]], PowerMod[#, 2, k] == n&, 1]] == 1;
a[n_] := Select[Range[n-1], residueQ[#, n]&] // Total;
Array[a, 60] (* Jean-François Alcover, Mar 13 2019 *)

a(n) = sum(k=0, n-1, k*issquare(Mod(k,n))); \\ Michel Marcus, Mar 13 2019

A165913 Irregular triangle read by rows: Squarefree nonzero quadratic residues.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 7, 1, 5, 6, 1, 3, 5, 1, 1, 3, 10, 1, 2, 7, 11, 1, 6, 10, 1, 1, 2, 13, 15, 1, 7, 10, 13, 1, 5, 6, 7, 11, 17, 1, 5, 1, 7, 15, 1, 3, 5, 11, 14, 15, 1, 2, 3, 6, 13, 1, 1, 6, 11, 14, 19, 21, 1, 3, 10, 13, 14, 17, 22, 23, 1, 7, 10, 13, 19, 22, 1, 21, 1, 5, 6, 7, 13, 22, 23

Offset: 1

Christopher Hunt Gribble, Sep 30 2009

The irregular triangle of numbers is:
..n....Squarefree nonzero quadratic residues
..1....
..2....1
..3....1
..4....1
..5....1
..6....1..3
..7....1..2
..8....1
..9....1..7
.10....1..5..6
.11....1..3..5
.12....1
.13....1..3.10
.14....1..2..7.11
.15....1..6.10
.16....1
.17....1..2.13.15
.18....1..7.10.13
.19....1..5..6..7.11.17
.20....1..5
.21....1..7.15
.22....1..3..5.11.14.15
.23....1..2..3..6.13
.24....1
.25....1..6.11.14.19.21
.26....1..3.10.13.14.17.22.23
.27....1..7.10.13.19.22
.28....1.21
.29....1..5..6..7.13.22.23

C. H. Gribble, Flattened irregular triangle read by rows as table of j, a(j) for j = 1: 78998 (rows 2:1000).

Cf. A046071.

Minor edit by Christopher Hunt Gribble, Oct 05 2009

A165919 Irregular triangle read by rows: square-full nonzero quadratic residues mod n.

Original entry on oeis.org

4, 4, 4, 4, 4, 4, 9, 4, 9, 4, 9, 4, 9, 12, 4, 8, 9, 4, 9, 4, 9, 4, 8, 9, 16, 4, 9, 16, 4, 9, 16, 4, 9, 16, 4, 9, 16, 18, 4, 9, 12, 16, 20, 4, 8, 9, 12, 16, 18, 4, 9, 12, 16, 4, 9, 16, 24, 4, 9, 12, 16, 25, 4, 9, 16, 25, 4, 8, 9, 16, 25, 4, 9, 16, 20, 24, 25, 28, 4, 9, 16, 24, 25

Offset: 5

Christopher Hunt Gribble, Sep 30 2009

The irregular triangle of numbers is:
..n....Square-full nonzero quadratic residues
..1....
..2....
..3....
..4....
..5.....4
..6.....4
..7.....4
..8.....4
..9.....4
.10.....4..9
.11.....4..9
.12.....4..9
.13.....4..9.12
.14.....4..8..9
.15.....4..9
.16.....4..9
.17.....4..8..9.16
.18.....4..9.16
.19.....4..9.16
.20.....4..9.16
.21.....4..9.16.18
.22.....4..9.12.16.20
.23.....4..8..9.12.16.18
.24.....4..9.12.16
.25.....4..9.16.24
.26.....4..9.12.16.25
.27.....4..9.16.25
.28.....4..8..9.16.25
.29.....4..9.16.20.24.25
.30.....4..9.16.24.25

C. H. Gribble, Flattened irregular triangle read by rows as table of j, a(j) for j = 5..69744 (rows 5:1000). [Entries in b-file edited by _N. J. A. Sloane_, Oct 04 2010]

Cf. A046071.

Minor edit and cross-reference added by Christopher Hunt Gribble, Oct 05 2009

Offset set to 5, keyword:tabf added - R. J. Mathar, Oct 09 2009

A372651 a(n) is the product of the distinct nonzero quadratic residues of n.

Original entry on oeis.org

1, 1, 1, 1, 4, 12, 8, 4, 28, 1080, 540, 36, 12960, 44352, 2160, 36, 1797120, 524160, 22619520, 2880, 1088640, 4790016000, 465813504, 6912, 5096577024, 8115883776000, 5477472000, 2419200, 267346759680000, 124104960000, 216218419200000, 244800, 143187264000

Offset: 1

Darío Clavijo, May 27 2024

nonn

Cf. A046071, A105612, A165909, A230366, A232195.

a(n) = my(list=List()); for (i=1, n-1, if (issquare(Mod(i, n)), listput(list, i))); vecprod(Vec(list)); \\ Michel Marcus, May 28 2024

from sympy import prod
def a(n):
  k, QS = 0,[]
  for i in range((n >> 1) + 1):
    if k > 0: QS.append(k)
    k += (i << 1) + 1
    k %= n
  return prod(set(QS))
print([a(n) for n in range(1, 34)])

from math import prod
from sympy.ntheory.residue_ntheory import quadratic_residues
def A372651(n): return prod(r for r in quadratic_residues(n) if r) # Chai Wah Wu, May 30 2024

a(n) mod n = A232195(n).

a(n) = Product_{k=1..n} A046071(n,k).

A166715 Irregular triangle read by rows: row n lists nonzero quadratic residues modulo the n-th term of A123239.

Original entry on oeis.org

1, 1, 1, 3, 4, 5, 9, 1, 3, 4, 9, 10, 12, 1, 3, 4, 7, 9, 10, 11, 12, 16, 21, 25, 26, 27, 28, 30, 33, 34, 36, 1, 2, 4, 5, 8, 9, 10, 16, 18, 20, 21, 23, 25, 31, 32, 33, 36, 37, 39, 40, 1, 3, 4, 5, 7, 9, 12, 15, 16, 17, 19, 20, 21, 22, 25, 26, 27

Offset: 1

A.K. Devaraj, Oct 20 2009

			Triangle starts:
1;
1;
1,3,4,5,9;
1,3,4,9,10,12;
...
Modulo A123239(3)=11, the quadratic residues are 1,3,4,5,9.

G. C. Greubel, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Quadratic Residue.

Cf. A046071, A063987, A123239.

MangammalQ[p_]:=Block[{k=3},While[k>2,k=Mod[3k,p]];k!=2];
A123239=Select[Prime[Range[17]],MangammalQ];
A166715=Flatten[Union[Mod[Range[Floor[#/2]]^2,#]]&/@A123239] (* Ray Chandler, Jul 21 2011 *)

Edited by N. J. A. Sloane, Oct 22 2009
Edited by Charles R Greathouse IV, Oct 28 2009
Edited, corrected and extended by Ray Chandler, Jul 21 2011

A096103 Table read by rows: row n contains the quadratic residues modulo n which are coprime to n.

Original entry on oeis.org

1, 1, 1, 1, 4, 1, 1, 2, 4, 1, 1, 4, 7, 1, 9, 1, 3, 4, 5, 9, 1, 1, 3, 4, 9, 10, 12, 1, 9, 11, 1, 4, 1, 9, 1, 2, 4, 8, 9, 13, 15, 16, 1, 7, 13, 1, 4, 5, 6, 7, 9, 11, 16, 17, 1, 9, 1, 4, 16, 1, 3, 5, 9, 15, 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18, 1, 1, 4, 6, 9, 11, 14, 16, 19, 21, 24, 1, 3, 9, 17, 23, 25, 1, 4

Offset: 2

Cino Hilliard, Jul 21 2004

Each '1' begins a row.

Row lengths are A046073. - Geoffrey Critzer, Jan 02 2015

			1;
1;
1;
1,4;
1;
1, 2, 4;
1;
1, 4, 7;
1, 9;
1, 3, 4, 5, 9;
1;
1, 3, 4, 9, 10, 12;
1, 9, 11;
1, 4;

Eric Weisstein's World of Mathematics, Quadratic Residue

Cf. A046071, A046073.

Table[Union[Mod[Select[Range[n], CoprimeQ[#, n] &]^2, n]], {n, 2, 20}] // Grid (* Geoffrey Critzer, Jan 02 2015 *)

maybesqgcd1(n) = { for(x=2,n, b=floor(x/2); a=vector(b+1); for(y=1,b, z=y^2%x; if(z<>0, a[y]=z; ) ); s=vecsort(a); c=1; for(j=2,b+1, if(s[j]<>s[j-1], c++; if(gcd(x,s[j])==1,print1(s[j]",")) ) ); ) }

Edited by Don Reble, Apr 16 2007

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

SageMath

Extensions

A063987 Irregular triangle in which n-th row gives quadratic residues modulo the n-th prime.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

SageMath

Extensions

A048152 Triangular array T read by rows: T(n,k) = k^2 mod n, for 1 <= k <= n, n >= 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

A034794 a(n) is the least prime p > a(n-1) such that a(n-1) is a quadratic residue mod p.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Extensions

A165909 a(n) is the sum of the quadratic residues of n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

A165913 Irregular triangle read by rows: Squarefree nonzero quadratic residues.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A165919 Irregular triangle read by rows: square-full nonzero quadratic residues mod n.

Views

Author

Keywords

Comments