Be u(n) a sequence beginning with:
```
u[1]  = 1,  u[2]  = 1,  u[3]  = 2,  u[4]  = 3,  u[5]  = 3,  u[6] = 4,

u[7]  = 5,  u[8]  = 5,  u[9]  = 6,  u[10] = 6,  u[11] = 6,  u[12] = 8,

u[13] = 8,  u[14] = 8,  u[15] = 10, u[16] = 9,  u[17] = 10, u[18] = 11,

u[19] = 11, u[20] = 12, u[21] = 12, u[22] = 12, u[23] = 12 etc...

```
- How is`u[8]` calculated?

We have `u[7] = 5` and `u[6] = 4`. These numbers tell us that we have to go backwards from index `8` to index `8 - 5 = 3` and to index `8 - 4 = 4` so to index `3` and `4`.

``` u[3] = 2``` and ```u[4] = 3```  hence ```u[8] = u[3] + u[4] = 2 + 3 = 5```.

- Another example: let us calculate `u[13]`. At indexes `12` and `11` we have `8` and `6`. Going backwards of `8` and `6` from `13` we get indexes `13 - 8 = 5` and `13 - 6 = 7`. 

``` u[5] = 3```  and ``` u[7] = 5```  so ``` u[13] = u[5] + u[7] = 3 + 5 = 8``` .

## Task
- 0) Express u(n) as a function of n, u[n - 1], u[n - 2]. (not tested).


- 1) Given two numbers `n, k (integers > 2)` write the function `length_sup_u_k(n, k) or lengthSupUK or length-sup-u-k` returning the number of terms `u[i] >= k` with `1 <= i <= n`. 
If we look above we can see that between `u[1]` and `u[23]` we have four `u[i]` greater or equal to `12`: `length_sup_u_k(23, 12) => 4`


- 2) Given `n (integer > 2)` write the function `comp(n)` returning the number of times where a term of `u` is less than its **predecessor** up to and including u[n]. 

## Examples:

```
u(900) => 455 (not tested)
u(90000) => 44337 (not tested)

length_sup_u_k(23, 12) => 4
length_sup_u_k(50, 10) => 35
length_sup_u_k(500, 100) => 304

comp(23) => 1 (since only u(16) < u(15))
comp(100) => 22
comp(200) => 63
```

## Note: Shell
Shell tests only `lengthSupUk`

Difficulty: introductory

Starter code:

def length_sup_u_k(n, k):
	

Solutions:
from itertools import islice, count

def u1():
    a = {1:1, 2:1}
    yield a[1]
    yield a[2]
    for n in count(3):
        a[n] = a[n-a[n-1]] + a[n-a[n-2]]
        yield a[n]
    
def length_sup_u_k(n, k):
    return len(list(filter(lambda x: x >= k, islice(u1(), 1, n))))
    
def comp(n):
    return sum(k1 < k0 for k0, k1 in zip(list(islice(u1(), 1, n)), list(islice(u1(), 2, n))))

def u_list(index):
    out = [1, 1]
    for i in range(2, index):
        out.append(out[i-out[-1]] + out[i-out[-2]])
    return out

def length_sup_u_k(n, k):
    return sum([1 for x in u_list(n) if x >= k])
    
def comp(n):
    us = u_list(n)
    return sum([1 for i in range(n-1) if us[i] > us[i+1]])


S,C = [1,1],[0,0]

def length_sup_u_k(n, k):  return update(n) or sum(v>=k for v in S[:n])
def comp(n):               return update(n) or C[n-1]

def update(n):
    for _ in range(n+1-len(S)):
        S.append( S[-S[-2]] + S[-S[-1]] )
        C.append( C[-1] + (S[-2]>S[-1]) )


def length_sup_u_k(n, k):
    u = {1: 1, 2: 1}
    
    count = 0
    if k == 1:
        count += 2
    for i in range(3, n+1):
        u[i] = u[i - u[i-1]] + u[i - u[i-2]]
        if u[i] >= k: count += 1
    return count
    
def comp(n):
    u = {1: 1, 2: 1}
    count = 0
    for i in range(3, n+1):
        u[i] = u[i - u[i-1]] + u[i - u[i-2]]
        if u[i] < u[i-1]: count += 1
    return count

def length_sup_u_k(n, k):
    return len(list(filter(lambda x: x >= k, create(n))))

def create(n):
    seq = []
    for i in range(n):
        seq.append(generate_term(i, seq))
    return seq
    
def generate_term(i, seq):
    if i == 0 or i == 1:
        return 1
    return seq[i - seq[i-1]] + seq[i - seq[i-2]]
    
def comp(n):
    count = 0
    seq = []
    for i in range(n):
        seq.append(generate_term(i, seq))
        if i != 0:
            if seq[i] < seq[i-1]:
                count += 1
    return count

def length_sup_u_k(n, k):
    return sum(i >= k for i in u(n))

def comp(n):
    ui = u(n)
    return sum(x > y for y,x in zip(ui[1:], ui[:-1]))
    
def u(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        seq = [1,1]
        for i in range(2, n):
            seq.append(seq[i-seq[i-1]] + seq[i-seq[i-2]])
            
        return seq


def length_sup_u_k(n, k):
    return len([x for x in fibSeq(n) if x >= k])


def comp(n):
    seq = fibSeq(n)
    return len([x for x in range(1,len(seq)) if seq[x] < seq[x-1]])


def fibSeq(n):
    sequence = [1,1]

    for i in range(2,n):
        sequence.append(sequence[i-sequence[i-1]] + sequence[i-sequence[i-2]])
    return sequence

def length_sup_u_k(n, k):
    count = 0
    u_ = u(n)
    for i in range(2,n+1):
        if u_[i] >= k:
            count += 1
    return count
    
def comp(n):
    count = 0
    u_ = u(n)
    for i in range(2,n+1):
        if u_[i] < u_[i-1]:
            count += 1
    return count

def u(n):
    u = [0, 1, 1]
    for i in range(3, n+1):
        u.append(u[i - u[i - 1]] + u[i - u[i - 2]])
    return u
    
    #     if n == 1 or n == 2:
    #         return 1
    #     return u(n - u(n-1)) + u(n - u(n-2))


def length_sup_u_k(n, k):
    a=[1,1]
    count = 0
    for i in range(2,n):
        a.append(a[i-a[i-1]]+a[i-a[i-2]])
        if a[i] >= k:
            count +=1
    return count
def comp(n):
    a=[1,1]
    count = 0
    for i in range(2,n):
        a.append(a[i-a[i-1]]+a[i-a[i-2]])
        if a[i] < a[i-1]:
            count +=1
    return count


def length_sup_u_k(n, k):
    greater_num=0
    
    number_table=[]
    for index in range(0, n):
        if index <= 1:
            number_table.append(1)
        else:
            first_index = number_table[index - 1]
            last_index = number_table[index - 2]
            new_number = number_table[index - first_index] + number_table[index - last_index]
            number_table.append(new_number)
        if number_table[index] >= k:
            greater_num +=1
    return greater_num
    
def comp(n):
    pred_suck_count = 0
    number_table=[]
    for index in range(0, n):
        if index <= 1:
            number_table.append(1)
            continue
        else:
            first_index = number_table[index - 1]
            last_index = number_table[index - 2]
            new_number = number_table[index - first_index] + number_table[index - last_index]
            number_table.append(new_number)
        if number_table[index] < number_table[index - 1]:
            pred_suck_count += 1
            
    return pred_suck_count