|
|
A202034
|
|
Number of distinct prime residues of k^n (mod n), k=0..n-1.
|
|
4
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|