How to quickly find the dependency of elements in a sequential series?

Question

Mathematics

Examples.
Given a row: 1,2,3,4,5
-------
Initial element (value): 1
It is clearly seen that each next element is 1 more than the previous one.

More difficult: 1,4,2,5,3,6,4
------
Initial element (value): 1
The next even number is 3 more than the previous one; odd - less by 2 than the previous one.

Here is how exactly (algorithm) it is possible to identify the existing dependence (if any) of elements of one arbitrary series?

Answer 1

If the dependence can be any (for example, fibbonacci numbers), then nothing. You can search for a sequence on oeis.org
. If only a dependency of the form +a_0, +a_1, +a_2,..., +a_k, +a_0, +a_1... is possible, i.e. a repeating fixed pattern of increments, i.e. a quick and easy solution.
First, if you are given 10 numbers, then you can always say that there is a pattern with a length of 9 increments.
But you can find the shortest pattern using the algorithm for finding a period in a string. Literally, by definition, the shortest pattern you need (like {+3, -2} for the second example) will be the period of the string. True, this is not a string, but an array of numbers, but this does not change the algorithms at all. You just have a non-standard alphabet.
First, from an array of numbers, go to an array of increments.
Then you can apply a greedy naive solution - just iterate over all possible period values ​​from 1 to n/2 and check that a[i] == a[i+str] for all i. As soon as everything coincided - you found the period. This is a square solution. If you are given a lot of numbers, then you can apply the function prefix : find the value of the function prefix (p) for the entire string and, if its value is more than half the length of the string, then the string has a period np. This will be a linear solution.
You can also apply the Duval algorithm . Also a linear solution, but more difficult to implement and understand.