Project 1: Check the Mathematics

Due by: Friday, January 19, 2024 at 11:59 p.m.

Introduction

"1, 2, 3... What comes next?" says Jim Moriarty, consulting criminal and evil mastermind. "If you can't guess, I'll blow up London!"

Unfortunately, there are an infinite number of mathematical sequences that start with those first three numbers. We can't write code that can do all of them, but we can write code for sequences that Jim Moriarty particularly likes. Let's see, he likes the Lazy Caterer's sequence, prime numbers, the Fibonacci sequence, the Collatz conjecture, and happy numbers.

Doubly unfortunately, none of those sequences start with 1, 2, 3! But that's just the kind of madman Jim Moriarty is, isn't he?

We have to assume that he is. Perhaps if we can find the first 50 numbers in each sequence, we can find a pattern and save London. And how are we going to do that? Well, we're going to write a program to find those sequences in C, of course!

You've probably heard of prime numbers, but the other sequences might be new to you. Fortunately, they can all be solved using only integer variables and loops. No arrays or complex data structures are required. Below you'll find links to explanations of each of the sequences we need to find.

• Lazy Caterer's sequence
• Prime numbers
• Fibonacci sequence
• Collatz stopping times
• Happy numbers

Implementation Details

Your task is to write a C program that will compute the first 50 terms of each of the sequences described below.

Lazy Caterer's sequence

Imagine a lazy caterer who wants to cut a cake into as many pieces as possible with a given number of cuts. The pieces don't have to be the same size or shape. With zero cuts, the cake is obviously in a single piece. With one cut, he can create a maximum of two pieces. With two cuts, he can create a maximum of four pieces. A normal person would probably make a third cut and create six pieces, but the lazy caterer will make a cut that does not cross the intersection of the previous cuts, giving seven pieces. Consider the illustrations below.

It turns out that there is a simple mathematical formula to determine the maximum number of pieces that can be made with n cuts. That number is (n² + n + 2)/2. For the purposes of this project, you will be printing out the maximum number of pieces that can be made with 0 through 49 cuts.

Prime numbers

Prime numbers are integers greater than 1 which are only divisible by 1 and themselves. The sequence of of prime numbers begins 2, 3, 5, 7, 11, and so on. There are an infinite number of prime numbers, and they have many fascinating applications in data structures and cryptography. Very large prime numbers are hard to find, and it can be difficult to factor a large number into its prime factors.

However, you only need to find the first 50 prime numbers. To do so, you can loop through values and use a second loop to test if the number is prime. Using the modulus operator (%), you can see what the remainder is when performing division. If the remainder is 0, then the divisor evenly divides the number. By testing to be sure that a number is not divisible by any value strictly between 1 and the number itself, you can tell that the number is prime. There are many ways to optimize this approach, and there are much faster approaches, but trial division will get the job done for numbers as small as the ones needed in this project.

Fibonacci sequence

The Fibonacci sequence was studied by Leonardo of Pisa in the early 13^th century to model the population of rabbits. The sequence begins 1, 1, 2, 3, 5, and so on. Each number in the sequence is the sum of the two previous.

With variables for the current term and the two previous terms, it is relatively efficient to generate each number in the sequence using a single loop. Note that the growth of Fibonacci numbers is fast. To represent even the first 50 terms, you will need to use variables of type long long. Further more, you will need to use the "%lld" format specifier to print out a long long value with printf().

Collatz stopping times

Consider an integer n greater than 1. If it is an even number, divide it by two. If it is an odd number, multiply it by 3 and then add 1, yielding 3n + 1. Repeat this process, applying the even rule or the odd rule as appropriate, until the number reaches 1. Well, we assume that it will reach one. We can't actually be sure. Mathematicians checked every number up into the billions, and they all eventually return to 1. The Collatz conjecture states that every integer greater than 1 will eventually return to 1 in this process, but it has never been proven.

The Collatz stopping time of a number is the number of operations needed before it becomes 1. For example, it takes 0 operations for 1 to become 1. It takes 1 operation, namely dividing by 2, for 2 to become 1. The number 3 is much more interesting. Since it it odd, we first get 3 ⋅ 3 + 1 = 10, then 10 / 2 = 5, then 3 ⋅ 5 + 1 = 16, 16 / 2 = 8, 8 / 2 = 4, 4 / 2 = 2, and finally 2 / 2 = 1, a total of 7 operations! This sequence is the number of Collatz operations needed before a number returns to 1, for the numbers 1 through 50.

