login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A233521 Number of disjoint subsets s of 0..(n-1) such that, for every x in s, x^x (mod n) is in s. 3

%I

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 24 01:21 EDT 2020. Contains 337315 sequences. (Running on oeis4.)