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

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

Offset: 1

Author

T. D. Noe, Feb 19 2014

Keywords

• nonn

Comments

According to Kurlberg et al. (who quote Crocker and Somer), for primes p, the count is between floor(sqrt((p-1)/2)) and 3p/4 + O(p^(1/2 + o(1))).

Note that the subtraction is not done mod n. - Robert Israel, Dec 17 2014

Examples

			For n = 5 the a(5) = 4 values are 1-1=0, 4-2=2, 2-3=-1, 1-4=-3. - _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), 1028-1029.
• Pär Kurlberg, Florian Luca, and Igor Shparlinski, On the fixed points of the map x -> x^x modulo a prime, arXiv:1402.4464 [math.NT], 2014.
• Lawrence Somer, The residues of n^n modulo p, The Fibonacci Quart., 19 (1981), 110-117.

Crossrefs

Cf. A065295, A233518, A233519, A233521.

Programs

Maple

f:= n -> nops({seq((x &^ x mod n - x) , x = 1 .. n-1)}):
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}]

PARI

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