Kata

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 isu[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) (cmp in COBOL) 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