cp's OEIS Frontend

A257301 Number of cubic nonresidues modulo n.

%I A257301 #18 Feb 22 2020 20:54:24
%S A257301 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,
%T A257301 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,
%U A257301 0,0,15,40,40,54,27,40,0,44,17,0,40,0,57,48,48,12,55,44,48,52,30
%N A257301 Number of cubic nonresidues modulo n.
%C A257301 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).
%H A257301 Stanislav Sykora, <a href="/A257301/b257301.txt">Table of n, a(n) for n = 1..10000</a>
%F A257301 a(n) = n - A046530(n).
%F A257301 Satisfies a(A074243(n))=0.
%F A257301 Satisfies a(n) <= n-3 (residues 0, 1, and n-1 are always present).
%F A257301 a(n) = n - A046530(n). - _Robert Israel_, Apr 20 2015
%e A257301 a(5)=0, because the set {(k^3)%5}, with k=0..4, evaluates to {0,1,3,2,4},
%e A257301         with no missing residue values.
%e A257301 a(7)=4, because the set {(k^3)%7}, with k=0..6, evaluates to
%e A257301         {0,1,1,6,1,6,6}, with missing residue values {2,3,4,5}.
%p A257301 seq(n - nops({seq(a^3 mod n,a=0..n-1)}), n=1..100); # _Robert Israel_, Apr 20 2015
%t A257301 Table[Length[Complement[Range[n - 1], Union[Mod[Range[n]^3, n]]]], {n, 100}] (* _Vincenzo Librandi_, Apr 20 2015 *)
%o A257301 (PARI) nrespowp(n,p) = {my(v=vector(n),d=0);
%o A257301   for(r=0,n-1,v[1+(r^p)%n]+=1);
%o A257301   for(k=1,n,if(v[k]==0,d++));
%o A257301   return(d);}
%o A257301 a(n) = nrespowp(n,3)
%o A257301 (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)))
%o A257301 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
%Y A257301 Nonresidues for other exponents: A095972 (p=2), A257302 (p=4), A257303 (p=5).
%Y A257301 Cf. A074243, A046530.
%K A257301 nonn
%O A257301 1,7
%A A257301 _Stanislav Sykora_, Apr 19 2015