#Yusra Naqvi
#HW 21

#OK to post

################################################################################
###Stuff from C21.txt###
################################################################################

#ParSeq(N): inputs a pos. integer N, and outputs the
#first N terms of the sequence enumerating partitions 

ParSeq:=proc(N) local F,q,i:

#F:=(1+x+x^2+x^3+x^4+....)*(1+x^2+x^4+x^6+....)*(1+x^3+x^6+...)
#F=1/(1-x)/(1-x^2)/(1-x^3)/......

F:=mul(1/(1-q^i),i=1..N):

F:=taylor(F,q=0,N+1):

[ seq(coeff(F,q,i),i=1..N)]:

end:

################################################################################
###End of stuff from C21.txt###
################################################################################

################################################################################
###New stuff for hw21.txt###
################################################################################

#1
#ParSeqBest(N): inputs a pos. integer N, and outputs the
#first N terms of the sequence enumerating partitions 
#using the fast recursion:
#p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+ ... 

ParSeqBest:=proc(N) local n:

[seq(ParBest(n),n=1..N)]:

end:

###

#ParBest(n): inputs a pos. integer n, and outputs the
#number of partitions of n using the fast recursion:
#p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+ ... 

ParBest:=proc(n) local P,m:
option remember:

if n=0 or n=1 then
 return(1):
fi: 

P:=0:
 
for m from 1 while m*(3*m+1)<=2*n do
 P:=P-((-1)^m)*ParBest(n-(m*(3*m-1)/2))-((-1)^m)*ParBest(n-(m*(3*m+1)/2)):
od:

if (m)*(3*m-1)<=2*n then
 P:=P-((-1)^m)*ParBest(n-(m)*(3*m-1)/2):
fi:

P:
 
end:

################################################################################

#2
#ParTime(N): gives the difference in time taken to calculate 
#ParSeqBest(N) vs. ParSeq(N)

ParTime:=proc(N) local t0,t1,t2:

t0:=time():
ParSeq(N):
t1:=time():
ParSeqBest(N):
t2:=time():

(t1-t0)-(t2-t1):

end:

###

#We list various values of N and ParTime(N):

#10: 0.

#100: 0.028

#200: 0.175

#500: 2.650

#1000: 21.729

################################################################################

#3
#ConjRC(N,K) that outputs the set all pairs [a,m], 0 < a ≤ m ≤ K such that
#p(n*m+a)= 0 mod m   for n ≤ N

ConjRC:=proc(N,K) local S,L,m,a,n:

S:={}:
L:=ParSeqBest(N*K+K):

for m from 1 to K do
 for a from 1 to m do
  if {seq(L[n*m+a] mod m,n=0..N)} = {0} then
   S:=S union {[a,m]}:
  fi: 
 od:
od:

S:
   
end:

###

#We find:

#ConjRC(400,30);
#{[1, 1], [4, 5], [5, 7], [6, 11], [24, 25]}

################################################################################