Extract the rule of the sequence

Processing Coding Questions
1

Hi!
I want to create a program, that given input “1,2,3,4,1,2,3,4,1,2,3,4”, returns 1,2,3,4.

It extracts the rule of the sequence.

Here is the code to get the sequence ( [Fibonacci number] % m)

ArrayList<Integer> fib = new ArrayList<Integer>();
ArrayList<Integer> modr = new ArrayList<Integer>();
int m = 3;
void addFib(int n_, int s1, int s2) {
  fib.add(s1);
  fib.add(s2);
  for (int i = 0, z = 0; i < n_; i++) {
    z = s1 + s2;
    s1 = s2;
    s2 = z;
    fib.add(z);
  }
}
void getMod(ArrayList<Integer> info, int m_) {
  for(int i = 0; i < info.size(); i++) modr.add( info.get(i) % m_);
  printArray(modr);
}


void setup() { addFib(100,0,1); getMod(fib,m); }

Can you help / show me your code?

2

First thing the first two terms of the Fibonacci sequence are [1,1, ...] not [0,1, ...]

The other problem is that the terms in the series grow rapidly and after the 44 term it exceeds the capacity of the Integer data type so you start getting negative numbers.

If you start the sequence correctly and use the Long data type you can get 89 terms, like this

ArrayList<Long> fib = new ArrayList<Long>();
ArrayList<Long> modr = new ArrayList<Long>();
int m = 3;
void addFib(int n_, long s1, long s2) {
  fib.add(s1);
  fib.add(s2);
  for (long i = 0, z = 0; i < n_; i++) {
    z = s1 + s2;
    s1 = s2;
    s2 = z;
    fib.add(z);
  }
}
void getMod(ArrayList<Long> info, int m_) {
  for (int i = 0; i < info.size(); i++) modr.add( info.get(i) % m_);
  printArray(modr);
}

void setup() { 
  addFib(89, 1, 1); 
  getMod(fib, m);
}
1 Like
3

Hi !

A simple solution would be to keep track of the index (size) of the shortest repeting sequence. See the code below (I haven’t tested it perfectly but so far it seems to work, and keep in mind it isn’t optimized and there may be faster solutions) :

ArrayList<Integer> getRule(ArrayList<Integer> seq) {
  if (seq.size() > 0) {
    int ruleSize = 1;                        //THE MINIMAL RULE SIZE IS 1 (if the sequence isn't empty)
    for (int i = 0; i < seq.size(); i++) {   //LOOP THROUGH THE SEQUENCE
      
      //AT EACH STEP, WE VERIFY THAT THE VALUE THAT WE HAVE IS EQUAL TO ALL THE ONES IN THE SAME POSITION MOD ruleSize
      //IF SEQ IS 1,2,3,1,2,3,1,2,3,1,2,3,1,2,3 and we're at index 9, we compare it to these :
      //*     *     *     |
      //1,2,3,1,2,3,1,2,3,1,2,3,1,2,3
      
      for (int k = 0; k < i / ruleSize; k++) {
        if (seq.get(i) != seq.get(i % ruleSize + k * ruleSize)) {
          ruleSize = i+1;     //IF ONE DOESN'T MATCH, THEN THE MINIMAL SEQ SIZE IS AT LEAST THE CURRENT INDEX + 1
        }
      }
    }

    //HERE WE FILL THE RULE GIVEN THE RULE SIZE

    ArrayList<Integer> ret = new ArrayList<Integer>();
    for (int i = 0; i < ruleSize; i++) ret.add(seq.get(i));

    return ret;
    
    //IF THE SEQUENCE WAS EMPTY, WE RETURN AN EMPTY ARRAY
    
  } else return new ArrayList<Integer>();
}

I’m not entirely sure of this code, but it might be a start :slight_smile:

1 Like
4

Another way is to only store the fibonacci number mod m, since fibonacci is modular consistant (because only an addition of terms and addition is modular consistant). Basically, given that

x1 = a1 * m + r1
x2 = a2 * m + r2
r1 + r2 = a3 * m + r3

are all euclidian divisions, then :

x1 + x2 = a1 * m + r1 + a2 * m + r2 = (a1 + a2) * m + (r1 + r2) = (a1 + a2 + a3) * m + r3

is the euclidian division of x1 + x2 (r3 is by definition the only number in [0, m-1] such that r1 + r2 = a3 * m + r3. You then add to both sides a multiple of m that doesn’t change the rest. The proof is pretty simple).

We therefore know that

x1 + x2 [mod m] = r3 = r1 + r2 [mod m]

and therefore only storing r1 and r2 (in your case, Fn mod m), is sufficient and the numbers will be less than m. basically, you’d write something like :

Fn+1 = (Fn + Fn-1) % m

I wrote it in python to test it, sure enough it works :

def fibo1(n, m):
    l = [1, 1]
    for i in range(n - 2):
        l += [l[-1] + l[-2]]
    l = [(v%m) for v in l]
    return l

def fibo2(n, m):
    l = [1, 1]
    for i in range(n - 2):
        l += [(l[-1] + l[-2])%m]
    return l

print(fibo1(50, 6))
print(fibo2(50, 6))

Resulting in :

[1, 1, 2, 3, 5, 2, 1, 3, 4, 1, 5, 0, 5, 5, 4, 3, 1, 4, 5, 3, 2, 5, 1, 0, 1, 1, 2, 3, 5, 2, 1, 3, 4, 1, 5, 0, 5, 5, 4, 3, 1, 4, 5, 3, 2, 5, 1, 0, 1, 1]
[1, 1, 2, 3, 5, 2, 1, 3, 4, 1, 5, 0, 5, 5, 4, 3, 1, 4, 5, 3, 2, 5, 1, 0, 1, 1, 2, 3, 5, 2, 1, 3, 4, 1, 5, 0, 5, 5, 4, 3, 1, 4, 5, 3, 2, 5, 1, 0, 1, 1]

Anyways :stuck_out_tongue:

1 Like