The Art Gallery Guardian

Find the period of a nice eventually periodic sequence


A sequence is periodic if si=si+ps_i = s_{i+p} for all ii, where p>0p>0 is called a period. A sequence is eventually periodic if there exists a nn and pp, such that si=si+ps_i = s_{i+p} for all i>ni>n. The sequence with index above nn is the periodic part.

A sequence is called uu-normal, if there exists si=si+ps_i=s_{i+p} for some p>0p>0 for all ii in a interval of length uu, then the sequence starting at sis_i is part of the periodic part.

When does uu-normal sequence comes up? Consider we have a recurrence relation that produces a sequence. Say it is of the form an=f(an1,an2,,anu)a_n = f(a_{n-1},a_{n-2},\ldots,a_{n-u}). The sequence a1,a_1,\ldots is uu-normal.

Problem1

Given a oracle that can take input ii and return the iith element in a uu-normal eventually periodic sequence aa. Find the smallest lexicographic pair (n,p)(n,p) where p>0p>0, such that ai=ai+pa_i=a_{i+p} for all i>ni>n.

One can solve this problem in O(ulognu)O(u \log \frac{n}{u}) time. First, consider the subsequence au,a2u,a_u,a_{2u},\ldots. We guess an upper bound on nn through exponential search in the subsequence. There is a O(u)O(u) time algorithm to decide if nnn'\geq n. For example using the KMP algorithm. We can quickly locate a nn' such that n[nu,n]n\in [n'-u,n'].

Let's take the sequence anu,,an+3ua_{n'-u},\ldots,a_{n'+3u}. We just need to solve the following problem. Given a O(u)O(u) length string, find the longest suffix that appears at least twice in the sequence. Let such suffix be ss. We know s3u|s|\geq 3u, which ss 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 nn. pp 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 O(lognu)O(\log \frac{n}{u}) calls to O(u)O(u) time string matching. The total running time is therefore O(ulognu)O(u\log \frac{n}{u}).

In many applications, we do not get oracle access to iith 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 uu and obtain nn', and test if nn is no larger than the current point. If so, again we have n[nu,n]n\in [n'-u,n'] and reduce to the previous problem. If not, advance the index by uu again and repeat. This gives us a O(n+u)O(n+u) time algorithm.

Posted by Chao Xu on 2019-02-05.
Tags: algorithms, infinite sequence.