A202034 Number of distinct prime residues of k^n (mod n), k=0..n-1.

0, 0, 1, 0, 2, 1, 3, 0, 0, 1, 4, 0, 5, 3, 6, 0, 6, 0, 7, 1, 2, 3, 8, 0, 1, 4, 0, 0, 9, 1, 10, 0, 11, 4, 11, 0, 11, 6, 3, 0, 12, 1, 13, 2, 3, 7, 14, 0, 2, 0, 15, 2, 15, 0, 3, 0, 5, 6, 16, 0, 17, 8, 0, 0, 18, 3, 18, 2, 19, 2, 19, 0, 20, 10, 2, 4, 21, 1, 21, 0, 0

Offset

1,5

Comments

If n is a prime number, a(n) = A000720(n) - 1 because the number of distinct residues of k^n (mod n) = n.

Links

Harvey P. Dale, Table of n, a(n) for n = 1..1000

Example

a(7) = 3  because  k^7 == 0, 1, 2, 3, 4, 5, 6 (mod 7) including 3 prime residues  2, 3, 5.

Maple

for n from 1 to 100 do: W:={}:for k from 0 to n-1 do:z:= irem(k^n, n): if type(z, prime)=true then W:=W union {z}:else fi:od: x:=nops(W): printf(`%d, `, x): od:

Mathematica

Table[Length[Select[Union[Table[Mod[k^n, n], {k, 0, n - 1}]], PrimeQ]], {n, 81}] (* Alonso del Arte, Dec 10 2011 *)
Count[Union[#], _?PrimeQ]&/@Table[PowerMod[k, n, n], {n, 100}, {k, 0, n-1}] (* Harvey P. Dale, Sep 24 2022 *)

Crossrefs

Cf. A000720, A132213, A195637.

Sequence in context: A367762 A002431 A259328 * A323881 A062963 A143255

Adjacent sequences: A202031 A202032 A202033 * A202035 A202036 A202037

Keyword

nonn

Author

Michel Lagneau, Dec 09 2011

Status

approved