A352635 Number of cyclic orbits of the function f(x) = x^2 + 1 on Z/nZ.
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, 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, 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
Offset: 1
Keywords
Examples
If n = 6 then there is a single cyclic orbit of size 2, namely {2, 5}.
If n = 7 then there are two cyclic orbits, both of size 1, namely {3} and {5}.
Links
- Chai Wah Wu, Table of n, a(n) for n = 1..10000
- Jeroen van der Meer, C implementation
Programs
-
Python
def o(n): orbits = set() for k in range(n): x, traj = k, [] while x not in traj: traj.append(x) x = (x**2 + 1) % n orbits.add(tuple(sorted(traj[traj.index(x):]))) return orbits print([len(o(n)) for n in range(1, 100)]) # Andrey Zabolotskiy, Apr 12 2022 -
Python
def A352635(n): cset, iset = set(), set() for i in range(n): if i not in iset: j, jset, jlist = i, set(), [] while j not in jset: jset.add(j) jlist.append(j) iset.add(j) j = (j**2+1) % n cset.add(min(jlist[jlist.index(j):])) return len(cset) # Chai Wah Wu, Apr 13 2022