Happy numbers

Given an positive integer, take each of its digits, square them, and sum them together. Then, repeat the process with the resulting number. A happy number has the property that it will eventually converge on 1. An unhappy number will never converge but will instead get caught in the cycle 4, 16, 37, 58, 89, 145, 42, 20, and back to 4.

Thus, if you reach 1 in the process of squaring and summing digits, the number is happy. If you ever reach 4, the number is unhappy.

Print out the first 50 happy numbers, starting 1, 7, 10, 13, 19, and so on.

Makefile

Provide a makefile which will compile your code into an executable named sequences. One of the benefits of using a makefile is that you are free to call your source code files whatever you want. Here is a link to some resources for the GNU make command.

Sample Output

The following shows the output for the program. Note that the lines will not necessarily wrap in the same places, depending on the size of your browser window and your terminal window.

Lazy Caterer's Sequence:
1 2 4 7 11 16 22 29 37 46 56 67 79 92 106 121 137 154 172 191 211 232 254 277 301 326 352 379 407 436 466 497 529 562 596 631 667 704 742 781 821 862 904 947 991 1036 1082 1129 1177 1226 

Prime Numbers:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 

Fibonacci Sequence:
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049 12586269025 

Collatz Stopping Times:
0 1 7 2 5 8 16 3 19 6 14 9 9 17 17 4 12 20 20 7 7 15 15 10 23 10 111 18 18 18 106 5 26 13 13 21 21 21 34 8 109 8 29 16 16 16 104 11 24 24 

Happy Numbers:
1 7 10 13 19 23 28 31 32 44 49 68 70 79 82 86 91 94 97 100 103 109 129 130 133 139 167 176 188 190 192 193 203 208 219 226 230 236 239 262 263 280 291 293 301 302 310 313 319 320 

The formatting of your output should match exactly. Of course you can do a rough check with your eyes, but to be sure that all the numbers and spacing are perfect, you can download the output here. Then, rather than printing the output of your program to the screen, you can redirect the output to a file using the > operator. For example, if your program is called sequences, you can send its output to a file called output.txt with the following command.

./sequences > output.txt

Once you have your output in a text file, you can compare it with the sample output using the diff utility. If you run diff with two files, it will print out any lines that differ between the two files. For example, to compare output.txt and numbers.txt, you can use the following command.

diff output.txt numbers.txt

Your output should match the sample exactly. This program has no input and always prints out the same data. For that reason, it might be tempting to write a program that prints out the appropriate output without computing each term of each sequence. However, doing so will earn you zero points.

Hints

The math in this project is not difficult. You should have written similar programs to compute terms of sequences in COMP 1600 or COMP 2000. You might want to write a solution to some parts of this project in Java first and then try to convert it to C.

No functions are required for this project, but they can make your code cleaner. Feel free to read ahead if you want to do so.

I do not recommend that you use recursion to find the numbers in the Fibonacci sequence. The obvious implementation to do so is very inefficient, requiring exponential time.

If you start getting negative numbers in your Fibonacci sequence, you are probably using int or long variables instead of long long.

Turn In

Zip the contents of your project directory, including the makefile, the source C file(s), and header files, if any. Upload this zip file to Blackboard. Do not include any object files or executables. Running the make command must compile all the required C source code files and generate an executable named sequences. Running the executable sequences must print the required output.

All work must be submitted before Friday, January 19, 2024 at 11:59 p.m. unless you are going to use a grace day.

Grading

Your grade will be determined by the following categories.

Category	Description	Weight
Lazy Caterer's Sequence	Your solution correctly generates the first 50 numbers in the Lazy Caterer's sequence.	15%
Prime Numbers	Your solution correctly generates the first 50 prime numbers.	15%
Fibonacci Sequence	Your solution correctly generates the first 50 terms of the Fibonacci sequence.	15%
Collatz Stopping Times	Your solution correctly generates the Collatz stopping times for the first 50 natural numbers.	15%
Happy Numbers	Your solution correctly generates the first 50 happy numbers.	15%
Formatting	Your formatting matches the sample output down to the character.	10%
Correct Makefile	Makefile makes executable called sequences when make is invoked. Command make clean should also remove all object and executable files.	5%
Programming Style	One of the goals for this project is to establish good coding style. Points will be awarded for following the guidelines listed in the coding standards for this course.	10%

Under no circumstances should any member of one team look at the code written by another team. Tools will be used to detect code similarity automatically.

Code that does not compile will automatically score zero points.