#Homework by Mike Murr
#OK to post
#hw12
read(`C12.txt`);

#congruent(k1,S,m) congruent checks to see whether k1 is congruent to
# a member of S mod m

congruent:=proc(k1,S,m) local j, okay;


if not (type(S,set) and type(m,integer) and nops(S)>=1) then
  print(`bad input`);
  return false;
fi;

okay:=false;

for j from 1 to nops(S) do
  if k1 mod m = S[j] then
    okay:=true;
  fi;
od;

return(okay);

end proc;

#PnkC(n,k,S,m): The LIST of integer partitions of n with largest part 
#              k where all parts are congruent to a member of S mod m
PnkC:=proc(n,k,S,m) local k1,L,L1:
option remember:

if not (type(n,integer) and type(k,integer) and n>=1 and k>=1 )then
 RETURN([]):
fi:
 
if k>n then
 RETURN([]):
fi:

if not congruent(k,S,m) then
# if the largest part is not congruent, the result is empty.
  return([]);
fi;

if k=n then
  if congruent(k,S,m) then
    RETURN([[n] ]):
  else
    return(FAIL);
  fi;
fi:

L:=[]:

for k1 from min(n-k,k) by -1 to 1 do
  if congruent(k1,S,m) then
    L1:=PnkC(n-k,k1,S,m):
    L:=[op(L), seq([k, op(L1[j])],j=1..nops(L1))]:
  fi;
od:

L:

end proc;

#PnC(n,S,m): The list of integer partitions of n in rev. lex. order,
#            where all parts are congruent to a member of S mod m
PnC:=proc(n,S,m) local k:
option remember:
[seq(op(PnkC(n,n-k+1,S,m)),k=1..n)]:
end proc;

#pnkC(n,k,S,m): The NUMBER of integer partitions of n with largest  
#          part k where all parts are congruent to a member of S mod m
pnkC:=proc(n,k,S,m) local k1, accum:
option remember:

if not (type(n,integer) and type(k,integer) and n>=1 and k>=1 )then
 RETURN(0):
fi:
 
if k>n then
 RETURN(0):
fi:

if not congruent(k,S,m) then
# if the largest part, k, is not congruent, no partition will begin
# with k.
  return(0);
fi;

if k=n then
  if congruent(k,S,m) then
    RETURN(1):
  else
    return(0);
  fi;
fi:

accum:=0;

for k1 from min(n-k,k) by -1 to 1 do
  if congruent(k1,S,m) then
    accum:=accum + pnkC(n-k,k1,S,m):
  fi;
od:

return(accum);

end proc;

#pnC(n,S,m) The NUMBER of partitions of n where all parts are congruent
#           to a member of S mod m

pnC:=proc(n,S,m) local k: option remember: 
if n=0 then
 RETURN(1):
fi:

add(pnkC(n,k,S,m),k=1..n):

end proc;

# [seq(pnC(n,{1},2),n=1..30)];
# This is OEIS A000009

# [seq(pnC(n,{1,4},5),n=1..30)];
# This is OEIS A003114

#differing(k,k1,DI) differing checks to see whether the difference of
# k and k1 is in DI. Returns true when the difference in NOT in DI.

differing:=proc(k,k1,DI) local j, okay;


if not (type(DI,set) and nops(DI)>=1) then
  print(`bad input`);
  return false;
fi;

if k < k1 then
  print(`k and k1 ?`);
  return false;
fi;

okay:=true;

for j from 1 to nops(DI) do
  if k - k1 = DI[j] then
    okay:=false;
  fi;
od;

return(okay);

end proc;

#PnkD(n,k,DI): The LIST of integer partitions of n with largest part 
#              k where the difference of two consecutive parts
#              is NOT in DI
PnkD:=proc(n,k,DI) local k1,L,L1:
option remember:

if not (type(n,integer) and type(k,integer) and n>=1 and k>=1 )then
 RETURN([]):
fi:
 
if k>n then
 RETURN([]):
fi:

if k=n then
  RETURN([[n]]);
fi;

L:=[]:

for k1 from min(n-k,k) by -1 to 1 do
  if differing(k,k1,DI) then
    L1:=PnkD(n-k,k1,DI):
    L:=[op(L), seq([k, op(L1[j])],j=1..nops(L1))]:
  fi;
od:

L:

end proc;

#PnD(n,DI): The list of integer partitions of n in rev. lex. order,
#           where the difference of two consecutive parts is
#           NOT in DI
PnD:=proc(n,DI) local k:
option remember:
[seq(op(PnkD(n,n-k+1,DI)),k=1..n)]:
end proc;

#pnkD(n,k,DI): The NUMBER of integer partitions of n with largest part 
#              k where the difference of two consecutive parts
#              is NOT in DI
pnkD:=proc(n,k,DI) local k1,accum:
option remember:

if not (type(n,integer) and type(k,integer) and n>=1 and k>=1 )then
 RETURN(0):
fi:
 
if k>n then
 RETURN(0):
fi:

if k=n then
  RETURN(1);
fi;

accum:=0;

for k1 from min(n-k,k) by -1 to 1 do
  if differing(k,k1,DI) then
    accum:=accum + pnkD(n-k,k1,DI);
  fi;
od:

return(accum);

end proc;

#pnD(n,DI) The NUMBER of partitions of n where the difference of
#          two consecutive parts is NOT in DI

pnD:=proc(n,DI) local k: option remember: 
if n=0 then
 RETURN(1):
fi:

add(pnkD(n,k,DI),k=1..n):

end proc;

#[seq(pnD(n,{0}),n=1..30)];
# This is also OEIS A000009, the same sequence as for pnC(n,{1},2)

#[seq(pnD(n, {0,1}), n = 1 .. 30)];
# This is OEIS A003114, the same sequence as for pnC(n,{1,4},5)