CSE102 - Computer Programming with C - Assignment 8  - Collatz Conjecture - Solved

In this assignment, you will experiment with pointers, recursions and an interesting mathematical conjecture, namely Collatz.  

Collatz conjecture has not been proven yet even though it is seemingly a simple problem. Consider the following function:

                                                                                           3𝑥 + 1     𝑖𝑓 𝑥 𝑖𝑠 𝑜𝑑𝑑

                                                                          𝑓(𝑥) = { 𝑥/2         𝑖𝑓 𝑥 𝑖𝑠 𝑒𝑣𝑒𝑛

 

Starting with an integer 𝑥0 the sequence 𝑥1 = 𝑓( 𝑥0), 𝑥2 = 𝑓( 𝑥1), …  tends end up with a loop 4, 2, 1, 4, 2, 1… Conjecture says that any starting integer should send this sequence to the same loop. (See https://www.youtube.com/watch?v=094y1Z2wpJg for an overview of this conjecture).

Towards the analysis of this conjecture, you are asked to write a few C functions: 1. (25 pts) Write a recursive function to generate and return the sequence. 

void generate_sequence (int xs, int currentlen, int seqlen, int *seq) 

Where xs is the first element of the sequence, seqlen is the length of the sequence, currentlen is the length of the sequence in the time of the function called, *seq is the array of the sequence.

2.      (30 pts) Write a recursive function such that given any function and a starting integer check if the sequence ends up in a loop.  

 

void check_loop_iterative(void (*f)(?), int xs, int seqlen, int *loop, int *looplen) 

 

The first input is the function for which the sequence will be generated (fill its parameters declared with “?” above), starting from the first integer xs with a length of seqlen. The last two arguments will return the loop and its length. If no loop is found, the function will not update *loop array and return 0 with looplen variable.

 

Note that the loop's length can be n/2 at most and 2 at least, you should search for a loop with every possible length (until you find one) in descending order.

 

3.      (20 pts) To be used in the previous function, you are asked to write a function to check if a given sequence of numbers has a loop in it.  

int has_loop(int *arr, int n, int looplen, int *ls, int *le) 

 

The function will receive a sequence starting from arr[0] and ending at arr[n-1]. It will check if there are any loops with a length of looplen. The first occurrence of the loop will be output with parameters ls and le.  

 

This is not a void function, it will return 1 if a loop exists, 0 otherwise.  

 

For example,

 {15, 7, 4, 2, 1, 4, 2, 1} has a loop starting at arr[2] and ending at ar[4]. In this case ls=2 and le=4.  

 

4.      (25 pts) Write another recursive function that calculates the histogram of the first digits of the sequence generated by a given function.

 

void hist_of_firstdigits(void (*f)(?), int xs, int seqlen, int *h, int digit) 

 

As before the first three parameters are for the generation of the sequence. h is the histogram of the first digits of the numbers that appear in the sequence. The size of this array will be 9 (you will ignore digit 0).  

 

For the following sequence:

                              {340, 170, 85, 256, 128, 64, 32, 16, 8, 4, 2, 1, 4, 2, 1} 

 

The first digits of each integer:

{3, 1, 8, 2, 1, 6, 3, 1, 8, 4, 2, 1, 4, 2, 1} 

 

The resulting histogram (*h) would be:

                                {5,3,2,2,0,1,0,2,0}
 

meaning that there are 0 numbers starting with digit 5 while there is only one number starting with digit 6.

 

Every time this function is being called; it should find the total numbers of integers starting with digit.

 Program flow: 

❖  In main, take the first element and the size of the sequence as inputs from the user (assume that the inputs will be proper, i.e., positive integers).

❖  In main, call the check_loop_iterative function.

❖  In check_loop_iterative function, generate & print the sequence (print it only once). Also, check if the sequence has a loop. If there is a loop, print its size and the indexes of its first occurrence. Do not print the loop itself in this function.  

❖  In main, print the loop (if any). If there is no loop, print this information.  

❖  In main, call the hist_of_firstdigits function. ❖ Print the histogram array in main.