Last Update: May 6, 2012
We will first learn Maple, and how to program in it. This semester we will focus on Sequences, both in general-studying important families of sequences and how to detect them- and in particular, studying particularly interesting members of Neil Sloane's zoo
In addition to the actual, very important content, students will master the methodology of computer-generated and computer-assisted research that is so crucial for their future. We will also have one guest lecture by Mr. Edinah Gnang, who will give a tutorial on the open-source beautiful (and powerful) computer algebra system SAGE, and one (on Feb. 23, 2012) by the high priest himself.
There are no prerequisites, and no previous programming knowledge is assumed. Also, very little overlap with previous years. The final projects will definitely lead to new sequences that should be entered into the OEIS, with due credit to the contributing students, thereby guaranteeing them immortality. Some of the final projects may lead to journal publications.
Added Jan. 30, 2012: Here is Yusra Naqui's answers
Added Jan. 30, 2012: See Kristen Lew's answers and Pat Devlin's answers
Added Jan. 30, 2012: See John Kim's answers and Pat Devlin's answers
Carefully Read George Andrews's cute 1979 Monthly Note, and convince yourself that his "theorem" can be rigorously proved by checking it for only 37 special cases (n=1..., 37).
[Version of Feb. 3, 2012, minor error in the sample output corrected, thanks to John C. Miller]
Write a procedure GFtoSeq(f,q,m) that inputs
an expression f in the variable q, and outputs the
list of numbers of length m, let's call it, L, such that
L[i] is the coefficient of q^{i} in the Maclaurin
(i.e. Taylor about q=0) expansion of f with respect to the variable q,
for i from 1 to m. For example,
GFtoSeq(1/(1-q)^2,q,10);
should output
[2,3,4,5,6,7,8,9,10,11]
[Hint, use the taylor and coeff commands].
Write a procedure F(m,x) that expresses trunc(x/m) as a quasi-polynomial in x of order m for integer x.
Find the quasi-polynomial (in our format) that describes George Andrews' succinct expression for T(n) in George Andrews's cute 1979 Monthly Note.
[Optional Challenge, 2 dollars to be divided among all correct answers] The problem that George Andrews solved is equivalent to enumerating integer partitions with three parts, [a,b,c] with a ≥ b ≥ c ≥ 0 that sum-up to n, and such that b+c ≥ a Find a quasi-polynomial for the number of integer partitions with four parts, [a,b,c,d], with a ≥ b ≥ c ≥ d ≥ 0 that sum-up to n, and such that b+c+d ≥ a .
[Big Challenge, 6 dollars to be divided among all correct answers] Find a quasi-polynomial for the number of integer partitions [a,b,c,d,e] with a ≥ b ≥ c ≥ d ≥ e ≥ 0 that sum-up to n, and such that b+c+d+e ≥ a .
Added Feb. 8, 2012: See John Kim's answers, Kristen Lew's answers and Nathaniel Shar's answers and
Read pages of 1-11 of this masterpiece
Write a procedure RecToSeq(C,n) that inputs a C-finite sequence,
in our notation, and a pos. integer n, and outputs the
list of length n with the first n terms of the sequence.
For example,
RecToSeq([[-1,-1],[1,1]],10);
Should output
[1,1,2,3,5,8,13,21,34,55] .
[version of Feb. 7, 2012, 8:14am, correcting the sample output (thanks to Yusra Naqvi and John Kim for detecting the error)
Using the fact that the sum of two C-finite sequences
of orders a and b is a is C-finite sequence of order ≤ a+b,
use procedure RecToSeq to
write a procedure Add1(C1,C2) that inputs two C-finite
sequences in our notation and outputs a C-finite sequence
that describes their sum.
In our notation. For example
Add1([[-1],[1]],[[-2],[1]]); should output
[[-3,2],[2,3]]
[version of Feb. 7, 2012, 6:32pm, correcting the sample output (thanks to Yusra Naqvi)
Using the fact that the product of two C-finite sequences
of orders a and b is a is C-finite sequence of order ≤ ab,
use procedure RecToSeq to
write a procedure Mult1(C1,C2) that inputs two C-finite
sequences in our notation and outputs the C-finite sequence
that is their product (in our notation).
For example
Mult1([[-2],[1]],[[-3],[1]]); should output
[[-6],[1]]
Use RecToSeq to write a procedure BT(C) that inputs a C-finite sequence and outputs its Binomial Transform (see the top of p. 11 of this masterpiece for definition).
[Corrected version, posted Feb. 9, 2012, thanks to Yusra Naqvi]
Use RecToSeq to write a procedure Tsect(C,t,r) that inputs
a C-finite sequence and a positive integer t, non-negative
integer r, (0 ≤ r < t) such that if C is the C-finite description of
a sequence a(n), then the output is the
C finite description of the sequence a(tm+r), m=0,1,2,3,4 ...
[On-going competition, starts today] Find as many published articles in the mathematical literature that are "trivial" in a similar way to the Fibonacci identity on p. 10 of this masterpiece. It will be entered, with due credit to the discoverer in the page. Compendium of Utterly Trivial Papers
[Optional, 25 cents for each solution, up to 3 dollars per person (i.e. each person is allowed up to 12 solutions, the rest can be done for free). Ongoing, while the semester lasts.]
Browse through the free problem sections in the issues of the Fibonacci Quarterly and find "proofs in the style of Zeilberger" (i.e. proving that A(n)=B(n) for all n by checking finitely many cases, with a full justification why the number of checked cases suffices)
Inputs:
GenHOMPol(X,d,a,co):
Inputs:
Outputs:
Inputs:
Outputs:
Inputs:
Outputs: a polynomial, let's call it, P(x[0],x[1], ..., x[ORDER]), of total degree ≤ DEGREE such that for all n, P(L[n],L[n+1], ..., L[n+ORDER])=0. For example, GuessPR([seq(2^i,i=1..30)],x,1,1); should output x[1]-2x[0].
Consider the list of lists
L:=[[8, 29, 104, 293, 680], [61, 112, 237, 496, 973], [216, 309, 504, 861, 1464], [557, 704, 989, 1472, 2237], [1192, 1405, 1800, 2437, 3400]]:
Let g=g(x,y) be the unique polynomial of degree 4 in both x and y,
such that
g(i,j)=L[i][j] 1 ≤ i,j ≤ 5
Added Feb. 21, 2012:See the nice solutions of Pat Devlin, John Kim, Kristen Lew, Ben Miles, Matthew Russell, Nathaniel Shar.
Added Feb. 21, 2012:See the nice solutions of Pat Devlin, John Kim, Kristen Lew, Nathaniel Shar.
Carefully read, and understand the following write-up on the Lagrange Inversion Formula
[Version of Feb. 23, 2012, corrected by Yusra Naqvi]
Write a procedure LIF(F,z,P,n) that inputs a polynomial F in z and P
signifying an
algebraic relation F(P,z)=0 and symbols P, z,
makes a change of dependent variable to get it to the format
required by the Lagrange Inversion Formula
(IF POSSIBLE, it is often not possible, in that case return FAIL)
and n, and outputs
(in the notation of that writeup PHI(z)^n/(n z^(n-1)) .
[Clarifying example, added Feb. 26, 2012, 11:05am]
The output of LIF(P-x*(1+P)^2,x,P,n) is simply
(1+x)^(2*n)/n/x^(n-1)
[So the constant term of this Laurent polynomial is the desired coefficient
that happen to be the Catalan number C(n) [thanks to John C. Miller for the correction, before
I erroneously wrote C(n-1)]
Note the variable "x" (or "z") has different meanings in the input and the output, but since it is
only a "place-holder" it does not matter (at least not to the computer).
Added Feb. 27, 2012:See the nice solutions of BenMiles, Pat Devlin, John Kim, Alex Gentul, Yusra Naqvi, Nathaniel Shar.
Added Feb. 27, 2012:See the nice solutions of Pat Devlin, John Kim, Yusra Naqvi, Matthew Russell, Nathaniel Shar, Charles Wolf.
AlgToSeq(F,P,x,K,f0): INPUTS
(i)a polynomial F in the variables P and x
denoting an algebraic relation satisfied by a formal
power series P(x), such that
F(P(x),x)=0
(ii) and (iii) variables P and as above
(iv): a pos. integer K
(v): f0 the constant term
OUTPUTS:
a sequence of length K+1 denoting the
coeff. of x^0 through x^K of the Maclaurin expansion
of the power series of P(x).
For example,
AlgToSeq(P*(1-x)-1,P,x,4,1); should output [1,1,1,1,1];
AlgToSeq(P-1-x*P^2,P,x,4,1); should yield:[1,1,2,5,14]
For example,
GuessDE([seq(1/i!,i=0..20)],x,Di,1);
should return
Di-1
Since the exponential function e^{x} is a solution of
the differential equation
(Di-1)e^{x}=0
Hint: First write
GuessDE1(L,x,Di,M)
for a differential operator with ORDER+DEGREE equal to M, and
then climb up.
Warning: Di and x DO not compute. A differential operator has the form
Sum(a[i,j]*x^i*Di^j, i+j<=M):
Since Maple does not that x and Di do not commute, it may write,e.g.
Di*x, but then the human should understand it as x*Di.
Another hint:
Di^j f(x)=diff(f(x),x$j) if j>0 but when j=0 D^j f(x)=f(x)
(Maple does not like diff(f(x),x$0);)
By composing GuessDE with AlgToSeq, write a program
AlgToDe(F,P,x,Di,K) that inputs a polynomial F(P,x) in the variables
P and x, representing an algebraic equation
F(P(x),x)=0
satisfied by a formal power series P(x), and a positive integer K,
and conjectures a differential operator "annihilating" P(x), by
using the first K+1 coefficients of the Maclaurin expansion of P(x).
For example
AlgToDE(P*(1-x)-1,P,x,30); should return
(1-x)*Di-1
Added March 5, 2012:See the nice solutions of Pat Devlin, John Kim, Kristen Lew, Ben Miles, Yusra Naqvi, Nathaniel Shar,
Added March 5, 2012:See the nice solutions of Pat Devlin, John Kim, KristenLew, Ben Miles, Yusra Naqvi, Matthew Russell, Nathaniel Shar, Charles Wolf,
GuessH(L,n,N): Inputs a sequence of numbers L
and symbols n and N
and finds a minimal (in the sense of ord+deg)
linear recurrence operator with
poly. coeffs. (conj.) annihilating the sequence L with
nops(L)>=(1+ORD)*(1+DEG)+ORD+6 .
For example,
GuessH([seq(i!,i=1..10)],n,N); should give
N-(n+1)
SpellOut(ope,n,N,f):
writes the fact ope(n,N)f(n)=0 in common language
phrased in terms of the sequence name f(n).
For example,
SpellOut(N-n-1,n,N,f); should give
f(n+1)-(n+1)f(n)=0
[debugged by John Kim] HtoSeq(ope,n,N,Ini,M): Inputs a linear recurrence operator ope phrased in terms of the discrete variable n and its corresponding shift operator N, and ORD=degree(ope,N) values for the sequence outputs the first M terms of the sequence. For example, HtoSeq(n+1-N,n,N,[1],4); should yield [1,2,6,24]
Try EmpiricalZeilbegrer out (with M large enough) and
Compare the about outputs with the Maple procedure
SumTools[Hypergeometric][Zeilberger](F,n,k,N)[1] ;
Write a procedure
DiagRec(F,x,y,z,M,n,N)
that inputs a rational function F of the variables x,y,z (whose denominator does not vanish at
(x,y,z)=(0,0,0) so it has a Taylor series around the origin, and a positive integer M
(indicating how many terms to use for guessing), and symbols n and N and
outputs a linear recurrence operator with polynomial coefficients, ope(n,N),
annihilating the sequence
a(n):=coeff of x^{n}y^{n}z^{n} in the Taylor expansion of F around the origin.
For example,
DiagRec(1/(1-x-y-z),x,y,z,40,n,N);
should return (I hope, I did it in my head)
(n+1)^2*N-3*(3*n+1)*(3*n+2) .
Hint: Either use mtaylor or iterated taylor.
Apply DiagRec(F,x,y,z,M,n,N) to
Added March 19, 2012: See the nice solutions of Alex Gentul, John Kim, BenMiles, YusraNaqvi, and Matthew Russell .
Added March 19, 2012: See the nice solutions of Alex Gentul, John Kim, BenMiles, and YusraNaqvi .
Using the above program, write a program
FindMu(ope,n,N)
that inputs a linear recurrence operator with polynomial coefficients,
ope(n,N), and outputs the root of the largest absolute value
of lcoeff(ope,n) (a certain polynomial in N), if it is positive, or
returns FAIL if it is negative, or if there are ties (i.e. both
a and -a are roots), or if the root(s) with maximal absolute value
are complex. For example,
FindMu((n+2)*N^2-(3*n+3)*N+(2*n+5),n,N);
should return: 2.
Using the above, write a program
FindTheta(ope,n,N,Ini)
that inputs a linear recurrence operator ope, phrased in terms of
n and the shift N, and Ini, a list of length degree(ope,N) indicating
the initial values of the sequence, and outputs a guessed
RATIONAL number such that the sequence defined by
a(m):=HtoSeq(ope,n,N,Ini,m)[m]
is given by:
a(m) IS ASYMPOTIC TO C*mu^{m} * m^{theta}
for some constant C, and the above mu that you found, using
FindMu(ope,n,N).
[Hint: look at log(a(m+1)/a(m)/mu)/log((m+1)/m) for very large m (you decide how large),
and then use the first (or second, you decide) convergent in the Maple command (see the help for it)
convert(%,confrac,cvgsts);
to get a good rational number approximation for theta .]
Using all the above, write a program
FindC(ope,n,N,Ini), that estimates the C in:
a(m) IS ASYMPTOTIC TO C*mu^{m}* m^{theta}
Use Maple's built-in command "identify" to see whether C can be
expressed in terms of known constants.
Combine all the above, and write a procedure
Asy(ope,n,N,Ini)
that inputs ope and Ini as above and outputs the leading asymptotics.
By combining with
EmpiricalZeilberger(F,n,k,N,L);
Write a program:
AsyBS(F,n,k,L)
that inputs a binomial coefficient expression phrased in terms of
n and k, and a pos. integer L (for guessing, made large enough) and
conjectures asymptotics for
a(n):=add(F(n,k),k=0..n)
What are:
Challenge! [5 dollars to be divided among all correct answers] Write a program
BetterAsy(ope,n,N,Ini,r)
that empirically finds an asymptotic expression for the sequence, let's call it a(n), annihilated by ope(n,N)
with the initial values given by Ini to order r, in other words
a(n)=C*mu^n*n^theta*(1+c[1]/n+c[2]/n^2+ ...+ c[r]/n^r +O(1/n^(r+1)) ),
for C,mu,theta as for Asy(ope,n,N,Ini), and c[1],c[2], ..., c[r], "nice" rational numbers.
If you can't find it, it should return FAIL. Then write BetterAsyBS(F,n,k,L,r) and try out
Added March 26, 2012: See the nice solutions of Patrick Devlin, John Kim, Kristen Lew, Yusra Naqvi, Matthew Russell, Nathaniel Shar,
Today we had a guest-lecture by the soon-to-be-Dr. Edinah Gnang, who gave a tutorial on the open-source beautiful (and powerful) computer algebra system SAGE. He followed William Stein's demo Sage worksheet.
[Assigned by guest-lecturer Mr. Edinah Gnang]
All homework (for this assignment alone)
should be uploaded to the secret directory that you gave me,
as file hw17.txt
[For people who don't have a math account, Sage is available on: apps.rutgers.edu After you login, just type "sage"
If you want the web enhanced view, just type "notebook()".
You will be prompted to establish a password. (I thank Philip Benjmain for this information).]
Today we wrote "brute force" programs to find the first few terms of Szemerédi's famously difficult sequences defined as follows.
Let a_{d}(n) be the largest size of a subset of {1, ...,n} avoiding arthmetical progressions of length d. Szemerédi's famous theorem says that for all d larger than 1,
a_{d}(n)/n -> 0 .
Even you and I can prove the case d=2, but the case d=3 is already worth a Fields medal, and was done in the early fifties by Klaus Roth. I strongly recommend David Wilson's lively and interactive webbook that gives a motivated and leisurely account of Roth's theorem that there is a constant C such that for all n
a_{3}(n)/n<=C/log(log(n))
Contains the following procedures:
Adn(d,n): Inputs positive integers d and n and outputs the set of all subsets of {1, ...,n} that DO NOT have an arithmetical progression of length d
IsBad(d,S): Does the set of pos. integers S contain an AP of length d?
adnS(d,n): a stupid way of computing a_{d}(n) as above.
NdnS(d,n): a stupid way of computing the number of subsets of {1, ...,n} that do not contain an AP of length d
[Just starting!]
Wn(A,FP,B,n): inputs
(i) A: a set of symbols (the alphabet)
(ii) FP: a set of forbidden patterns, given as a list
where B denotes Blank. For example, if FP contains
[1,B,1,B,1] then our words may not contain
10101, 10111, 11101, 11111
(iii) B: a symbol for Blank
(iv) n a positive integer
Outputs:
The number of words in the alphabet A of length n that
AVOID all the patterns of FP.
For example,
Wn({0,1},{[1,B,1]},B,3); should return 6
WGn(A,FP,B,n,BFP) [Just strating!]: inputs
(i) A: a set of symbols (the alphabet)
(ii) FP: a set of forbidden patterns, given as a list
where B denotes Blank. For example, if FP contains
[1,B,1,B,1] then our words may not contain
10101, 10111, 11101, 11111
(iii) B: a symbol for "Blank" (or "wild character")
(iv) n a pos. integer
(v): Another set of patterns (same format as for FP)
Outputs:
The number of words in the alphabet A of length n that
AVOID all the patterns of FP and IN ADDITION AVOID
the set of patterns BFP at the beginning
For example,
WGn({0,1},{[1,B,1]},B,3,{[0]});
should return 2
(corresponding to the set of words {[1,0,0],[1,1,0]})
All homework (for this assignment alone) should be uploaded to the secret directory that you gave me, as file hw18.txt
Added April 2, 2012: See the nice solutions of Patrick Devlin, John Kim, BenMiles, John Miller, Yusra Naqvi, Matthew Russell, and Nathaniel Shar.
Contains the following procedures, in addition to
adnM(d,n): a mediocre way of computing a_{d}(n) as above.
NdnM(d,n): a mediocre way of computing the number of subsets of {1, ...,n} that do not contain an AP of length d
[Finished! (hopefully)]
Wn(A,FP,B,n): inputs
(i) A: a set of symbols (the alphabet)
(ii) FP: a set of forbidden patterns, given as a list
where B denotes Blank. For example, if FP contains
[1,B,1,B,1] then our words may not contain
10101, 10111, 11101, 11111
(iii) B: a symbol for Blank
(iv) n a positive integer
Outputs:
The number of words in the alphabet A of length n that
AVOID all the patterns of FP.
For example,
Wn({0,1},{[1,B,1]},B,3); should return 6
WGn(A,FP,B,n,BFP) [Finished!, hopefully]:
Important note:
In class I forgot to put "option remember".
Please make sure that you have the new version
of
C19.txt,
(or add it yourself).
inputs
(i) A: a set of symbols (the alphabet)
(ii) FP: a set of forbidden patterns, given as a list
where B denotes Blank. For example, if FP contains
[1,B,1,B,1] then our words may not contain
10101, 10111, 11101, 11111
(iii) B: a symbol for "Blank" (or "wild character")
(iv) n a pos. integer
(v): Another set of patterns (same format as for FP)
Outputs:
The number of words in the alphabet A of length n that
AVOID all the patterns of FP and IN ADDITION AVOID
the set of patterns BFP at the beginning
For example,
WGn({0,1},{[1,B,1]},B,3,{[0]});
should return 2
(corresponding to the set of words {[1,0,0],[1,1,0]})
All homework (for this assignment alone) should be uploaded to the secret directory that you gave me, as file hw19.txt
By using Wn(A,FP,B,n), with A={0,1}, and appropriate FP, that
you have to program yourself, write a procedure
NdnC(d,n), that finds, in a clever way, N_{d}(n).
[Hint, the largest "difference" an AP of size d in {1, ...n}
can have is (n-d)/(d-1)]
Modify Wn(A,FP,B,n) to procedure
WnX(A,FP,B,n,x)
(using an analog/extension of WnG(A,FP,B,n) that you may call
WnGX(A,FP,B,n,x)) that outputs not
just the number of words of length n avoiding the set of patterns
in FP but the weight enumerator where the weight of a word
a1 a2 a3 ... an
is
x[a1]x[a2] ... x[an]
For example
WnX({1,2},{[1,B,1]},B,3,x);
should return expand((x[1]+x[2])^3-x[1]*(x[1]+x[2])*x[1]);
[Hint: It is a minor programming modification in the line:
co:=co+WGn(A,FP,B,n-1,BFP1): ]
Using your
WnX(A,FP,B,n,x)
with A={0,1}, write a procedure
adnC(d,n)
that computes a_{d}(n) cleverly.
[Hint: similar to NdnC(d,n), but now you need the degree of x[1] in
the weight-enumerator.]
[Human Problem]: Using generatingfunctionology and linear algebra,
prove that for any finite set of finite patterns,
the "infinite sequence"
[seq(Wn(A,FP,B,n), n=1..infinity)]:
is C-finite.
Added April 2, 2012: See the nice solutions of Patrick Devlin, John Kim, KristenLew, BenMiles, Yusra Naqvi, Matthew Russell, and Nathaniel Shar.
If S is a set of non-negative integers, then
mex(S)
is defined to be the smallest non-negative integer that
is NOT in S. For example,
mex({0,1,2,5})
is 3, and
mex({2,3,5})
is 0.
Define an integer sequence by the simple recurrence
a[i]:=mex({0,1} union {seq(j*a[r],j ≥ 1, 1 ≤ r < i}, i ≥ 1
[Important remark by Michael Somos: Before one can program this definition for a computer one has to rephrase it so that the domain of j is finite]
Prove the following simple properties about this sequence
There are infinitely many i such that
a_{i+1} - a_{i}=2 ,
a_{i}+ a_{j}=2n .
Reminder: You must pick a project by April 4, 2012, if you have not done so already. Please Email me with a commitment (remember, you can propose your own project).
All homework (for this assignment alone) should be uploaded to the secret directory that you gave me, as file hw20.txt
It is clear that every word of length ≥ k in the alphabet {0,1}
must contain
one of the 2^{k} patterns of length k (forget about Blanks in this
problem). Call a set of length-k patterns
unavoidable
if every sufficiently long word in {0,1} must contain one of
its members. By using GFunT(A,B,FP,T),
with A={0,1}, and FP ranging over all 2^{(2k)}
possible sets of length-k B-free
patterns,see which of them outputs
a polynomial in T (i.e. a rational function in T whose denominator is 1).
In other words, write a program, UA(k), that inputs a positive integer k, and outputs
the set of sets of length-k-patterns as described above. Of course for k > 4 it
would be hopeless. For example
UA(1);
should return:
{{[0],[1]}}
Find UA(2), UA(3), and if possible, UA(4).
Call a set of patterns of length k almost unavoidable
if asymptotically, the number of words of length n
avoiding that set of patterns has polynomial growth
(as opposed to exponential growth, the default).
By using GFunT(A,B,FP,T),
with A={0,1}, and FP ranging over all 2^{(2k)}
possible sets of B-free length-k-patterns, see which of them outputs
a rational function whose denominator has roots whose
absolute value is ≥ 1
write a program AUA(k), that inputs a positive integer k, and outputs
the set of sets of patterns as described. Of course for k > 4 it
would be hopeless. For example
AUA(1);
should return:
{ {[0],[1]}, {[0]}, {[1]} } .
Find AUA(2), AUA(3), and if possible, AUA(4).
IsImpliedPattern(pat1,pat2,B) ,
that inputs two patterns, pat1, pat2 and outputs true if and only if
any occurrence of pat1 implies an occurrence of pat2 .
For example,
IsSubPattern([1,1,1],[1,1],B);
and
IsSubPattern([1,3,1],[1,B,1],B);
should both return "true", while
IsSubPattern([2,1,1],[1,B,1],B);
should return
False
Added April 9, 2012: See the nice solutions of Philip Benjamin, Patrick Devlin, John Kim, Yusra Naqvi, Matthew Russell, and Nathaniel Shar.
All homework (for this assignment alone) should be uploaded to the secret directory that you gave me, as file hw21.txt
Note: Since the last homework assignment was longer than usual, this one makes up for it by being shorter then usual.
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.
Added April 9, 2012: See the nice solutions of Philip Benjamin, Patrick Devlin, John Kim, Yusra Naqvi, Matthew Russell, and Nathaniel Shar.
All homework (for this assignment alone) should be uploaded to the secret directory that you gave me, as file hw22.txt
[Correction posted April 12, 2012, 11:30am: The first problem is cancelled due to the previously erroneous definition of "split". The true definition uses a theorem of Conway that is implemented here.]
SplitUp(L) ,
that inputs a list in {1,2,3}*, L, and outputs it as a list of lists
[L1,L2,L3, ...]
where
L=[op(L1),op(L2), op(L3), ...]
and L1,L2,L3, are atoms.
Added April 16, 2012: See the nice solutions of Philip Benjamin, Patrick Devlin, Alex Gentul, John Kim, Ben Miles, Yusra Naqvi, Matthew Russell, and Nathaniel Shar.
URT(N): the first N terms of the enumerating sequence for the number of UNLABELED rooted trees with n vertices. Using Arthur Cayley's seminal approach from 1883.
All homework (for this assignment alone) should be uploaded to the secret directory that you gave me, as file hw23.txt
I think there's a little bug in the current experimental math homework. I don't think that the current definition of Mat() in (2) works to calculate Conway's constant as the largest eigenvalue in (3). (When I did this, the largest eigenvalue was over 4).
Instead, I think that the way to construct Mat() should be to compute SplitUp(JC1(atom i)), and then Mat(i,j) is the number of times that atom j appears in SplitUp(JC1(atom i)) (possibly multiple times).
Find RLT1({1},20), RLT1({1,2},20), RLT1({1,2,3},20), RLT1({1,3},20).
Are any of these in Sloane?
Find RLT2({1},20), RLT2({1,2},20), RLT2({1,2,3},20), RLT2({1,3},20).
Are any of these in Sloane?
Added April 16, 2012: See the nice solutions of Patrick Devlin, Alex Gentul, Ben Miles, John Miller, Yusra Naqvi, Matthew Russell, and Nathaniel Shar.
Added April 16, 2012: Read John Horton Conway's masterpiece
Pat Devlin would have won it, but due to putting wrong initial conditions, his first answer was wrong (he later corrected it, but Neil and a few other people got it). The runner-up (and the first amongst the math students [Neil is a CS student]) was John Miller, who won 1 dollar.
Since it was such a nice day, the remaining hour was spent outside, using the primitive computers between our shoulders, and primitive media called paper and pencils. We studied, and did paper-and-paper experimental math with p. 10 and the first quarter of p. 11, with Dr. Z.'s crash course on enumerative combinatorics.
All homework (for this assignment alone) should be uploaded to the secret directory that you gave me, as file hw24.txt
(a) Find all such n less than one million.
(b) By using the Matrix formula given in the wiki article, find P(2^20).
PAB(A,B,0)=3, PAB(A,B,1)=0, P(A,B,2)=2*A and for n ≥ 3, by the recurrence
PAB(A,B,n)=A*PAB(A,B,n-2)+B*PAB(A,B,n-3)
Write a procedure, PseudoPrime(A,B,N) that inputs positive integers A and B and a positive integer N and finds all composite (i.e. non-prime) n such that PAB(A,B,n)/n is an integer.
"For A=43 and B=41, find the smallest pseudoprime that is NOT divisible by either 41 or 43"
Added 7:15am, April 23, 2012:
John Kim is the lucky win!
His program finally found the number: 2976487.
It took John Kim's machine 4570 seconds, which is roughly 1 hour and 16 minutes.
Front: 1 ; Back: 6; Left:3; Right: 4; Bottom:2; Top=5.
For example
Polya({[1,2],[2,1]},c);
should output
(c^2+c)/2
[seq(CC(i),i=1..infinity)]
in Sloane?
Added April 23, 2012: See the nice solutions of Phil Benjamin, Patrick Devlin, John Kim, Kristen Lew, John Miller, Yusra Naqvi, Matthew Russell, Nathaniel Shar, and Charles Wolf.
Warning: do not dare go beyond N=6.
All homework (for this assignment alone) should be uploaded to the secret directory that you gave me, as file hw25.txt
ConULG(n) ,
that inputs a pos. integer n, and outputs ONE representative
from each equivalence class.
Use this to write a procedure
NuConULSeqSlow(N):
that counts, the number of connected unlabeled graph (alias
equivalence class under permuting labels) on n vertices for
n from 1 to N.
Is
NuConULSeqSlow(6):
in Sloane?
Added April 23, 2012: See the nice solutions of John Kim, Kristen Lew, John Miller, Matthew Russell, Yusra Naqvi, and Nathaniel Shar.
All homework (for this assignment alone) should be uploaded to the secret directory that you gave me, as file hw26.txt
Added April 30, 2012: See the nice solutions of Patrick Devlin, John Kim, Kristen Lew, Matthew Russell, Yusra Naqvi, and Nathaniel Shar.
All homework (for this assignment alone) should be uploaded to the secret directory that you gave me, as file hw27.txt
Added April 30, 2012: See the nice solutions of John Kim, Kristen Lew, Matthew Russell, Yusra Naqvi, and Nathaniel Shar.
Next, the students were given the following one-dollar challenge
(that I learned from Haim Shapira's wonderful book (in Hebrew)
about Game theory). Two teams of gladiators are competing as follows.
First the coach of each team lines them up according to the way
that he thinks best, and then the two gladiators fight until one of
them is out of the game. The probability of a gladiator of weight a
beating a gladiator of weight b is a/(a+b). When a gladiator wins,
he goes to the end of his team's line, and when he loses, he is out of
the game. The team who is the first to lose all its members if the winner.
First question: write a Maple code that computes the probability
Pr(L1,L2)
of team 1 beating team 2 with the lists of the weights given by that order.
Second Question: What is the optimal ordering that the coaches
should choose?
Pat Devlin was the dollar, John Miller, came second, and Nathaniel
Shar and Ben Miles came third for the first question. The answer
to the second question (that is obvious from the output of the first,
at least for small teams, and since we are doing experimental mathematics,
we believe that is true for all sizes is that
It does not matter
(in other words, the coaches are superfluous)
Then we continued with a crash course in Combinatorial Game Theory, and wrote the following code:
GW(x)=mex(GW(y), x->y)
No due date! (open until the prize is claimed)