cp's OEIS Frontend

A046530 Number of distinct cubic residues mod n.

%I A046530 #66 Oct 05 2024 22:30:32
%S A046530 1,2,3,3,5,6,3,5,3,10,11,9,5,6,15,10,17,6,7,15,9,22,23,15,21,10,7,9,
%T A046530 29,30,11,19,33,34,15,9,13,14,15,25,41,18,15,33,15,46,47,30,15,42,51,
%U A046530 15,53,14,55,15,21,58,59,45,21,22,9,37,25,66,23,51,69,30,71,15,25,26,63
%N A046530 Number of distinct cubic residues mod n.
%C A046530 In other words, number of distinct cubes mod n. - _N. J. A. Sloane_, Oct 05 2024
%C A046530 Cubic analog of A000224. - _Steven Finch_, Mar 01 2006
%C A046530 A074243 contains values of n such that a(n) = n. - _Dmitri Kamenetsky_, Nov 03 2012
%H A046530 T. D. Noe, <a href="/A046530/b046530.txt">Table of n, a(n) for n = 1..1000</a>
%H A046530 Steven R. Finch and Pascal Sebah, <a href="http://arXiv.org/abs/math.NT/0604465">Squares and Cubes Modulo n</a>, arXiv:math/0604465 [math.NT], 2005-2016.
%H A046530 Shuguang Li, <a href="http://pldml.icm.edu.pl/pldml/element/bwmeta1.element.bwnjournal-article-aav86i2p113bwm">On the number of elements with maximal order in the multiplicative group modulo n</a>, Acta Arithm. 86 (2) (1998) 113, see proof of theorem 2.1.
%H A046530 Param Parekh, Paavan Parekh, Sourav Deb, and Manish K. Gupta, <a href="https://arxiv.org/abs/2310.11768">On the Classification of Weierstrass Elliptic Curves over Z_n</a>, arXiv:2310.11768 [cs.CR], 2023. See p. 7.
%F A046530 a(n) = n - A257301(n). - _Stanislav Sykora_, Apr 21 2015
%F A046530 a(2^n) = A046630(n). a(3^n) = A046631(n). a(5^n) = A046633(n). a(7^n) = A046635(n). - _R. J. Mathar_, Sep 28 2017
%F A046530 Multiplicative with a(p^e) = 1 + Sum_{i=0..floor((e-1)/3)} (p - 1)*p^(e-3*i-1)/k where k = 3 if (p = 3 and 3*i + 1 = e) or (p mod 3 = 1) otherwise k = 1. - _Andrew Howroyd_, Jul 17 2018
%F A046530 Sum_{k=1..n} a(k) ~ c * n^2/log(n)^(1/3), where c = (6/(13*Gamma(2/3))) * (2/3)^(-1/3) * Product_{p prime == 2 (mod 3)} (1 - (p^2+1)/((p^2+p+1)*(p^2-p+1)*(p+1))) * (1-1/p)^(-1/3) * Product_{p prime == 1 (mod 3)} (1 - (2*p^4+3*p^2+3)/(3*(p^2+p+1)*(p^2-p+1)*(p+1))) * (1-1/p)^(-1/3) = 0.48487418844474389597... (Finch and Sebah, 2006). - _Amiram Eldar_, Oct 18 2022
%p A046530 A046530 := proc(n)
%p A046530         local a,pf ;
%p A046530         a := 1 ;
%p A046530         if n = 1 then
%p A046530                 return 1;
%p A046530         end if;
%p A046530         for i in  ifactors(n)[2] do
%p A046530                 p := op(1,i) ;
%p A046530                 e := op(2,i) ;
%p A046530                 if p = 3 then
%p A046530                         if e mod 3 = 0 then
%p A046530                                 a := a*(3^(e+1)+10)/13 ;
%p A046530                         elif e mod 3 = 1 then
%p A046530                                 a := a*(3^(e+1)+30)/13 ;
%p A046530                         else
%p A046530                                 a := a*(3^(e+1)+12)/13 ;
%p A046530                         end if;
%p A046530                 elif p mod 3 = 2 then
%p A046530                         if e mod 3 = 0 then
%p A046530                                 a := a*(p^(e+2)+p+1)/(p^2+p+1) ;
%p A046530                         elif e mod 3 = 1 then
%p A046530                                 a := a*(p^(e+2)+p^2+p)/(p^2+p+1) ;
%p A046530                         else
%p A046530                                 a := a*(p^(e+2)+p^2+1)/(p^2+p+1) ;
%p A046530                         end if;
%p A046530                 else
%p A046530                         if e mod 3 = 0 then
%p A046530                                 a := a*(p^(e+2)+2*p^2+3*p+3)/3/(p^2+p+1) ;
%p A046530                         elif e mod 3 = 1 then
%p A046530                                 a := a*(p^(e+2)+3*p^2+3*p+2)/3/(p^2+p+1) ;
%p A046530                         else
%p A046530                                 a := a*(p^(e+2)+3*p^2+2*p+3)/3/(p^2+p+1) ;
%p A046530                         end if;
%p A046530                 end if;
%p A046530         end do:
%p A046530         a ;
%p A046530 end proc:
%p A046530 seq(A046530(n),n=1..40) ; # _R. J. Mathar_, Nov 01 2011
%t A046530 Length[Union[#]]& /@ Table[Mod[k^3, n], {n, 75}, {k, n}] (* _Jean-François Alcover_, Aug 30 2011 *)
%t A046530 Length[Union[#]]&/@Table[PowerMod[k,3,n],{n,80},{k,n}] (* _Harvey P. Dale_, Aug 12 2015 *)
%o A046530 (Haskell)
%o A046530 import Data.List (nub)
%o A046530 a046530 n = length $ nub $ map (`mod` n) $
%o A046530                            take (fromInteger n) $ tail a000578_list
%o A046530 -- _Reinhard Zumkeller_, Aug 01 2012
%o A046530 (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 A046530 a(n)=my(f=factor(n));prod(i=1,#f[,1],g(f[i,1],f[i,2])) \\ _Charles R Greathouse IV_, Jan 03 2013
%o A046530 (PARI) a(n)={my(f=factor(n)); prod(i=1, #f~, my(p=f[i,1], e=f[i,2]); 1 + sum(i=0, (e-1)\3, if(p%3==1 || (p==3&&3*i<e-1), 1/3, 1)*(p-1)*p^(e-3*i-1)) )} \\ _Andrew Howroyd_, Jul 17 2018
%Y A046530 For number of k-th power residues mod n, see A000224 (k=2), A052273 (k=4), A052274 (k=5), A052275 (k=6), A085310 (k=7), A085311 (k=8), A085312 (k=9), A085313 (k=10), A085314 (k=12), A228849 (k=13).
%Y A046530 Cf. A000578, A087786, A257301.
%K A046530 nonn,mult,easy,nice
%O A046530 1,2
%A A046530 _David W. Wilson_