# Determining the length of a repeating sequence, with noise

first time poster.

I'm trying to determine the length of a repeating sequence, with noise. I.e. given the sequence 4, 12, 3, 4, 12, 3, 4, 12, 3, ... the period is apparently 3.

Now, what if the sequence was more complicated. What if each value had added noise? I was thinking of something with autocorrelation, or Fourier transform (my intuition tells me the repeating signal has a major frequency component, right? How can I determine which?)

It feels like this should be easy, but I'm having trouble implementing a solution.

Thanks

-

In connection with certain algorithms for integer factorization, there are methods due to Floyd and Brent for the so-called "cycle finding" problem. It would look like you can adapt these to your situation, but in the noisy case you will have to use a "fuzzy equality" comparison function, e.g. |x - y| <= tol where x and y are the two entities being compared, and tol is a small quantity.