|
%I #64 Oct 25 2023 09:31:02
%S 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 29,30,11,19,33,34,15,9,13,14,15,25,41,18,15,33,15,46,47,30,15,42,51,
%U 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 Number of distinct cubic residues mod n.
%C Cubic analog of A000224. - _Steven Finch_, Mar 01 2006
%C A074243 contains values of n such that a(n) = n. - _Dmitri Kamenetsky_, Nov 03 2012
%H T. D. Noe, <a href="/A046530/b046530.txt">Table of n, a(n) for n = 1..1000</a>
%H 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 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 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 a(n) = n - A257301(n). - _Stanislav Sykora_, Apr 21 2015
%F 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 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 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 := proc(n)
%p local a,pf ;
%p a := 1 ;
%p if n = 1 then
%p return 1;
%p end if;
%p for i in ifactors(n)[2] do
%p p := op(1,i) ;
%p e := op(2,i) ;
%p if p = 3 then
%p if e mod 3 = 0 then
%p a := a*(3^(e+1)+10)/13 ;
%p elif e mod 3 = 1 then
%p a := a*(3^(e+1)+30)/13 ;
%p else
%p a := a*(3^(e+1)+12)/13 ;
%p end if;
%p elif p mod 3 = 2 then
%p if e mod 3 = 0 then
%p a := a*(p^(e+2)+p+1)/(p^2+p+1) ;
%p elif e mod 3 = 1 then
%p a := a*(p^(e+2)+p^2+p)/(p^2+p+1) ;
%p else
%p a := a*(p^(e+2)+p^2+1)/(p^2+p+1) ;
%p end if;
%p else
%p if e mod 3 = 0 then
%p a := a*(p^(e+2)+2*p^2+3*p+3)/3/(p^2+p+1) ;
%p elif e mod 3 = 1 then
%p a := a*(p^(e+2)+3*p^2+3*p+2)/3/(p^2+p+1) ;
%p else
%p a := a*(p^(e+2)+3*p^2+2*p+3)/3/(p^2+p+1) ;
%p end if;
%p end if;
%p end do:
%p a ;
%p end proc:
%p seq(A046530(n),n=1..40) ; # _R. J. Mathar_, Nov 01 2011
%t Length[Union[#]]& /@ Table[Mod[k^3, n], {n, 75}, {k, n}] (* _Jean-François Alcover_, Aug 30 2011 *)
%t Length[Union[#]]&/@Table[PowerMod[k,3,n],{n,80},{k,n}] (* _Harvey P. Dale_, Aug 12 2015 *)
%o (Haskell)
%o import Data.List (nub)
%o a046530 n = length $ nub $ map (`mod` n) $
%o take (fromInteger n) $ tail a000578_list
%o -- _Reinhard Zumkeller_, Aug 01 2012
%o (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 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 (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 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 Cf. A000578, A087786, A257301.
%K nonn,mult,easy,nice
%O 1,2
%A _David W. Wilson_
|
