#Ok to post homework
#Tifany Tong, October 4th, 2020, HW #8

# Question 1:

# (i) 0

# (ii) 4741685087960650685822461715671211099459856575685906645393

# (iii) 234303065886413369536085349033389448858104244347193374824719

# Question 2:

PnkHelper := proc(n, k, L, max) local S, i, K, val1, B:
option remember:
if n < 0 then RETURN({}): fi: 
if n = 0 then RETURN({L}): fi:
S := {}:
for K from max by -1 to 1 do 
  B := [op(L), K]:
  val1 := PnkHelper(n - K, k, B, K):
  if val1 <> {} then S := S union val1:
  fi: 
od: 
S:
end:

Pnk := proc(n, k):
return PnkHelper(n-k, k, [k], k):
end:

# Question 3:

PnkHelper2 := proc(n, k, max, count) local S, i, K, val1, B:
option remember:
if n < 0 then RETURN(0): fi:
if n = 0 then RETURN(1): fi:
S := 0:
for K from max by -1 to 1 do 
  val1 := PnkHelper2(n - K, k, K, count + 1):
  S := S + val1:
od:
S:
end:

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

# Question 4: 
pn := proc(n) local i, count:
count := 0:
for i to n do 
  count := count + pnk(n, i):
od:
return count:
end:

# seq(pn(n),n=0...30) comes out to [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 corresponds to A41 in the OEIS. 

# Question 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]