A096013 -id:A096013 - cp's OEIS frontend

A095972 Number of quadratic nonresidues modulo n.

0, 0, 1, 2, 2, 2, 3, 5, 5, 4, 5, 8, 6, 6, 9, 12, 8, 10, 9, 14, 13, 10, 11, 18, 14, 12, 16, 20, 14, 18, 15, 25, 21, 16, 23, 28, 18, 18, 25, 31, 20, 26, 21, 32, 33, 22, 23, 40, 27, 28, 33, 38, 26, 32, 37, 44, 37, 28, 29, 48, 30, 30, 47, 52, 44, 42, 33, 50, 45, 46, 35, 60, 36, 36, 53

Offset: 1

Cino Hilliard, Jul 21 2004

nonn

A218578(n) is the number of times n occurs in this sequence. - Dmitri Kamenetsky, Nov 03 2012

T. D. Noe, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Quadratic Nonresidue

Cf. A096013, A218578.

A095972 := proc(n)
    local a,q;
    a := 0 ;
    for q from 0 to n-1 do
        if numtheory[quadres](q,n) = -1 then
            a := a+1 ;
        end if;
    end do;
    a ;
end proc: # R. J. Mathar, Nov 05 2012

Table[Length[Complement[Range[n-1], Union[Mod[Range[n]^2, n]]]], {n, 100}] (* T. D. Noe, Nov 06 2012 *)

A095972(n)={local(v);v=vector(n,i,1);for(i=0,floor(n/2),v[i^2%n+1]=0);sum(i=1,n,v[i])} \\ Michael B. Porter, Apr 30 2010

