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

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,2

Comments

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

Links

Table of n, a(n) for n=1..71.

Formula

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

Mathematica

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

Prog

(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

Crossrefs

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

Sequence in context: A097246 A277886 A359588 * A063659 A255563 A331288

Adjacent sequences: A337865 A337866 A337867 * A337869 A337870 A337871

Keyword

nonn

Author

José María Grau Ribas, Sep 27 2020

Status

approved