Find the period of a nice eventually periodic sequence
A sequence is periodic if for all , where is called a period. A sequence is eventually periodic if there exists a and , such that for all . The sequence with index above is the periodic part.
A sequence is called -normal, if there exists for some for all in a interval of length , then the sequence starting at is part of the periodic part.
When does -normal sequence comes up? Consider we have a recurrence relation that produces a sequence. Say it is of the form . The sequence is -normal.
Given a oracle that can take input and return the th element in a -normal eventually periodic sequence . Find the smallest lexicographic pair where , such that for all .
One can solve this problem in time. First, consider the subsequence . We guess an upper bound on through exponential search in the subsequence. There is a time algorithm to decide if . For example using the KMP algorithm. We can quickly locate a such that .
Let’s take the sequence . We just need to solve the following problem. Given a length string, find the longest suffix that appears at least twice in the sequence. Let such suffix be . We know , which has to overlap with any other occurrence of the sequence. The claim is that the partial match table in the KMP algorithm would give us such information. Hence we can obtain . can also be obtained in the same time. Note that KMP algorithm only uses the fact one can check equality of two elements. So the sequence can contain elements from very general space.
The total running time is calls to time string matching. The total running time is therefore .
In many applications, we do not get oracle access to th index of the sequence. But we can read the sequence from the beginning as a list. In that case, we don’t do binary search, but linear search. Advance the index by and obtain , and test if is no larger than the current point. If so, again we have and reduce to the previous problem. If not, advance the index by again and repeat. This gives us a time algorithm.