cp's OEIS Frontend

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

%I A352635 #49 Apr 13 2022 13:01:52
%S A352635 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 A352635 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 A352635 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 A352635 Number of cyclic orbits of the function f(x) = x^2 + 1 on Z/nZ.
%H A352635 Chai Wah Wu, <a href="/A352635/b352635.txt">Table of n, a(n) for n = 1..10000</a>
%H A352635 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 A352635 If n = 6 then there is a single cyclic orbit of size 2, namely {2, 5}.
%e A352635 If n = 7 then there are two cyclic orbits, both of size 1, namely {3} and {5}.
%o A352635 (Python)
%o A352635 def o(n):
%o A352635     orbits = set()
%o A352635     for k in range(n):
%o A352635         x, traj = k, []
%o A352635         while x not in traj:
%o A352635             traj.append(x)
%o A352635             x = (x**2 + 1) % n
%o A352635         orbits.add(tuple(sorted(traj[traj.index(x):])))
%o A352635     return orbits
%o A352635 print([len(o(n)) for n in range(1, 100)]) # _Andrey Zabolotskiy_, Apr 12 2022
%o A352635 (Python)
%o A352635 def A352635(n):
%o A352635     cset, iset = set(), set()
%o A352635     for i in range(n):
%o A352635         if i not in iset:
%o A352635             j, jset, jlist = i, set(), []
%o A352635             while j not in jset:
%o A352635                 jset.add(j)
%o A352635                 jlist.append(j)
%o A352635                 iset.add(j)
%o A352635                 j = (j**2+1) % n
%o A352635             cset.add(min(jlist[jlist.index(j):]))
%o A352635     return len(cset) # _Chai Wah Wu_, Apr 13 2022
%Y A352635 Related to A000374 and A023153.
%K A352635 nonn
%O A352635 1,7
%A A352635 _Jeroen van der Meer_, Apr 12 2022