SUMMER 2012 Assignment #3

Due June 06 by midnight.

1. Prove that m^2 = SUM( floor((m+k)/(2k+1)) PHI(2k+1)), k=0..m-1 ), 
   where PHI(k) is the Euler totient function.    

2. What are the Stern-Brocot fractions that approximate sqrt(2)?
   Determine the first 16 such fractions using Maple or Sage and
   show the absolute error for each fraction

3. Given a sequence of integers b[1],b[2],b[3],... define a
   transformed sequence of integers a[1],a[2],a[3],... by 

   a[n] = SUM( b[k]*floor(n/k), k=1..n )

   Find a formula for b[n] in terms of a[1],a[2],...,a[n].
   Your formula can be a sum, but it should not be a recursion.
   Mobius inversion may prove helpful at some point.

4. Use Chinese remaindering to find numbers x and y such that
   gcd(x+i,y+j) > 1 for all 0<=i<4 and 0<=j<4.
   NOTE: Chinese remaindering is for solving for x where
   x = a[i] mod n[i] for i=1..k, where the n[i]'s are
   relatively prime.  There is a command for it in Maple: chrem.