### Information about the Project

Students are encouraged to do an individual special project. This
could involve a historical report on material of the course, or
learning a topic in algebra not discussed in the course, or writing a
computer program/developing some algorithm, etc. The choice of a topic
and the exact scope of the special project are to be determined after
consultation with the instructor. A short list of potential project topics
is enclosed below. However if you would like to work on a different
project/topic please come see me during office hours to talk about it.
Projects are **individual** and are expected to be neatly
written/presented. Programs/computer code without accompanying
(mathematical) explanations/description are **NOT** acceptable.

For any of the programming projects, please email to sorin at math.sunysb.edu
the program source code + actual project (in readable form -- indented and commented), as well as
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*...

You will need to make your selection and also inform me in writing via email by 03/01, the latest. The project is due before or on 04/08/2005.

- Let n be a positive integer, and define
T(n) = n/2 if n is even, and (3n+1)/2 otherwise,
so for instance T(2)=1, and T(5)=8. Form the sequence obtained by iterating T:
n, T(n), T(T(n)), T(T(T(n))), .... For instance starting with n=7 we get the
sequence 7,11,17,26,13,20,10,5,8,4,2,1,2,1, ... A well known conjecture asserts
that the sequence obtained by iterating T always reaches 1 no matter which positive
number n begins the sequence.
- Find the sequence obtained by iterating T starting with n=39
- Show that if we start the sequence from n=(2
^{2k}-1)/3, k>1, one always reaches 1. - Write a program that verifies the above conjecture for all values of n smaller than 10000.
- Using the above numerical evidence make conjectures concerning the number of iterations needed in the above sequence till one reaches 1.

- Discuss and find divisibility tests for an integer n by any of the following numbers 2, 3, 5, 7, 9, 11, 13, 101. Write a program that tests such divisibilities (for very large integers). Discuss historical aspects.
- According to the "theory" of biorhythms there are three
cycles in your life that start the day you are born. These
are the physical, emotional and intellectual cycles of
length 23, 28 and 33 days, respectively. Each cycle follows
a sine curve with period equal to the length of that cycle,
starting with value 0, climbing to value 1 one quarter of
the way through the cycle, dropping back to value 0 one-half
of the way through the cycle, etc and getting back to value
0 at the end of the cycle.
- For which says of your life will you be at a triple peak, where all three cycles are at maximum values?
- For which says of your life will you be at a triple nadir, where all three cycles are at minimum values?
- When in your life will all three cycles be at neutral position?
- Write a program that plots biorhythm charts and finds triple peaks and triple nadirs.

- Discuss the complexity of the euclidean algorithm for computing gcd's. Show Lam\'e's result that the number of divisions needed to find the gcd of two integers via the euclidean algorithm does not exceed the number of decimal digits in the smaller of the two integers. Write a program that checks Lam\'e's bound for various pairs of large integers of your choice. Use the numerical evidence to see how far is Lam\'e's bound from the number of actual divisions. Discuss the number needed of steps in other algorithms for finding the gcd (e.g. the least-remainder algorithm).
- A composite number n that satisfies n | b
^{n-1}-1 for all integers b with (b,n)=1 is called a Carmichael number.- Show that if n is a Carmichael number then it is squarefree.
- Show that 2821=7*13*31 is a Carmichael number.
- Show that if
n=p is a product of distinct primes such that_{1}p_{2}...p_{n}p for all_{i}-1|n-1i , thenn is a Carmichael number. Use this to show that 564651361 is a Carmichael number. You may also try to write a program to find other Carmichael numbers.

- Discuss Vigenere and Hill ciphers (encryption, decryption). Write a program that can perform encryption, decryption using such methods. Discuss vulnerability via statistics of blocks in the encrypted test. Write a program that does cryptanalysis for such cyphers based on statistics of blocks (for small sizes of blocks).
- 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) for a constant^{2}C , approximately equal to 0.66016. Determine how accurate this asymptotic formula is for values ofn as large as you can compute. - Compare the number of primes of the form
4n+1 and the number of primes of the form4n+3 for a range of values ofn . Can you make any conjectures about the relationship between these numbers? - Gather evidence for the following conjectures, or find counterexamples if you can:
- Lehmer has conjectured that
n is prime if φ(n ) dividesn-1 . - Charmichael has conjectured that for every positive integer
n there is a positive integerm distinct fromn such that φ(n )= φ(m ).

- Lehmer has conjectured that
- Describe a good method to
- Find the number of zeroes at the end of
the decimal expansion of
n! . Write a simple program that uses your method and test it. - Find the prime factorization of
n! . Write a simple program that uses your method and test it.

- Find the number of zeroes at the end of
the decimal expansion of
- A short (4 to 5 typed pages) paper on the mathematical contributions of a number theorist. Note: This is not a biography - you will need to describe mathematical results, their proofs, etc.
- A short (4 to 5 typed pages) historical report on material discussed in the course. You will need to describe mathematical results, outline proofs, etc