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: EASY
Tags: Complete search
Skill types: Complete search

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