A165909 -id:A165909 - 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

A046071 Triangle of nonzero quadratic residues mod n.

Original entry on oeis.org

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

Eric W. Weisstein

Rows start with 1'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, 12,
1, 2, 4, 7, 8, 9, 11
1, 4, 6, 9, 10,
- _Geoffrey Critzer_, Apr 03 2015

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

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

Cf. A096008 (including zeros), A063987.

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

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

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

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

for n in range(2, 16): print(quadratic_residues(n)[1:]) # Peter Luschny, Jun 02 2024

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

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).

A373286 a(n) = Product_{k=1..n} (k^2 mod n if k^2 mod n > 0).

Original entry on oeis.org

1, 1, 1, 1, 16, 48, 64, 16, 784, 233280, 291600, 20736, 167961600, 281014272, 74649600, 1679616, 3229640294400, 2472693350400, 511642685030400, 2751882854400, 4854321355161600, 2085841207296000000, 216982220508758016, 15850845241344, 25975097361564696576

Offset: 1

Darío Clavijo, May 30 2024

nonn

a(n) mod A372651(n) = 0.

Cf. A165909, A230366, A372651.

a[n_]:=Product[Max[Mod[k^2,n],1],{k,n}]; Array[a,25] (* Stefano Spezia, May 30 2024 *)

a(n) = my(x); prod(k=1, n, if ((x=lift(Mod(k,n)^2))>0, x, 1)); \\ Michel Marcus, May 30 2024

def a(n):
  tmp = 1
  for i in range(1, n+1):
    if (k := pow(i,2,n)): tmp *= k
  return tmp
print([a(n) for n in range(1, 26)])

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

A046071 Triangle of nonzero quadratic residues mod n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

SageMath

Extensions

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

Views

Author

Keywords

Crossrefs

Programs

PARI

Python

Python

Formula

A373286 a(n) = Product_{k=1..n} (k^2 mod n if k^2 mod n > 0).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Python