# Fastest way to determine period of eventually periodic sequence?

(Note: The original version of the question generated 1 upvote. Adding various explanatory comments in 3 subsequent Edits, generated 2 downvotes, which leads me to think added in the overall confusion, so I am reverting this back to the original. Eric Towers covered the question with his answer sufficiently.)

How can I extract the period of an eventually periodic sequence $$a_n$$, other than manually examining the entire orbit and making comparisons?

If my function is $$f(z)$$, my starting point is $$z_0$$, denoting the iterates of $$f$$ as $$f^{(n)}(z)$$, $$n\in \mathbb{N}$$, the orbit will be: $$\{z_0, f(z_0), f^{(2)}(z_0), \ldots,f^{(n)}(z_0),\ldots\}$$, and the sequence is given by $$a_n=f^{(n)}(z_0)$$, with $$a_0=z_0$$, etc.

A necessary (but not sufficient - depends on precision $$\epsilon$$, etc) condition for an eventually $$p$$-periodic convengence is obviously $$|a_{n+p}-a_n|\le \epsilon$$, for given $$\epsilon>0$$, so if I check a (finite always) orbit backwards starting at the last point $$a_N$$ for matches, then if the condition is satisfied for $$a_N$$ and $$a_{N-p}$$, then that's close to the converging period being $$p$$.

This calculation obviously contributes at least $$O(N)$$ for each point on my graphics plane in the worst case and stalks badly the calculations for the overall convergence.

Is there a faster way to check a finite list of values of $$a_n$$ for (almost - eventual) periodicity, under the assumption that $$a_n$$ is eventually periodically convergent?

• You might want to try to formulate this question very very carefully. Is the input sequence infinite? Is the algorithm supposed to be $O(p)$, where $p$ is the period? Or $O(N)$, where $N$ is the number of sequence-values examined? How, by examining finitely many values in a sequence, could one possibly tell that the remainder of the sequence was periodic, or almost periodic? Are we to answer this question only for sequences defined by iterated function application, or general sequences? That's a lot of questions, but on the face of it, this question seems ludicrous, so...they need answers. Sep 19 '20 at 21:54
• Moreover, you are talking about real numbers. How do you give a real as input to an algorithm? Sep 19 '20 at 23:00
• And how is this sequence given? In general there is obviously no way to determine the period of a sequence just by examining finitely many terms... Sep 19 '20 at 23:03
• What "clarification"? What you're literally asking for is obviously impossible - if what you want is something thats not obviously impossible i can't see what it might be. You say your edit "reflects" his comments - it would be better to answer his questions. HOW IS THE SEQUENCE GIVEN? (eg, you have a formula, or a recurrence, or just the first million terms...) Sep 19 '20 at 23:21
• It's clear that the question makes no sense unless you have a formula. It does not follow, obviously or not, that you do have such a formula. Sep 19 '20 at 23:36

If exact computation is possible in reasonable time (for instance if this is a sequence of integers), Floyd's algorithm finds the period in time $$O(\mu +\lambda)$$, where $$\mu$$ is the index of the first element of the cycle and $$\lambda$$ is the period. It requires $$O(1)$$ storage (since it only ever stores two sequence values). Brent has a similar algorithm with the same asymptotics. There are several algorithms that trade increased space complexity for time complexity.