A095972 -id:A095972 - cp's OEIS frontend

A218578 The number of times n occurs in A095972.

2, 1, 3, 1, 1, 3, 2, 0, 2, 2, 2, 1, 2, 1, 3, 1, 2, 0, 4, 0, 2, 2, 1, 2, 0, 2, 2, 1, 3, 1, 2, 1, 2, 3, 0, 1, 2, 2, 1, 1, 2, 1, 2, 0, 3, 1, 2, 1, 2, 0, 4, 1, 2, 3, 2, 0, 2, 1, 2, 0, 2, 1, 0, 2, 0, 3, 3, 0, 4, 1, 2, 0, 2, 1, 3, 2, 0, 0, 3, 1, 0, 3, 2, 3, 0, 1, 3

Offset: 0

Dmitri Kamenetsky, Nov 03 2012

nonn

Alternative definition: a(n) = number of k such that A000224(k) = k - n.

			a(0) is 2, because 0 occurs only twice in A095972. a(1) is 1, because 1 occurs only once in A095972.

T. D. Noe, Table of n, a(n) for n = 0..10000

Cf. A000224, A095972, A218620 (greedy inverse).

A218578 := proc(n)
    local f;
    f := 0 ;
    for q from 1 to 2*n+2 do
        if A095972(q) = n then
            f := f+1 ;
        end if;
    end do:
    f ;
end proc: # R. J. Mathar, Nov 05 2012

nn = 100; t = Table[Length[Complement[Range[n-1], Union[Mod[Range[n]^2, n]]]], {n, 2*nn + 2}]; Table[Count[t, n], {n, 0, nn}] (* T. D. Noe, Nov 06 2012 *)

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

A218620 Least number m to appear exactly n times in A095972.

Original entry on oeis.org

7, 1, 0, 2, 18, 128, 443, 2666, 1353, 2706

Offset: 0

M. F. Hasler, Nov 03 2012

One has n/2 <= A095972(n)+1 <= n, therefore an integer m can appear in A095972 only between indices m and 2m, and this sequence is effectively computable.

A000224 Number of squares mod n.

Original entry on oeis.org

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

A096013 Irregular triangle read by rows: row n lists quadratic nonresidues modulo n.

Original entry on oeis.org

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

Offset: 3

Cino Hilliard, Jul 21 2004

The length of row n is A095972(n).

			Triangle starts:
  2;
  2, 3;
  2, 3;
  2, 5;
  3, 5, 6;
  2, 3, 5, 6, 7;
  2, 3, 5, 6, 8;
  ...

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

Cf. A095972.

(* As a Triangle *) Table[Complement[Range[n - 1], Mod[Range[n/2]^2, n]], {n, 3, 30}] // Column (* Mo Li, Sep 01 2019 *)

isA096013(n,m)={local(r);r=1;for(i=0,floor(m/2),if(i^2%m==n,r=0));r} \\ Michael B. Porter, May 05 2010

Edited by Don Reble, May 07 2006

A257301 Number of cubic nonresidues modulo n.

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 4, 3, 6, 0, 0, 3, 8, 8, 0, 6, 0, 12, 12, 5, 12, 0, 0, 9, 4, 16, 20, 19, 0, 0, 20, 13, 0, 0, 20, 27, 24, 24, 24, 15, 0, 24, 28, 11, 30, 0, 0, 18, 34, 8, 0, 37, 0, 40, 0, 41, 36, 0, 0, 15, 40, 40, 54, 27, 40, 0, 44, 17, 0, 40, 0, 57, 48, 48, 12, 55, 44, 48, 52, 30

Offset: 1

Stanislav Sykora, Apr 19 2015

nonn

a(n) is the number of values r, 0<=r=0, (m^p)%n != r. Compared to quadratic nonresidues (p=2, sequence A095972), the most evident difference is the frequent occurrence of a(n)=0 (for values of n which belong to A074243).

			a(5)=0, because the set {(k^3)%5}, with k=0..4, evaluates to {0,1,3,2,4},
        with no missing residue values.
a(7)=4, because the set {(k^3)%7}, with k=0..6, evaluates to
        {0,1,1,6,1,6,6}, with missing residue values {2,3,4,5}.

Stanislav Sykora, Table of n, a(n) for n = 1..10000

Nonresidues for other exponents: A095972 (p=2), A257302 (p=4), A257303 (p=5).

Cf. A074243, A046530.

seq(n - nops({seq(a^3 mod n,a=0..n-1)}), n=1..100); # Robert Israel, Apr 20 2015

Table[Length[Complement[Range[n - 1], Union[Mod[Range[n]^3, n]]]], {n, 100}] (* Vincenzo Librandi, Apr 20 2015 *)

nrespowp(n,p) = {my(v=vector(n),d=0);
  for(r=0,n-1,v[1+(r^p)%n]+=1);
  for(k=1,n,if(v[k]==0,d++));
  return(d);}
a(n) = nrespowp(n,3)

