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

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

Last Update: May 17, 2010.

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 PRIMES. We will learn how to tell whether any given integer is a prime in polynomial time (thanks to AKS), really understand the elementary proof of the Prime Number Theorem, and, who knows?, may be one of you will prove the Goldbach conjecture?

But the actual content is not that important, it is mastering the methodology of computer-generated and computer-assisted research that is so crucial for your future.

There are no prerequisites, and no previous programming knowledge is assumed. Also, very little overlap with previous years. The final projects for this class may lead to journal publications.

Added March 22, 2010: Pick a project ! (First draft due May 5, 2010, 11:59:59pm).

Added April 7, 2010: Read Kellen Myers translation of Rene Taton's tribute to Viggo Brun (1885-1978). One of the heroes of this course.

Diary and Homework

Programs done on Thurs., Jan. 21, 2010

Note that Kellen Myers has an even better implementation , and he calls them unaryadd(x,y) and unarymult(x,y) .

Homework for Thurs., Jan. 21, class (due Jan. 25, 2010)

  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.
  2. (For experts, optional for novices) Write programs Sub1 for subtraction and Div1 for division (outputting the quotient and remainder).
  3. (For experts only) Write (from scratch!) addition and multiplication programs for positive integers represented in binary, as a list of 0's and 1's (for example 5 is [1,0,1]).
  4. (For everyone) Read carefully, and understand, pages 225-230 (sections 1 and 2) of Norman Levinson's paper,

Programs done on Monday, Jan. 25, 2010

Homework for Monday, Jan. 25, class (due Jan. 28, 2010)

  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.
  2. (Optional for Novices, required for Experts) Write a program , IF(n), that inputs a positive integer, and outputs the prime-factorization p1k1p2k2p3k3 ... as a list of pairs [[p1,k1],[p2,k2],[p3,k3], ... ]. For example, IF(600); should output [[2,3],[3,1],[5,2]] . Compare your output with ifactor(N);
  3. (for everyone) Define π(n) to be nops(SA(x)); write a program that inputs a pos. integer N and outputs the list of π(n)/(n/log(n)) for i=1..N. Do you see a trend?
  4. Challenge( 5 dollars for the best entry): write a faster program for PrimeList(N) ; (Note: Brian Nakamura told me that the Sieve of Eratosthenes (SA(N) in our program) is pretty good for the first million primes, so try to use it!)
  5. (For everyone) Read (again!) carefully, and understand, pages 225-230 (sections 1 and 2) of Norman Levinson's paper.

Programs done on Thursday, Jan. 28, 2010

[Note: the lucky winner is Dennis Hou! He won five dollars!].

Homework for Thurs., Jan. 28, class (due Feb. 1, 2010)

  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. Hand-in (only!) two pages of random examples (that you made-up yourself).
  2. (For everyone) The Prime Number Theorem states that the number of primes < x is asymptotic to x/log(x) (i.e. their ratio goes to 1). Conjecture an order-of-magnitude asymptotics for the number of twin-prime pairs < x
  3. (For experts, optional for novices): Write a program that inputs positive integers N and k and outputs the set of all arithmetical progressions of length k consisting all of prime numbers ≤ N. Using the above program, write another program (of one line) that finds the number of such APs.
  4. (For everyone) Read (again!) carefully, and understand, pages 225-230 (sections 1 and 2) of Norman Levinson's paper. Also do a first reading of section 3 (p. 230-234).

Programs done on Monday, Feb. 1, 2010

