A105612 -id:A105612 - cp's OEIS frontend

A000224 Number of squares mod n.

1, 2, 2, 2, 3, 4, 4, 3, 4, 6, 6, 4, 7, 8, 6, 4, 9, 8, 10, 6, 8, 12, 12, 6, 11, 14, 11, 8, 15, 12, 16, 7, 12, 18, 12, 8, 19, 20, 14, 9, 21, 16, 22, 12, 12, 24, 24, 8, 22, 22, 18, 14, 27, 22, 18, 12, 20, 30, 30, 12, 31, 32, 16, 12, 21, 24, 34, 18, 24, 24, 36, 12

Offset: 1

N. J. A. Sloane

For any n > 2, there are quadratic nonresidues mod n, so a(n) < n. - Charles R Greathouse IV, Oct 28 2022
Conjecture: n^2 == 1 (mod a(n)*(a(n)-1)) if and only if n is an odd prime. - Thomas Ordowski, Apr 13 2025
This conjecture holds at least up to n = 10^8. - Michel Marcus, Apr 13 2025

			The sequence of squares (A000290) modulo 10 reads 0, 1, 4, 9, 6, 5, 6, 9, 4, 1, 0, 1, 4, 9, 6, 5, 6, 9, 4, 1,... and this reduced sequence contains a(10) = 6 different values, {0,1,4,5,6,9}. - _R. J. Mathar_, Oct 10 2014

T. D. Noe, Table of n, a(n) for n = 1..10000
Imanuel Chen and Michael Z. Spivey, Integral Generalized Binomial Coefficients of Multiplicative Functions, Preprint 2015; Summer Research Paper 238, Univ. Puget.
Steven R. Finch and Pascal Sebah, Squares and Cubes Modulo n, arXiv:math/0604465 [math.NT], 2006-2016.
Shuguang Li, On the number of elements with maximal order in the multiplicative group modulo n, Acta Arithm. 86 (2) (1998) 113, see proof of theorem 2.1.
Param Parekh, Paavan Parekh, Sourav Deb, and Manish K. Gupta, On the Classification of Weierstrass Elliptic Curves over Z_n, arXiv:2310.11768 [cs.CR], 2023. See p. 6.
E. J. F. Primrose, The number of quadratic residues mod m, Math. Gaz. v. 61 (1977) n. 415, 60-61.
Walter D. Stangl, Counting Squares in Z_n, Math. Mag. 69 (1996) 285-289.

Cf. A095972, A046530 (cubic residues), A052273 (4th powers), A052274 (5th powers), A052275 (6th powers), A085310 (7th powers), A085311 (8th powers), A085312 (9th powers), A085313 (10th powers), A085314 (11th powers), A228849 (12th powers).

a000224 n = product $ zipWith f (a027748_row n) (a124010_row n) where
   f 2 e = 2 ^ e `div` 6 + 2
   f p e = p ^ (e + 1) `div` (2 * p + 2) + 1
-- Reinhard Zumkeller, Aug 01 2012

A000224 := proc(m)
    {seq( modp(b^2,m),b=0..m-1) };
    nops(%) ;
end proc: # Emeric Deutsch
# 2nd implementation
A000224 := proc(n)
    local a,ifs,f,p,e,c ;
    a := 1 ;
    ifs := ifactors(n)[2] ;
    for f in ifs do
        p := op(1,f) ;
        e := op(2,f) ;
        if p = 2 then
            if type(e,'odd') then
                a := a*(2^(e-1)+5)/3 ;
            else
                a := a*(2^(e-1)+4)/3 ;
            end if;
        else
            if type(e,'odd') then
                c := 2*p+1 ;
            else
                c := p+2 ;
            end if;
            a := a*(p^(e+1)+c)/2/(p+1) ;
        end if;
    end do:
    a ;
end proc: # R. J. Mathar, Oct 10 2014

