login
A293485
The number of 8th powers in the multiplicative group modulo n.
5
1, 1, 1, 1, 1, 1, 3, 1, 3, 1, 5, 1, 3, 3, 1, 1, 2, 3, 9, 1, 3, 5, 11, 1, 5, 3, 9, 3, 7, 1, 15, 1, 5, 2, 3, 3, 9, 9, 3, 1, 5, 3, 21, 5, 3, 11, 23, 1, 21, 5, 2, 3, 13, 9, 5, 3, 9, 7, 29, 1, 15, 15, 9, 2, 3, 5, 33, 2, 11, 3, 35, 3, 9, 9, 5, 9, 15, 3, 39, 1, 27, 5, 41, 3, 2
OFFSET
1,7
COMMENTS
The size of the set of numbers j^8 mod n, gcd(j,n)=1, 1<=j<=n.
LINKS
FORMULA
A000010(n) / a(n) = A247257(n).
Multiplicative with a(2^e) = 1 for e<=4, a(2^e) = 2^(e-5) for e>=5; a(p^e) = (p-1)*p^(e-1)/8 for p == 1 (mod 8); a(p^e) = (p-1)*p^(e-1)/4 for p == 5 (mod 8); a(p^e) = (p-1)*p^(e-1)/2 for p == {3,7} (mod 8). - R. J. Mathar, Oct 15 2017 [corrected by Georg Fischer, Jul 21 2022]
MAPLE
A293485 := proc(n)
local r, j;
r := {} ;
for j from 1 to n do
if igcd(j, n)= 1 then
r := r union { modp(j &^ 8, n) } ;
end if;
end do:
nops(r) ;
end proc:
seq(A293485(n), n=1..120) ;
MATHEMATICA
a[n_] := EulerPhi[n]/Count[Range[0, n - 1]^8 - 1, k_ /; Divisible[k, n]];
Array[a, 100] (* Jean-François Alcover, May 24 2023 *)
f[p_, e_] := (p - 1)*p^(e - 1)/Switch[Mod[p, 8], 1, 8, 5, 4, _, 2]; f[2, e_] := If[e <= 4, 1, 2^(e - 5)]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Aug 10 2023 *)
PROG
(PARI)
\\ The following two functions by Charles R Greathouse IV, from A247257:
g(p, e) = if(p==2, 2^min(e-1, 4), if(p%4==3, 2, if(p%8==5, 4, 8)));
A247257(n) = my(f=factor(n)); prod(i=1, #f~, g(f[i, 1], f[i, 2]));
A293485(n) = (eulerphi(n)/A247257(n)); \\ Antti Karttunen, Dec 05 2017
CROSSREFS
The number of k-th powers in the multiplicative group modulo n: A046073 (k=2), A087692 (k=3), A250207 (k=4), A293482 (k=5), A293483 (k=6), A293484 (k=7), this sequence (k=8).
Cf. A085311, A247257 (order of the kernel isomorphism of Z/nZ to this group), A000010.
Sequence in context: A322821 A213621 A053575 * A250207 A216319 A355001
KEYWORD
nonn,mult
AUTHOR
R. J. Mathar, Oct 10 2017
STATUS
approved