Algorithm for detecting recursion

user_11428287 0
Viewed 138

I am trying to implement a method that would be given an array of the first k integer values of a sequence. Based on the given values, the method would detect if it is possible to generate the values of the sequence using linear recurrence with integer coefficients.

  1. If it's not possible, an error would be given.
  2. If it is possible, the method would return an array C of the integer coefficients required to generate the sequence, of size s <= k, with s smallest as possible.

For the Fibonacci sequence, given the input {0,1,1,2,3,5,13}, the method would return {1,1}.

For the Tribonacci sequence, given the input sequence of at least 3 values, the method would return {1,1,1}

For a known recurrence relation f(n) = f(n - 1) + f(n - 2) - 3 * f(n - 5) + 4 * f(n - 10), any input sequence of less than 10 values would return an error, but given a sequence of at least 10 consecutive values, the method would return {1,1,0,0,-3,0,0,0,0,4}, corresponding to the coefficients of the recurrence (zeroes in the i'th position of the array indicate that the f(n - i) value is not required).

Obviously the recurrence is not known in advance, it's just for simplicity I am giving examples with known recurrences. But the method would need to detect it by itself.

Can it even be done? Is there any known algorithm for this? I tried programming something in Java but really it's nothing more than a brute force, detecting ALL possible recurrences which isn't very helpful... I would love to see code samples of efficient attempts at this if it is possible or any points in the right direction.

EDIT

After some searching, I stumbled accros the "Berlekamp–Massey algorithm", which seems related to this topic.

recursion integer arrays algorithm java
1 Answers

Given a particular s, you get a linear equation (with s unknowns) for each element of the sequence after the first s.

For example, if s=2 and the sequence is 1, 1, 2, 3, 5, 8 then have unknowns a, b, and equations 1a + 1b = 2, 1a + 2b = 3, 2a + 3b = 5 and so on. You can try to solve these using any method for solving linear equations -- for example gaussian elimination. If s is small, then some of your equations need to be linear combinations of earlier ones, but gaussian elimination will find those for you. In this example, 2a+3b=5 is a linear combination of 1a+1b=2 and 1a+2b=3 (just add them up).

So you can try s=1, s=2, s=3 and so on, until you find a solution.

user_14007930
Related