#OK to post
# Soham Palande, Assignment 8, 10/04/2020


#PART 1

#(i)
#0

#(ii)
#4741685087960650685822461715671211099459856575685906645393

#(iii)
#234303065886413369536085349033389448858104244347193374824719



#PART 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:

#PART 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:

#PART 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. 

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



#PART 6
# Srinivasa Ramanujan discovered these partition congruences modulo 5, 7, and 11