Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $G:N\to\{0,1\}$, and let $L$ be some period of $G$, so that $G(i+kL)=G(i)$. What's the best a good way to find the smallest period of $G$? I mean an algorithm that takes ($G$,$L$) and outputs the smallest period.

share|improve this question

2 Answers 2

up vote 1 down vote accepted

Let $G[m,n]$ denote the string formed by the values of $G$ between based indices $m$ and $n$ (inclusive). (Here all indices are $1$-based.)

Use a string matching algorithm to locate the first occurrence of the string $G[1,L]$ within the string $G[2,2L]$. The index of this occurrence is equal to the minimal period.

You can easily find linear-time string matching algorithms off the shelf (for instance, Knuth-Morris-Pratt can be implemented in a dozen lines of code). With a bit more care you could probably read off the period from the prefix table rather than performing an explicit query.

share|improve this answer

You could take the discrete Fourier transform of $G$ on $[1,2,\ldots,L]$. If $g$ is the GCD of those $k$ where the Fourier transform is nonzero, the minimal period is $L/g$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.