Math 640: EXPERIMENTAL MATHEMATICS Spring 2012 (Rutgers University) Webpage

http://sites.math.rutgers.edu/~zeilberg/math640_12.html

Last Update: May 6, 2012


Added May 6, 2012: See the students' FINAL PROJECTS

Added March 21, 2012: Pick a project
Ongoing contest: Contribute entries to the Compendium of Utterly Trivial Papers The person who contributes the most entries would get the prize "The Princeton Companion of Mathematics".
[Added April 30, 2012: unfortunately, they were no submissions by students, so no prize was awarded. But contributions from anyone to this important page are welcome!]
Another ongoing contest (starts Feb. 14, 2012) Contribute interesting new sequences to OEIS, stating that they were inspired by Dr. Z.'s 2012 ExpMath class. Send me the links, so that I can post them with due credit, in this page. The person with the most number of contributions, would get a copy of the first edition of Sloane's "handbook" signed by Neil Sloane!

Description

Experimental Mathematics used to be considered an oxymoron, but the future of mathematics is in that direction. In addition to learning the philosophy and methodology of this budding field, students will become computer-algebra wizards, and that should be very helpful in whatever mathematical specialty they are doing (or will do) research in.

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.

Diary and Homework

Programs done on Thurs., Jan. 19, 2012

Homework for Thurs., Jan. 19, class (due Sunday Jan. 22, 10:00pm)

All homework should be uploaded to the secret directory that you gave me, as file hw1.txt
  1. (For Novices only) Read and do all the examples, plus make up similar ones, in the first 30 pages of Frank Garvan's awesome Maple booklet, available in the secret url that I gave you.
  2. (Mandatory for experts, highly recommended for novices) Let f(n) be the number of ways of writing the pos. integer n only using 1,2, or 3, where you can use them as many times as you want and order does matter, so 1+1+2 is NOT the same as 1+2+1. For example 3=3,1+2,2+1,1+1+1, so f(3)=4. Write a Maple procedure that inputs n and outputs f(n). Find out whether it is in the OEIS.
  3. (Mandatory for experts, recommended for novices) Let f(a,b) be the number of ways of walking from the corner of 0th St. and 0th Ave to the corner of ath St. and bth Ave., in the so-called Manhattan lattice, where you walk positively (in the direction of increasing streets and avenues). Write a Maple procedure to find f(a,b). Is the sequence f(n,n) in the OEIS?
  4. (Mandatory for experts, recommended for novices) Let g(a,b) be like f(a,b) above but in addition you can walk on "Broadway" that joins (0,0),(1,1),(2,2) etc. . Write a Maple procedure to find g(a,b). Is the sequence {g(n,n)} in the OEIS?
  5. (Mandatory for experts, recommended for novices) Let h(a,b) be like f(a,b) above but in addition you can walk diagonally from (a,b) to (a+1,b+1) in addition to (a+1,b) and (a,b+1). Write a Maple procedure to find h(a,b). Is the sequence {h(n,n)} in the OEIS?
  6. Read the first four pages of Dr. Z.'s crash course on enumerative combinatorics
  7. Become a registered user in the OEIS by clicking here, so you would be able to submit new (and interesting!) sequences to OEIS.
  8. [5 dollars to be divided among those who get it right, please no peeking in the internet!]. Let
    M(n)=add(mobius(i),i=1..n), where mobius(n)=0 if n is divisible by a square, 1, if it is a product of an even number of distinct primes, and -1, if it is a product of an odd number of prime numbers. Prove, or find a counterexample, to the plausible conjecture, that we verified in class for n up to 2000, that |M(n)| ≤ n1/2 .


    Added Jan. 23, 2012: tricked you! This was known as the Mertens conjecture, famously disproved by Andrew Odlyzko and te Riele, see this masterpiece of exposition. The slightly weaker statement that for every ε there is an N(ε) such that |M(n)| ≤ n1/2+ε for n ≥ N(ε) is equivalent to a million dollar problem

    Added Jan. 30, 2012: Here is Yusra Naqui's answers


