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,4

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.

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

Example

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

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}]

Crossrefs

Cf. A065295, A233518, A233519, A233520.

Sequence in context: A065295 A296604 A261211 * A035685 A205509 A118736

Adjacent sequences: A233518 A233519 A233520 * A233522 A233523 A233524

Keyword

nonn

Author

T. D. Noe, Feb 19 2014

Status

approved