A085311 -id:A085311 - cp's OEIS frontend

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

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

R. J. Mathar, Oct 10 2017

The size of the set of numbers j^8 mod n, gcd(j,n)=1, 1<=j<=n.

Antti Karttunen, Table of n, a(n) for n = 1..16384
Richard J. Mathar, Size of the Set of Residues of Integer Powers of Fixed Exponent, research paper, 2017.

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.

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) ;

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 *)

\\ 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

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]

A337868 Number of distinct residues of x^r (mod n), x=0..n-1, r=2, ..., n.

Original entry on oeis.org

0, 2, 3, 3, 5, 6, 7, 6, 7, 10, 11, 9, 13, 14, 15, 11, 17, 14, 19, 15, 21, 22, 23, 17, 21, 26, 20, 21, 29, 30, 31, 21, 33, 34, 35, 21, 37, 38, 39, 28, 41, 42, 43, 33, 35, 46, 47, 32, 43, 42, 51, 39, 53, 40, 55, 39, 57, 58, 59, 45, 61, 62, 49, 41, 65, 66, 67, 51, 69, 70, 71

Offset: 1

José María Grau Ribas, Sep 27 2020

nonn

Sequence is submultiplicative: a(m*n) <= a(m) * a(n) for m,n coprime. - Charles R Greathouse IV, Dec 19 2022

For n > 1, this is the number of distinct residues of x^r (mod n) with r > 1, that is, the restriction r <= n is not needed. - Charles R Greathouse IV, Dec 22 2022

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).

T[n_] := Union@Mod[Flatten@Table[Range[n]^i, {i, 2, n}], n];
Table[Length[T@n], {n, 1, 144}]

a(n)=if(n==1, return(0)); my(s); for(k=0,n-1, my(x=Mod(k,n)); forprime(p=2,n, if(ispower(x,p), s++; break))); s\\ Charles R Greathouse IV, Dec 22 2022

For n > 1, a(n) >= A000010(n) + 1 as all invertible elements of Z/nZ are powers, as is 0. (Conjecture: equality holds exactly for A000430, the primes and squares of primes.) - Charles R Greathouse IV, Dec 23 2022

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula