List of possible projects.

1. (Mike & Andy) Let $n\in {\bf Z}^+$. Prove that
   1. if $\phi(n)=n-1$ then $n$ is prime.
   2. if $n$ is even then $\phi(2n)=2\phi(n)$.
   3. if $n$ is odd then $\phi(2n)=\phi(n)$.
   (For a definition of the Euler $\phi$ function, see example 8.5 on page 366-7.)
2. (Jessica & Jonathan & Mike ) How many positive integers less than 1,000,000 are
   1. divisible by 2, 3, or 5?
   2. not divisible by 7, 11, or 13?
   3. divisible by 3 but not by 7?
3. (Derek & Jordi) Let $a, b, c\in {\bf Z}^+$ with $c=gcd(a,b)$. Prove that
   $$\phi(ab)\phi(c)=\phi(a)\phi(b)c$$
   .
4. Use generating functions to find the number of ways to make change for $1 using pennies, nickels, dimes, and quarters with
   1. no more than 10 pennies and no more than 10 nickels.
   2. no more than 10 coins.
   You may want to use Mathematica here, though you should be able to solve the problem without using a CAS.
5. (Mike & Andy) How many 10-digit telephone numbers use only the digits 1, 3, 5, and 7, with each digit appearing at least twice, or not at all.
6. Give a combinatorial interpretation of the coefficient of $x^r$ in the expansion of $(1+x+x^2+x^3+\dots )^n$. (Assume that both $n$ and $r$ are positive integers.) Use this interpretation to write down a formula for this coefficient. Now write the power series expansion of $(1+x+x^2+x^3+\dots )^n$.
7. (Jessica & Jonathan & Mike ) Determine the generating function for the number of partitions of $n\in {\bf N}$ where 1 occurs at most once, 2 occurs at most twice, 3 at most thrice, and in general, $k$ occurs at most $k$ times, for every $k\in {\bf Z}$.