# Extract the rule of the sequence

**URL:** <https://discourse.processing.org/t/extract-the-rule-of-the-sequence/27547>\
**Category:** Coding Questions\
**Created:** [February 2, 2021, 4:30pm UTC](https://discourse.processing.org/t/extract-the-rule-of-the-sequence/27547 "2021-02-02T16:30:58Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![CodeMasterX](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/codemasterx/32/2942_2.png) [@CodeMasterX](https://discourse.processing.org/u/CodeMasterX)\
**Post date:** [February 2, 2021, 4:30pm UTC](https://discourse.processing.org/t/extract-the-rule-of-the-sequence/27547/1 "2021-02-02T16:30:58Z")

</div>

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)

```auto
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?

---

<div class="post-metadata">

**Author:** ![quark](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/quark/32/26_2.png) [@quark](https://discourse.processing.org/u/quark)\
**Post date:** [February 2, 2021, 6:05pm UTC](https://discourse.processing.org/t/extract-the-rule-of-the-sequence/27547/2 "2021-02-02T18:05:36Z")

</div>

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

```auto
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);
}

```

---

<div class="post-metadata">

**Author:** ![r.jaoui](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/r.jaoui/32/11777_2.png) [@r.jaoui](https://discourse.processing.org/u/r.jaoui)\
**Post date:** [February 2, 2021, 6:07pm UTC](https://discourse.processing.org/t/extract-the-rule-of-the-sequence/27547/3 "2021-02-02T18:07:54Z")

</div>

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) :

```auto
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 🙂

---

<div class="post-metadata">

**Author:** ![r.jaoui](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/r.jaoui/32/11777_2.png) [@r.jaoui](https://discourse.processing.org/u/r.jaoui)\
**Post date:** [February 2, 2021, 6:24pm UTC](https://discourse.processing.org/t/extract-the-rule-of-the-sequence/27547/4 "2021-02-02T18:24:37Z")

</div>

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 :

```auto
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 :

```auto
[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 😛