Homework for Monday, Feb. 1, class (due Feb. 4, 2010)

  1. (For Novices only) Read and do all the examples, plus make up similar ones, in pages 90-120 of Frank Garvan's awesome Maple booklet. Hand-in (only!) two pages of random examples (that you made-up yourself).
  2. (For everyone): using the package numtheory, write a program that inputs a pos. integer n and outputs the sum of mobius(n) over all the divisors of n. Make a conjecture about these sums.
  3. (For experts, a big challenge for novices) [wording corrected Feb. 3, 2010, 5:48pm, thanks to Emilie Hogan]
    Using the solve command, and by setting up a system of N linear equations with the N unknowns a[i] (i=1...N), find numbers a[i]'s that satisfy the system of equations
    {a[1]=1,seq( add(a[d], d in divisors(n))=0,n=2..N)}:
    Can you conjecture an "explicit" form for the a[i]'s? Do the a[i]'s depend on N?
  4. (For experts, a big challenge for novices) Consider all 2n subsets of {1,2, ..., n}. Define a 2n by 2n matrix M labelled by subsets such that M[T,S]=1 if S is a subset of T, and 0 otherwise. Write a program that inputs a pos. integer N and outputs the inverse of that matrix. Can you conjecture a "closed-form" for the entries, let's call them N[T,S].
  5. (For everyone) Define A(n) to be the sum of mobius(i) for i &le n. Conjecture an asymptotic upper bound for |A(n)|
  6. (Mandatory for experts, optional for novices): Prove (rigorously!) the very weak inequality |A(n)|<=100000000 n0.9999999999
  7. (For everyone) Read (again!) carefully, and understand, section 3 (p. 230-234) of Levinson's beautiful article.

Programs done on Thursday, Feb. 4, 2010

Homework for Monday, Feb. 4, class (due Feb. 7, 2010)

  1. (For everyone (but failry challenging for novices)) Recall that the mobius function μ(n) (given in the numtheory package of Maple as mobius(n)) is defined as (-1)r if n is square-free and a product of r distinct primes, and 0 otherwise. Write a home-made program, mobius1(n) that looks at ifactors(n)[2], and first decides whether it is square-free. If it is not then return 0, if it is, then return (-1) to the power of the length of ifactors(n)[2].
  2. (For everyone) The analog of the Mobius function for sets is:

    μ(S) := (-1)|S|   ,

    where |S| is the number of elements of S. Write a program that inputs a set S and outputs the sum of μ(T) where the sum ranges over all subsets T of S (including S itself and the empty set). you may use the function powerset(S) in combinat); . What do you get? Can you make a conjecture? By human means prove that conjecture.

  3. Check Eq. (3.2) empirically by writing a program Check32(f,n,x), that inputs an expression f (representing a function of n), a symbol n, and a real number x, and outputs the difference between the left side and right side. Use the "int" command and the trunc command. Check it out for a few f's and make sure that you get 0. For example Check32(n^3,n,30); should give 0.
  4. Check Lemma 3.3., i.e. Eq. (3.7) by writing a program Check37(N) that finds the maximum of the absolute value of the left side of (3.7) and ln(x) for x between 1 and N, and the winning x.
  5. Check Lemma 3.4 empirically, by writing a program Check34(N), that finds the largest value of |(ψ(x)-&pi(x)ln(x))/(xln(ln x)/ln x))| for x between 1 and N, and the x where it is achieved.
  6. (For everyone) Read (again!) carefully, and understand, everthing up to the end of section 3 (p.234) of Levinson's beautiful article.

Programs done on Monday, Feb. 8, 2010