Programs done on Monday, Jan. 23, 2012

Homework for Monday, Jan. 23, class (due Sunday Jan. 29, 10:00pm)

All homework should be uploaded to the secret directory that you gave me, as file hw2.txt
  1. (For Novices only) Read and do all the examples, plus make up similar ones, in pages 30-60 of Frank Garvan's awesome Maple booklet, available in the secret url that I gave you. Reproduce some sample examples.
  2. (For Experts, optional for Novices) Generalize the Collatz problem as follows. Write a procedure GC(x,L,n) that inputs such that if n=1 mod m then CG(x,L,n) is L1(n), if n=2 mod m then CG(x,L,n) is L2(n), ... if n=0 mod m then GC(x,L,n) is Lm(n). For example GC(x,[3*x+1,x/2],n) gives the same output as C(n) of file C2.txt . Adapt file C2.txt to handle this more general scenario.
  3. (For Experts, optional for Novices) By focusing on lists L whose entries are of the form a*x+b, with a and b rational, and such that it always maps positive integers to positive integers, experiment with other Collatz type rules, and formulate analogs of the 3x+1 conjecture.
  4. (For Experts, optional for Novices) For example, what happens if L=[(x-1)/3,(x-2)/3,4*x/3] ?
  5. (For Experts, highly recommended for Novices) In the Calkin-Wilf construction, write a procedure Parent(x), that inputs a positive rational number and outputs its (unique!) parent. For example Parent(1/2) should give 1.
  6. (For Experts, recommended for Novices) Write a procedure kCousins(x,k) that inputs a fraction x and a positive integer k and outputs the list in order, from left to right, of all the k-th degree cousins of x, which means that they have the same (great)k-1-grandparent but not the same (great)k-2-grandparent. (Note the list may be empty, 1/2 does not have any first-cousins (neither do Abel or Cain for that matter).
  7. [5 dollars to be divided amongst those who can do it without peeking at the internet (or any other media, e.g. paper)] Let [w[0],w[1],w[2],w[3], ....] (=[1,2,1,3, ...] be the Calkin-Wilf sequence of integers (i.e. such that w[0]/w[1], w[1]/w[2], ... gives the Calkin-Wilf recounting of the rationals), find a nice formula for the generating function
    Σn=0 w[n]xn

Added Jan. 30, 2012: See Kristen Lew's answers and Pat Devlin's answers

Programs done on Thurs. Jan. 26, 2012

Homework for Thurs., Jan. 26, class (due Sunday Jan. 29, 10:00pm)

All homework should be uploaded to the secret directory that you gave me, as file hw3.txt
  1. (For Novices only) Read and do all the examples, plus make up similar ones, in pages 60-90 of Frank Garvan's awesome Maple booklet, available in the secret url that I gave you. Reproduce some sample examples.
  2. (For Everyone) Modify procedure GuessPol(L,x) to make it more efficient, by only forming the first d+1 equations rather than the nops(L) equations, and then have the computer check that plugging-in x=d+2, x=d+3, ..., x=nops(L) into P(x) gives L[x], and returns FAIL otherwise.
  3. (For Everyone, challenging for Novices) Write a procedure GuessRat1(L,x,d1,d2) that inputs a list L of size larger than d1+d2+4 (it should return FAIL if the list L is not long enough), a variable name x, and non-neg. integers d1 and d2 and tries to find a rational function R(x)=P(x)/Q(x) where P(x) is a polynomial of degree d1, and Q(x) is a polynomial of degree d2, such that R(x)=L[x] for all x between 1 and nops(L). Test it for random example like
    [seq(i^2/(i^2+3),i=1..20)]
  4. (For Everyone, challenging for Novices) Using GuessRat1(L,x,d1,d2), write a procedure, GuessRat(L,x) that tries to find a rational function as above with d1+d2 as small as possible and d1+d2+4 ≤ nops(L), and returns FAIL if none is found. Test it for random example like
    [seq(i^3/(i^5+3),i=1..20)]
  5. (For Everyone, challenging for Novices) Write a Maple procedure FF(x,k) that inputs a number of variable x, and a non-neg. integer k and outputs the falling factorial of degree k Pk(x):=x(x-1) .... (x-k+1).
  6. (Human mathematics, for everyone) Prove by human means that Pk(x+1)-Pk(x)=kPk-1(x). Use this to find a "discrete Taylor" expansion for an arbitrary polynomial using the "discrete derivative" ΔF(x):=F(x+1)-F(x).
  7. (For Experts, recommended for Novices) Using the above, and procedure Di(L), write a possibly more efficient version of GuessPol(L,x). Call it BetterGuessPol(L,x). Compare the performance, by using time(); for sample lists gotten from polynomials of high degree (say above 60).

Added Jan. 30, 2012: See John Kim's answers and Pat Devlin's answers

Programs done on Monday Jan. 30, 2012

Homework for Monday, Jan. 30, 2012 class (due Sunday Feb. 5, 2012 10:00pm)

All homework (for this assignment alone) should be uploaded to the secret directory that you gave me, as file hw4.txt
  1. (For Novices only) Read and do all the examples, plus make up similar ones, from page 90 to the end, of Frank Garvan's awesome Maple booklet, available in the secret url that I gave you. Reproduce some sample examples.
  2. (For everyone) Using NGF(L,a) of C4.txt or GuessPol(L,a) from C3.txt, for G(a,b) (a ≥ b) for b=0,1,2,3,4,5, use human pattern-recognition to conjecture an explicit expression for G(a,b). (Hint, you will have to shift it to start at b). Having conjectured it, use Maple to prove it rigorously (by using induction on a+b)
  3. (For everyone) Modify G(a,b) and write a procedure Gk(k,a,b) that counts the number of ways of walking from [0,0] to [a,b] with positive unit steps, always staying in the region a-b ≥ -k. Conjecture, and then prove explicit expressions for Gk(1,a,b), and, if possible, Gk(2,a,b)
  4. (For everyone) Modify G(a,b) and write a procedure Gk1k2(k1,k2,a,b) that counts the number of ways of walking from [0,0] to [a,b] with positive unit steps, always staying in the region -k1 ≤ a-b ≤ k2. Find out whether the sequences {Gk1k2(k,k,a,a), a=0,1,2,3, ...} for k=1,k=2,k=3 are in Sloane. Try to conjecture explicit expressions for Gk1k2(k,k,a,a), as a function of a for k=1,k=2,k=3.
  5. (For experts, recommended for novices) Write a procedure F3(a,b,c) to compute the number of ways of walking in 3D Manhattan from [0,0,0] to [a,b,c] using the unit steps [1,0,0],[0,1,0],[0,0,1]
  6. (For experts, challenge for novices) Write a procedure G3(a,b,c) to compute the number of ways of walking in 3D Manhattan from [0,0,0] to [a,b,c] using the unit steps [1,0,0],[0,1,0],[0,0,1] always staying in the region a ≥ b &ge c
  7. [Big Challenge!] Using GuessPol or NGF applied to
    [seq(G3(a1,b,c), a1=b..40)] for specific b and c such that b ≥ c ≥ 0, try to guess an explicit expression for G3(a,b,c) as a function of a,b,c. Having found it, use Maple to prove it rigorously by induction on a+b+c.

Programs done on Thurs. Feb. 2, 2012

Homework for Thurs., Feb. 2, 2012 class (due Sunday Feb. 5, 2012 10:00pm)

All homework (for this assignment alone) should be uploaded to the secret directory that you gave me, as file hw5.txt (please have one file per assignment, i.e. don't mix-up hw4.txt and hw5.txt).
  1. 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).

  2. [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 qi 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].

  3. It is well-known (and not too hard to see) that the number of partitions of n into at most m parts, usually denoted by pm(n), is the coefficient of qn in the Maclaurin expansion of
    1/((1-q)(1-q2) ... (1-qm))
    (In other words the above is the generating function
    pm(0) +pm(1)q+pm(2)q2+ ... + pm(n)qn + ... )
    Write a procedure pmn(m,n) that inputs a pos. integer m, and outputs a quasipolynomial of degree m and order lcm(1,..,m) that describes pm(n). Test your program for m=1,2,3,4,5. (Warning: Don't go too far!)
  4. Write a procedure F(m,x) that expresses trunc(x/m) as a quasi-polynomial in x of order m for integer x.

  5. Find the quasi-polynomial (in our format) that describes George Andrews' succinct expression for T(n) in George Andrews's cute 1979 Monthly Note.

  6. [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 .

  7. [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

Programs done on Monday Feb. 6, 2012

Homework for Monday, Feb. 6, 2012 class (due Sunday Feb. 12, 2012, 10:00pm)

All homework (for this assignment alone) should be uploaded to the secret directory that you gave me, as file hw6.txt
  1. Read pages of 1-11 of this masterpiece

  2. 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] .

  3. [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]]

  4. [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]]

  5. 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).

  6. [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 ...

  7. [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

  8. [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)


Added Feb. 13, 2012: See the nice solutions of Pat Devlin, John Kim, Kristen Lew, Ben Miles, Matthew Russell, Nathaniel Shar, Charles Wolf.

Programs done on Thurs. Feb. 9, 2012

Homework for Thurs., Feb. 9, class (due Sunday Feb. 12, 10:00pm)

All homework (for this assignment alone) should be uploaded to the secret directory that you gave me, as file hw7.txt
  1. Write a procedure Gsomosk(Ini,k,n): that outputs the n-th term of the Somos-k recurrence, where Somos-k is the natural k-th order analog of the Somos-4 recurrence (first think what it is).
    [Notes, as pointed out by Charles Wolff, k should equal nops(Ini), so it is redundant, but I like to keep it for readability]
  2. Find out, experimentally, for which k, Somos-k, with Ini=[1$k], seem to always produce integers.
  3. Find out, experimentally, for which k, Somos-k, with Ini=[x[1], ..., x[k]], seem to always produce Laurent polynomials (rational functions whose denominators are monomials)
  4. The total degree of a monomial x1a1 x2a2 x3a3 ... is a1+a2+a3+... a homogeneous polynomial of degree d is one for which each of its terms is a monomial of degree d. Adapt GenPol(X,d,a,co), to write a procedure GenHomPol(X,d,a,co) that yields a homog. polynomial of total degree d.
  5. Using GenHomPol(X,d,a,co), write a program GenNonHomPol(X,d,a,co) of total degree d (in other words one that is the sum of a homog. polynomials of total degree i for i=0...d)

Added Feb. 13, 2012: See the nice solutions of Pat Devlin, John Kim, Kristen Lew, Ben Miles, Matthew Russell, Nathaniel Shar.

Programs done on Monday, Feb. 13, 2012

Added April 9, 2012: See the nice solutions of Philip Benjamin, Patrick Devlin, John Kim, Yusra Naqvi, Matthew Russell, and Nathaniel Shar.

Programs done on Thurs., April 5, 2012

Today we started studying sequences enumerating integer partitions satisfying various conditions. Inspired by Euler's Odd=Distinct theorem and the Rogers-Ramanujan Identities.

Homework for Thrus. April 5, 2012 class (due Sunday April 8, 10:00pm)

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.

  1. 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.

  2. Using restart, and time(), find out how much faster is ParSeqBest(N) than ParSeq(N), for various N up to 10000.

  3. Write a procedure, ConjRC(N,K) that outputs the set 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)?

Added April 9, 2012: See the nice solutions of Philip Benjamin, Patrick Devlin, John Kim, Yusra Naqvi, Matthew Russell, and Nathaniel Shar.

Programs done on Monday, April 9, 2012

Today we studies John Conway's Look and Say sequence.

Homework for Monday April 9, 2012 class (due Sunday April 15, 10:00pm)

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.]

  1. CANCELLED!

  2. Using split(w1,w2), that returns true if and only if w1w2 splits into w1.w2, write a procedure

    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.

Programs done on Thursday, April 12, 2012

Today we used the Lagrange Inversion Formula to enumerate labeled rooted trees, and Cayley's method to enumerated rooted unlabeled trees.

Homework for Thurs. April 12, 2012 class (due Sunday April 15, 10:00pm)

All homework (for this assignment alone) should be uploaded to the secret directory that you gave me, as file hw23.txt

  1. Write a procedure PT() (PT for Periodic Table), that inputs nothing, and outputs, the set of Conway's 92 elements. Verify that indeed you got 92 of them.
    Hint: Start with [3], and keep applying SplitUp(L), of the previous homework assignment, that is based on the true/false procedure
    split(w1,w2)
    that you should use as a black box.


    Added April 13, 2012, 11:35am]: The statements of problems 2 and 3 are erroneous as stated, please ignore them, and do Matthew Russell's version right below

  2. Write a procedure Mat(), that inputs nothing, and outputs the 0-1 matrix such that entry (i,j) has a 1 if and only if the "molecule" (that may be an atom)
    JC1(w)
    applied to atom i, has atom j in it.

  3. By using the built-in linalg package (or LinearAlgebra) find the numerical estimate of Conway's constant, by finding the largest eignevalue of Mat().


    [Added April 13, 2012, 11:40am] Matthew Russell's correction:

    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).


  4. Using LIF(P,u,N), and exponential generatingfunctionolgy, write a procedure,
    RLT1(S,N),
    that inputs a set of positive integers S, and a positive integer N, and outputs the list of size N whose i-th entry is the number of rooted labeled trees on i vertices where each vertex either has outdegree 0 (a leaf) or an outdegree that belongs to S.

    Find RLT1({1},20), RLT1({1,2},20), RLT1({1,2,3},20), RLT1({1,3},20).

    Are any of these in Sloane?

  5. Using LIF(P,u,N), and exponential generatingfunctionolgy, write a procedure,
    RLT2(S,N) ,
    that inputs a set of positive integers S, and a positive integer N, and outputs the list of size N whose i-th entry is the number of rooted labeled trees on i vertices where each vertex either has outdegree 0 (a leaf) or an outdegree that DOES NOT belongs S.

    Find RLT2({1},20), RLT2({1,2},20), RLT2({1,2,3},20), RLT2({1,3},20).

    Are any of these in Sloane?

  6. Read and understand the section on Polya-Redfield theory (p. 10 and the first quarter of p. 11) in Dr. Z.'s crash course on enumerative combinatorics, that appeared in "Princeton Companion to Mathematics",(Timothy Gowers, ed.)

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