a(n)=my(f=factor(n));n-prod(i=1,#f[,1],if(f[i,1]==2,2^f[1,2]\6+2,f[i,1]^(f[i,2]+1)\(2*f[i,1]+2)+1)) \\ Charles R Greathouse IV, Jul 15 2011

from math import prod
from sympy import factorint
def A095972(n): return n-prod((p**(e+1)//((p+1)*(q:=1+(p==2)))>>1)+q for p, e in factorint(n).items()) # Chai Wah Wu, Oct 07 2024

a(n) = n - A000224(n). - R. J. Mathar, Nov 05 2012

Edited by Don Reble, May 07 2006

A373748 Triangle read by rows: T(n, k) is k if k is a quadratic residue modulo n, otherwise is -k and is a quadratic nonresidue modulo n. T(0, 0) = 0 by convention.

Original entry on oeis.org

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

Offset: 0

Peter Luschny, Jun 27 2024

			Triangle starts:
  [0] [0]
  [1] [0,  1]
  [2] [0,  1,  2]
  [3] [0,  1, -2,  3]
  [4] [0,  1, -2, -3,  4]
  [5] [0,  1, -2, -3,  4,  5]
  [6] [0,  1, -2,  3,  4, -5,  6]
  [7] [0,  1,  2, -3,  4, -5, -6,  7]
  [8] [0,  1, -2, -3,  4, -5, -6, -7,  8]
  [9] [0,  1, -2, -3,  4, -5, -6,  7, -8,  9]
 [10] [0,  1, -2, -3,  4,  5,  6, -7, -8,  9,  10]

Carl Friedrich 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.
Peter Luschny, SageMath: is_quadratic_residue.

Signed version of A002262.
Cf. A000004 (column 0), A001477 (main diagonal), A255644(n) + n (row sums).
Cf. A096008, A096013, A373749.

QR := (a, n) -> ifelse(n = 0, 1, NumberTheory:-QuadraticResidue(a, n)):
for n from 0 to 10 do seq(a*QR(a, n), a = 0..n) od;

qr[n_] := qr[n] = Join[Table[PowerMod[k, 2, n], {k, 0, Floor[n/2]}], {n}];
T[0, 0] := 0; T[n_, k_] := If[MemberQ[qr[n], k], k, -k];
Table[T[n, k], {n, 0, 11}, {k, 0, n}] // Flatten

def Trow(n):
    q = set(mod(a * a, n) for a in range(n // 2  + 1)).union({n})
    return [k if k in q else -k for k in range(n + 1)]
for n in range(11): print(Trow(n))

A165898 a(n) = sum of the quadratic nonresidues of n.

Original entry on oeis.org

0, 0, 2, 5, 5, 7, 14, 23, 24, 20, 33, 52, 39, 49, 75, 106, 68, 93, 95, 155, 140, 121, 161, 234, 175, 156, 225, 294, 203, 285, 279, 424, 363, 272, 420, 534, 333, 361, 533, 645, 410, 553, 473, 748, 765, 575, 658, 1004, 686, 700, 867, 1027, 689, 882, 1100, 1288

Offset: 1

Christopher Hunt Gribble, Sep 29 2009

nonn

The table below shows n, the number of quadratic nonresidues (QNRs)
of n (A095972), the sum of the QNRs of n and the QNRs of n (A096013)
for n=1:10.
..n..num QNRs..sum QNRs.........QNRs
..1.........0.........0
..2.........0.........0
..3.........1.........2.........2
..4.........2.........5.........2..3
..5.........2.........5.........2..3
..6.........2.........7.........2..5
..7.........3........14.........3..5..6
..8.........5........23.........2..3..5..6..7
..9.........5........24.........2..3..5..6..8
.10.........4........20.........2..3..7..8

C. H. Gribble, Table of n, a(n) for n=1,...,1000.

Cf. A096013

A165916 Irregular triangle read by rows: squarefree quadratic non-residues.

Original entry on oeis.org

2, 2, 3, 2, 3, 2, 5, 3, 5, 6, 2, 3, 5, 6, 7, 2, 3, 5, 6, 2, 3, 7, 2, 6, 7, 10, 2, 3, 5, 6, 7, 10, 11, 2, 5, 6, 7, 11, 3, 5, 6, 10, 13, 2, 3, 5, 7, 11, 13, 14, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 3, 5, 6, 7, 10, 11, 14, 2, 3, 5, 6, 11, 14, 15, 17, 2, 3, 10, 13, 14, 15

Offset: 3

Christopher Hunt Gribble, Sep 30 2009

The irregular triangle of numbers is:
..n....Squarefree quadratic non-residues
..1....
..2....
..3....2
..4....2..3
..5....2..3
..6....2..5
..7....3..5..6
..8....2..3..5..6..7
..9....2..3..5..6
.10....2..3..7
.11....2..6..7.10
.12....2..3..5..6..7.10.11
.13....2..5..6..7.11
.14....3..5..6.10.13
.15....2..3..5..7.11.13.14
.16....2..3..5..6..7.10.11.13.14.15
.17....3..5..6..7.10.11.14
.18....2..3..5..6.11.14.15.17
.19....2..3.10.13.14.15

C. H. Gribble, Flattened irregular triangle read by rows j = 3 to 200

Cf. A096013.

Flatten[Table[Select[Complement[Range[n - 1], Mod[Range[n/2]^2, n]], SquareFreeQ], {n, 3, 30}]] (* T. D. Noe, Nov 22 2011 *)

Minor edit by Christopher Hunt Gribble, Oct 05 2009

A165925 Irregular triangle read by rows: square-full quadratic non-residues.

Original entry on oeis.org

8, 8, 8, 8, 8, 12, 8, 12, 8, 12, 12, 8, 12, 8, 12, 18, 8, 12, 18, 8, 12, 20, 8, 18, 20, 8, 18, 20, 8, 12, 18, 20, 8, 18, 20, 24, 8, 12, 18, 20, 24, 12, 18, 20, 24, 27, 8, 12, 18, 27, 8, 12, 18, 20, 27, 28, 12, 24, 27, 8, 12, 18, 20, 24, 27, 28, 8, 18, 20, 24, 28, 32, 12, 20, 24, 27, 28

Offset: 9

Christopher Hunt Gribble, Sep 30 2009

The irregular triangle of numbers is:
..n....Square-full quadratic non-residues
..1....
..2....
..3....
..4....
..5....
..6....
..7....
..8....
..9.....8
.10.....8
.11.....8
.12.....8
.13.....8
.14....12
.15.....8.12
.16.....8.12
.17....12
.18.....8.12
.19.....8.12.18
.20.....8.12.18
.21.....8.12.20
.22.....8.18
.23....20
.24.....8.18.20
.25.....8.12.18.20
.26.....8.18.20.24
.27.....8.12.18.20.24
.28....12.18.20.24.27
.29.....8.12.18.27
.30.....8.12.18.20.27.28
.31....12.24.27
.32.....8.12.18.20.24.27.28
.33.....8.18.20.24.28.32
.34....12.20.24.27.28

C. H. Gribble, Flattened irregular triangle read by rows j = 9 to 200

Cf. A096013.

Flatten[Table[Select[Complement[Range[n - 1], Mod[Range[n/2]^2, n]], ! SquareFreeQ[#] &], {n, 9, 34}]] (* T. D. Noe, Nov 22 2011 *)

A028731 Nonsquares mod 18.

Original entry on oeis.org

2, 3, 5, 6, 8, 11, 12, 14, 15, 17

Offset: 1

N. J. A. Sloane

			Since 6 is not a perfect square and there is no solution in integers to x^2 = 6 mod 18, 6 is in the sequence.
Although 7 is not a perfect square either, we verify that x^2 = 7 mod 18 does have solutions, such as x = 5, x = 13. Therefore 7 is not in the sequence.

Cf. A010380.

Row 18 of A096013.

Complement[Range[17], PowerMod[Range[18], 2, 18]] (* Alonso del Arte, Nov 18 2019 *)

is(n) = n<18 && !issquare(Mod(n, 18)) \\ Felix Fröhlich, Dec 18 2019

val squaresMod18 = (0 to 17).map(n => n * n).map(_ % 18)
(0 to 17).diff(squaresMod18) // Alonso del Arte, Nov 18 2019

A028747 Nonsquares mod 34.

Original entry on oeis.org

3, 5, 6, 7, 10, 11, 12, 14, 20, 22, 23, 24, 27, 28, 29, 31

Offset: 1

N. J. A. Sloane

Cf. A010395, A096013 (row 34).

for(k=0, 34, if(!issquare(Mod(k, 34)), print1(k, ", "))) \\ Hugo Pfoertner, Dec 02 2019

Incorrect term 17 removed by Alonso del Arte, Nov 30 2019

A028792 Nonsquares mod 79.

Original entry on oeis.org

3, 6, 7, 12, 14, 15, 17, 24, 27, 28, 29, 30, 33, 34, 35, 37, 39, 41, 43, 47, 48, 53, 54, 56, 57, 58, 59, 60, 61, 63, 66, 68, 69, 70, 71, 74, 75, 77, 78

Offset: 1

N. J. A. Sloane

			x^2 = 7 mod 79 has no solutions, hence 7 is in the sequence.
x^2 = 8 mod 79 has the solutions x = 18 and x = 61, so 8 is not in the sequence.

Cf. A010440 (complement), A096013 (row 79).

[n: n in [0..78] | not IsSquare(R! n) where R:= ResidueClassRing(79)]; // Vincenzo Librandi, Jan 23 2020

Complement[Range[78], PowerMod[Range[78], 2, 79]] (* Alonso del Arte, Jan 15 2017 *)

isok(n) = (n < 79) && (kronecker(n, 79) == -1); \\ Michel Marcus, Jan 15 2017

isok(n) = (n < 79) && (! issquare(Mod(n, 79))); \\ Michel Marcus, Jan 15 2017

(0 to 78).diff((1 to 79).map(n => n * n % 79)) // Alonso del Arte, Jan 22 2020

Legendre symbol (a(n)/79) = -1. - Alonso del Arte, Jan 15 2017

A028796 Nonsquares mod 83.

Original entry on oeis.org

2, 5, 6, 8, 13, 14, 15, 18, 19, 20, 22, 24, 32, 34, 35, 39, 42, 43, 45, 46, 47, 50, 52, 53, 54, 55, 56, 57, 58, 60, 62, 66, 67, 71, 72, 73, 74, 76, 79, 80, 82

Offset: 1

N. J. A. Sloane

Cf. A010444 (complement), A096013 (row 83).

[n: n in [0..82] | not IsSquare(R! n) where R := ResidueClassRing(83)]; // Vincenzo Librandi, Jan 24 2020

Complement[Range[0, 82], PowerMod[Range[83], 2, 83]] (* Alonso del Arte, Jan 23 2020 *)

(0 to 82).diff((1 to 83).map(n => n * n % 83)) // Alonso del Arte, Jan 23 2020

A028802 Nonsquares mod 89.

Original entry on oeis.org

3, 6, 7, 12, 13, 14, 15, 19, 23, 24, 26, 27, 28, 29, 30, 31, 33, 35, 37, 38, 41, 43, 46, 48, 51, 52, 54, 56, 58, 59, 60, 61, 62, 63, 65, 66, 70, 74, 75, 76, 77, 82, 83, 86

Offset: 1

N. J. A. Sloane

Cf. A010450 (complement), A096013 (row 89).

Select[Range[88], JacobiSymbol[#, 89] == -1 &] (* Harvey P. Dale, Mar 01 2015 *)

(0 to 88).diff((1 to 89).map(n => n * n % 89)) // Alonso del Arte, Jan 24 2020

cp's OEIS Frontend

A095972 Number of quadratic nonresidues modulo n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A373748 Triangle read by rows: T(n, k) is k if k is a quadratic residue modulo n, otherwise is -k and is a quadratic nonresidue modulo n. T(0, 0) = 0 by convention.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

SageMath

A165898 a(n) = sum of the quadratic nonresidues of n.

Views

Author

Keywords

Comments

Links

Crossrefs

A165916 Irregular triangle read by rows: squarefree quadratic non-residues.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A165925 Irregular triangle read by rows: square-full quadratic non-residues.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A028731 Nonsquares mod 18.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI

Scala

A028747 Nonsquares mod 34.

Views

Author

Keywords

Crossrefs

Programs

PARI

Extensions

A028792 Nonsquares mod 79.

Views

Author

Keywords

Examples

Crossrefs

Programs

Magma

Mathematica