cp's OEIS Frontend

A293485 The number of 8th powers in the multiplicative group modulo n.

%I A293485 #32 Aug 10 2023 02:20:50
%S A293485 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,
%T A293485 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,
%U A293485 2,3,5,33,2,11,3,35,3,9,9,5,9,15,3,39,1,27,5,41,3,2
%N A293485 The number of 8th powers in the multiplicative group modulo n.
%C A293485 The size of the set of numbers j^8 mod n, gcd(j,n)=1, 1<=j<=n.
%H A293485 Antti Karttunen, <a href="/A293485/b293485.txt">Table of n, a(n) for n = 1..16384</a>
%H A293485 Richard J. Mathar, <a href="/A293482/a293482.pdf">Size of the Set of Residues of Integer Powers of Fixed Exponent</a>, research paper, 2017.
%F A293485 A000010(n) / a(n) = A247257(n).
%F A293485 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]
%p A293485 A293485 := proc(n)
%p A293485     local r,j;
%p A293485     r := {} ;
%p A293485     for j from 1 to n do
%p A293485         if igcd(j,n)= 1 then
%p A293485             r := r union { modp(j &^ 8,n) } ;
%p A293485         end if;
%p A293485     end do:
%p A293485     nops(r) ;
%p A293485 end proc:
%p A293485 seq(A293485(n),n=1..120) ;
%t A293485 a[n_] := EulerPhi[n]/Count[Range[0, n - 1]^8 - 1, k_ /; Divisible[k, n]];
%t A293485 Array[a, 100] (* _Jean-François Alcover_, May 24 2023 *)
%t A293485 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 *)
%o A293485 (PARI)
%o A293485 \\ The following two functions by _Charles R Greathouse IV_, from A247257:
%o A293485 g(p, e) = if(p==2, 2^min(e-1, 4), if(p%4==3, 2, if(p%8==5, 4, 8)));
%o A293485 A247257(n) = my(f=factor(n)); prod(i=1, #f~, g(f[i, 1], f[i, 2]));
%o A293485 A293485(n) = (eulerphi(n)/A247257(n)); \\ _Antti Karttunen_, Dec 05 2017
%Y A293485 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).
%Y A293485 Cf. A085311, A247257 (order of the kernel isomorphism of Z/nZ to this group), A000010.
%K A293485 nonn,mult
%O A293485 1,7
%A A293485 _R. J. Mathar_, Oct 10 2017