|
|
A046530
|
|
Number of distinct cubic residues mod n.
|
|
27
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
|
|
LINKS
|
|
|
FORMULA
|
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
|
|
MAPLE
|
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:
|
|
MATHEMATICA
|
Length[Union[#]]&/@Table[PowerMod[k, 3, n], {n, 80}, {k, n}] (* Harvey P. Dale, Aug 12 2015 *)
|
|
PROG
|
(Haskell)
import Data.List (nub)
a046530 n = length $ nub $ map (`mod` n) $
take (fromInteger n) $ tail a000578_list
(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)))
(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
|
|
CROSSREFS
|
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).
|
|
KEYWORD
|
nonn,mult,easy,nice
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|