Information about Project
In addition to homework you will be required to hand in a research/scholarship/computing projects. Projects with a nontrivial writing component may be used to satisfy the Mathematics Upper Division Writing Requirement. The project should be handed in final form by 04/17. You need to make your selection and also inform me of it (in writing) by 02/28. Here is a list of suggestions for your projects:
 Discuss the existence, number, etc of nonnegative solutions of a
diophantine equation
ax+by=n wherea,b,n are positive, (a,b )=1. For instance Show that whenever
n≥(a1)(b1) then there always are nonnegative solutions.  Show that if
n=(a1)(b1)1 then there are no nonnegative solutions.  For how many nonnegative integers
n<(a1)(b1)1 does there exist a nonnegative solution to the above equation?  Write a program to find all
n for which the above equation has nonnegative solutions.
 Show that whenever
 Give estimates for the number of bit operations needed to
compute each of the following:

n! 
n choosek  Find the binary expansion of a number given its decimal expansion.

 Write a program to explore the following statements. For
those you believe true try to provide a proof!
 If
p_{1} ,p_{2} , ... ,p_{t} are primes not exceedingn thenp_{1}p_{2}...p_{t} ≤4^{n}.  The
n th prime numberp_{n} is smaller than 2^{2n1}.  The
n th prime numberp_{n} is smaller or equal than 2^{n}.
 If
 Fermat numbers are numbers of the form
F_{n}=2^{2n}+1 , for positive integersn . Find the last 2 digits of a Fermat number
F_{n} in its decimal expansion.  Estimate the number of decimal digits in the Fermat number
F_{n} .  What is the the gcd of
F_{n} andn ?
Show that ( F_{n} ,F_{m} )=1, for distinct positive integersn andm .  Find the last 2 digits of a Fermat number
 Write a program that finds all twin primes less than 20,000. Hardy and Littlewood
conjectured that the number of twin primes not exceeding
n is asymptotic toC n/(ln n)^{2} for a constantC , approximately equal to 0.66016. Determine how accurate this asymptotic formula is for values ofn as large as you can compute.  Prove that unique factorization holds in Z+Z[i] (where i is the imaginary unit). Describe an analogue of the Euclidean algorithm in this context. What happens for numbers of type Z+Z√5?
 Show that if
p is a prime of the form4k+3 andq=2p+1 is prime, thenq divides the Mersenne number M_{p}=2^{p}1. (Hint: use Legendre symbols).  Derive an explicit formula that gives the day of the week of any
day of any given year in the Julian or the Gregorian calendars. Use these formulas
to find the day of the week of the following important dates
(Hint: Use the Julian calendar before September 3, 1752 and the
Gregorian calendar after that date):
 October 12, 1492 (Columbus sights land in the Caribbean)
 July 4, 1776 (US Declaration of Independence)
 March 30, 1867 (US buys Alaska from Russia)
 July 20, 1969 (First man on the moon)

A Carmichael number is an absolute pseudoprime
n , that is a numbern such thata^{n1}≅1 (mod n) for all positive integersa such that(a,n)=1 . Show that if
n is a Carmichael number then it is squarefree.  Show that if
n=p_{1}p_{2}...p_{n} is a product of distinct primes such thatp_{i}1n1 for alli , thenn is a Carmichael number. Use this to show that 564651361 is a Carmichael number. Can you write a program to find other Carmichael numbers?  Find as many Charmichael numbers of the form
(6m+1)(12m+1)(18m+1) as you can.
 Show that if
 An integer
n is called highly composite if τ(n )= τ(m ) for all integersm <n . Find all highly composite numbers not exceeding 10,000.  Suppose that a new Stony Brook ID will be implemented where
each student gets assigned a 10 digit code word
x_{1} x_{2}...x_{10} . Each digit is a decimal digit, and the valid codes are those satisfying the congruences∑x_{i} ≅ ∑ix_{i} ≅ ∑i^{2}x_{i} ≅ ∑i^{3}x_{i} ≅ 0 (mod 11) . How many valid 10 digit code words there are? Will there be enough many such IDs for all the SB students?
 Show how any two errors in such a code word can be corrected.
 For instance suppose we have typed 0204906710 as a code word but we have made two mistakes. What should have been the correct code word?
 Discuss the cryptanalysis of Vigenere ciphers and write a program to decrypt messages which have been encrypted using such ciphers.
For any of the programming projects, please email me at sorin at math.sunysb.edu both the program source code (in readable form  indented and commented) and the project, and please hand in the program outline and a reasonable amount of program output. You can use any programming language you like (within reasonable limits  i.e., a language for which there exist easily available compilers). Preferred ones are Maple, Mathematica (yes, they are programming languages), C, OCAML and Java, but you can also use C++, Pascal, Python, Fortran, Lisp, Turing machine...