# Experimental Math - Homework 21 - Due April 8
# Phil Benjamin
# Note: this homework (or any homework) can be freely uploaded
# to Experimental Math web site

# Problem 1
# ParSeqBest(N)
# Input: N positive integer
# Output: first N terms of sequence enumerating partitions
#	using the recursion: 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) + ...

# Approach: use two recursive subsequences
#	add((-1)^(m-1)*p(n-m*(3*m-1)/2) + add((-1)^(m-1)*p(n-m*(3*m+1)/2)

ParSeqBest := proc(N)
	local n1;
	return [seq(ParSeqBest1(n1),n1=1..N)];
end:

ParSeqBest1 := proc(n) option remember;
	local m, p;
	if n = 0 then return 1; end;
	p := 0;
	for m from 1 while n >= m*(3*m-1)/2 do
		p := p + (-1)^(m-1)*ParSeqBest1(n - m*(3*m-1)/2);
	end;
	for m from 1 while n >= m*(3*m+1)/2 do
		p := p + (-1)^(m-1)*ParSeqBest1(n - m*(3*m+1)/2);
	end;
	return p;
end:

# Problem 2
# time ParSeqBest(N) and ParSeq(N) for N with various values up to 10000
# Unfinished

# Problem 3
# ConjRC(N,K)
# Input: N,K positive integers
# Output: all pairs [a,m] with 0 <= a < m <= K
#	and p(n*m+a) = 0 (mod m) for all n <= N
# Experiment:
#	ConjRC(400,30) --> ???

# Note: the congruence is trivially true for m = 1 so use m > 1
# Strategy: generate partitions up to N*K;
# For each [a,m] pair, check all congruences in range
#	add to set of output pairs if check works

ConjRC := proc(N,K)
	local a, m, n, RCout, ParSeq, isGood;

	ParSeq := ParSeqBest(N*K);
	RCout := {};
	for m from 2 to K do
		for a from 0 to (m-1) do
			isGood := true;
			for n from 1 while isGood and n*m+a <= nops(ParSeq) do
				if (ParSeq[n*m+a] mod m) <> 0 then isGood := false; end;
			end;
			if isGood then RCout := RCout union {[a,m]}; end;
		end;
	end;
	return RCout;
end:

# Note: These solutions are "Ramanujan Congruences"
# Experiment:
#	ConjRC(400,30) --> {[4,5],[5,7],[6,11],[24,25]}