Homework for Monday, Feb. 8, class (due Feb. 11, 2010)

  1. A random sequence of {1,-1} of length n has the properties that Write a procedure RS1(L), that inputs a list of length n consisting of 1's and -1's and computes
  2. Write a program RS(N,K) that repeats RS1(RandSeq(N)) K times, and finds the minimum of all the a1's, the minimum of all the a2's, and the minimum of all the a3's.
  3. Compare RS1(KOZ(Mob(N))) and RS(nops(KOZ(Mob(N)),100) for N from 100 to 100000, incremented by 100.
  4. Another interesting "statistics" that a sequence (i.e. list), L[i] -1's and 1's has is the number of times that "I was not in the red", i.e. the number of i's such that L[1]+...+L[i] > 0 or L[1]+...+L[i]=0 and L[i]=-1. Write a program W(L) that computes this number for any such list L's of -1's and 1's.
  5. Write a program that AS(N,K,x) that inputs positive integers N and K, and a variable x, and generates K RandSeq(N), computes W(L) for each of these K random sequenecs, and adds up x^W(L).
  6. Compare notes with W(KOZ(Mob(N)) for various N's.

Programs done on Thursday, Feb. 11, 2010

Mandatory(!) Special Homework, due Feb. 14, 2010

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

  1. Use maple to find the polynomial g (as an expression in x and y, of degree 4 in x and degree 4 in y). [Hint, write a generic polynomial in two variables x,y, of degree 4 in each, with 25 undetermined coefficients, and use the solve command].
  2. Using, xmpale, do:
    plots[implicitplot](g,x=-6..6,y=-5..5,axes=none);
  3. print it out.
  4. Cut it out.
  5. Write inside it: "I love Experimental Math".
  6. Tape it on the door of Hill 704.

Homework for Thurs., Feb. 11, class (due Feb. 15, 2010)

  1. Write a program Check49Abstract(x) that takes an abitrary function F(x) (left as a symbolic function!), and defining G(x)=Sum(F(x/i),i=1..trunc(x)) (2.11), Checks Equation (4.9) of Levinson's paper for all arguments less than x.
  2. Defining R(x)=ψ(x)-x, check empirically Eq. (5.1) by writing a procedure Check51(X) that inputs a positive integer X, and outputs the maximum of the left side of (5.1) divided by x, amongst all x ≤ X. What is Check51(100)? Check51(1000)?, how far can you go with a reasonable amount of time?
  3. (Challenge!) Write a (numerical) procedure that inputs a real number ≥ 2 and outputs a floating-point approximation to S(y) as defined by (5.3) (p. 238).
    Hint: R(x)=psi(x)-x, and psi(x) is a piece-wise constant function that changes every time you encounter a prime-power. Break the interval of integration [2,y] into segments [2,3],[3,4],[4,5],[5,7],[7,8], ..., between two consecutive prime-powers and add-up all these integrals.
  4. Write a procedure Check57(x) that computes the largest ratio of the left-side of (5.7) divided by y, for y between 2 and x.
  5. Write a procedure L2(n) that computes Λ2(n) of (4.14). What is Λ2(1000)?
  6. Write a procedure Check513(x) that checks Eq. (5.13). It inputs a positive integer x, and find the largest K1 for y between 2 and x. (i.e. the left side minus the first term of the right side divided by ylog(y)).
  7. Read a first reading of the non-elementary, but nevertheless, beautiful proof of PNT, due to to Don Newman, as told by Don Zagier

Programs done on Monday, Feb. 15, 2010

Homework for Monday, Feb. 15, 2010 class (due Feb. 18, 2010)

  1. Write a program that inputs an expression f of t (defined for t ≥ 0) describing a bounded and locally integrable function, and computes
    g(z)=Int(f(t)*exp(-z*t),t=0..infinity)
    where z is a complex number with positive Real Part given in floating point. Experiment with f(t)=1/(1+t^2) and try to plot the real and imaginary parts of g(z).
  2. Write an experimental numerical program that inputs a function f(t) and real numbers a and b (a < b), and a positive integer K. It outputs an approximate location of its minimum in that interval, and the value as follows. Break-up the interval into K equal part, evaluate the function at the intermediate points (a,a+(b-a)/K,a+2(b-a)/K,..., b) look at the minimum of these, and then between the two neighbors, break the new (smaller) interval again, and keep doing it until you have located a very small interval where that minimum is located.
  3. Apply the above program to locate the first 10 zeroes of f(t):=abs(Zeta(1/2+I*t)).
  4. Plot abs(Zeta(x+I*t)) for various x's (≠ 1/2) and t between 0 and 100, and convince yourself empirically that RH is right.
  5. Read the wikipedia article on the Fermat primality test and translate into a Maple prorgram the pseudocode given there. Test it out.
  6. Read the wikipedia article on the Miller-Rabin probabilistic primality test and translate into a Maple prorgram the pseudocode given there. Test it out.
  7. ($5 award for the nicest proof!) Find the nicest proof (combinatorial if possible) to Fermat's little theorem that ap-a is divisible by p for every a and every prime integer p.

Programs done on Thursday, Feb. 18, 2010

Homework for Thursday, Feb. 18, 2010 (corrected Feb. 21, 20101) class (due Feb. 22, 2010)

  1. Check how good is IsPrime(n,k) by writing a program CheckInPrime(N,K,k) for N a large (but not too large) positive integer, picks at random an integer between 1 and N, let's call it i, and sees whether our IsPrime(i,k) agrees with Maple's built-in isprime(i)
    [Added Feb. 21, 2010 (9:01am): The original version of the question stupidly asked to look at IsPrime(ithprime(i),k) that is always true (there are no false negatives in the Miller-Rabin test). Many thanks to Asya Pritsker for pointing this out!]
    Do it for K times, and find out how many were false primes. After you write it, try out (Note: if things are too slow, you can make the first two inputs smaller).
  2. ($5 for the best entry) Write a Maple program that enters the date [x,y,z] in the American format Month/Day/Year (Gregorian calendar) and outputs the day of the week (1=Sunday, ..., 6=Friday, 0=Saturday).
  3. Write an algorithm for human mental math that computes the day of the week of a given date. master it carefully. There will be a contest, and the person who can do it fastest (in their head) for some randomly chosen dates, will win $5.
  4. Look up the "Extended Euclidean algorithm", and write a program Egcd(a,b) that inputs two positive integers a and b, and outputs the greatest common divisor, let's call it d, and two (not necessarily positive) integers, let's call them e and f such that
    e*a+f*b=d
    The output should be in the form d,[e,f]. For example Ecgd(3,2); should return : 1, [1,-1].
  5. Look up Euler's toitent function and write two programs ET1(a), ET2(a), both of which compute the Euler toitent function φ(a), as follows. Check that ET1(a)=ET2(a) for a between 1 and 10000.
  6. Read a first reading of the The Agrawal-Kayal-Saxena (AKS) masterpiece
  7. (Riddle) I overheard at a bookstore two people talking. One person says to the other: look at that book, it has a number in its title. I just noticed that the product of the ages of my three daughters equals to that number. All my daughters know how to read. Can you tell, for sure, the ages of my daughters? The other man replied, Yes, their ages are .... (but I didn't hear what he said), and the first man replied: "yes", you got it!
    Myself, being very smart, I figured out the ages of that man's daughters, even though I didn't hear what the other man said. Can you?

Programs done on Monday, Feb. 22, 2010

Homework for Monday, Feb. 22, 2010 class (due Feb. 25, 2010)

  1. Finish procedure AKS(n).
  2. Write a procedure FindAllPrimesAKS(M,N) that inputs pos. integers M and N ( M < N) and outputs the list of prime integers between M and N, that uses the procedure AKS(n) that you have just programmed.
  3. Write a procedure FindAllPrimesMR(M,N,k) that inputs pos. integers M and N ( M < N) and outputs the list of prime integers between M and N, that uses the procedure IsPrime(n,k) from feb18.txt.

  4. [Modified, Feb. 24, 2010, thanks to Kellen Myers, the previous inputs would take years]
    Run FindAllPrimesAKS(1000,1100), and FindAllPrimesAKS(1000,1100,3). Did you get the same output? How long did they each take?

Programs done on Thursday, Feb. 25, 2010

Homework for Monday, Feb. 25, 2010 class (due March 1, 2010)

  1. ($5 for the fasted entry in Maple(!)) Try to optimize AKS(n), without "cheating", i.e. without replacing any procedures or steps by probabilistic versions. Call it MyAKS(n). How much faster can you have it run?
    [Added March 1, 2010: congratulations to Josh Loftus for winnig the prize!]
  2. Read the first half of the proof of theorem 4.1 (up to end of page 4) masterpiece very carefully, and write it, by hand in your own words, spelling out everything.
  3. Write a Maple program Check43(N) that empirically checks Lemma 4.3 for all n from 2 to N. Make sure that Check43(100) returns true.
  4. Write a Maple program IsIntrospective(f,X,m,r,p) that inputs a polynomial expression f in the variable X, an integer m, and a prime number p, and outputs true iff m introspective for f(X). Check that all the first 100 primes numbers are introspective for X+a for all 1 ≤ a,r ≤p-1
  5. Write a Maple program AKSgp(n,p,r) that inputs a composite integer n, one of its prime divisors p, and an integer r relatively prime to n (and hence to p), and outputs the set of elements of the group G described in the last paragraph of page 4. It should return FAIL, if the conditions for n,p, and r, are not satisfied.

Programs done on Monday, March 1, 2010

Homework for March 1, 2010 class (due March 4, 2010)

  1. Finish up the homework that you didn't do last time. It is very important!
  2. ($5 for the fastest entry in Maple(!)) Try to optimize AKS(n), even on top of what Josh Loftus did (e.g. do the exponentiation (X+a)n by repeated squaring, and moding-out by n and by Xr-1 at each step of the squaring. Call it MyAKS(n). Compare the running times, by typing
    restart: read FileName: t0:=time(): {seq(MyAKS(n),n=1..10000)};time()-t0;
    and
    restart: read FileName: t0:=time(): {seq(AKS(n),n=1..10000)};time()-t0;
  3. For a pair of two fair (cubical, i.e. 6-faced) dice, the probability that the sum of the dots of the two faces that landed on top is 2 equals 1/36, that it is 3 equals, 2/36, that it is 4, equals 3/36, ..., that it is 11 equals 2/36, that it is 12 equals 1/36. Construct two other, non-standard, dice (with positive number of dots on each face, but you may have repeats) that would give the exact same probability distribution as the above-mentioned pair of fair dice, for the total number of dots on the top faces.
  4. (A chellenge!) Generalize the above by writing a Maple program, NSD(r,k) (for Non-Standard dice) that inputs two positive integers r and k, and outputs all r-tuples of non-standard k-faced dice that yield the same distribution as r standard k-faced dice (with 1,2,3, ..., k dots on the faces, and each face is equally likely to be on top).
    Note: the previous problem was NSD(2,6);
  5. One way to define the cyclotomic polynomial Cyc(n,t) is the largest-degree monic polynomial that divides tn-1. Write a program Cyc(n,t) that inputs a pos. integer n, and a variable t, and outputs the n-th cylotomic polynomial, by following the following steps
    1. Use Maple's factor to find the irreducible factors of tn-1.
    2. By loking at op(i,f) for i from 1 to nops(f) find the one with the largest degree, and make it monic.
    Compare your output with Maple's built-in command cyclotomic.
  6. Read carefully the continuation of the proof of the validity of the AKS algorithm (p.5). Try to understand every step, fill-in details, and rewrite it in your own words.

Programs done on Thursday, March 4, 2010

Homework for March 4, 2010 class (due March 8, 2010)

  1. (real challenge, I don't know the answer, $5 for best entry) Why is NewAKS(n) so much slower than AKS(n). It is supposed to be faster! In particular, NewAKS(271) seems to take for ever.
  2. (real challenge, I don't know the answer, $5 for best entry) Resurrect NewAKS(n) to be faster than AKS(n).
  3. Adapt the AKS(n) procedure to just output the integer r at the end of step 2, that is used subsequently. Is that sequence in Sloane?
  4. According to Kellen Myers, my method of producing the cylclotomic polynomials is not a good one. He is probably right. Write two different good programs, using different formulas/algorithms to generate the cylotomic polynomial (you can consult wikipedia or any source) and make sure that it coincides with the output of cylotomic(n,x) in the numtheory package of maple
  5. Write a Maple procedure that inputs a prime p and an integer r and outputs a polynomial h(x) that is an irreducible factor of cyclotomic(r,x) mod p.

Programs done on Monday, March 8, 2010

Homework for March 8, 2010 class (due March 11, 2010)

  1. By using the methodology of Gen(S,c) or otherwise, write a Maple program ScG(L,X,h,p) that inputs a positive integer L, a variable X, an irreducible polynomial h in the variable X mod p, and a prime p, and outputs the subgroup of Fp[X]/(h(X)) generated by by X+1,X+2, ..., X+L. Test your program for small primes p and L and h(X) an irreducible factor of cylcotomic(X,r) mod p for various r's.
  2. By mimicking the program IV(k,n), write a program, NuIV(k,n) that computes recusively the number of elements in IV(k,n). So replace union by adding etc. Check the program by verifying that NuIV(k,n)=nops(IV(k,n)) for k between 0 and 8 and n between 0 and 10.
  3. By using experimental mathematics, conjecture a closed-form expression for NuIV(k,n).
  4. Prove your conjecture (by induction or otherwise)
  5. (challenge, $5 to be divided). Find a combinatorial proof by establishing a bijection with a well-known problem (i.e. an even more well-known one).
    [Added March 11, 2010: Aron Samkoff and Kellen Myers shared the prize]

Programs done on Monday, March 8, 2010

Today we mainly finished up understanding the beautiful AKS proof. The little programming we did is contained in:

Homework for March 11, 2010 class (due March 22, 2010)

  1. Write a program AlmostPrimes(N,k) that inputs an integer N, and outputs all the integers less than or equal to N that are the product of at most k primes.
  2. Determine experimentally (empirically) an asymptotic formula for the number of almost k-primes < N
  3. Determine experimentally (empirically) an asymptotic formula (in n) for the number of solutions of a+b=2n, where a and b are almost k-primes
  4. Read, as carefully as you can Viggo Brun's classic paper on the Goldbach problem
  5. Write a Maple program N(Delta,D,x,aList,pList) that implelents the function in p.101 of Viggo Brun's paper.
  6. Have a good Spring Break. See you Monday, March 22, 2010.

Programs done on Monday, March 22, 2010

Today we mainly finished up understanding the beautiful AKS proof. The little programming we did is contained in:

Homework for March 22, 2010 class (due March 25, 2010)

  1. A permutation pi of {1,...n} is a derangement if for every i between 1 and n, pi[i] ≠ i . Write a program Der(n) that computes the number of derangements in two different ways using PIE(S,P) by defining S to be convert(permute(n),set) and P the list of sets of permutations whose i-th element is the set of permutations with pi[i]=i. (Note: this is a most inefficient way of doing it, but do it anyway).
  2. By looking at PIE, derive a quick formula for Der(n).
  3. What is the limit of Der(n)/n! ?
  4. Read carefully my three-page masterpiece
  5. Write a program, Bonfferoni(S,P,k), that checks the identity version of the Bonfferoni formula as descibed in Example 2 on p. 2. (Hint: The left-over is a sum over subsets of k-elements {i1, i2, ..., ik} of (-1)k times |S[i1] intersect S[i2]...intersect S[ik] intersect (S minus S[ik+1]) intersect (S minus S[ik+2])... intersect (S minus S[nops(P)])
  6. For a set T={i1,i2, ... ik}, let xT denote x[i1]* ...*x[ik]. The Bonferonni identity follows from the algebraic identity
    (1-x1)(1-x2) ...(1-xn)=Sum((-1)|T|xT, |T| < k)+ Sum((-1)|T|xT(1-x[max(T)+1])(1-x[max(T)+2])...(1-x[n)), |T|= k) .
    Write a program Bo(n) that tests this algebraic identity empirically for a pos. integer n.

Programs done on Thurs, March 25, 2010

Homework for March 25, 2010 class (due March 29, 2010)

  1. ($5) Find the factual mistake in my masterpiece (Hint: it is in the Speculations section).

  2. An implicant, denoted by [S,T], where S is a subset of T and T is a subset of {1, ...,n}, is the collection of all subsets of {1,...,n} that contain S and is a subset of T (i.e. the "interval" in the Boolean lattice between S and T). For example [{3,4},{3,4,7,8}] consists of the four sets {{3,4},{3,4,7},{3,4,8},{3,4,7,8}}. Write a Maple program: Implicant(S,T) that outputs that interval.

  3. (challenge!) A Boolean function, f, on n variables can be viewed as a collection of subsets of {1,2,..,n}. A prime-implicant (not to be confused with prime number) is an implicant that is containded in f, and is not contained in a larger implicant. Write a program PrimeImplicants(f,v,n) that inputs a "Boolean function" f (i.e. a collection of subsets of {1,...,n}, a member v in f, and outputs all prime-implicants containing v. (Note: this is always non-empty, but may-be the singelton {v}, in case v is not part of a larger implicant.

  4. (challenge!) Write a program, QM(f,n) that "simplifies" a Boolean function f (given as above) and outputs a collection of prime-implicants whose union is f. For example SB({{1},{2},{1,2}}) should return {[{1},{1,2}],[{2},{1,2}]}. You should do it "greedily" by first picking members of f that have only one prime-implicant, and removing the members of that prime -mplicant, getting a smaller f. When you run out of such members of f, pick members of f that have a unique largest prime-implicant, and choose that prime-implicant in the constructed collection of prime-implicants, and remove all their members. Finally, when you are left with the reduced f, where each member has several maximal-size prime-implicants, choose any at random, until you cover everything. If you succeeded you (essentially) programmed the Quine-McClusky algorithm. It is equivalent to expressing a set of vertices of the n-dimensional unit cube as a union of "walls" of various dimensions, as economically as possible.

Programs done on Thurs, March 29, 2010

Special Homework for March 29, 2010 class (due March 30, 2010)

Usual Homework for March 29, 2010 class (due April 5, 2010)

  1. Using the description in my masterpiece, write a procedure BrunSieve to construct the BrunSieve(k,N) first naively, and then, if possible cleverly.

April 1,2010

We had a visiting lecture by the famous Professor Andrew Baxter.

Prof. Baxter's Homework for April 1, 2010 class (due April 8, 2010)

  1. Write a procedure that uses tubeplot to plot the (p,q)-torus knot for a given p and q, using the parameterization given at: wikpedia's page on Torus knot
  2. Use textplot and the DrawYoung program we wrote in class to draw Young Tableaux, as illustrated at wikipedia's page on Young tableaux
  3. Use the DrawYoung program as a guide to write a procedure to draw 3-D Young Diagrams for Plane Partitions (use the cube command in plottools). See an example here.

Programs done on Monday, April 5, 2010

Homework for April 5, 2010 class (due April 8, 2010)

  1. (Really easy!) The procedure we did in class, BrunSieve(k,N), with k a pos. integer (number of properties) and N a weakly decreasing set of integers N=[N1, ..., Nr] only outputs the subsets of {1,...,k}, {i1,i2, ..., ir}, with k ≥ i1 > i2 > ... > ir ≥ 1 with i1 ≤ N1, i2 ≤ N2, ..., ir ≤ Nr. Using this as a subroutine, write a Maple program FullBrunSieve(k,N) that outputs all subsets (including the crucial empty set) with ≤ r elements, such that if it is written {i[1],i[2], ..., i[s]} with s ≤ r and k ≥ i[1] > i[2] > i[3] > ... > i[s] ≥ 1 we have i[1] ≤ N1, ..., i[s] ≤ Ns .
  2. Experiment with ApplySieve and convince yourself that if N1=N2,N3=N4, ..., N[n-1]=N[n] (n even) you get an upper sieve and with N2=N3,N3=N4, ..., N[n-1]=N[n] (n odd) you get a lower sieve.
  3. Write a procedure Check12(x,r) that inputs a real positive number x, and a pos. integer r, and computes both sides of Eq. (12) on p.114 of Viggo Brun's classic paper with D=1, and check empirically for all x &le 1000 and all r ≤ 10 that it is always true (provided that the condition m+2 > σ=1/p1+...+1/pr holds ).

Programs done on Thursday, April 8, 2010