# Homework 21. 8-April-2012. Pat Devlin # # I don't care about keeping my work private # Help:=proc(): print(`ParSeqBest(n)`): print(`ConjRC(N,K)`): print(` ParSeq(N), PD1(n,k) `): print(`PD(n), ParSeqS(N), CheckCond(p,CongCond)`): print(`PD1Cond(n,DiffC,CongC), PDCond(n,DiffC,CongC), `): print(` ParSeqCond(N,DiffC,CongC) ` ): end: ############# # Problem 1 # ############# ParSeqBest:=proc(n) local k, p: option remember: if(n=0) then return 1: fi: if(n<0) then return 0: fi: p:=0: for k from 1 to infinity do if((3*k^2 -k)/2 > n) then return p: fi: p:=p+(-1)^(k+1) * (ParSeqBest(n-(3*k^2-k)/2) + ParSeqBest(n- (3*k^2 + k)/2)): od: return p: end proc: ############# # Problem 2 # ############# # ParSeqBest seems much faster [hence the name?] ############# # Problem 3 # ############# ConjRC:=proc(N,K) local a, m, goodPairs, L, k: goodPairs:={}: L:=[seq(ParSeqBest(k), k=1..((N+1)*(K+1)+2*K))]: for a from 1 to K do for m from a to K do if(thisWorks(a,m,N, L)) then goodPairs:=goodPairs union {[a,m]}: fi: od: od: return goodPairs: end proc: thisWorks:=proc(a,m,N, L) local n: for n from 1 to N do if(not ((L[n*m+a] mod m) = 0)) then return false: fi: od: return true: end proc: # The output of ConjRC(400, 30) is # {[1, 1], [4, 5], [5, 7], [6, 11], [24, 25]} ## ## From class 21 below #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: #PD1(n,k): the number of partitions of n with largest part k PD1:=proc(n,k) local k1: option remember: if n=1 then if k=1 then RETURN(1): else RETURN(0): fi: fi: if n=k then RETURN(1): fi: if k>n or k<1 then RETURN(0): fi: add(PD1(n-k,k1),k1=1..k): end: PD:=proc(n) local k: add(PD1(n,k),k=1..n): end: #ParSeqS(N): inputs a pos. integer N, and outputs the #first N terms of the sequence enumerating partitions #Hopefully faster version ,but actually much slower ParSeqS:=proc(N) local n: [seq(PD(n),n=1..N)]: end: #CheckCond(p,CongCond): given a pos. integer p #and a set of pairs CongCond {[a,m]} checks #whehter p mod m=a for at least one of the members CheckCond:=proc(p,CongCond) local c,a,m: for c in CongCond do a:=c[1]: m:= c[2]: if (p-a) mod m = 0 then RETURN(true): fi: od: false: end: #PD1Cond(n,k,DiffC, CongC): #the number of partitions of n with largest part k #where the difference between consectuive parts CANNOT #belong to the set of non-neg. integer DiffC #and the parts MUST be of the form #a mod m for some [a,m] in CongC #For example, PD1Cond(n,k,{0},{[0,1]}): #is the number of distinct partitions of n with largest #part k, and PD1Cond(n,k,{},{[1,2]}) #is the number ... of partitions into odd parts PD1Cond:=proc(n,k,DiffC,CongC) local k1,s: option remember: if not CheckCond(k,CongC) then RETURN(0): fi: if n=1 then if k=1 then if CheckCond(1,CongC) then RETURN(1): else RETURN(0): fi: else RETURN(0): fi: fi: if n=k then RETURN(1): fi: if k>n or k<1 then RETURN(0): fi: s:=0: for k1 from 1 to k do if not member(k-k1,DiffC) then s:=s+PD1Cond(n-k,k1,DiffC,CongC): fi: od: s: end: PD:=proc(n) local k: add(PD1(n,k),k=1..n): end: PDCond:=proc(n,DiffC,CongC) local k: add(PD1Cond(n,k,DiffC,CongC),k=1..n): end: #ParSeqCond(N,DiffC,CongC): inputs a pos. integer N, #and Difference conditions DiffC (to avoid) #and congruence conditions, CongC (to obey) #and outputs the #first N terms of the sequence enumerating partitions #with these conditions. #For example, ParSeqCond(10,{},{[0,1]}); should be the #same as ParSeq(N) # ParSeqCond:=proc(N,DiffC,CongC) local n: [seq(PDCond(n,DiffC,CongC),n=1..N)]: end: