Last Update: May 5, 2016.
We will first learn Maple, and how to program with it. This semester we will get an overview of some of the major open problems in mathematics, and see that using experimental mathematics will make us understand them much better, and hence increase our chances of solving them from ε2 to ε. We will also learn how to search the internet for "minor" open problems, that are directly doable by using readily available computer algebra software, and result in publishable articles.
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.
There are no prerequisites (in particular, no prior knowledge of Maple, or any programming experience, is assumed). Also, no overlap with previous years.
Added Jan. 25, 2016: Students are encouraged to solve any problem in the Problem Section of the American Mathematical Monthly in its 100 years of existence, using Maple in a substantial way. All solutions will be posted, with due credit in this page. The three people submitting the most solved problems will get prizes.
[Added May 10, 2016: Mingjia Yang won the prize.]
Read the wikipedia entry on Millenium Prize Problems
Read (or at least skim) Steve Smale's list of problems
It should be sent to the email address
ShaloshBEkhad at gmail dot com
Subject: HomeWork#X
and then attach a .txt file(s) called
hwXYourFirstNameYourLastName.txt
where X is the number of the assignment
Except for the first assignment, you should have two attached .txt files.
For example, when Anthony Zaleski submits homework assignments 2 and 3, he should email ShaloshBEkhad at gmail dot com, with
Subject: HomeWork#2#3
and attach the text files (the source code plus human comments (such lines must start with #)
hw2AnthonyZaleski.txt and hw3AnthonyZaleski.txt
#Please do not post homework
or
#OK to post homework
Hn(n)+exp(Hn(n))*log(Hn(n))-sigma(n) ,
where sigma(n) is the sum of divisors of n. Jeff Lagarias proved that JL(n)>0 for every n, iff the Riemann Hypothesis is true. So in order to disprove RH, all yon need is to come-up with an integer n0 such that JL(n0)<0.
Subject: hw#1
and an attachment
hw1FirstNameLastName.txt
Read and do all the examples, plus make up similar ones,
in the first 30 pages of Frank Garvan's
awesome Maple booklet
(
part 1,
part 2)
Only record a small sample in hw1YourName.txt .
Note: a few commands are no longer valid in today's Maple. The
most important one is that " has been replaced by %.
Amicable(N)
that inputs a positive integer N and outputs the set of all pairs [a,b], with 1 ≤ a < b ≤ N that are amicable.
What is
Amicable(1000)?
C(eps,N)
that inputs a small positive number, eps, and a large positive integer N, and outputs the maximum of
abs(evalf(M(n)/n^(1/2+eps)))
for n from 1 to N. Here M(n) is the Mertens function, that we called Mer(n) in the Maple code.
Using this procedure, find
C(1/10,3000); C(1/100,5000); C(0,10000);
n is a left-to-right maximum if JL(n) is larger than JL(m) for all m < n .
Write a procedure
LtoRmaxJL(N)
that finds the locations of all the left-to-right maxima of JL(n) up N.
What is
LtoRmaxJL(2000)?
Do you notice anything about these numbers?
Added Jan. 25, 2016: See the students' nice Solutions to the 1st homework assignment
Subject: hw#2
and an attachment
hw2FirstNameLastName.txt
Read and do all the examples, plus make up similar ones,
in the pages 30-60 of Frank Garvan's
awesome Maple booklet
(
part 1,
part 2)
Only record a small sample in hw2YourName.txt .
Sum((-1)^n*(a^n+b^n)/(n+2),n=1..infinity)
where and b are the roots of x^2+x+1/2=0. Write a procedure
Gen11876(c1,c2)
that, more generally, does the same for the roots of x^2+c1*x+c2=0. In particular
Gen11876(1,1/2)
should give the answer to the original problem (that we found out was π-3).
Try to find other values of c1 and c2 such that Gen11876(c1,c2); gives "nice" answers.
Type in Maple
plot(evalf(abs(Zeta(1/2+s*I))),s=1..100);
To get a very rough idea of the location of the first few non-trivial zeros of ζ(s) .
Then by using
plot(evalf(abs(Zeta(1/2+s*I))),s=a..b);
for smaller and smaller intervals [a,b] locate numerically these zeros hopefully confirming the data in mathworld
Hint: For example it seems that there is a root between s=13 and s=15, so type plot(evalf(abs(Zeta(1/2+s*I))),s=13..15);
Now it looks like that there is a root between s=14.1 and s=14.2, so type
plot(evalf(abs(Zeta(1/2+s*I))),s=14.1..14.2);
Now it looks like that there is a root between s=14.13 and s=14.14, so type
plot(evalf(abs(Zeta(1/2+s*I))),s=14.13..14.14);
and keep narrowing it down until you get as many digits as in the table in mathworld. For the first root it is: 14.134725
Repeat for the other roots with s < 100.
IsNormal(x,K,d)
to write a procedure
IsNormalG(x,K,d,g)
That inputs the same as IsNormal(x,K,d), but also a positive integer d, and outputs a list L of size dg such that its entries are the number of occurrences of g consecutive digits in the base-d representation of x (up to K places). In particular
IsNormalG(x,K,d,1)
should be the same as IsNormal(x,K,d).
Hint: You may want to first write a subroutine, ListToNum(L,d), that inputs a list of digits in base d, and outputs its numerical value, For example ListToNum([1,0,2],3) should be 3^2+0*3+2*1=11. Then in the main program replace the line
f:=add(z[L[i]],i=1..nops(L)):
By
f:=add(z[ ListToNum([op(i..i+g-1,L],d),i=1..nops(L)-g+1):
HowNormal(x,K,d)
that uses IsNormal(x,K,d), getting as output a list L of size d. Calling the sum of the entries of L, |L| (in Maple: add(L[i],i=1..nops(L)), or, convert(L,`+`)). The output of HowNormal(x,K,d) should be
add( (L[i]/|L| -1/d)^2, i=1..d)
Note that the closer x is to being normal, the smaller this should be.
For K=4, d=10. Find the output of HowNormal(sqrt(n),4,10) for all n from 2 to 1000 that are NOT perfect squares. What sqrt(n) is the most normal? What is the least normal?
Added Feb. 1, 2016: See the students' nice Solutions to the 2nd homework assignment
Subject: hw#3
and an attachment
hw3FirstNameLastName.txt
Read and do all the examples, plus make up similar ones,
in the pages 60-90 of Frank Garvan's
awesome Maple booklet
(
part 1,
part 2)
Only record a small sample in hw3YourName.txt .
EvalPP(L)
that inputs a list of positive integers L, and finds the quadratic irrationality whose continued fraction is Linfinity (i.e. L repeated infinitely many times)
Hint: Extend the "self-similarity" argument we did for y=2infinity that it implied that y=2+2/y. Now we have y=ListToN([op(L),y]):
EvalP(Pair), where Pair is a pair of lists of positive integers (e.g. those that come as outputs of CfSq(n)), Pair=[M,L], and outputs the EXACT value of the continued fraction
M Linfinity
For example
EvalP([[1],[2]]);
should output sqrt(2).
Proved(CfSq(n))
that first uses CfSq(n) to guess an ultimately-periodic continued fraction representation, and then goes on to rigorously prove it, by proving that EvalP(CfSq(n)) equals sqrt(n)
[Hint: Maple is terrible in simplifying surds (quadratic irrationalities), you should use simplify( EvalP(CfSq(n))-sqrt(n)) and make sure that you get 0.
Added Feb. 1, 2016: See the students' nice Solutions to the 3rd homework assignment
Subject: hw#4
and an attachment
hw4FirstNameLastName.txt
Read and do all the examples, plus make up similar ones,
in the pages 90-120 of Frank Garvan's
awesome Maple booklet
(
part 1,
part 2)
Only record a small sample in hw4YourName.txt .
BTP(K)
that inputs a large integer K and outputs the smallest integer p, larger than K, such that both p and p+2 are primes.
[Comment added Feb. 3, 2016: a couple of people noted that if you did not know whether the Twin Prime conjecture is true, the above program may never halt, but I believe in it, so I am not worried. Those who are skeptical can write a program that limits the search from K to 10^10+10*K]
ExpProveTwinPrimeConjecture1(n)
that picks a random integer, let's call it, m, between 10n and 102n , and finds twin primes larger than m.
ExpProveTwinPrimeConjecture(n,K)
that tries out
ExpProveTwinPrimeConjecture1(n)
K times, and if it always found such twin primes, it returns true. Otherwise false.
ExpProveTwinPrimeConjecture(50,100)
and find an empirical proof of the Twin Prime Conjecture (that there exist infinitely many primes p such that p+2 is also prime)
FactorTime1(n)
that takes two random primes, p, q, between 10n and 10n+10[n/2], multiplies them, and (using the Maple command time()) finds how long it takes to do
ifactor(p*q)
FactorTime(n,K)
that does FactorTime1(n) K times, and takes the average
FactorTimePlot(N,K)
that plots
FactorTime(n,K)
for n between 1 and N
FactorTimePlot(N,10)
for N that will make it run in reasonable time.
LtoRmax(L)
that inputs a list of numbers and outputs the sublist of entries that are larger than all the previous entries.
For example
LtoRmax([2,1,5,4,11,3,13,12,10,3]);
should output
[2,5,11,13]
LtoRmax(C(m^(1/3),infinity))
is a finite sequence, otherwise it is infinite. Hence these sequences are very important. For m between 2 and 20 (except for 8) find the first few terms , using LtoRmax(C(m^(1/3),300). Are they in the OEIS? Should they be? If you feel that they should, you are welcome to submit them.
Added Feb. 8, 2016: See the students' nice Solutions to the 4th homework assignment
Subject: hw#5
and an attachment
hw5FirstNameLastName.txt
Hints: First write Pli1(L,n,d) that uses the Lagrange Interpolation formula to fit the first d+1 entries of L with a polynomial of degree d (it always exists), and then checks whether it fits the remaining data. For efficiency's sake check whether the polynomial fits the data, in turn, for L[d+2],L[d+3] and as soon as you get a disagreement, return FAIL.
Also use the Maple commands "add" and "mul" to implement the Lagrange interpolation formula succinctly.
RandPolSeq(n,d,K)
that inputs a variable n, a positive integer d, a large positive integer K, and outputs a polynomial, let's call it p, in n, of degree d, with coefficients between 1 and K (chosen randomly). Use these to generate its list of values from 1 to 3*d, call the list L, and then use both GP(L,n) and the GPli(L,n) that you created above, and see whether they both give you p back, and find out which procedure is faster, (for fairly large d, of course for small d they are both very fast), by using the Maple command time().
0 ≤ x12 ≤ x13 ≤ x23 ≤ n
that obey the triangle condition
x23 ≤ x12 +x13
Hint: Introduce a counter, co, then do a triple do-loop with x12, x13, x23 each going from 0 to n, and then for each candidate check whether the condition is satisfies, and in that case, add 1 to co.
Hint: Once you have the four entries a11,a12,a21,a22, the remaining 5 entries can be determined and must all be non-negative, use a similar approach to the above problem to do the brute-force counting, and then try to fit the data with a polynomial.
Added Feb. 8, 2016: See the students' nice Solutions to the 5th homework assignment
Subject: hw#6
and an attachment
hw6FirstNameLastName.txt
Solve(R,n)
that inputs a pair R=[ini,rec] (same type of input as in RecToSeq(R,N)) and a variable n, and outputs a closed-form solution for x(n), the n-th term of the solution of the recurrence (as above R=[ini,rec], where rec=[c1, ..., ck]
x(n)=c1*x(n-1)+ ... + ck*x(n-k)
You may assume that all the roots of the so-called indicial equation
z^k-c1*z^(k-1)-... ck*z^0=0
are distinct.
Hint: first use Maple to solve the indicial equation, call its roots a1, ..., ak, set up a template
x(n)=C1*a1^n+ ... + Ck*ak^n
and use linear algebra (again Maple's solve, but this time solving a system of linear equations) to find C1, ..., Ck but using the initial conditions x(0)=ini[1], ..., x(k-1)=ini[k]
Check that the output agrees with the output of RecToSeq(R,N), also compare your output to Maple's built-in command "rsolve"
[Human exercise] prove that if the largest root of the indicial equation
z^k-c1*z^(k-1)-... - ck*z^0=0
is a1, and abs(a1) is larger than the absolute value of the other roots, then the limit of the ratio of consecutive terms in the sequence x(n),
limit (x(n+1)/x(n), n=infinity)
equals a1.
IrratMeasureSequence(R,N)
that inputs a recurrence R=[ini,rec] and a positive integer N and finds the first N terms of the sequence of real numbers, delta(n) such that
|x(n+1)/x(n)-a1| is roughly 1/(x(n)^delta(n))
Hint
delta(n)= -log(|x(n+1)/x(n)-a1|)/log(x(n))
See whether this sequence seems to converge.
What are the outputs of
IrratMeasureSequence([[0,1],[1,1]],100);
IrratMeasureSequence([[0,1,1],[1,1,1]],100);
Note: The Definition of Δf(x) there has a typo it should be
Δf(x)= (Σx->y w(x,y)) f(x) - Σx->y w(x,y) f(y)
TestUZ1(M)
that inputs a symmetric matrix M of non-negative integers (but with lots of zero entry), and where the diagonal entries are 0, and tests the assertion of the theorem.
Hints: First form the "Laplacian matrix", then use Maple to find the smallest eigenvalue, and the corresponding eigenvector, gather the subsets of vertices where they are negative and non-negative and find that they are both connected. You may want to write a subroutine
CC(M,i)
that inputs the weighted symmetric matrix M (that implies a graph if you put an edge between vertex x and vertex y, when the weight is non-zero and there is no edge if w(x,y)=0, and a vertex i, and find the connected component containing i.
RandomWG(n,K,alpha)
that inputs a random symmetric matrix with non-negative entries, between 0 and K, and all 0 on the diagonal, and about alpha*n^2 0 entries.
Write a procedure
TestUZ(M,K,T)
that tests TestUZ1(M) for T random weighted graphs (alias symmetric matrices) generated by RandomWG(n,K,alpha)
and returns true if it is always true, or a counterexample as soon as it is false.
Added Feb. 15, 2016: See the students' nice Solutions to the 6th homework assignment
x(n)=c1*x(n-1)+...+ck*x(n-k)
Subject: hw#7
and an attachment
hw7FirstNameLastName.txt
Power(R,k)
that inputs a C-finite sequence R=[ini,rec] and a positive integer k and outputs the description of its k-th power.
Conjecture (and if you wish, prove, but I am not offering any money for that) a closed form expression for the coefficients of the linear recurrence satisfied by the the sequence of k-th powers of the Fibonacci sequence, (Fn)k
[Added Feb. 15, 2016: Mingjia Yang won the prize! These are (except for the sign) the Fibonomial Coefficients, and this result goes back to the Israeli amateur mathematician (and distinguished historian) Dov Jarden, and is referenced in Knuth's Art of Computer Programming]
GuessP2V(L,x,y)
that inputs a list of lists L and two variables x and y, and outputs a polynomial P, in the variables x and y such that
P(i,j)=L[i][j]
for all i from 1 to nops(L) and all j from 1 to nops(L[i]). if it can't find anything, it should return FAIL.
P:= GuessP2V( [[12, 71, 236, 591, 1244, 2327, 3996], [39, 128, 335, 744, 1463, 2624, 4383], [ 124, 263, 540, 1039, 1868, 3159, 5068], [327, 536, 911, 1536, 2519, 3992, 6111] , [732, 1031, 1532, 2319, 3500, 5207, 7596], [1447, 1856, 2511, 3496, 4919, 6912, 9631], [2604, 3143, 3980, 5199, 6908, 9239, 12348]],x,y);
type
plots[implicitplot(P,x=-6..6,y=-6..6,axes=none):
also use the textblock command to insert, inside this curve, the phrase
YourName LOVES EXPERIMENTAL MATHEMATICS
where YourName is replaced by your name. If possible, have colors.
By using help, (or Garvan's book), find out how to save your plot as a .jpg file.
Save it as file
hw7FirstNameLastName.jpg
and include it as an attachment (in addition to hw7FirstNameLastName.txt, that should contain the Maple code.
Added Feb. 15, 2016: See the students' nice Solutions to the 7th homework assignment (including valentines)
x(n)=c1(n)*x(n-1)+c2(n)*x(n-2)+...+ck(n)*x(n-k)
Subject: hw#8
and an attachment
hw8FirstNameLastName.txt
Write a procedure
PRecToSeqW(R,n,N,w): inputs a P-recursive sequence R=[ini,rec(n)] where ini is a list of the initial value, rec is a list of rational functions in n, representing the coefficients of the recurrence, N is a ( usually) large positive integer, and w is a small positive integer (but at least nops(ini)) representing the "window size", and outputs the list consisting of the terms N-w+1 through N of that sequence starting at n=N-w+1 and ending at n=N. In other words, write a P-recursive analog of RecToSeqW(R,N,w). In particular,
PRecToSeqW(R,n,N,w)[w]
should give you the N-th term of the sequence.
Added Feb. 18, 2016: See the students' nice Solutions to the 8th homework assignment
Subject: hw#9
and an attachment
hw9FirstNameLastName.txt
Write a procedure
FindSecondAperyMiracle(F,k,n,N0,Max) ,
that finds a positive integer m ≤ Max (if it exists, otherwise RETURN FAIL), that has the property that if you multiply the n-th term of the sequence
anSeq:=PRS(R0,n,N):
(where R0=[[0$(ORDER-1),1], R[2]], and R=Z(F,k,n), in other words it is the sequence that Apéry and van der Poorten call a_n,
[except that instead of the initial conditions being [0,1] they take [0,AnotherInteger], but this only causes the constant
to be multiplied by an integer, and does not change the irrationality status]
while b_n is the original sequence of integers, given by PRS(R,n,N), and the sequence of approximations is then a_n/b_n )
by
lcm(1,...n)^m
you always get integers.
(Recall that the sequence starts at n=0 so the n-th term of the Apery sequence is RAseq(F,k,n,N0)[n+1])
What are
ope(n,N)
(in the same form as the output of SumTools[Hypergeometric][Zeilberger](F,n,k,N)[1])
is (under some conditions that are always true in our cases) asymptotically approximately
C(n)αn
for some very slowly-growing function, C(n) (e.g. polynomial) such that C(n+1)/C(n) goes to 1 as n goes to infinity,
where α is the largest root of the poynomial in N that is the leading coefficient in n of ope(n,N).
For example, if
ope(n,N)= n^2*(N-1)*(N-2) + 3*n*N^3 +N^4
then α=2. Write a procedure
FindAlpha(F,k,n)
That inputs an expression F involving binomial coefficients in the variables k and n and outputs the α (a certain algebraic number, for the most interesting cases for us, the larger root of a quadratic equation).
Hint: the command in Maple for the leading coefficient of a polynomial P of n is: lcoeff(P,n).
2*log(α)/(log(α)+m) .
Write a procedure
RigDel(F,k,n)
that finds the rigorous δ that would make you famous if it is bigger than 1.
What are
Added Feb. 22, 2016: See the students' nice Solutions to the 9th homework assignment
Subject: hw#10
and an attachment
hw10FirstNameLastName.txt
(and indicate whether it is OK to post)
Canon(C)
that inputs a cycle (a list of distinct numbers except the first and last entries that are the same) and outputs the same cycle, but with its smallest element appearing at the first entry. For example
Canon([5,3,6,2,5]);
should output [2,5,3,6,2] .
InfoC(L,n,N,K)
that inputs a Collatz-like rule L, phrased in terms of the symbol n, a positive integer N and a fairly large positive integer K, and returns FAIL if there exists an integer n1<=N whose orbit-length exceeds K, and otherwise returns the pair
[[champ,record],Per]
where champ is the integer <=N with the longest orbit, record is that record-length, and Per is the set of all periodic orbits written in canonical form. For example
Info([3*n+1,n/2],n,100,1000);
should return
[[97, 119], {[1, 4, 2, 1]}]
Info([c1*(n+4)/5,c2*(n+3)/5, c3*(n+2)/5, c4*(n+1)/5, c5*n/5],n,4000,10000);
for ALL
1 ≤ c1 ≤ 4 1 ≤ c2 ≤ 4 1 ≤ c3 ≤ 4 1 ≤ c4 ≤ 4 6 ≤ c5 ≤ 11
[Note added Feb. 25, 2016: if this takes too much time and space, restrict the range. Also it is wise not to allow c5=10, since this would obviously lead to FAIL.]
Added Feb. 29, 2016: See the students' nice Solutions to the 10th homework assignment
Subject: hw#11
and an attachment
hw11FirstNameLastName.txt
(and indicate whether it is OK to post)
What day of the week (according to our current calendar that was not yet used then) was Jesus' birthday? Your birthday? Dr. Z.'s birthday (July 2, 1950)?
PO3(c1,c2,c3,m)
that inputs integers c1, c2, c3 (NOT divisible by 3) and outputs all periodic orbits of length m for the Collatz-like rule
L=[c1*(n+2)/3,c2*(n+1)/3, c3*n/3]
Champ3(m)
that finds the (c1,c2,c3) with period of length m with the largest smallest element for
1 ≤ c1,c2 ≤ 2 4 ≤ c3 ≤ 7
and also returns that orbit.
What are
Champ3(2), Champ3(3), Champ3(4),Champ3(5)?
Added Feb. 29, 2016: See the students' nice Solutions to the 11th homework assignment
Subject: hw#12
and an attachment
hw12FirstNameLastName.txt
(and indicate whether it is OK to post)
Seq(f,z,N)
that inputs the same parameters as Inv(f,z,N) (and uses it), and outputs the list of the first N coefficients of the inverse function of f. For example
Seq(exp(z)-1,z,10);
should output
[1, -1/2, 1/3, -1/4, 1/5, -1/6, 1/7, -1/8, 1/9, -1/10]
Seq(z-z^k,z,100);
in the OEIS? (once you kick out the zeroes).
S_2(n):=1^2+2^2+ ... + n^2 ,
equals
n*(n+1)*(2*n+1)/6
Conjecture a formula for the decimal representation of S_2(10^k), in terms of k, and then use Maple to prove your conjecture.
JohnRogers1(P,n,b,Maxk)
that returns FAIL if all the b digits show up when k ranges from 1 to Maxk, and otherwise the set of missing digits.
[Hint: use convert(...,base, b) .]
JohnRogers(P,n,MaxB,Maxk)
that inputs all the bases, from 2 to MaxB, that have the John Rogers property.
What are the outputs to
JohnRogers(sum(i^r,i=1..n),n,20,15)
for r from 2 to 10?
Added March 7, 2016: See the students' nice Solutions to the 12th homework assignment
Inv2(P,x,y,N): inputs a pair of polynomials P=[f(x,y),g(x,y)] in the variables x and y, and a pos. integer N, outputs the beginning (up to degree N) of the inverse transformation
Subject: hw#13
and an attachment
hw13FirstNameLastName.txt
(and indicate whether it is OK to post)
Inv3(P,x,y,z,N)
that inputs a list, P, of lenght 3, [f(x,y,z),g(x,y,z), h(x,y,z)] and outputs the beginning (up to total degree N) of the inverse transformation (that consists of formal power series). Include a final step that applies procedure Comp(P,Q,x) to test that the output is indeed correct, or else return FAIL.
[Hint: First write a procedure Chop3(P,x,y,z,i);]
What are
Invk(P,x,N)
that inputs a list, P, of length, k, say, a list x of variables (of the same length), say x=[x1,x2,.., xk], and the members of P are each polynomials in the variables [x1,..., xk], and outputs a list of length k that consists of the beginning (up to degree N) of the k components of the inverse transformation. What is
Invk([x1-x2^2-x3^2-x4^2-x5^2, x2-x1^2-x3^2-x4^2-x5^2, x3-x1^2-x2^2-x4^2-x5^2, x4-x1^2-x2^2-x3^2-x5^2,x5-x1^2-x2^2-x3^2-x4^2],[x1,x2,x3,x4,x5],5);
[Hint: First write a procedure
Chopk(P,x,i)
that inputs a polynomial in the list of variables x, and a positive integer i, and outputs the terms whose total degree is ≤ i (Hint-Squared: Use recursion)]
Added March 7, 2016: See the students' nice Solutions to the 13th homework assignment
[Written by Emily Kukura]
Subject: hw#14
and an attachment
hw14FirstNameLastName.txt
(and indicate whether it is OK to post)
RandElem(x,MaxC,Maxr)
that inputs a list of variables x, a large positive integer C, and a not-too-large (in applications) positive integer R, and first picks random 1 ≤ i ≠ j ≤ nops(x), then a random r between 1 and Maxr, then a random C between -MaxC and MaxC, and outputs the pair of transformations
[Elem(x,C,i,j,r), Elem(x,-C,i,j,r)]
(that are inverses of each other)
RandEpair(x,MaxC,Maxr,T)
and outputs a pair of transformations, inverses of each other.
Hint: Use Comp(P,Q,x) many times, in both directions.
More detailed hint (Added March 12, 2016): Prepare the list of T pairs of elementary transformations and their inverses, let'd denote them like this (in humanese)
[[E1,E1^(-1)], ..., [ET,ET^(-1)]
then the forward transformation is
E1E2 ... ET
and its inverse is
ET^(-1) ... E1^(-1)
Calling the output pair P, check that indeed both Comp(P[1],P[2],x) and Comp(P[2],P[1],x) are the identity mapping x.
Invk(P[1],x,N)=P[2]
where N is sufficiently large, for several random outputs of P:=RandEpair([x,y,z,w],10,5,4);
[Note: this is a first step in solving a Battleship puzzle]
Write a procedure
ZeroOneMatrices(RowSums,ColumnSums)
that inputs lists of non-negative integers RowSums, ColumnSums, of lengtha m, and n, say (i.e. nops(RowSums)=m, nops(ColumnSums)=n) and such that they have the same sum (k, say, if not it returns FAIL), and outputs the set of m by n 0-1 matrices (given as lists-of-lists) whose row sums are given by the list RowSums and whose column-sums are given by the list ColumnSums.
Hint: First write a procedure Vecs(n,k) that inputs positive integers n and k and outputs the set of 0-1 vectors (given as lists) of length n that add-up to k (or equivalently, have k 1's and n-k 0's. Use recursion. Then for the main procedure, also use recursion, the base case is with one row, and then finding all the legal options for the bottom row, and calling the same procedure, with modified RowSums and ColumnSums for each choice, and taking the union.
What is the set
ZeroOneMatrices([1,1,1,1],[1,1,1,1])?
Which of the following sequences are in the OEIS?
Added March 20, 2016: See the students' nice Solutions to the 14th homework assignment
C15.txt , Contains procedures
Subject: hw#15
and an attachment
hw15FirstNameLastName.txt
(and indicate whether it is OK to post)
JGbetter(N)
that implements the still unproved (byt absolutely certain) second formula in Jesus Guillera's homepage that used the PSLQ, and verify that indeed increasing N by one gives you five more decimal places.
Write a procedure
FindMachin(x,k)
that inputs x and outputs the only y such that
AT([x$k,y])=1.
What
FindMachin(1/5,4)?
BestMachin(k,N)
that tries out all x=1/r, from from 1 to N, and outputs the "best" Machin-like formula
AT([x$k,y])=1
with min(x,y) as small as possible.
Sum(A(n)*x^n/n!,n=0..infinity)=sec(x)+ tan(x)
Note that this implies that the limit of A(n)/(A(n-1)*n) as n goes to infinity is 2/Pi, since the radius of convergence of sec(x)+tan(x) is Pi/2 (why?)
Find a natural infinite power series that converges as slow as possible to π
[Remark: here is an example of an unnatural series
4*Sum((-1)^i/(2*i+1)+ Sum((-1)^j,j=0..10^1000000000), i=1..infinity)]
Added March 20, 2016: See the students' nice Solutions to the 15th homework assignment
Vecs(d,r): all vectors of length r whose sum is larger than 0 and ≤ d
GenPol(x,d,a): inputs a list of variables x, a degree d, and a symbol a outputs a generic polynomial of degree d with coeffices of the form a[.] followed by the set of coefficients
Subject: hw#16
and an attachment
hw16FirstNameLastName.txt
(and indicate whether it is OK to post)
FindTrans(m,n,x,y)
That inputs positive integers m and n, and outputs the set of polynomial transformations (possibly given symbolically)
(x,y) -> [P(x,y),Q(x,y)]
where the degree of P(x,y) is m, the degree of Q(x,m) is n, and the leading parts of P(x,y) and Q(x,y) are xm and xn respectively
[In other words, P(x,y)=xm + SomePolynomialOfDegree(<=m-1), Q(x,y)=xn + SomePolynomialOfDegree(<=n-1)],
whose Jacobian determinant is identically equal to 1.
What are FindTrans(2,1,x,y), FindTrans(3,2,x,y)?
ProveTameConj(M)
that rigorously proves that if m < n ≤ M, and n/m is NOT an integer, then there do not exist a polynomial transformation in two variables [P(x,y),Q(x,y)] where the degree of P(x,y) is m, and its leading part is xm, and the degree of Q(x,y) is n, and its leading part is xn. It should input true, or a counterexample.
What is the largest M for which your computer can do it in reasonable time?
[Note: ProveTameConj(∞) is (almost) a proof of the tame-generator conjecture that implies the Jacobian conjecture. To get a full proof, you have to consider (for the cases where m and n are not relatively prime), more general leading terms ]
[Hint: replace sin(x)^2 by y, then cos(x)^2 is 1-y. using the Maple command "limit", find the required limit for y of the form 1/m, where m is an integer. Find the pattern, and determine a symbolic expression, in terms of y, for that limit. Finally replace y by sin(x)^2 to get the answer].
Program bn(x) for numerical integer n and numerical floating point x, and verify that bn(x) is close to what you found above for large n. How fast (or slow) is the convergence?
[Hints: arctanh(z)=z+z^3/3+z^5/5+z^7/7+ ...; arctanh(x)+arctanh(y)=arctanh((x+y)/(1+x*y)); Maple knows how to evaluate the right side, and tanh(arcsinh(z)/2) simplifies to a certain algebraic expression in z, that you can either derive directly, using hyperbolic trig, or better still, doing identify(evalf( tanh(arcsinh(n)/2))) for n=2,3,4,5,6 and guessing the expression].
Added March 28, 2016: See the students' nice Solutions to the 16th homework assignment
Subject: hw#17
and an attachment
hw17FirstNameLastName.txt
(and indicate whether it is OK to post)
Guest co-Lecturer:Nathan Fox .
C18.txt , Contains procedures
NF(n): The n-th term of the Nathan Fox Sequence
Subject: hw#18
and an attachment
hw18FirstNameLastName.txt
(and indicate whether it is OK to post)
Added April 4, 2016: See the students' nice Solutions to the 18th homework assignment
SAW71(): The number of self-avoiding walks from 65 to 71 taken from OEIS sequence A001411
Subject: hw#19
and an attachment
hw19FirstNameLastName.txt
(and indicate whether it is OK to post)
PlotWalk(W)
that inputs a walk in the 2D square-lattice and outputs a picture of it.
RandSAW(n)
that inputs a positive integer n, and outputs a random self-avoiding walk with n steps, or FAIL if it gets stuck. It does not have to be guaranteed to be uniformly-at-random.
[Hint: At every step, find out the neighbors that are not yet visited, and pick one of them uniformly at random].
PlotRandSAW(n)
that plots a random self-avoiding walk
Added April 4, 2016: See the students' nice Solutions to the 19th homework assignment
Contains procedures
Subject: hw#20
and an attachment
hw20FirstNameLastName.txt
AllSATS(F,x,n)
that inputs a Boolean expression F in x[1], ..., x[n], and outputs the set of all vectors in {false,true}^n that satisfy the expression. For example
AllSATS(x[1] or x[2] ,x,2)
should output the set {[true,true],[true,false],[false,true]}
AveTime(n,r,K,HowMany)
that inputs positive integers n,r,and K, and outputs the average time it takes to run SAT(RCNF(x,n,r,K))
when it is execeuted HowMany times.
(Hint, use: time( SAT(RCNF(x,n,r,K))) HowMany times and take the average time)
TimePlotSAT(r,M,Maxn, HowMany)
that inputs positive integers r, M, Maxn, and HowMany, and outputs a plot of the average running time
of SAT(RCNF(x,n,r,M*n)) over HowMany runs
for n from 1 to Maxn.
What are the plots of
Added April 11, 2016: See the students' nice Solutions to the 20th homework assignment
Today we had a "field trip" to attend Zeev Rudnick's fascinating talk
Subject: hw#21
and an attachment
hw21FirstNameLastName.txt
Zeev(a,N)
that inputs an irrational number a, and a positive integer N and outputs the sorted list of all numbers of the form a*m2+n2 that are ≤ N, given as floating point numbers, use Digits=20 .
Rudnick(a,N)
that inputs an irrational number a, and an integer N, and outputs the quantity
δamin(N) defined in page 11 of Zeev Rudnick's talk. Confrim the claimed inequality for fairly large N, say N=10000, and N=20000.
GenSeq:=proc(f,x,N)
that inputs a rational function f in the variable x and a positive integer N, and outputs the sequence of Maclaurin coefficients (i.e. Taylor coefficients around x=0) from the coefficient of x to the coefficient of xN.
For example,
GenSeq(x/(1-x-x^2),x,100);
should give the first 100 Fibonacci numbers.
CheckLucas(L)
that inputs a sequence of positive integers, L, and outputs true iff the Lucas property
gcd(L[m],L[n])=L[gcd(m,n)]
holds for all 1 ≤ m < n ≤ N.
What are
GenSeq(x/(1-a*x-b*x^2),x,infinity);
for a and b relatively prime positive integers.
[Added April 8, 2018: the original statement (posted yesterday), erroneously, did not mention that a and b must be relatively prime. I thank Zeev Rudnick for making this correction, and he won 1 dollar].
Confirm empirically the asymptotic inequality, for the eighth moment of the Riemann Zeta function on p. 17 of Zeev Rudnick's talk.
[Warning, you have to take T fairly large to start getting small numbers (relatively to T), since the left side is supposed to be (assuming RH) about (log T)16 (see p.12 of Chris Hughes's talk)].
Added April 11, 2016: See the students' nice Solutions to the 21th homework assignment
Contains procedures
{1,3,-4} denotes x[1] AND x[3] AND (not x[4])
For example, SubCube({1,-3},3)={[1,0,0],[1,1,0]}.
For example, TF({{1,2}}) equals {[1,1,0],[1,1,1]}
Subject: hw#22
and an attachment
hw22FirstNameLastName.txt
ALSO, Please, HAVE in the first line
#FirstName LastName, HOMEWORK 22, OK (or NOT OK) to POST
HowManyPoints(n,r,K,L,t)
that inputs a positive integer n, a positive integer r, a positive integer K, and a large positive integer L, and a symbol t, and outputs the sum of
tnops(TF(RDNF(n,r,K))
when RDNF(n,r,K) is run L times. Note that the coefficient of t2n tells you how many out of these L random DNFs happen to be tautologies
What do you get from
Write a procedure
HowManyTaut(n,r,MaxK,L)
that for each K from 1 to MaxK runs RDNF(n,r,K) L times, finds the ratio of those that are tautologies and outputs the list, of length, MaxK, whose i-th entry is that ratio for running RDNF(n,r,K) L times.
Note: Of course, every time you run it you would different answers, since things are random, but if L is large enough you should close answers (by the law of large numbers)
What do you get from
Added April 18, 2016: See the students' nice Solutions to the 22nd homework assignment
Contains all the procedures of C22.txt (see Help22(); for a list) as well as the new procedures:
IsTb(f,n): Is f a tautology? Inputs a DNF (using our data structure) of n variables, a positive integer n, and outputs true or false followed by a positive integer k.
We use Inclusion and Exclusion and the Bonferroni inequalities. It exits with true and false as soon as it knows for sure (one way or another). It also outputs the exit "stage" k, indicating how soon it knew for sure whether it is a tautology or not. The hope is that often we can know for sure before doing the nops(f) steps.
Subject: hw#23
and an attachment
hw23FirstNameLastName.txt
ALSO, Please, HAVE in the first line
#FirstName LastName, HOMEWORK 23, OK (or NOT OK) to POST
GettingOut(n,r,K,L)
that calls RDNF(n,r,K) L times, and outputs a list, let's call it Data, of length K, such that for i from 1 to K, L[i] is the number of times the second output to IsTb(f,n), what is called k there, happens to be i. Of course the list, Data, should add-up to L. Also plot the histogram i->Data[i].
[Of course, since RDNF(n,r,K) is random, you would get different answers each time, but for large L you should be able to see the trend.]
What did you get for
In each case plot the corresponding histogram to see what is going on.
Using procedure
ZeroOneMatrices(RowSums,ColumnSums)
that you did in homework 14,
Write a program
SolveBattleship(RowSums,ColumnSums,SetOfAlreadyCovered Locations,NumberOfSubmarines,NumberOfDestoyers,NumberOfCruisers)
that solves any Battleship puzzle. Apply your program to solve
this puzzle, stolen from a recent New York Times magazine.
Added April 18, 2016: See the students' nice Solutions to the 23rd homework assignment
We first discussed the class group project, and here is some very rudimentary, Maple code written by Dr. Z.: C24.txt
[See Help(); for a list of the procedures, and the comments to them]
Subject: hw#24
and an attachment
hw24FirstNameLastName.txt
ALSO, Please, HAVE in the first line
#FirstName LastName, HOMEWORK 24, OK (or NOT OK) to POST
Franklin(L)
that inputs a partition into distinct parts (given as a decreasing list of positive integers) and outputs its image, under the Franklin mapping, if its exists, or else returns FAIL.
Write a procedure
DP(n)
that inputs a non-negative integer n, and outputs the set of partitions of n into distinct parts. For example, DP(4) should output {[4],[3,1]}.
CheckFranklin(n)
that verifies that for every member, L, of DP(n) for which Franklin(L) is not FAIL, Franklin(Franklin(L))=L. In other words, that the Franklin map is an involution on its domain.
BressoudZeilberger(L,j)
that inputs an integer partition L (written as a weakly-decreasing list of positive integers) and an integer j (that may be negative, zero, or positive), and outputs another such pair L1,j1, where j1 is either j+1 or j-1, as the case may be, and such that convert(L,`+`)+ a(j)=convert(L1,`+`)+ a(j1), where a(j)=(3j2 +j)/2 (as in the above B-Z paper).
Check that your program agrees with the example given in that paper.
Added April 25, 2016: See the students' nice Solutions to the 24th homework assignment
Contains procedures
p(n)=p(n-1)+p(n-2) +...- (-1)^j* ( p(n-j*(3*j+1)/2) + p(n-j*(3*j-1)/2) )+...
Subject: hw#25
and an attachment
hw25FirstNameLastName.txt
ALSO, Please, HAVE in the first line
#FirstName LastName, HOMEWORK 25, OK (or NOT OK) to POST
HRR(n)
That inputs a positive integer and computes p(n) using the famous Hardy-Ramanujan-Rademacher formula, cited, for example in the wikipedia entry on partitions
Hint: you first have to write a little procedure to compute Dedekind sums. You quit the summation as soon as the terms are way below one.
Use HRR(n), to write a procdure SeqHRR(N) that should output the same as SeqP(N) we did in class. What is faster? for large N? What is faster, p(10000) or HRR(10000)?
Write a procedure
RamanujanStyleMiracles(R,S,N)
that inputs positive integers R, S, and N, finds the set of all quadruples
[r,s,p1,j]
with r ≤ R, s ≤ S, such that the sequence A(r,s)(n), defined by the generating function
Sum(A(r,s)(n)*q^n,n=0..infinity)= mul(1+q^i,i=1..infinity)^r/(mul(1-q^i,i=1..infinity))^s
(conjecturally, using FindRC(L) with a list of N terms) seems to satisfy the congruence relation
A(r,s)(p1*n+j) == 0 (mod p1)
What is
RamanujanStyleMiracles(5,5,300)?
Added April 25, 2016: See Dr. Silviu Radu's very interesting message that pointed out to this interesting paper by Dennis Eichhorn and Ken Ono (an associate producer of the upcoming movie "The man who knew infinity")
Added April 25, 2016: See the students' nice Solutions to the 25th homework assignment
[Note: A few minor corrections and additions have been added after class.]
Contains procedures
((1+q)*(1+q^2)*...)^r/((1-q)*(1-q^2)*...)^s
and then conjectures Ramanujan-style congruences. Procedure written by John Chiarelli
For example, typing
GenPaper(3,3,1000,20);
produces the fully computer-generated article that contains 16 theorems.
Typing
GenPaper(2,7,2000,20);
produces the fully computer-generated article that contains 42 theorems.
Added April 28, 2016: It turns out that the r=0 case has already been studied by Matthew Boylan and Edinah Gnang and Dr. Z., see this masterpiece, and the Maple package BOYLAN, and the numerous output files in this webpage. But for r > 0 it is wide open. To that end Dr. Z. modified procedure GenPaper to write procedure
GenPaperG(R1,R2,S1,S2,N,N1)
that searches for Ramanujan-style congruences for R1 ≤ r ≤ R2, and S1 ≤ a ≤ S2, and outputs the first N1 terms of the associated integer sequence. The new version of C26.txt contains this new procedure.
Typing
GenPaperG(1,17,0,17,4000,24):
produces the fully computer-generated article that contains 620 theorems!
In fact, it was terminated, since it almost reached 1MB, and enough is enough.
Work on the class project to develop a Logic puzzle webbook inspired by the NP-hard Satisfiability problem.
[Note: A few minor corrections and additions have been added after class. In particular MS(n) now works correctly]
Contains procedures
Please email ShaloshBEkhad at gmail dot com a message with
Subject: hw#27
and an attachment
hw27FirstNameLastName.txt
ALSO, Please, HAVE in the first line
#FirstName LastName, HOMEWORK 27, OK (or NOT OK) to POST
Added May 2, 2016: See the students' nice Solutions to the 27th homework assignment
Guru Neil Sloane gave a great guest lecture
Added May 5, 2016: See the great class project