CMSC 313 Spring 2012

Announcements | Exams | FAQ | Home | Projects | Resources | Schedule / Notes | Staff | Syllabus

The Objective

Background

It is interesting to note that if an integer, N, is not a palindrome then reversing the digits of N (to form N') and forming the sum N + N' will often produce a palindrome. For example, if N = 123, then N' = 321 and N + N' = 444 is a palindrome.

If N + N' is not a palindrome, continuing this process will often produce a palindrome eventually. For example if N = 964, N' = 469 then N + N' = 1433 which is not a palindrome. Continuing, however, we set N = 1433 so N' = 3341 and now N + N' = 4774 which is a palindrome.

Although most numbers produce a palindromic number with just a few (less than 10) reverse and add iterations, some take many more iterations. For example, the number 89 takes 24 iterations of the reverse and add algorithm before a palindromic number is produced.

Some numbers are being tested that appear to never form a palindromic number regardless of the number of reverse and add iterations that have been performed. A lychrel (pronounced la-shrel) is a number that has been proven to never form a palindrome even after repeated reversal and addition. Wade VanLandingham is credited for the term lychrel. Although proof has been found that some numbers in other bases are lychrels, proof has not been found that any base 10 number is a lychrel. So numbers in base 10 that appear to be lychrels can technically only be called candidate lychrels. Several candidate lychrels are known. The smallest candidate lychrel is 196. The reverse/add algorithn has not yet produced a palindromic number from 196 even after millions of iterations. The first million non-palindromic numbers were discovered by John Walker.

If you're interested, more information about lychrels can be found at http://www.p196.org/

The Task

Since we don't want your project to run forever, you'll need to check to see if the integer input by the user is a candidate lychrel first. If it is, don't attempt to perform the reversal and adds, just print a message and continue. See the sample output below. A list of candidate lychrels will be provided in a file that is read by your progam.

If the number input by the user is not a candidate lychrel, you should check to see if it is a palindrome. If it's not a palindrome, perform as many reverse/add iterations as necessary until a palindrome is formed, printing the numbers used and the sum at each iteration. After the palindrome has been formed you must display the number of reverse and add interation that were necessary to create it.

How does your program work?

1. Your program prompts the user for the name of the file containing candidate lychrels.
2. Your program prompts the user for an integer to test.
   1. If the integer is zero, exit your program.
   2. If the integer is a candiate lychrel, output an appropriate message and prompt for a new integer.
   3. If the integer is a palindrome, output an appropriate message and prompt for a new integer.
   4. Otherwise, perform the reverse/add algorithm above until a palindrome is found, printing all sums along the way. Print the number of iterations required to produce the palindrome. Prompt for a new integer.

Candidate Lychrel File Format

Hints, Notes and Requirements

1. (N) Because the reverse/add algorithm can create very large integers very quickly, it is necessary to use the unsigned long long data type. Use the %llu format to input and output variables of this type.
2. (N) You may assume that the name of the candidate lychrel file is no more than 100 characters.
3. (N) You may assume that integers input by the user are non-negative.
4. (R) If the candidate lychrel file cannot be opened for reading, an appropriate error message should be printed and your program should terminate.
5. (N) Functions not required for this project. If you choose do use functions, be sure to design your functions well and provide all required function comments. Poorly written/documented functions will result in point deductions.
6. (R) This is an individual project. Do your own work. Be sure to read the course course collaboration policy.
7. (R) Because this is a relatively small project (and your first C project) all your code should be placed into one .c file which MUST named project1.c. If your file is not named project1.c, our grading scripts will not execute properly and a regrade will be necessary.
8. (H) Loops are clearly necessary in this program. The use of break or continue to exit any of those loops will result in point deductions.
9. (H) Your output will be easier to read with large values if you print them in columns (see sample output below).
10. (N) Even though unsigned long long variables can store very large values, it is still possible that some values are too big to be stored in them. This may lead to false results. Try 879 and see what happens.

Sample Output

linux3[132]% Project1
Please input the candidate lychrel filename: lychrels.dat
Please input the value of N: 999
999 is a palindrome

Please input the value of N: 7235
                     7235 +                      5327 =                     12562
                    12562 +                     26521 =                     39083
                    39083 +                     38093 =                     77176
                    77176 +                     67177 =                    144353
                   144353 +                    353441 =                    497794
A palindrome was obtained in 5 iterations

Please input the value of N: 196
196 is a candidate lychrel

Please input the value of N: 0

Goodbye

linux1[104]% 

Project Grading

1. Functionality (35 points)
   Note that your functionality score will be zero if your code does not compile or create an executable.
   1. Basic cases - A file with a few candiate lychrels; the user inputs an integer that is a candidate lychrel; the user inputs a palindrome; the user inputs a integer that becomes a palindrome.
   2. More complex cases - the user inputs a single digit integer; the user inputs a large integer; the user inputs an integer with the same repeated digit (e.g. 666666)
   3. Atypical cases - This might be an empty file or a file that cannot be opened; The user inputs zero as the first integer.
   4. Stress Cases - A large candidate lychrel file; the user inputs an integer that takes many iterations before becoming a palindrome.
2. Code
1. Style (15 points) - we expect that your code adheres to the course coding standards, particularly with respect to comments, naming conventions, readability, and generality

Submitting the Program

You can submit your project using the submit command.

submit cs313 Proj1 project1.c

See this page for a description of other project submission related 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

Top of Page Last Modified: Monday, 06-Feb-2012 11:15:46 EST