|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,7
|
|
COMMENTS
|
The size of the set of numbers j^8 mod n, gcd(j,n)=1, 1<=j<=n.
|
|
LINKS
|
|
|
FORMULA
|
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
|
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:
|
|
MATHEMATICA
|
a[n_] := EulerPhi[n]/Count[Range[0, n - 1]^8 - 1, k_ /; Divisible[k, n]];
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)
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]));
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,mult
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|