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