A046530 Number of distinct cubic residues mod n.
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, 29, 30, 11, 19, 33, 34, 15, 9, 13, 14, 15, 25, 41, 18, 15, 33, 15, 46, 47, 30, 15, 42, 51, 15, 53, 14, 55, 15, 21, 58, 59, 45, 21, 22, 9, 37, 25, 66, 23, 51, 69, 30, 71, 15, 25, 26, 63
Offset: 1
Links
- T. D. Noe, Table of n, a(n) for n = 1..1000
- Steven R. Finch and Pascal Sebah, Squares and Cubes Modulo n, arXiv:math/0604465 [math.NT], 2005-2016.
- Shuguang Li, On the number of elements with maximal order in the multiplicative group modulo n, Acta Arithm. 86 (2) (1998) 113, see proof of theorem 2.1.
- Param Parekh, Paavan Parekh, Sourav Deb, and Manish K. Gupta, On the Classification of Weierstrass Elliptic Curves over Z_n, arXiv:2310.11768 [cs.CR], 2023. See p. 7.
Crossrefs
Programs
-
Haskell
import Data.List (nub) a046530 n = length $ nub $ map (`mod` n) $ take (fromInteger n) $ tail a000578_list -- Reinhard Zumkeller, Aug 01 2012 -
Maple
A046530 := proc(n) local a,pf ; a := 1 ; if n = 1 then return 1; end if; for i in ifactors(n)[2] do p := op(1,i) ; e := op(2,i) ; if p = 3 then if e mod 3 = 0 then a := a*(3^(e+1)+10)/13 ; elif e mod 3 = 1 then a := a*(3^(e+1)+30)/13 ; else a := a*(3^(e+1)+12)/13 ; end if; elif p mod 3 = 2 then if e mod 3 = 0 then a := a*(p^(e+2)+p+1)/(p^2+p+1) ; elif e mod 3 = 1 then a := a*(p^(e+2)+p^2+p)/(p^2+p+1) ; else a := a*(p^(e+2)+p^2+1)/(p^2+p+1) ; end if; else if e mod 3 = 0 then a := a*(p^(e+2)+2*p^2+3*p+3)/3/(p^2+p+1) ; elif e mod 3 = 1 then a := a*(p^(e+2)+3*p^2+3*p+2)/3/(p^2+p+1) ; else a := a*(p^(e+2)+3*p^2+2*p+3)/3/(p^2+p+1) ; end if; end if; end do: a ; end proc: seq(A046530(n),n=1..40) ; # R. J. Mathar, Nov 01 2011
-
Mathematica
Length[Union[#]]& /@ Table[Mod[k^3, n], {n, 75}, {k, n}] (* Jean-François Alcover, Aug 30 2011 *) Length[Union[#]]&/@Table[PowerMod[k,3,n],{n,80},{k,n}] (* Harvey P. Dale, Aug 12 2015 *) -
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));prod(i=1,#f[,1],g(f[i,1],f[i,2])) \\ Charles R Greathouse IV, Jan 03 2013
-
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
Formula
a(n) = n - A257301(n). - Stanislav Sykora, Apr 21 2015
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
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
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
Comments