A233521 Number of disjoint subsets s of 0..(n-1) such that, for every x in s, x^x (mod n) is in s.

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

Offset: 1

Author

T. D. Noe, Feb 19 2014

Keywords

• nonn

Comments

This is very loosely based on the work of Kurlberg et al. It appears that a(n) = 1 at only six n: 1, 2, 3, 5, 11, 59.

Examples

			The simplest nontrivial case is n = 4. In this case, a(4) = 2 because there are two subsets: {0,1,2} and {3}. Note that 0^0 == 1 (mod 4), 1^1 == 1 (mod 4), 2^2 == 0 (mod 4), and 3^3 == 3 (mod 4).
		

Links

• T. D. Noe, Table of n, a(n) for n = 1..1000
• Pär Kurlberg, Florian Luca, and Igor Shparlinski, On the fixed points of the map x -> x^x modulo a prime, arXiv 1402.4464

Crossrefs

Cf. A065295, A233518, A233519, A233520.

Programs

Mathematica

Table[toDo = Range[0, n-1]; sets = {}; While[Length[toDo] > 0, k = toDo[[1]]; toDo = Rest[toDo]; lst = {k}; While[q = PowerMod[k, k, n]; ! MemberQ[lst, q], AppendTo[lst, q]; toDo = Complement[toDo, {q}]; k = q]; AppendTo[sets, lst]]; Do[int = Intersection[sets[[i]], sets[[j]]]; If[int != {}, sets[[i]] = Union[sets[[i]], sets[[j]]]; sets[[j]] = {}], {i, Length[sets]}, {j, i+1, Length[sets]}]; Length[DeleteCases[sets, {}]], {n, 100}]