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
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
KEYWORD
nonn
AUTHOR
José María Grau Ribas, Sep 27 2020
STATUS
approved