Stuff done on Monday, April 16, 2012

The first ten minutes of today's class were dedicated to describing a contest, to be the first to compute the smallest Perrin-false-prime (see the wiki entry on Perrin numbers). Congratulations to Neil J. Lutz who won 5 dollars for being the first to get the correct answer (271441 (=5212)). It was done in less than five minutes!

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.

Homework for Monday April 16, 2012 class (due Sunday April 22, 10:00pm)

All homework (for this assignment alone) should be uploaded to the secret directory that you gave me, as file hw24.txt

  1. Background:
    The Perrin sequence P(n) is defined by
    P(0)=3,P(1)=0,P(2)=2
    and for n ≥ 3, by the recurrence
    P(n)=P(n-2)+P(n-3)
    Perrin (and other people, e.g. E.B. Escott in 1909) proved that if n is prime, then P(n)/n must he an integer. Perrin and Escott wondered whether the converse is true. Escott believed that it was false, but did not find a counterexample. The first counterexample, n=271441, was found in 1982 by Adams and Shanks, and again, in 2012, in a few minutes of programming and a few seconds of computation, by Neil Lutz, and quite a few other people in today's class.

    (a) Find all such n less than one million.

    (b) By using the Matrix formula given in the wiki article, find P(2^20).

  2. Define the generalized Perrin sequence, PAB(A,B,n), by

    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.


    Added 9:40am, April 20, 2012: John C. Miller offers the following $5 challenge to the FIRST person to answer the following question:

    "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.


  3. Write a procedure Mul(P,Q) that inputs two permutations (written as lists) of the same lengths and outputs their product. For example,
    Mul([2,3,1,4],[2,1,4,3]);
    should output
    [1,4,2,3]

  4. Write a procedure Gp(S) that inputs a set of permutations of the same length (output FAIL if S is not a set or it is not a set of lists of the same length, etc.) and outputs the set of all permutations that belong to the group generated by the members of S. (Don't forget the identity permutation!). For example
    Gp({[2,1]});
    should output
    {[1,2],[2,1]}   .
    and
    Gp({[2,1,3,4],[1,2,4,3]});
    should output
    {[1,2,3,4],[2,1,3,4],[1,2,4,3],[2,1,4,3]}   .

  5. Find the subgroup of S6 generated by the three rotations (about the x,y, and z axes) of a cube. Using Nathaniel Shar's suggestion, let's stick to the usual convention:

    Front: 1 ; Back: 6; Left:3; Right: 4; Bottom:2; Top=5.

  6. Write a procedure PermToCyc(P) that inputs a permutation P and outputs its cycle structre, as a set of cycles, with the convention that the smallest entry of the cycle is written first. For example
    PermToCyc([3,5,6,4,2,1]);
    should output
    {[1,3,6],[2,5],[4]} .

  7. Write a procedure Polya(G,c) that inputs a subgroup of the symmetric group Sn, G, and outputs the number of ways to color a combinatorial structure on n vertices with c colors, whose group of symmetry happens to be G.

    For example

    Polya({[1,2],[2,1]},c);
    should output
    (c^2+c)/2

  8. Find a polynomial expression, CC(c), for the number of ways of coloring a cube with c colors, where two colorings are considered the same if one can be gotten from the other by a sequence of rotations as above. Is the sequence

    [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.

Programs done on Thursday, April 19, 2012

Today we did "brute-force" counting of labeled connected graphs, and labeled trees, as well as much faster ways using generatingfunctionology. In the homework students will be asked to extend the brute-force approach to enumerate unlabeled graphs and trees.

Homework for Thursday April 19, 2012 class (due Sunday April 22, 10:00pm)

All homework (for this assignment alone) should be uploaded to the secret directory that you gave me, as file hw25.txt


REMINDER: Final projects are due May 4, 2012, 23:59. Please put them in the secret url directory where your homework resides, and please indicate whether you give permission to post it.
  1. Find your facebook distance to Dr. Z. (=1+ your facebook distance to Ian Page)

  2. Recall that a labeled tree on {1, ...,n} is a connected labeled graph on {1, ...,n} with exactly n-1 edges. Generalize NuLabTreesSlow(N), to write a procedure
    NuLabAlmostTreesSlow(N,a)
    that inputs a pos. integer N, and a non-neg. integer, a, and outputs the list consisting of the number of labeled connected graph on {1, ..., n} with exactly n-1+a edges, for n=1,2, ..., N.
    [In particular
    NuLabAlmostTreesSlow(N,0);
    should output the same as
    NuLabTreesSlow(N);   ]

  3. By using
    WtCCSeqFast(N,y):
    (that outputs a list whose n-th entry is a polynomials of degree n(n-1)/2 in y, for n=1..N )
    and extracting the coefficient of the right power of y, write a procedure
    NuLabAlmostTreesFast(N,a);
    that gives you the same output as NuLabAlmostTreesSlow(N,a), but much faster.

  4. By taking N=20, find out for which a is the sequence
    NuLabAlmostTreesFast(20,a);
    in Sloane?

  5. Write a procedure
    Image(G,n,pi)
    that inputs a simple labeled graph G (in our notation) of {1, ...,n}, a pos. integer n, and a permutation pi of {1, ...,n} and outputs the image under pi, in other words, the graph where label i goes to label pi[i] for i=1,2, ,... n.

  6. By starting out with the output of ConG(n), and using combinat's function "permute(n)", write a procedure

    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?

  7. Do the analogous things for unlabeled trees, and see whether you get Neil Sloane's favorite sequence, A000055.

  8. Do the analogous things for almost trees. For which a's are the sequences
    "number of unlabeled connected graphs with n vertices and n-1+a edges"
    in Sloane?

Added April 23, 2012: See the nice solutions of John Kim, Kristen Lew, John Miller, Matthew Russell, Yusra Naqvi, and Nathaniel Shar.

Programs done on Monday, April 23, 2012

Today we implemented the basics of Polya theory.

Homework for Monday April 23, 2012 class (due Sunday April 29, 10:00pm)

All homework (for this assignment alone) should be uploaded to the secret directory that you gave me, as file hw26.txt


FIRST REMINDER: Final projects are due May 4, 2012, 23:59. Please put them in the secret url directory where your homework resides, and please indicate whether you give permission to post it.
SECOND REMINDER: Please enter all your contributions to the OEIS contest in the secret directory, by April 29, 10:00pm, in the file MyOEIS.txt, with links to the actual sequences. The grand prize (for the person with the largest number of contributions) will be given the last day of classes, April 30, 2012.
  1. How many necklaces are there with 15 beads colored Red, 23 beads colored Blue, and 12 beads colored Green?

  2. In how many ways can you color the faces of a cube (up to rotational symmetry) with 3 faces colored Red, 2 faces colored Blue, and one face colored Green?

Added April 30, 2012: See the nice solutions of Patrick Devlin, John Kim, Kristen Lew, Matthew Russell, Yusra Naqvi, and Nathaniel Shar.

Programs done on Thursday, April 26, 2012

Today we continued to implement Polya theory.

Homework for Thursday April 26, 2012 class (due Sunday April 29, 10:00pm)

All homework (for this assignment alone) should be uploaded to the secret directory that you gave me, as file hw27.txt

  1. Finish Procedure
    SSe(Se,N)
    that we didn't have a chance to do in class.

  2. Find as many sets Se (that contain 0) for which
    SSe(Se,20)
    is in Sloane.

Added April 30, 2012: See the nice solutions of John Kim, Kristen Lew, Matthew Russell, Yusra Naqvi, and Nathaniel Shar.

Stuff and Programs done on Monday, April 30, 2012

Today, was the last class of this wonderful course. First we announced the winners of the OEIS contest. These were Patrick Devlin and Matthew Russell, that each contributed 27 sequences to the OEIS, and they each won a rare copy of the first edition of the OEIS, that was called "Handbook of Integer Sequences". Neil Sloane kindly agreed to sign them.

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:

REMINDER: Final projects are due May 4, 2012, 23:59. Please put them in the secret url directory where your homework resides, and please indicate whether you give permission to post it.

OPTIONAL challenges for Monday April 30, 2012 class

No due date! (open until the prize is claimed)

  1. ($25) We mentioned in class (you prove it!) that the losing positions (alias the positions where the Grundy function is 0) can be written as
    [trunc(phi*n),trunc(phi*n)+n]
    where phi is the Golden Ratio (1+sqrt(5))/2. Find an analogous characterization (that should be much faster than using the recurrence) for the positions where the Grundy function evaluates to 1.

  2. ($30) ditto for the positions where the Grundy function evaluates to 2.

  3. ($35) ditto for the positions where the Grundy function evaluates to 3.

  4. ($100) find a fast way (much faster than our program GW(a,b)) to compute the value of the Grundy function for position [a,b]

Added May 6, 2012: See the students' FINAL PROJECTS
Added May 14, 2012: Here are the students' evaluations.
Dr. Z.'s teaching page