Length[Union[#]]& /@ Table[Mod[k^2, n], {n, 65}, {k, n}] (* Jean-François Alcover, Aug 30 2011 *)
a[2] = 2; a[n_] := a[n] = Switch[fi = FactorInteger[n], {{, 1}}, (fi[[1, 1]] + 1)/2, {{2, }}, 3/2 + 2^fi[[1, 2]]/6 + (-1)^(fi[[1, 2]]+1)/6, {{, }}, {p, k} = fi[[1]]; 3/4 + (p-1)*(-1)^(k+1)/(4*(p+1)) + p^(k+1)/(2*(p+1)), , Times @@ Table[ a[Power @@ f], {f, fi}]]; Table[a[n], {n, 1, 100}] (* _Jean-François Alcover, Mar 09 2015 *)

a(n) = local(v,i); v = vector(n,i,0); for(i=0, floor(n/2),v[i^2%n+1] = 1); sum(i=1,n,v[i]) \\ Franklin T. Adams-Watters, Nov 05 2006

a(n)=my(f=factor(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 A000224(n): return 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) = A105612(n) + 1.
Multiplicative with a(p^e) = floor(p^e/6) + 2 if p = 2; floor(p^(e+1)/(2p + 2)) + 1 if p > 2. - David W. Wilson, Aug 01 2001
a(2^n) = A023105(n). a(3^n) = A039300(n). a(5^n) = A039302(n). a(7^n) = A039304(n). - R. J. Mathar, Sep 28 2017
Sum_{k=1..n} a(k) ~ c * n^2/sqrt(log(n)), where c = (17/(32*sqrt(Pi))) * Product_{p prime} (1 - (p^2+2)/(2*(p^2+1)*(p+1))) * (1-1/p)^(-1/2) = 0.37672933209687137604... (Finch and Sebah, 2006). - Amiram Eldar, Oct 18 2022
If p is an odd prime, then a(p) = (p + 1)/2. - Thomas Ordowski, Apr 09 2025

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

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

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

A271547 Decimal expansion of Product_{p prime} (1+1/(2p))*sqrt(1-1/p), a constant related to the asymptotic average number of squares modulo n.

Original entry on oeis.org

8, 1, 2, 1, 0, 5, 7, 1, 1, 1, 6, 3, 1, 2, 2, 5, 1, 1, 7, 0, 6, 2, 5, 0, 9, 6, 4, 5, 8, 1, 8, 8, 7, 1, 7, 6, 5, 6, 0, 5, 7, 7, 1, 0, 0, 4, 8, 3, 6, 6, 9, 9, 2, 4, 3, 6, 0, 9, 2, 1, 8, 2, 0, 0, 3, 7, 8, 0, 9, 4, 0, 6, 2, 0, 4, 2, 5, 3, 2, 2, 0, 7, 5, 5, 8, 0, 2, 5, 4, 0, 2, 3, 5, 0, 4, 0, 2, 9, 9, 8

Offset: 0

Jean-François Alcover, Apr 10 2016

			0.81210571116312251170625096458188717656057710048366992436092182...

Steven R. Finch and Pascal Sebah, Squares and Cubes Modulo n, arXiv:math/0604465 [math.NT], 2006-2016.

Cf. A046073, A105612.

digits = 100; Exp[NSum[-( (-1)^n + 2^(n - 1))*PrimeZetaP[n]/(n* 2^n), {n, 2, Infinity}, NSumTerms -> 3 digits, WorkingPrecision -> digits + 10]] // RealDigits[#, 10, digits]& // First

Equals exp(Sum_{n>=2} -((-1)^n + 2^(n-1))*P(n)/(n*2^n)), where P(n) is the prime zeta P function.

A182865 Minimal number of quadratic residues: a(n) is the least integer m such that any nonzero square is congruent (mod n) to one of the squares from 1 to m^2.

Original entry on oeis.org

1, 1, 1, 2, 3, 3, 2, 4, 5, 5, 3, 6, 7, 6, 3, 8, 8, 9, 5, 9, 11, 11, 6, 12, 13, 13, 7, 14, 15, 15, 7, 15, 17, 15, 8, 18, 19, 18, 10, 20, 21, 21, 11, 20, 23, 23, 9, 24, 24, 24, 13, 26, 26, 25, 14, 27, 29, 29, 15, 30, 31, 28, 15, 30, 33, 33, 17, 33, 35, 35, 16, 36, 37, 36, 19, 35, 39, 39, 15, 40, 41, 41, 21, 40, 43, 42, 22, 44, 40, 42, 23, 45, 47, 45, 21, 48, 48, 44, 24

Offset: 2

Jean-François Alcover, Feb 01 2011

Up to n=3600, a(n) is equal to floor(n/2) 1262 times (about 35% of the cases).
Sometimes the ratio a(n)/n is unexpectedly low:
a(100)/100 = 24/100 = 0.24
a(144)/144 = 23/144 = 0.159722...
a(3600)/3600 = 539/3600 = 0.149722...

			For n = 100, one gets a(100) = 24 (far less than the expected floor(100/2) = 50).

Vincenzo Librandi, Table of n, a(n) for n = 2..1000
Eric Weisstein's World of Mathematics, Quadratic Residue

It should be noticed that, when n is prime, the corresponding sublist is A005097, i.e., (primes-1)/2.
Cf. A096008.
Sequence A105612 (number of nonzero quadratic residues mod n) is different from this sequence at positions such as 9, 15, 18, 21, and 24.

q[n_, k_] := Cases[Union[Mod[Range[k]^2, n]],_?Positive];
a[n_] := (r = q[n, Floor[n/2]]; k = 0; While[r != q[n, ++k]]; k); Table[a[n], {n, 2, 100}]

Formula and sequence corrected to eliminate zeros from lists of quadratic residues. Anyway, mod computed with or without offset 1 gives the same list.

A269472 Decimal expansion of Product_{p prime} (1-(p^2+2)/(2(p^2+1)(p+1))) / sqrt(1-1/p), a constant related to the asymptotic average number of squares modulo n.

Original entry on oeis.org

1, 2, 5, 6, 9, 1, 3, 6, 1, 0, 2, 1, 0, 1, 8, 8, 5, 9, 5, 9, 4, 9, 2, 1, 1, 5, 7, 6, 9, 4, 6, 8, 6, 0, 8, 9, 4, 9, 4, 0, 4, 5, 9, 8, 8, 6, 8, 0, 7, 5, 0, 8, 7, 6, 7, 7, 9, 8, 5, 7, 1, 8, 1, 9, 3, 4, 7, 5, 1, 8, 2, 3, 8, 4, 5, 7, 4, 5, 4, 1, 4, 8, 7, 5, 5, 3, 9, 7, 5, 4, 8, 9, 7, 8, 6, 4, 9, 1, 1, 5, 7, 6, 4, 5, 0, 9, 9, 6

Offset: 1

Jean-François Alcover, Apr 13 2016

			1.2569136102101885959492115769468608949404598868075...

Steven R. Finch and Pascal Sebah, Squares and Cubes Modulo n, arXiv:math/0604465 [math.NT], 2006-2016.

Cf. A046073, A105612, A271547.

digits = 104; m0 = 100; Clear[s]; s[m_] := s[m] = Sum[(1 + 2*(-1)^n - 4*(-1)^n*ChebyshevT[n, 1/4] + 4*Switch[Mod[n, 4], 2, -1, 3, 0, 0, 1, 1, 0])/(2*n) PrimeZetaP[n], {n, 2, m}] // N[#, digits]& // Exp; s[m0]; s[m = 2 m0]; While[RealDigits[s[m], 10, digits] != RealDigits[s[m/2], 10, digits], m = 2 m; Print[m]]; RealDigits[s[m]][[1]]
(* Second program: *)
$MaxExtraPrecision = 1000; Clear[f]; f[p_] := (1 - (p^2 + 2)/(2 (p^2 + 1) (p + 1)))/ Sqrt[1 - 1/p]; Do[c = Rest[CoefficientList[Series[Log[f[1/x]], {x, 0, m}], x]]; Print[f[2] * Exp[N[Sum[Indexed[c, n]*(PrimeZetaP[n] - 1/2^n), {n, 2, m}], 112]]], {m, 100, 1000, 100}] (* Vaclav Kotesovec, Jun 19 2020 *)

sqrt(prodeulerrat((1-(p^2+2)/(2*(p^2+1)*(p+1)))^2/(1-1/p))) \\ Amiram Eldar, May 29 2021

Formula in name and last digit corrected by Vaclav Kotesovec, Jun 19 2020

cp's OEIS Frontend

A000224 Number of squares mod n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

A046071 Triangle of nonzero quadratic residues mod n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

SageMath

Extensions

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

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

Views

Author

Keywords

Crossrefs

Programs

PARI

Python

Python

Formula

A271547 Decimal expansion of Product_{p prime} (1+1/(2p))*sqrt(1-1/p), a constant related to the asymptotic average number of squares modulo n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A182865 Minimal number of quadratic residues: a(n) is the least integer m such that any nonzero square is congruent (mod n) to one of the squares from 1 to m^2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A269472 Decimal expansion of Product_{p prime} (1-(p^2+2)/(2(p^2+1)(p+1))) / sqrt(1-1/p), a constant related to the asymptotic average number of squares modulo n.

Views

Author

Keywords

Examples