# Matthew Russell
# Experimental Math
# Homework 21
# I give permission to post this

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

# Write a procedure ParSeqBest(N), that inputs and outputs the same as ParSeq(N)
# and ParSeqS(N), but using the fast recursion (that goes back to Euler) described in this wiki page, i.e.
# p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+ ... +(-1)^(m-1)*p(n-m*(3*m-1)/2)+(-1)^(m-1)*p(n-m*(3*m+1)/2)+ ...
# Reminder: make sure to have "option remember" , and to have the initial values correctly.

ParBest:=proc(N) local i:
option remember:
if N<0 then
	return 0:
fi:
if N=0 then
	return 1:
fi:

return add((-1)^(i+1)*ParBest(N-(i*(3*i-1))/2),i=1..floor(evalf((1/6*(1+24*N)^(1/2.0))+1)))
	+add((-1)^(i+1)*ParBest(N+(i*(-3*i-1))/2),i=1..floor(evalf((1/6*(1+24*N)^(1/2.0))+1))):

end:

ParSeqBest:=proc(N) local i:

return [seq(ParBest(i),i=0..N)]:

end:

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

# Using restart, and time(), find out how much faster is ParSeqBest(N) than ParSeq(N),
# for various N up to 10000.

# N=1000:
# ParSeqBest(N) = .168 seconds
# ParSeq(N) = 34.454 seconds
# N=1200:
# ParSeqBest(N) = .208 seconds
# ParSeq(N) = 60.455 seconds

# I'm scared to go much further with ParSeq.


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

# Write a procedure, ConjRC(N,K) that outputs the set of
# 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, a, m, flag, n:

S:={}:
for a from 1 to K do
	for m from a to K do
		flag:=true:
		for n from 0 to N while flag do
			if ParBest(n*m+a) mod m <>0 then
				flag:=false:
			fi:
		od:
		if flag then
			S:=S union {[a,m]}:
		fi:				
	od:
od:

return S:

end:

# What is the output of ConjRC(400,30)? 
# {[1, 1], [4, 5], [5, 7], [6, 11], [24, 25]}

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