A337868 - OEIS

%I #14 Jan 18 2023 09:34:39

%S 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,

%T 20,21,29,30,31,21,33,34,35,21,37,38,39,28,41,42,43,33,35,46,47,32,43,

%U 42,51,39,53,40,55,39,57,58,59,45,61,62,49,41,65,66,67,51,69,70,71

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

%C Sequence is submultiplicative: a(m*n) <= a(m) * a(n) for m,n coprime. - _Charles R Greathouse IV_, Dec 19 2022

%C 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

%F 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

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

%t Table[Length[T@n], {n, 1, 144}]

%o (PARI) 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

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

%K nonn

%O 1,2

%A _José María Grau Ribas_, Sep 27 2020