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,7

Comments

a(n) is the number of values r, 0<=r<n, such that, for p=3 and for any m>=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).

Links

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

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

Example

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

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

Prog

(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

Crossrefs

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

Cf. A074243, A046530.

Sequence in context: A316965 A241284 A019322 * A298801 A340297 A369928

Adjacent sequences: A257298 A257299 A257300 * A257302 A257303 A257304

Keyword

nonn

Author

Stanislav Sykora, Apr 19 2015

Status

approved