A087692 Number of cubes in multiplicative group modulo n.

1, 1, 2, 2, 4, 2, 2, 4, 2, 4, 10, 4, 4, 2, 8, 8, 16, 2, 6, 8, 4, 10, 22, 8, 20, 4, 6, 4, 28, 8, 10, 16, 20, 16, 8, 4, 12, 6, 8, 16, 40, 4, 14, 20, 8, 22, 46, 16, 14, 20, 32, 8, 52, 6, 40, 8, 12, 28, 58, 16, 20, 10, 4, 32, 16, 20, 22, 32, 44, 8, 70, 8, 24, 12, 40, 12, 20, 8, 26, 32, 18, 40

Offset: 1

Author

Yuval Dekel (dekelyuval(AT)hotmail.com), Sep 27 2003

Keywords

• mult
• nonn

Comments

Cubic analog of A046073. - Steven Finch, Mar 01 2006

Links

• Robert Israel, Table of n, a(n) for n = 1..10000
• Steven R. Finch and Pascal Sebah, Squares and Cubes Modulo n, arXiv:math/0604465 [math.NT], 2006-2016.

Crossrefs

Cf. A000010, A060839, A046073 (squares), A250207 (4th powers).

Programs

Maple

b:= proc(p,i)
  if p = 3 then if i=1 then 2 else 2*3^(i-2) fi
  elif p mod 6 = 1 then (p-1)*p^(i-1)/3
  else (p-1)*p^(i-1)
  fi
end proc:
seq(mul(b(f[1],f[2]), f = ifactors(n)[2]), n = 1 .. 1000); # Robert Israel, Jan 04 2015

Mathematica

Map[Length,Table[Select[Range[n],CoprimeQ[#, n] && IntegerQ[PowerMod[#, 1/3, n]] &], {n, 1, 82}]] (* Geoffrey Critzer, Jan 07 2015 *)
f[p_, e_] := (p - 1)*p^(e - 1)/If[Mod[p, 6] == 1, 3, 1]; f[3, e_] := 2*3^(e-2); f[3, 1] = 2; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Aug 10 2023 *)

PARI

a(n) = my(f = factor(n)); prod(j=1, #f~, p=f[j,1]; k=f[j,2]; if (p == 3, if (k==1, 2, 2*3^(k-2)), if ((p % 6) == 1, ((p-1)*p^(k-1))/3, (p-1)*p^(k-1)))); \\ Michel Marcus, Jan 05 2015

Formula

a(n) = phi(n) / A060839(n).

Multiplicative with a(3) = 2, a(3^k) = 2*3^(k-2) otherwise;

a(p^k) = (p-1)*p^(k-1)/3 if prime p == 1 mod 6; a(p^k) = (p-1)*p^(k-1) for all other primes p. - Robert Israel, Jan 04 2015

Sum_{k=1..n} a(k) ~ c * n^2/log(n)^(1/3), where c = (17/(36*Gamma(2/3))) * Product_{p = 3 or p prime == 2 (mod 3)} (1+1/*p)*(1-1/p)^(2/3) * Product_{p prime == 1 (mod 3)} (1+1/(3*p))*(1-1/p)^(2/3) = 0.33051128776333262024... (Finch and Sebah, 2006). - Amiram Eldar, Oct 18 2022

Extensions

More terms from Steven Finch, Mar 01 2006