A257301 Number of cubic nonresidues modulo n.

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

Author

Stanislav Sykora, Apr 19 2015

Keywords

• nonn

Comments

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

Examples

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

Links

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

Crossrefs

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

Cf. A074243, A046530.

Programs

Maple

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

Mathematica

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

PARI

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)

PARI

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

Formula

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