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