A233520 - OEIS

%I #30 Jan 05 2025 19:51:40

%S 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,

%T 11,21,19,18,16,19,12,28,18,18,18,30,13,33,20,22,23,36,18,28,20,23,27,

%U 39,17,35,24,32,30,43,20,46,33,26,37,37,22,49,34,34,30

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

%C 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))).

%C Note that the subtraction is not done mod n. - _Robert Israel_, Dec 17 2014

%H T. D. Noe, <a href="/A233520/b233520.txt">Table of n, a(n) for n = 1..10000</a>

%H Roger Crocker, <a href="http://www.jstor.org/stable/2317129">On residues of n^n</a>, Amer. Math. Monthly, 76 (1969), 1028-1029.

%H Pär Kurlberg, Florian Luca, and Igor Shparlinski, <a href="http://arxiv.org/abs/1402.4464">On the fixed points of the map x -> x^x modulo a prime</a>, arXiv:1402.4464 [math.NT], 2014.

%H Lawrence Somer, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/19-2/somer.pdf">The residues of n^n modulo p</a>, The Fibonacci Quart., 19 (1981), 110-117.

%e 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

%p f:= n -> nops({seq((x &^ x mod n - x) , x = 1 .. n-1)}):

%p seq(f(n), n=1..100); # _Robert Israel_, Dec 17 2014

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

%o (PARI) a(n) = #Set(vector(n-1, j, lift(Mod(j, n)^j) - j)); \\ _Michel Marcus_, Dec 16 2014

%Y Cf. A065295, A233518, A233519, A233521.

%K nonn

%O 1,3

%A _T. D. Noe_, Feb 19 2014