login
Number of cyclic orbits of the function f(x) = x^2 + 1 on Z/nZ.
1

%I #49 Apr 13 2022 13:01:52

%S 1,1,1,1,1,1,2,1,1,1,1,1,3,2,1,1,1,1,2,1,2,2,1,1,1,4,3,2,1,1,3,1,1,2,

%T 2,1,3,2,3,1,1,2,3,2,3,2,2,1,6,1,1,4,1,3,1,2,2,2,1,1,3,3,2,1,3,2,4,2,

%U 1,2,3,1,3,4,1,2,2,4,5,1,3,1,1,2,3,4,1,2,3,3,6,2,3,3,2,1,4,10

%N Number of cyclic orbits of the function f(x) = x^2 + 1 on Z/nZ.

%H Chai Wah Wu, <a href="/A352635/b352635.txt">Table of n, a(n) for n = 1..10000</a>

%H Jeroen van der Meer, <a href="https://github.com/Jeroen-van-der-Meer/math-models/blob/master/periodicities/number_of_orbits.c">C implementation</a>

%e If n = 6 then there is a single cyclic orbit of size 2, namely {2, 5}.

%e If n = 7 then there are two cyclic orbits, both of size 1, namely {3} and {5}.

%o (Python)

%o def o(n):

%o orbits = set()

%o for k in range(n):

%o x, traj = k, []

%o while x not in traj:

%o traj.append(x)

%o x = (x**2 + 1) % n

%o orbits.add(tuple(sorted(traj[traj.index(x):])))

%o return orbits

%o print([len(o(n)) for n in range(1, 100)]) # _Andrey Zabolotskiy_, Apr 12 2022

%o (Python)

%o def A352635(n):

%o cset, iset = set(), set()

%o for i in range(n):

%o if i not in iset:

%o j, jset, jlist = i, set(), []

%o while j not in jset:

%o jset.add(j)

%o jlist.append(j)

%o iset.add(j)

%o j = (j**2+1) % n

%o cset.add(min(jlist[jlist.index(j):]))

%o return len(cset) # _Chai Wah Wu_, Apr 13 2022

%Y Related to A000374 and A023153.

%K nonn

%O 1,7

%A _Jeroen van der Meer_, Apr 12 2022