

A233520


The number of distinct values of x^x (mod n)  x for x in 0 < x < n.


4



0, 1, 2, 2, 4, 2, 5, 4, 5, 5, 6, 4, 10, 7, 8, 9, 11, 5, 12, 9, 12, 10, 15, 9, 14, 12, 14, 12, 19, 11, 21, 19, 18, 16, 19, 12, 28, 18, 18, 18, 30, 13, 33, 20, 22, 23, 36, 18, 28, 20, 23, 27, 39, 17, 35, 24, 32, 30, 43, 20, 46, 33, 26, 37, 37, 22, 49, 34, 34, 30
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

According to Kurlberg et al. (who quote Crocker and Somer), for primes p, the count is between floor(sqrt((p1)/2)) and 3p/4 + O(p^(1/2 + o(1))).
Note that the subtraction is not done mod n.  Robert Israel, Dec 17 2014


LINKS

T. D. Noe, Table of n, a(n) for n = 1..10000
Roger Crocker, On residues of n^n, Amer. Math. Monthly, 76 (1969), 10281029.
Pär Kurlberg, Florian Luca, and Igor Shparlinski, On the fixed points of the map x > x^x modulo a prime arX1v 1402.4464
Lawrence Somer, The residues of n^n modulo p, The Fibonacci Quart., 19 (1981), 110117.


EXAMPLE

For n = 5 the a(5) = 4 values are 11=0, 42=2, 23=1, 14=3.  Robert Israel, Dec 17 2014


MAPLE

f:= n > nops({seq((x &^ x mod n  x) , x = 1 .. n1)}):
seq(f(n), n=1..100); # Robert Israel, Dec 17 2014


MATHEMATICA

fs[p_] := Module[{x = Range[p  1]}, Length[Union[PowerMod[x, x, p]  x]]]; Table[fs[n], {n, 100}]


PROG

(PARI) a(n) = a(n) = #Set(vector(n1, j, lift(Mod(j, n)^j)  j)); \\ Michel Marcus, Dec 16 2014


CROSSREFS

Cf. A065295, A233518, A233519, A233521.
Sequence in context: A333836 A125296 A294097 * A243271 A232245 A121895
Adjacent sequences: A233517 A233518 A233519 * A233521 A233522 A233523


KEYWORD

nonn


AUTHOR

T. D. Noe, Feb 19 2014


STATUS

approved



