#John Kim #Use whatever you like #read "C:/Users/John Y. Kim/Documents/Maple/hw21.txt": #C21.txt Help:=proc(): 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: #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: #ParSeqBest(N): inputs and outputs the same as ParSeq(N) #and ParSeqS(N), but using the fast recursion #(that goes back to Euler) given by: #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)+ ... ParSeqBest:=proc(N) local n: option remember: [seq(p(n),n=1..N)]: end: #p(n): outputs the number of partitions of n. p:=proc(n) local m: option remember: if n<0 then 0: elif n=0 or n=1 then 1: else add((-1)^(m-1)*p(n-m*(3*m-1)/2)+(-1)^(m-1)*p(n-m*(3*m+1)/2),m=1..floor(sqrt(2*n/3))+1): fi: end: #restart: read "C:/Users/John Y. Kim/Documents/Maple/hw21.txt": time(ParSeqBest(100)); # 0.078 #restart: read "C:/Users/John Y. Kim/Documents/Maple/hw21.txt": time(ParSeq(100)); # 0.031 #restart: read "C:/Users/John Y. Kim/Documents/Maple/hw21.txt": time(ParSeqBest(500)); # 0.405 #restart: read "C:/Users/John Y. Kim/Documents/Maple/hw21.txt": time(ParSeq(500)); # 3.260 #restart: read "C:/Users/John Y. Kim/Documents/Maple/hw21.txt": time(ParSeqBest(1000)); # 1.045 #restart: read "C:/Users/John Y. Kim/Documents/Maple/hw21.txt": time(ParSeq(1000)); # 22.682 #restart: read "C:/Users/John Y. Kim/Documents/Maple/hw21.txt": time(ParSeqBest(10000)); # 10.046 #too scared to run ParSeq(10000). #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 . #What is the output of ConjRC(400,30)? ConjRC:=proc(N,K) local a,m,S,n: S:={}: for m from 1 to K do for a from 1 to m do if {seq(p(n*m+a),n=0..N)} mod m = {0} then S:=S union {[a,m]}: fi: od: od: S: end: #ConjRC(400,30); # {[1, 1], [4, 5], [5, 7], [6, 11], [24, 25]}