# Problem 1

# OK to post homework
# Hari Amoor, 10/07/2020, Assignment 8

# Problem 1

# (i) We arrive at x = 0
# (ii) We arrive at x = 4741685087960650685822461715671211099459856575685906645393
# (iii) We conclude that x = 234303065886413369536085349033389448858104244347193374824719

# Problem 2

PnkHelperFunc := proc(n, k, L, m) local S, i, X, v, Y:
option remember:
if n < 0 then RETURN({}): fi:
if n = 0 then RETURN({L}): fi:

S := {}:
for X from m by -1 to 1 do
  Y := [op(L), X]
  v := PnkHelperFunc(n - X, k, Y, X):
  if v <> {} then S := S union v: fi:
od:
S:
end:

Pnk := proc(n, k):
return PnkHelperFunc(n - k, k, k, 0):
end:

# Problem 3

PnkHelperFunc2 := proc(n, k, m, c) local S, i, X, v, Y:
option remember:
if n < 0 then return ({}): fi:
if n = 0 then RETURN(1): fi:

for X from m by -1 to 1 do
  v := PnkHelperFunc2(n - X, k, X, c + 1):
  S := S + v:
od:

S:
end:

pnk := proc(n, k):
return PnkHelperFunc2(n - k, k, k, 0):
end:

# Problem 4

pn := proc(n) local i, c:
c := 0:
for i to n do 
  c := c + pnk(n, i):
od:
return c:
end:

# seq(pn(n),n=0...30) equals [1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604],
# which equals A41 in the OEIS.

# Problem 5

# [seq(p(5*n+4) mod 5, n=1..50)] = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
# [seq(p(7*n+5) mod 7, n=1..50)] = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
# [seq(p(11*n+6) mod 11, n=1..50)] = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]