g(p, e)=if(p==3, (3^(e+1)+if(e%3==1, 30, if(e%3, 12, 10)))/13, if(p%3==2, (p^(e+2)+if(e%3==1, p^2+p, if(e%3, p^2+1, p+1)))/(p^2+p+1), (p^(e+2)+if(e%3==1, 3*p^2+3*p+2, if(e%3, 3*p^2+2*p+3, 2*p^2+3*p+3)))/3/(p^2+p+1)))
a(n)=my(f=factor(n)); n-prod(i=1, #f~, g(f[i,1], f[i,2])) \\ Charles R Greathouse IV, Apr 20 2015

a(n) = n - A046530(n).
Satisfies a(A074243(n))=0.
Satisfies a(n) <= n-3 (residues 0, 1, and n-1 are always present).
a(n) = n - A046530(n). - Robert Israel, Apr 20 2015

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

A257302 Number of 4th power nonresidues modulo n.

Original entry on oeis.org

0, 0, 1, 2, 3, 2, 3, 6, 5, 6, 5, 8, 9, 6, 11, 14, 12, 10, 9, 16, 13, 10, 11, 20, 19, 18, 17, 20, 21, 22, 15, 28, 21, 24, 27, 28, 27, 18, 31, 36, 30, 26, 21, 32, 37, 22, 23, 44, 27, 38, 41, 44, 39, 34, 43, 48, 37, 42, 29, 52, 45, 30, 47, 58, 57, 42, 33, 58

Offset: 1

Stanislav Sykora, Apr 19 2015

nonn

a(n) is the number of values r, 0<=r=0, (m^p)%n != r.

Stanislav Sykora, Table of n, a(n) for n = 1..10000

Cf. A095972 (p=2), A257301 (p=3), A257303 (p=5).

Table[Length[Complement[Range[n - 1], Union[Mod[Range[n]^4, n]]]], {n, 100}] (* Vincenzo Librandi, Apr 20 2015 *)

nrespowp(n,p) = {my(v=vector(n),d=0);
  for(r=0,n-1,v[1+(r^p)%n]+=1);
  for(k=1,n,if(v[k]==0,d++));
  return(d);}
a(n) = nrespowp(n,4)

a(n) = n - A052273(n).

Satisfies a(n) <= n-2 (residues 0 and 1 are always present).

A257303 Number of 5th power nonresidues modulo n.

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 0, 3, 2, 0, 8, 3, 0, 0, 0, 7, 0, 4, 0, 5, 0, 16, 0, 9, 20, 0, 8, 7, 0, 0, 24, 15, 24, 0, 0, 15, 0, 0, 0, 15, 32, 0, 0, 35, 10, 0, 0, 21, 6, 40, 0, 13, 0, 16, 40, 21, 0, 0, 0, 15, 48, 48, 14, 30, 0, 48, 0, 17, 0, 0, 56, 37, 0, 0, 60, 19, 56, 0, 0, 35, 26, 64, 0, 21, 0, 0, 0, 73, 0

Offset: 1

Stanislav Sykora, Apr 19 2015

nonn

a(n) is the number of values r, 0<=r=0, (m^p)%n != r.

Stanislav Sykora, Table of n, a(n) for n = 1..10000

Cf. A095972 (p=2), A257301 (p=3), A257302 (p=4).

Table[Length[Complement[Range[n - 1], Union[Mod[Range[n]^5, n]]]], {n, 100}] (* Vincenzo Librandi, Apr 20 2015 *)

nrespowp(n,p) = {my(v=vector(n),d=0);
  for(r=0,n-1,v[1+(r^p)%n]+=1);
  for(k=1,n,if(v[k]==0,d++));
  return(d);}
a(n) = nrespowp(n,5)

a(n) = n-A052274(n).

Satisfies a(n) <= n-3 (residues 0, 1, and n-1 are always present).

A212887 a(n) is the prime p corresponding to the smallest integer k such that k^2 == p (mod prime(n)).

Original entry on oeis.org

2, 5, 3, 2, 17, 2, 7, 5, 7, 23, 41, 2, 11, 5, 3, 59, 29, 71, 2, 17, 11, 3, 43, 41, 37, 7, 31, 17, 13, 7, 5, 47, 59, 47, 151, 2, 23, 17, 79, 5, 3, 59, 2, 113, 2, 29, 71, 23, 17, 83, 5, 67, 61, 131, 53, 47, 43, 41, 31, 17, 13, 11, 7, 67, 239, 53, 227, 47, 2, 107

Offset: 4

Michel Lagneau, May 29 2012

nonn

The corresponding values of k are {3, 4, 4, 6, 6, 5, 6, 6, 9, 8, 16, 7, 8, 8, 8, 27, …}

			a(8) = 17 because 17 == 6^2 mod 19 where 19 = prime(8) and 6 is the smallest k.
Remark : 11 == 7^2 mod 19, but 7 > 6.

Michel Lagneau, Table of n, a(n) for n = 4..10000

Cf. A000224, A095972.

for n from 2 to 100 do:p:=ithprime(n):i:=0:for k from 0 to p-1 while(i=0) do: q:=irem(k^2,p):if type(q,prime)=true then i:=1:printf(`%d, `,q):else fi:od:od:

cp's OEIS Frontend

A218578 The number of times n occurs in A095972.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

A218620 Least number m to appear exactly n times in A095972.

Views

Author

Keywords

Comments

A000224 Number of squares mod n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

A096013 Irregular triangle read by rows: row n lists quadratic nonresidues modulo n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A257301 Number of cubic nonresidues modulo n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

A257302 Number of 4th power nonresidues modulo n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A257303 Number of 5th power nonresidues modulo n.

Views