CMSC 313 Project 1

Number Theory

Assigned	Monday, Sept 14, 2009
Program Due	11:59pm Tuesday, Sept 22, 2009
Points	30 points for correctness (6 tests, 5 points each) 10 points for design, coding style 40 points total
Updates

The Objective

The objective of this assignment is to become familiar with good design practices, writing in C in a Unix environment, and using functions. It may also heighten your appreciation of mathematics.

The Background

The study of mathematics is separated into many fields. The one that tends to lead students to discover the beauty of mathematics is the field of number theory. This field deals with numbers and their relationships to each other.

The field of number theory has lead to discoveries such as :

Prime numbers -- those which can only be divided by themselves and one. Some special primes that you might find interesting are of the form 2^p - 1, where p is prime. These are called Mersenne Primes after the French monk Marin Mersenne who discovered them. The search for Mersenne primes continues. You can participate in the search for new Mersenne primes by joining GIMPS (the Great Internet Mersenne Prime Search). The 45th and largest known Mersenne prime is 2^43,112,609 - 1, a 12,978,189 digit number, was discovered on August 23, 2008 by Edson Smith at UCLA. On September 6, 2008 the 46th known Mersenne prime, 2^37,156,667 - 1, an 11,185,272 digit number was found by Hans-Michael Elvenich in Langenfeld, Germany. This was the first Mersenne prime to be discovered out of order since 2^110,503 - 1 in 1988.
Perfect numbers -- ancient mathematicians were interested in the relationship of a number and the sum of its divisors. A positive integer that is equal to the sum of its divisors (excluding itself) is called a "perfect" number. For example, the divisors of 6 are 1, 2 and 3. Since 6 = 1 + 2 + 3, 6 is a perfect number. The next three perfect numbers are 28, 496 and 8128. If the sum of the divisors is greater than the number, the number is called "abundant". If the sum of the divisors is less than the number, the number is called "deficient". Perfect numbers demonstrate some interesting properties -- all known perfect numbers end in 6 or 8; there are no known odd perfect numbers. The largest known perfect number is (2^3021376) * (2^3021377 - 1) which is 1,819,050 digits in length (and ends in 6).

Squares -- many positive integers are considered geometric in nature. You learned about perfect squares in high school -- 1, 4, 9, 16. They are called "squares" because a group of 1, 4, 9 or 16 dots can be arranged in a square.

Triangular numbers -- Groups of 1, 3, or 6 dots can be arranged in a triangle and so these numbers are called "triangular" numbers. (If you've ever gone bowling, you'll recognize that 10 is also triangular.)
A more natural example arises when we consider a group of people who meet for the first time and everyone shakes hands with everyone else. The number of handshakes will be a triangular number.
Turns out that triangular numbers are the sum of consecutive integers.
To us this may just be an interesting relationship. To early Pythagoreans, it showed the mysterious nature of the universe and the way in which numbers and shapes have esoteric relationships.

The Task

This is an individual project. Do your own work. Positive integers can be categorized in many different ways. This project will let you investigate some familiar and some new ways of looking at integers. Your mission is to write a program that examines a positive integer greater than 1 that the user specifies and categorizes it as follows:

ODD or EVEN
PRIME or COMPOSITE -- a prime number is an integer greater than one that is divisible only by itself and one. Any number that is not "prime" is "composite".
PERFECT / ABUNDANT / DEFICIENT --- as described above
SQUARE -- as described above
TRIANGULAR -- as described above

Your program should also verify the user's input. We promise to enter an integer, but we don't promise it will be greater than 1. If an invalid integer is input, print an appropriate message and reprompt the user for new integer.

Your program MUST break the project into functions according to top-down design principles. Each function should perform just one task. Don't forget to use #defines to make your code more readable. Because this is a relatively small project (and your first project) all your code should be placed into one .c file named project1.c.

A makefile is provided for this project. Copy the makefile from Mr. Frey's public directory (/afs/umbc.edu/users/f/r/frey/pub/313/proj1/) to your working directory for this project. It is not necessary to edit the makefile provided you name your file project1.c, but the makefile should be submitted in case you've decided to change it.

If you wish to use functions from the C math library you must #include <math.h> in your .c file. The rules inside the makefile will link the math library with your .o files.

Submitting the Program

To submit your project, type the following at the Unix prompt: make submit

or you can submit your files separately using the submit command. See this page for a description of project submission commands. To verify that your project was submitted, you can execute the following command at the Unix prompt. It will show all files that you submitted in a format similar to the Unix 'ls' command.

submitls cs313 Proj1

Monday, 14-Sep-2009 09:04:42 EDT