|
%I #7 Apr 22 2014 12:27:51
%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,
%T 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,
%U 9,1,30,7,8,22,19,16,21,4,17,9,23,4,27,5,10,19,14,14
%N Number of disjoint subsets s of 0..(n-1) such that, for every x in s, x^x (mod n) is in s.
%C 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.
%H T. D. Noe, <a href="/A233521/b233521.txt">Table of n, a(n) for n = 1..1000</a>
%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
%e 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).
%t 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}]
%Y Cf. A065295, A233518, A233519, A233520.
%K nonn
%O 1,4
%A _T. D. Noe_, Feb 19 2014
|
